Теоретичний мінімум для програміста Кросспост

Шарпіц продовжує радувати нас чудовими постами в жж. Пропоную обговорити цей епічний піст:

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

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

C++

Мультитредність, обідають філософи, deadlock/race condition/starvation, атомарність, lock інструкції процесора, CAS або LL/SC, wait/lock/obstruction-free, ABA problem, написання lock-free контейнерів, spin-lock , TLS/per-thread data, OpenMP, MPI, map-reduce, critical section/mutex/semaphore/condition variable, WaitForSingleObject/WaitForMultipleObjects, green thread/coroutine, pthreads

Мова асемблера x86, Зубков/Хайд/Дреппер/Касперски/Фог/Абраш, AT&T та Intel-синтаксис, masm32, макроси, стек, купа/менеджери купи, угоди виклику, hex-коди, машинне представлення даних, IEEE754, little/big endian, SIMD, апаратні винятки, переривання, віртуальна пам'ять, реверсинг, зрив стека та купи, return oriented programming, alphanumeric shellcode, L1/L2/RAM/page fault та їх таймінг

Апаратне забезпечення, Хоровіц-Хілл, напівпровідникова електроніка/спінтроніка/фотоніка, транзистор, схемотехніка, мікрокод, технологія створення процесорів, VID/PID, Verilog/VHDL/SystemC, Arduino, пристрої пам'яті (ROM → EEPROM, RAM , SSD, HDD, DVD), RISC/CISC, Flynn's taxonomy ([SM]I[SM]D), принстонський та гарвардський підхід, архітектури процесорів, архітектури x86

Процесори, конвеєризація, hyper-threading, out-of-order execution, спекулятивне виконання, branch predict, префетчинг, множинний асоціативний кеш, кеш-лінія/кеш-промах, такти, кільця захисту, пам'ять таймінг пам'яті

Дискретна математика, K2, теорема Поста, схеми, кінцеві автомати, клітинні автомати, автомат Калашнікова, ДКА та НДКА

Обчислюваність, машина Тьюринга, нормальні алгоритми Маркова, машина Поста, діофантові рівняння Матіясевича,лямбда-функції Черча, частково рекурсивні функції Кліні, комбінаторне програмування Шейнфінкеля, Brainfuck, еквівалентність тьюрингових трясов, проблема зупинки та самозастосовності, рахунковість безлічі обчислюваних функцій, RAM-машина, алгоритм Тарського, SAT/SMT-солвери

Мови програмування, граматики, ієрархія Хомського, теорема Майхілла-Нероуда, лема про накачування та лема Огдена, алгебра Кліні, НДКА -> ДКА, алгоритмічно нерозв'язні завдання у формальних мовах, Драгонбук, Фрідл, регекспи та їх складність, PCRE/POSIX RE, БНФ, Boost.Spirit + Karma + Qi/Ragel, LL, LR/SLR/LALR/GLR, PEG/packrat, yacc /bison/flex/antlr, статичний аналіз коду, компіляція/декомпіляція/обфускація/деобфускація, Clang/LLVM/XMLVM, GCCXML, OpenC++, побудова віртуальних машин, JiT/AoT/GC, DSL/DSEL

Алгоритми та комбінаторна оптимізація, Кормен/Скієна/Седжвік/Кнут/Ахо-Хопкрофт-Ульман/Пападимитріу/Шрайвер-Голдберг/Препарату-Шеймос, структури даних, алгоритми, складність та символи Ландау, класи складності, NP повні завдання, графи та дерева, потоки в мережах, матриця Кірхгофа, дерева пошуку (особливо RB-дерево та B-дерево), occlusion detection, купа, хеш-таблиці та ідеальний хеш, мережі Петрі, алгоритм українського селянина, метод Карацуби та матричне множення Винограда-Штрассена, сортування, жадібні алгоритми та матроїди, динамічне програмування, лінійне програмування, diff-алгоритми, рандомізовані алгоритми та алгоритми нечіткого пошуку, псевдовипадкові числа, нечітка логіка

