Оригінальний матеріал від Дениса Остапенка

Більшість програмістів-початківців, особливо тих, хто навчається в коледжах, не знають, як розвивати свої навички та що їм слід знати, щоб ефективно працювати. Дивно, але повсякденне використання продуктів і технологій, створених іншими розробниками та заснованих на добре розвинених галузях знань, не дає їм уявлення про те, як вони працюють і як реалізовані.

Теорія масового обслуговування та мобільні мережі на основі GSM; PHP-скрипти, що виконуються на віддалених серверах, передають згенерований вміст через Ethernet за допомогою протоколу TCP/IP на мережеві карти з інтерфейсом NDIS на ПК користувачів; процесори, що перевпорядковують і спекулятивно виконують інструкції, щоб компенсувати обмеження напівпровідникової електроніки щодо тактової частоти та швидкості світла; автомобілі та літаки, спроєктовані комп'ютером, ліки та ДНК, секвеновані комп'ютерами; комп'ютерні ігри, де крихітний шматочок відбитого світла потребує мегабайтів наукових статей, повних інтегралів Френеля; електронні фільми та книги; алгоритми NLP і TreeNet, що отримують результати пошуку з величезних баз даних — це речі, якими ми користуємося щодня, створені геніальними розробниками програмного забезпечення завдяки їхнім фундаментальним знанням і таланту, а також, звісно, методології розробки програмного забезпечення та управління складністю, перевірені роками.

Ми з друзями взяли на себе клопіт підготувати теоретичний мінімум розробника програмного забезпечення на основі видатних IT-галузей, деякі частини якого вже включені до університетських програм з інформатики, інші взяті з інтерв'ю та практичного досвіду. Деякі пункти потребують лише Вікіпедії та займають 5 хвилин на вивчення, інші можуть зайняти місяці, але саме це вам потрібно знати та розуміти. Ласкаво просимо пропонувати виправлення та доповнення.

