Теоретический минимум для программиста - Public forum of MSU united student networks

Это копипаста из ЖЖ

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

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

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

C++, стандарт, Comeau, 1TBS, Страустрап/D&E/Джосаттис/Вандервуд, Дьюхэрст/Мейерс/Саттер, RAII, правило трех, exception-safety, Александреску/Абрахамс-Гуртовой, type erasure, CRTP, NVI, SFINAE, Koenig lookup, Duff's device, Boost, Сик-Ламсдейн/Карлссон, TR1, TR on C++ performance, тест Степанова, forwarding problem, SPECS, C++0x

Компиляторы, особенности реализации стандарта, ограничения реализации, интринсики, отличия стандартных библиотек (контейнеры, rand), ABI, реализация виртуальных функций, виртуального наследования, исключений, RTTI, switch, указателей на функции и методы; оптимизации, copy elision (RVO, NRVO), sizeof на различных платформах, дефайны компилятора и среды, __declspec, ключи компилятора, empty-base optimization, статическая и динамическая линковка, манглинг, распределенная компиляция, precompiled header, single compilation unit, (strict) aliasing/restrict, inline/_forceinline, volatile

Мультитредность, обедающие философы, 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 и их тайминг

Аппаратное обеспечение, полупроводниковая электроника/спинтроника/фотоника, NOR/NAND, транзистор, схемотехника, микрокод, технология создания процессоров, VID/PID, Verilog/VHDL/SystemC, Arduino, устройство HDD/SSD/DVD, RISC/CISC, Flynn's taxonomy ([SM]I[SM]D), принстонский и гарвардский подход, архитектуры процессоров, архитектуры x86

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

Дискретная математика, 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-дерево), куча, хэш-таблицы и идеальный хэш, сети Петри, алгоритм русского крестьянина, метод Карацубы и матричное умножение Винограда-Штрассена, сортировки, жадные алгоритмы и матроиды, динамическое программирование, линейное программирование, diff-алгоритмы, рандомизированные алгоритмы и алгоритмы нечеткого поиска, псевдослучайные числа, нечеткая логика

Машинное обучение, машинное зрение, OpenCV, image processing, OCR, фильтры Собеля, каскад Хоара, введение в психофизиологию зрения, TreeNet, нейросети, сети Кохонена, генетические алгоритмы, муравьиные алгоритмы, information retrieval/data mining/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, файловые системы, NDIS/miniport/FS drivers/filter driver, Mm-, Io-, Ldr-функции, DKOM и руткиты, GDT/IDT/SDT, ядра Windows/Linux/BSD, POSIX

COM, OLE/ActiveX/COM+, ATL, Роджерсон/Таварес, апартменты, моникеры, дополнительные ключевые слова VC++

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

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

Форматы, XML/XSLT/XPath/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, MySQL/PostgreSQL/MS SQL/BDB/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)

Веб-программирование и скриптовые языки, Фланаган/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

Проектирование GUI, Раскин, юзабилити, основы дизайна и типографики, закон Фиттса, основы верстки, LaTeX

http://sharpc.livejournal.com/67583.html
-
От себя отмечу, что не раскрыта тема верификации/валидации ПО, а COM можно оставить в истории.

Пора посыпать голову пеплом?

Редактировал vissi (25.03.2011 14:40)