Машинне навчання, машинний зір, OpenCV, image processing, OCR, фільтри Собеля, каскад Хоара, введення в психофізіологію зору, TreeNet, нейромережі, мережі Кохонена, генетичні алгоритми, мурашині алгоритми, information retrieval/datamining/natural language processing, алгоритми оптимізації, SVM, gradient boosting, метод відпалу, hill climbing, підходи до моделювання AI

Кількісні методи, метод Гаусса, інтер- та екстраполяція, сплайни, МНК, метод Ейлера і Рунге-Кутти, дихотомія/метод Ньютона, метод Сімпсона, метод Монте-Карло, метод Галеркіна, QR і LU-декомпозиція, FFT/STFT, збіжність та стійкість

Теорія інформації, стиснення, Хаффман, RLE, LZ, коди корекції помилок, інформаційна ентропія, формула Шеннона, складність Колмогорова

Криптографія, Ященко, симетрична, асиметрична, Діффі-Хеллман, RSA, DES, AES, еліптичні криві, хешування (MD5, SHA, CRCn), DHT, криптостійкість, криптоатаки, WEP/WPA/WPA2 та атаки на них, цифровий підпис та сертифікати, HTTPS/SSL, доказ з нульовим розголошенням

Математика, Кнут-Грехем-Паташник/Зорич/Вінберг, матан, лінал, комплан, функан, диффгем, теорія чисел, дифури/інтури/урчпи/варіаційне обчислення/оптимальне управління, що виконують функції, ряди, комбінаторика, теорвер/матстат/столби/теорія масового обслуговування, ланцюги Маркова, інтегральні перетворення (Фур'є, Лаплас, вейвлет), NZQRCHOS, матпакети (Mathematica, Maple)

Фізика, правила Кірхгофа, комплексний опір, швидкість і частота світла, лагранжіан

Хімія, стехіометрія, хімія кремнію :)

Архітектура та стиль коду, Макконнелл/Фаулер/Лебланк/Гамма/Александреску-Саттер, захисне програмування, патерни, GRASP, UML, OOP/OOD/OOA, правило Лісків, метрики коду

Методології розробки, Waterfall/RUP/Agile/Scrum/Kanban/XP, TDD/BDD, CASE

Тестування, юніт-тести, функціональне, навантажувальне, інтеграційне тестування, тестування UI

Інструментальнізасоби розробки, IDE, IntelliSense, відладчики (VS/Olly/WinDbg/kdb/gdb) та трейсери (strace/ltrace), valgrind, системи контролю версій (SVN, GIT), merge/branch/trunk, системи іменування файлів та бранчів, continuous integration, ant, code coverage, статичний аналіз, профайлінг, lint, багтрекери, документування коду, збирачі коду типу cmake

Фреймворки, Qt, moc та метаінформація, концепція слот-сигнал, Саммерфілд-Бланшет/Шлеє, PoCo, промислові бібліотеки: GMP, i18n, lapack, fftw, pcre

Операційні системи, Ріхтер/Соломон-українсинович/Робачевський/Вахалія/Стівенс/Linux Kernel Internals, менеджер пам'яті, менеджер купи та її пристрій (LAL/LFH/slab), менеджер процесів, context switch, реальний та захищений режим, здійсненні файли (PE/ELF/Mach), об'єкти ядра, налагоджувальні механізми (strace/ptrace/dtrace/pydbg, Debug API) та мінідампи, bash, мережевий стек та високопродуктивні сервери, netgraph, CR0, IPC, віконна підсистема, система безпеки: ACE/ACL і права доступу, технології віртуалізації, RTOS (QNX), програмування драйверів, IRQL, IRP, файлові системи, BigTable, NDIS/miniport/FS drivers/filter driver, Mm-, Io-, Ldr-функції, DKOM та руткіти, GDT/IDT/SDT, ядра Windows/Linux/BSD, POSIX

COM, OLE/ActiveX/COM+, ATL, Роджерсон/Таварес, апартменти, монікери, додаткові ключові слова VC++, DCOM RPC, CORBA, TAO