1. C++, стандарт, Comeau, 1TBS, Stroustrup/D&E/Josuttis/Vandevoorde, Dewhurst/Mayers/Sutter, RAII, правило трьох, виняткова безпека, Alexandrescu/Abrahams-Gurtovoy, стирання типів, CRTP, NVI, SFINAE, пошук Кеніга, пристрій Даффа, Boost, Siek-Lumsdaine/Karlsson, TR1, TR про продуктивність C++, ABI, тест Степанова, проблема пересилання, SPECS, C++0x
2. Компілятори, відмінності реалізацій стандарту, обмеження реалізацій, інтринсики, відмінності стандартних бібліотек (контейнери, rand), ABI, реалізація віртуальних функцій, віртуальне успадкування, винятки, RTTI, switch, покажчики на функції та методи; оптимізації, усунення копіювання (RVO, NRVO), sizeof на різних платформах, визначення компіляторів і середовищ, __declspec, командний рядок компілятора, оптимізація порожнього базового класу, статичне та динамічне зв'язування, декорація імен, розподілена компіляція, попередньо скомпільований заголовок, єдина одиниця компіляції, (суворий) аліасінг/restrict, inline/_forceinline, volatile
3. Багатопотоковість, проблема обідаючих філософів, взаємне блокування/гонка даних/голодування, атомарність, інструкції блокування CPU, CAS або LL/SC, без очікування/блокування/перешкод, проблема ABA, реалізація lock-free контейнерів, spin-lock, TLS/дані на потік, OpenMP, MPI, map-reduce, критична секція/м'ютекс/семафор/змінна умови, WaitForSingleObject/WaitForMultipleObjects, green thread/корутина, pthreads, модель акторів
4. Мова асемблера x86, Zubkov/Hyde/Drepper/Kasperski/Fog/Abrash, синтаксис AT&T та Intel, masm32, макрокоманди, стек, купа/менеджер купи, угоди про виклики, hex-коди, машинне представлення даних, IEEE754, little/big endian, SIMD, апаратні винятки, переривання, віртуальна пам'ять, реверс-інжиніринг, переповнення стеку та купи, return oriented programming, алфавітно-цифровий шеллкод, L1/L2/RAM/page fault та їхні таймінги
5. Апаратне забезпечення, Horowitz-Hill, напівпровідникова електроніка/спінтроніка/фотоніка, транзистор, схемотехніка, мікрокод, технологія процесорів, VID/PID, FPGA, Verilog/VHDL/SystemC, SISAL, Arduino, пам'ять (ROM → EEPROM, RAM, SSD, HDD, DVD), RISC/CISC, таксономія Флінна ([SM]I[SM]D), гарвардська та принстонська архітектури комп'ютера, архітектури CPU, архітектури x86
6. Процесори, конвеєризація, гіперпоточність, виконання не по порядку, спекулятивне виконання, передбачення переходів, попередня вибірка, набірно-асоціативний кеш, рядок кешу/промах кешу, тактовий цикл, кільця захисту, моделі пам'яті багатопроцесорних систем (SMP, NUMA), таймінги пам'яті
7. Дискретна математика, K2, теорема Поста, схеми, скінченні автомати, клітинні автомати, автомат Калашникова гвинтівка, DFA та NFA
8. Обчислюваність, машина Тюрінга, алгоритми Маркова, машина Поста, десята проблема Гільберта, лямбда-функції Черча, частково рекурсивні функції Кліні, комбінаторна логіка Шенфінкеля, Brainfuck, еквівалентність Turing tarpit, проблеми зупинки та самозастосовності, зліченність множини обчислюваних функцій, RAM-машина, алгоритм Тарського, SAT/SMT-розв'язувачі, теорія формальних систем
9. Мови програмування, граматики, ієрархія Хомського, теорема Майгілла-Нероуда, лема про накачування для регулярних мов та лема Огдена, алгебра Кліні, NFA → DFA, нерозв'язні проблеми у формальних мовах, Dragonbook, Friedl, регулярні вирази та їхня складність, PCRE/POSIX RE, BNF, Boost.Spirit + Karma + Qi/Ragel, LL, LR/SLR/LALR/GLR, PEG/packrat, yacc/bison/flex/antlr, статичний аналіз коду, компіляція/декомпіляція/обфускація/деобфускація, Clang/LLVM/XMLVM, GCCXML, OpenC++, реалізація VM, JiT/AoT/GC, DSL/DSEL
10. Алгоритми та комбінаторна оптимізація, Cormen/Skiena/Sedgewick/Knuth/Aho-Hopcroft-Ullman/Papadimitriou/Shriver-Goldberg/Preparata-Shamos, структури даних, алгоритми, складність і символи Ландау, класи складності, NP-повні задачі, графи та дерева, мережеві потоки, матриця Кірхгофа, дерева пошуку (особливо RB-дерево та B-дерево), виявлення оклюзій, двійкова купа, хеш-таблиці та ідеальний хеш, мережі Петрі, алгоритм російського селянського множення, метод Карацуби та множення матриць Винограда-Штрассена, алгоритми сортування, жадібні алгоритми та матроїди, динамічне програмування, лінійне програмування, алгоритми diff, рандомізовані та нечіткі алгоритми пошуку, псевдовипадкові числа, нечітка логіка
11. Чисельні методи, метод дихотомії/Ньютона, інтер- та екстраполяція, сплайни, методи Гаусса/Якобі/Зейделя, QR та LU-розклади, SVD, метод найменших квадратів, методи Рунге-Кутти, метод Адамса, формули Ньютона-Котеса, метод Монте-Карло, метод Рітца, метод Бубнова-Гальоркіна, метод скінченних різниць/елементів, БПФ/КПФ, збіжність і стійкість
12. Машинне навчання, машинний зір, OpenCV, обробка зображень, OCR, фільтри Зобеля, ознаки Хаара, вступ до психофізіології зору, TreeNet, нейронні мережі, самоорганізаційна карта Кохонена, генетичні алгоритми, алгоритми мурашиних колоній, інформаційний пошук/інтелектуальний аналіз даних/обробка природної мови, алгоритми оптимізації, PCA, SVM, градієнтний бустинг, імітація відпалу, підйом на пагорб, методи моделювання ШІ
13. Теорія інформації, стиснення, Хаффман, RLE, LZ, ECC, стиснення з втратами (зображення, аудіо, відео), інформаційна ентропія, формула Шеннона, колмогорівська складність
14. Криптографія, Yaschenko, симетрична (DES, AES), асиметрична (RSA), Diffie-Hellman, еліптичні криві, хешування (MD5, SHA, CRCn), DHT, криптографічно стійкі системи, криптографічні атаки, WEP/WPA/WPA2 та атаки, цифрові підписи та сертифікати, HTTPS/SSL, доказ з нульовим розголошенням
15. Математика, Knuth-Graham-Patashnik/Zorich/Winberg/Rudin (Real and complex analysis, не Principles)/Lang, математичний аналіз, лінійна алгебра, комплексний аналіз, функціональний аналіз, диференціальна геометрія, теорія чисел, ЧДП/ЗДП/інтегральні рівняння/варіаційне числення/оптимальне керування, твірні функції, ряди, комбінаторика, теорія ймовірностей/математична статистика/випадкові процеси/теорія масового обслуговування, ланцюги Маркова, інтегральні перетворення (Фур'є, Лапласа, вейвлет), NZQRCHOS, комп'ютерна алгебра (Mathematica, Maple)
16. Фізика, правила Кірхгофа, електричний імпеданс, швидкість і частота світла, лагранжіан
17. Хімія, стехіометрія, хімія кремнію :)
18. Архітектура та стиль коду, McConnell/Fowler/Leblanc/Gamma/Alexandrescu-Sutter/Booch, захисне програмування, патерни, GRASP, UML, ООП (Smalltalk), ООD/ООА, принцип підстановки Лісков, метрики коду
19. Методології розробки програмного забезпечення, Waterfall/RUP/Agile/Scrum/Kanban/XP, TDD/BDD, CASE
20. Тестування, модульні тести, функціональне, навантажувальне, інтеграційне тестування, тестування UI
21. IDE, IntelliSense, налагоджувачі (VS/Olly/WinDbg/kdb/gdb) та трасувальники (strace/ltrace), формат налагоджувальної інформації DWARF2, valgrind, vcs (SVN, GIT), merge/branch/trunk, системи іменування файлів і гілок, безперервна інтеграція, ant, покриття коду, статичний аналіз, верифікація та валідація програмного забезпечення (Frama-C, RAISE (RSL), Coq), профілювання, lint, баг-трекер, генератори документації, системи збірки (cmake)
22. Фреймворки, Qt, moc та метаінформація, конструкція сигналів і слотів, Summerfield-Blanchett/Schlee, PoCo, загальні бібліотеки: GMP, i18n, lapack, fftw, pcre
23. Операційні системи, Silberschatz/Richter/Solomon-Russinovich/Robachevsky/Vahalia/Stevens/Linux Kernel Internals, менеджер пам'яті, менеджер купи та його внутрішня будова (LAL/LFH/slab), менеджер процесів, перемикання контексту, реальний і захищений режими, формати виконуваних файлів (PE/ELF/Mach), об'єкти ядра, налагоджувальні хуки (strace/ptrace/dtrace/pydbg, Debug API) та мінідампи, bash, мережевий стек і високонавантажені веб-сервери, netgraph, CR0, IPC, підсистема вікон, безпека: ACE/ACL та права доступу, технології віртуалізації, RTOS (QNX), розробка драйверів, IRQL, IRP, файлові системи, BigTable, NDIS/miniport/FS драйвери/filter driver, Mm-, Io-, Ldr-функції, DKOM і руткіти, GDT/IDT/SDT, ядро Windows/Linux/BSD, POSIX
24. COM, OLE/ActiveX/COM+, ATL, Rogerson/Tavares, апартаменти, монікери, MIDL, DCOM RPC, CORBA, D-bus, TAO
25. Мережі, модель OSI/модель Інтернету, Ethernet, TCP/IP, вікно TCP, алгоритм Нагла, сокети, Protocol buffers/Thrift/Avro/ASN.1, AMQP, ICMP, маршрутизація/BGP/OSPF, ARP, атака Мітніка, syn flood, HTTP/FTP, P2P, DHCP, SMB/NBNS, IRC/XMPP, POP3/SMTP/ESMTP/IMAP, DNS, WiFi/WiMax/GSM/CDMA/EDGE/Bluetooth, ACE, Wireshark
26. Графіка, алгоритм Брезенхема, колірні моделі, трасування променів проти полігональної графіки, OpenGL/GLSL/Open Inventor, DirectX/DirectShow/DirectAudio/HLSL, stencil/depth/alpha-test, графічний конвеєр DirectX 11, шейдери, моделі освітлення (Phong), пропускна здатність, fillrate, OpenCL/CUDA, ландшафти, LOD, тіні, текстури та фільтрація, згладжування, HDR, тонмапінг
27. Формати, XML/XSLT/XPath/XMLStarlet/DOM/SAX, RTF/ODF, JSON/BSON, torrent, YAML, JPEG/PNG/WebP, AVI/MPEG/RIFF/WAV/MP3/OGG/WebM, SVG, Unicode, однобайтові кодування/UTF-8/UTF-16/UCS-2/UTF-32
28. РБД, Gruber, ANSI SQL, T-SQL, ODBC, MySQL/PostgreSQL/MS SQL/BDB/SQLite/Sphinx, збережені процедури, тригери, алгебри Кодда/А, Tutorial D, нормальні форми, оптимізація та виконання запитів, структури даних індексів, транзакції та ACID, теорема CAP Брюера, NoSQL, key-value сховища, шардинг, ORM (C++ ODB), ERD, OLAP
29. Прикладне програмування, C#/F#/Nemerle, Schildt/Troelsen/Richter, узагальнене програмування, yield, linq/plinq, рефлексія, AST, WCF, WinForms/WPF/Silverlight, AOP, фреймворки логування, .NET assembly
30. Квантові обчислення, алгоритм Шора, квантова криптографія
31. Функціональне програмування, Haskell/Ocaml/Scheme/Alice або Oz, SICP/TaPL/YAHT/Purely Functional Data Structures/Harrison-Field, HOF (map/fold/filter), система типів Хіндлі-Мілнера, монади, типові класи, алгебричні типи даних, залежні типи, ліниве/енергійне обчислення, логічне програмування (Prolog або Mercury), конкурентне програмування (Erlang або Oz)
32. Веб-розробка та скриптові мови, Flanagan/Zend PHP5 Certification Course + Study Guide, Apache/nginx, CGI/FastCGI, PHP/Zend Framework/phpDaemon/Zend Engine/Doctrine або Propel/CodeIgniter або Symphony або Yii, Python/Django/Twisted, Ruby/RoR, ASP.NET MVC, JavaScript/jQuery/ExtJS/node.js, JS ООП, HTML5/XHTML/doctype/табличні та div-макети/CSS3, RSS, canvas/WebGL, Ajax/Comet/WebSockets, проблеми безпеки (XSS, SQL-ін'єкції, CSRF), високе навантаження, SWIG
33. Дизайн GUI, Raskin, зручність використання, основи дизайну та типографіки, закон Фіттса, принципи макетування, LaTeX.

Оновлення: Деякі питання дуже поширені, тому гарна ідея дати відповіді в цьому дописі.

Цей список справедливо критикують за відсутність систематизації та РАПТОВЕ сусідство дуже різноманітних тем, різних за змістом і глибиною. Це особливість, а не баг! Написання систематичної програми майже для кожного пункту тут зайняло б стільки ж місця, скільки зміст деяких великих книг, тому краще включати назви книг/авторів. Отже, як користуватися цим списком? Вам слід читати хороші книги, щоб отримати розуміння згаданих предметів. Автори навіть не думали, що хтось вирішить, що пристрій Даффа за складністю та розміром дорівнює Святому Стандарту! Однак наш критерій все одно застосовний, бо читання сотні книг для початківців з C++ не дасть вам уявлення, що таке пристрій Даффа, але якщо ви знаєте, що вивчати (деякі частини нашого списку, наприклад, C++), ви дуже швидко зустрінете кожне поняття. Сенс програми, зумовлений її розміром, полягає в тому, щоб оцінити, скільки знань ви здобули, читаючи книги.

Ми також отримуємо багато критичних відповідей від тих, хто вважає себе програмістами, але вважає, що вивчити все це неможливо, або немає потреби знати все, бо звичайний розробник не використає це в повсякденній практиці. Ми вважаємо, що ці люди не бачать різниці між ерудицією/пам'яттю та знанням. Цінне знання для розробника програмного забезпечення — це не точний формат пакета NBNS, а методи, які використовували інші розробники, іншими словами, його здатність перевинаходити або ідентифікувати ці методи в різних галузях. Здатність аналізувати та синтезувати (яка досягається наполегливою працею та навчанням) відрізняє людину від google, який не зможе розв'язати div2 250 навіть у довгостроковій перспективі. Цей список спрямований на розвиток цих здібностей. Звісно, вам потрібно доповнювати здібності знаннями в конкретній галузі, як-от фізика ігор, розробка java-мотлоху чи проєктування ІС.

Питання тих, хто не вважає себе достатньо розумним, щоб освоїти цей список, або вважає, що не зможе застосувати свої знання та забуде/втратить їх, також потребує окремого абзацу. Загалом список поступається програмам факультетів інформатики провідних університетів, тому освоїти його за 5 років цілком можливо, навіть поєднуючи з роботою. Від 1/3 до 2/3 обговорюваних питань зазвичай використовуються в розробці ігор, інші можна використати, відповідаючи на запитання на StackOverflow.

Є також група людей, які заперечують вивчення зазначених предметів, бо вважають, що програмування — це лише для заробляння грошей. Ці люди насправді не потребують цього списку, він не стосується питань крадіжок, шахрайства чи примушування інших працювати замість вас.

Деякі люди кажуть: «Я добре заробляю без такої освіти». Їм варто зауважити, що після 45 деградація мозку легко помітна, бо більшості людей важко працювати з кодом навіть звичайної цикломатичної складності. Повільна втрата здатності писати код (супроводжувана відсутністю аналітико-синтетичної діяльності) може призвести до відсутності професійної роботи та інших проблем. Деякі люди продовжують активно працювати в старості, але це зумовлено їхніми видатними результатами в минулому. Ви можете використати TopCoder, щоб оцінити свою продуктивність.

Я вдячний усім, хто допоміг мені виправити всі ці дратівливі баги, особливо моїм колегам, які не лише практично освоїли цей список, але й зробили дуже цінні коментарі.

Пов'язані посилання:
Книги, які варто прочитати в IT
Матриця компетентності програміста
Список Баткіна
MIT OpenCourseWare
Курси інтернет-університету

 посилання на знімок в Internet Archive — використовується, коли оригінал зник або доступний лише з деяких країн.