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

sharpc — 24.03.2011 Многие начинающие программисты, особенно обучающиеся в провинциальных вузах, часто не знают, в какую сторону им развиваться, и что они должны знать для того, чтобы эффективно работать по специальности. Удивительно, но каждый день используя продукты и технологии, созданные другими программистами на основании развитых областей знания, они даже не догадываются о том, как они устроены.

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

Я и мои единомышленники взяли на себя труд составить теоретический минимум для программиста на основании наиболее ярких отраслей IT, вошедших даже в программы нормальных университетов, на основании собеседований и постоянно пригождающихся на практике знаний. Часть из пунктов этого минимума можно изучить за 5 минут по википедии, часть же потребует серьезного труда на протяжении нескольких месяцев, но это именно то, что обязательно следует знать и чем следует свободно владеть. В комментариях приветствуются исправления и дополнения.

1. C++, стандарт, Comeau, 1TBS, Страустрап/D&E/Джосаттис/Вандервуд, Дьюхэрст/Мейерс/Саттер, RAII, правило трех, exception-safety, Александреску/Абрахамс-Гуртовой, type erasure, CRTP, NVI, SFINAE, Koenig lookup, Duff's device, Boost, Сик-Ламсдейн/Карлссон, TR1, TR on C++ performance, ABI, тест Степанова, forwarding problem, SPECS, C++0x
   
   
2. Компиляторы, особенности реализации стандарта, ограничения реализации, интринсики, отличия стандартных библиотек (контейнеры, rand), ABI, реализация виртуальных функций, виртуального наследования, исключений, RTTI, switch, указателей на функции и методы; оптимизации, copy elision (RVO, NRVO), sizeof на различных платформах, дефайны компилятора и среды, __declspec, ключи компилятора, empty-base optimization, статическая и динамическая линковка, манглинг, распределенная компиляция, precompiled header, single compilation unit, (strict) aliasing/restrict, inline/_forceinline, volatile
   
   
3. Мультитредность, обедающие философы, 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, модель акторов
   
   
4. Язык ассемблера x86, Зубков/Хайд/Дреппер/Касперски/Фог/Абраш, AT&T и Intel-синтаксис, masm32, макросы, стек, куча/менеджеры кучи, соглашения вызова, hex-коды, машинное представление данных, IEEE754, little/big endian, SIMD, аппаратные исключения, прерывания, виртуальная память, реверсинг, срыв стека и кучи, return oriented programming, alphanumeric shellcode, L1/L2/RAM/page fault и их тайминг
   
   
5. Аппаратное обеспечение, Хоровиц-Хилл, полупроводниковая электроника/спинтроника/фотоника, транзистор, схемотехника, микрокод, технология создания процессоров, VID/PID, Verilog/VHDL/SystemC, Arduino, устройства памяти (ROM → EEPROM, RAM, SSD, HDD, DVD), RISC/CISC, Flynn's taxonomy ([SM]I[SM]D), принстонский и гарвардский подход, архитектуры процессоров, архитектуры x86
   
   
6. Процессоры, конвейеризация, hyper-threading, out-of-order execution, спекулятивное исполнение, branch predict, префетчинг, множественный ассоциативный кэш, кэш-линия/кэш-промах, такты, кольца защиты, память в мультипроцессорных системах, тайминг памяти
   
   
7. Дискретная математика, K2, теорема Поста, схемы, конечные автоматы, клеточные автоматы, автомат Калашникова, ДКА и НДКА
   
   
8. Вычислимость, машина Тьюринга, нормальные алгоритмы Маркова, машина Поста, диофантовы уравнения Матиясевича, лямбда-функции Черча, частично рекурсивные функции Клини, комбинаторное программирование Шейнфинкеля, Brainfuck, эквивалентность тьюринговых трясин, проблема останова и самоприменимости, счетность множества вычислимых функций, RAM-машина, алгоритм Тарского, SAT/SMT-солверы, теория формальных систем
   
   
9. Языки программирования, грамматики, иерархия Хомского, теорема Майхилла-Нероуда, лемма о накачке и лемма Огдена, алгебра Клини, НДКА -> ДКА, алгоритмически неразрешимые задачи в формальных языках, Драгонбук, Фридл, регекспы и их сложность, 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
   
   
10. Алгоритмы и комбинаторная оптимизация, Кормен/Скиена/Седжвик/Кнут/Ахо-Хопкрофт-Ульман/Пападимитриу/Шрайвер-Голдберг/Препарата-Шеймос, структуры данных, алгоритмы, сложность и символы Ландау, классы сложности, NP-полные задачи, графы и деревья, потоки в сетях, матрица Кирхгофа, деревья поиска (особенно RB-дерево и B-дерево), occlusion detection, куча, хэш-таблицы и идеальный хэш, сети Петри, алгоритм русского крестьянина, метод Карацубы и матричное умножение Винограда-Штрассена, сортировки, жадные алгоритмы и матроиды, динамическое программирование, линейное программирование, diff-алгоритмы, рандомизированные алгоритмы и алгоритмы нечеткого поиска, псевдослучайные числа, нечеткая логика
    
    
11. Численные методы, дихотомия/метод Ньютона, интер- и экстраполяция, сплайны, метод Гаусса/Якоби/Зейделя, QR и LU-декомпозиция, SVD, МНК, метод Рунге-Кутты, метод Адамса, формула Ньютона-Котеса, метод Монте-Карло, метод Ритца, метод Бубнова-Галеркина, метод конечных разностей/элементов, FFT/STFT, сходимость и устойчивость
    
    
12. Машинное обучение, машинное зрение, OpenCV, image processing, OCR, фильтры Собеля, каскад Хоара, введение в психофизиологию зрения, TreeNet, нейросети, сети Кохонена, генетические алгоритмы, муравьиные алгоритмы, information retrieval/data mining/natural language processing, алгоритмы оптимизации, метод главных компонент, SVM, gradient boosting, метод отжига, hill climbing, подходы к моделированию AI
    
    
13. Теория информации, сжатие, Хаффман, RLE, LZ, коды коррекции ошибок, сжатие с потерями (изображения, аудио, видео), информационная энтропия, формула Шеннона, сложность Колмогорова
    
    
14. Криптография, Ященко, симметричная, асимметричная, Диффи-Хеллман, RSA, DES, AES, эллиптические кривые, хэширование (MD5, SHA, CRCn), DHT, криптостойкость, криптоатаки, WEP/WPA/WPA2 и атаки на них, цифровая подпись и сертификаты, HTTPS/SSL, доказательство с нулевым разглашением
    
    
15. Математика, Кнут-Грэхем-Паташник/Зорич/Винберг, матан, линал, комплан, функан, диффгем, теория чисел, дифуры/интуры/урчпы/вариационное исчисление/оптимальное управление, производящие функции, ряды, комбинаторика, теорвер/матстат/слупы/теория массового обслуживания, цепи Маркова, интегральные преобразования (Фурье, Лаплас, вейвлет), NZQRCHOS, матпакеты (Mathematica, Maple)
    
    
16. Физика, правила Кирхгофа, комплексное сопротивление, скорость и частота света, лагранжиан
    
    
17. Химия, стехиометрия, химия кремния :)
    
    
18. Архитектура и стиль кода, Макконнелл/Фаулер/Лебланк/Гамма/Александреску-Саттер/Буч, защитное программирование, паттерны, GRASP, UML, OOP (Smalltalk), OOD/OOA, правило Лисков, метрики кода
    
    
19. Методологии разработки, Waterfall/RUP/Agile/Scrum/Kanban/XP, TDD/BDD, CASE
    
    
20. Тестирование, юнит-тесты, функциональное, нагрузочное, интеграционное тестирование, тестирование UI
    
    
21. Инструментальные средства разработки, IDE, IntelliSense, отладчики (VS/Olly/WinDbg/kdb/gdb) и трейсеры (strace/ltrace), valgrind, системы контроля версий (SVN, GIT), merge/branch/trunk, системы именования файлов и бранчей, continuous integration, ant, code coverage, статический анализ, верификация и валидация ПО (Frama-C, RAISE (RSL), Coq), профайлинг, lint, багтрекеры, документирование кода, сборщики кода типа cmake
    
    
22. Фреймворки, Qt, moc и метаинформация, концепция слот-сигнал, Саммерфилд-Бланшет/Шлее, PoCo, промышленные библиотеки: GMP, i18n, lapack, fftw, pcre
    
    
23. Операционные системы, Silberschatz/Рихтер/Соломон-Руссинович/Робачевский/Вахалия/Стивенс/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
    
    
24. COM, OLE/ActiveX/COM+, ATL, Роджерсон/Таварес, апартменты, моникеры, MIDL, DCOM RPC, CORBA, TAO
    
    
25. Сеть, 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
    
    
26. Графика, алгоритм Брезенхема, цветовые модели, трассировка лучей vs полигональная графика, OpenGL/GLSL/Open Inventor, DirectX/DirectShow/DirectAudio/HLSL, stencil/depth/alpha-test, графический конвейер в DirectX 11, шейдеры, модели освещения (Фонг), пропускная способность, fillrate, OpenCL/CUDA, ландшафты, лоды, тени, текстурирование и фильтрация, антиалиасинг, HDR, tone mapping
    
    
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. Базы данных, Грубер, 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
    
    
29. Прикладное программирование, C#/F#/Nemerle, Шилдт/Троелсен/Рихтер, генерики, 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/Харрисон-Филд, HOF (map/fold/filter), система типов Хиндли-Милнера, монады, тайпклассы, АТД, dependent types, ленивость/энергичность, логическое программирование (Prolog или Mercury), конкурентное программирование (Erlang или Oz)
    
    
32. Веб-программирование и скриптовые языки, Фланаган/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, ООП в JavaScript, HTML5/XHTML/doctype/табличная и блочная верстка/CSS3, RSS, canvas/WebGL, Ajax/Comet/WebSockets, вопросы безопасности: XSS, SQL injection, CSRF, highload, SWIG
    
    
33. Проектирование GUI, Раскин, юзабилити, основы дизайна и типографики, закон Фиттса, основы верстки, LaTeX
    