Мережа, OSI, Ethernet, TCP/IP, TCP window, алгоритм Нейгла, сокети, Protocol buffers/Thrift/Avro/ASN.1, AMQP, ICMP, роутинг, ARP, атака Митника, syn flood, HTTP /FTP, P2P, DHCP, SMB/NBNS, IRC/XMPP, POP3/SMTP/ESMTP/IMAP, DNS, WiFi/WiMax/GSM/CDMA/EDGE/Bluetooth, ACE, Wireshark

Графіка, алгоритм Брезенхема, колірні моделі, трасування променів vs полігональна графіка, OpenGL/GLSL/OpenInventor, DirectX/DirectShow/DirectAudio/HLSL, stencil/depth/alpha-test, графічний конвеєр у DirectX 11, шейдери, моделі освітлення (Фонг), пропускна спроможність, fillrate, OpenCL/CUDA, ландшафти, човни, тіні, текстурування та фільтрація , антиаліасинг, HDR, tone mapping

Формати, 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

Бази даних, Грубер, ANSI SQL, T-SQL, ODBC, MySQL/PostgreSQL/MS SQL/BDB/SQLite/Sphinx, процедури, що зберігаються, тригери, алгебра Кодда/А, Tutorial D, нормальні форми, оптимізація та виконання запитів, структури даних індексів, транзакції та ACID, CAP-теорема Брюєра, NoSQL, key-value storage, шардинг, ORM (C++ ODB), ERD, OLAP

Прикладне програмування, C#/F#/Nemerle, Шилдт/Троелсен/Ріхтер, генерики, yield, linq/plinq, рефлексія, AST, WCF, WinForms/WPF/Silverlight, AOP, фреймворки логування, .NET assembly

Квантові обчислення, алгоритм Шора, квантова криптографія

Функціональне програмування, Haskell/Ocaml/Scheme/Alice або Oz, SICP/TaPL/YAHT/Purely Functional Data Structures/Харрісон-Філд, HOF (map/fold/filter), монади, тайпкласи, АТД, система типів Хіндлі-Мілнера, лінивість/енергійність, логічне програмування (Prolog або Mercury), конкурентне програмування (Erlang або Oz)

Проектування GUI, Раскін, юзабіліті, основи дизайну та друкарні, закон Фіттса, основи верстки, LaTeX

Дуже значну кількість критики теормін зустрічає і з боку людей, які вважають себе програмістами, які вважають, що все це знати неможливо, вивчати занадто довго, а в деякій абстрактній вузькій.практиці більшість не використовується. Ці люди, на жаль, просто не розуміють, у чому різниця між ерудицією/пам'яттю та знаннями. Цінність для програміста має не запам'ятовування точного формату якогось із пакетів NBNS, а оволодіння підходами, які використовувалися при розробці, тобто не здатність відтворити, а здатність відтворити або впізнати, в тому числі в іншій області. Саме здатність людини до аналізу та синтезу (яка все ж таки не береться з нізвідки, а досягається активною пізнавальною працею) відрізняє її від гугла, який навіть у дуже віддаленій перспективі не навчиться вирішувати навіть div2 250. Саме на розвиток цієї здатності і спрямований теоретичний мінімум, який у процесі роботи обов'язково доведеться доповнювати domain-specific знаннями, чи то особливості ігрової фізики, розробка оперденів на Java чи створення реальних мікросхем.

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

«Нас і тут непогано годують». Цей аргумент зустрічає своє спростування у другому за активністю обговоренні статті у metaclass:Все, що повинен знати програміст, щоб його після 40 років не викинули на Смітник, Де Бомжі.Справді, у віці близько 45 років починає активно виявлятисядеградація мозку, що призводить до суттєвих проблем у розумінні та здатності оперувати кодом із звичайною цикломатичною складністю. Втрата здатності писати код у поєднанні з нездатністю через відсутність тренувань до аналізу/синтезу – гарантований шлях саме туди. Деякі люди зберігають здатність оперувати нормальною цикломатичною складністю і в старості, проте лише за рахунок показників, що перевищують норму, в молодості. Перевірити, чи ви входите до зони ризику, можна на TopCoder.

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