UPD: Некоторые комментарии повторяются довольно часто, и разумно было бы попробовать ответить на них в апдейте поста.


Этот теормин вполне справедливо критикуется за отсутствие системности изложения и ВНЕЗАПНЫЕ соседства различных как по глубине, так и по содержанию топиков. Это не бага, это фича. Системное изложение программы по практически любому из пунктов заняло бы места не меньше, чем оглавления пухлых талмудов, поэтому лучше как раз названия этих талмудов и приводить. Как же тогда работать с этим списком? Следует брать хорошие книжки по тематике и читать их до тех пор, пока все упомянутые слова не встретятся в процессе чтения. Авторы и в страшном сне не могли предположить, что кто-то решит, что устройство Даффа посчитают по глубине и объему чем-то равным полуторатысячестраничному Священному Стандарту. Однако этот критерий вполне рабочий — можно перечитать сотню книг по C++ для начинающих, и ни разу не встретить упоминания о нем, но если читать действительно полезные книги и статьи (для тем, подобных C++, такие книги существуют и перечислены), то все слова довольно быстро встречаются. Смысл программы, обусловленный ее размером, именно в том, чтобы дать возможность оценить, достаточное ли количество книг по теме прочитано.

Весьма значительное количество критики теормин встречает и со стороны людей, считающих себя программистами, которые полагают, что все это знать невозможно, изучать слишком долго, а в некоторой абстрактной узкой практике большая часть не используется. Эти люди, к сожалению, просто не понимают, в чем разница между эрудицией/памятью и знаниями. Ценность для программиста имеет не запоминание точного формата какого-нибудь из пакетов NBNS, а овладение подходами, которые использовались при разработке, другими словами не способность воспроизвести, а способность воссоздать или опознать, в том числе в другой области. Именно способность человека к анализу и синтезу (которая все же не берется из ниоткуда, а достигается активным познавательным трудом) отличает его от гугла, который даже в очень отдаленной перспективе не научится решать даже div2 250. Именно на развитие этой способности и направлен теоретический минимум, который в процессе работы обязательно придется дополнять domain-specific знаниями, будь то особенности игровой физики, разработка оперденей на Java или создание реальных микросхем.

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

Отдельную категорию людей, высказывающуюся в стиле «я такого не знаю, я такое запрещаю» составляют те, кто полагает, что цель программиста заключается не в улучшении мира, а в зарабатывании денег. Им этот теоретический минимум действительно не нужен, а следует поискать самоучители по тому, как правильно и со знанием всех тонкостей воровать, обманывать и заставлять работать вместо себя других.

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



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

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

Оставить комментарий

Популярные посты:

• Архив