Когда я в заинтересованно спрашиваю что же именно должен знать НАСТОЯЩИЙ ПРОГРАММИСТ обычно получаю в ответ какие-нить частные проблемы именно того прогера, с которым я в эту минуту беседую. Причем выдаваемые чуть ли не за истинную сущность всего программирования как такового. Ну что-то типа -- "Если ты не знаешь как использовать семафоры в Делфи ты не программист". Или -- "если ты не знаешь как устроены хэш-таблицы ты не программист". Мне это надоело, я покопался в интернете и решил собрать в один пост все, что должен знать НАСТОЯЩИЙ ПРОГРАММИСТ по мнению самих НАСТОЯЩИХ ПРОГРАММИСТОВ. Список с разбивкой по разделам знания под катом
МАТЕМАТИКА
• Численные методы, дихотомия/метод Ньютона, интер- и экстраполяция, сплайны, метод Гаусса/Якоби/Зейделя, QR и LU-декомпозиция, SVD, МНК, методы Рунге-Кутты, метод Адамса, формулы Ньютона-Котеса, метод Ритца, метод Бубнова-Галеркина, метод конечных разностей/элементов, FFT/STFT, сходимость и устойчивость, l-bfgs и другие квазиньютоновские методы, adagrad, PARAFAC, cassowary, interior point methods, вариационные методы для байесовского вывода, nesterov, автоматическое дифференцирование, alternating least squares, what every computer scientist should know about floating point arithmetics by Goldberg, Nocedal & Wright/Boyd & Vandenberghe
• Алгоритмы, Кнут-Грэхем-Паташник/Зорич/Винберг, Spivak/Dummit-Foote, математический анализ, линейная алгебра, комплексный анализ, функциональный анализ, дифференциальная геометрия, теория чисел, дифференциальные уравнения/интегральные уравнения/вариационное исчисление/оптимальное управление, производящие функции, ряды, комбинаторика, теория вероятностей/математическая статистика/случайные процессы/теория массового обслуживания, цепи Маркова, интегральные преобразования (Фурье, Лаплас, Вейвлет), NZQRCHOS, матпакеты (Mathematica, Maple), теория категорий
• Теория информации, сжатие, Хаффман, RLE, BWT, LZ, коды коррекции ошибок, сжатие с потерями (изображения, аудио, видео), информационная энтропия, формула Шеннона, сложность Колмогорова, maximum entropy problem, kullback-leibler divergence, elias/shannon-elias encoding
• Дискретная математика, K2, теорема Поста, схемы, конечные автоматы (ДКА и НДКА), автомат Калашникова, клеточные автоматы
• Криптография, Шнайер/Ященко, Принцип Керкгоффса, симметричная (DES, AES), асимметричная (RSA), качество ГПСЧ, алгоритм Диффи-Хеллмана, эллиптические кривые, хэширование (MD5, SHA, CRCn), DHT, криптостойкость, криптоатаки (атака гроссмейстера), WEP/WPA/WPA2 и атаки на них, цифровая подпись и сертификаты, PKI, HTTPS/SSL, доказательство с нулевым разглашением, пороговая схема, murmurhash/cityhash, DKIM
• Квантовые вычисления, алгоритм Шора, квантовая криптография
ОБЩИЕ ОСНОВЫ ПРОГРАММИРОВАНИЯ
• Мультитредность, обедающие философы, deadlock/livelock/race condition/starvation, атомарность, lock инструкции процессора, memory model/barrier/ordering, 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/WaitForMultipleObjec
• Вычислимость, машина Тьюринга, нормальные алгоритмы Маркова, машина Поста, диофантовы уравнения Матиясевича, лямбда-функции Черча, частично рекурсивные функции Клини, комбинаторное программирование Шейнфинкеля, Brainfuck, эквивалентность тьюринговых трясин, проблема останова и самоприменимости, счетность множества вычислимых функций, RAM-машина, алгоритм Тарского, SAT/SMT-солверы, теория формальных систем, interactive proofs, теорема Левина-Кука, 3SAT, PSPACE = NPSPACE, #P
• Алгоритмы и комбинаторная оптимизация, Кормен/Скиена/Седжвик/Кнут/Ахо-Хопкрофт-У
• Машинное обучение, Тибширани/Bishop, подходы к моделированию AI, переобучение/кроссвалидация, байесовские сети, нейросети, сети Кохонена, Restricted Boltzmann machine, градиентный спуск/hill climbing, стохастическая оптимизация (метод Монте-Карло, метод отжига, генетические алгоритмы, муравьиные алгоритмы), SVM, gradient boosting, кластерный анализ, метод главных компонент, LSH, обучение с подкреплением, MDP, information retrieval/data mining/natural language processing, машинное зрение, Szeliski, OpenCV, image processing, OCR, фильтры Собеля, каскад Хаара, Viola-Jones framework, SURF, введение в психофизиологию зрения, IPython/pandas/scikit-learn, (ME)HMM, CRF, label bias problem, stacked NN, LeToR, factorization machines, autoencoders, RNN/CNN, вместо NLP лучше отдельные задачи (language modelling, co-reference detection, text chunking, POS-tagging, probabilistic parsing, statistical machine translation, misspell correction, question answering, NER, collocation detection, text summarization, speech recognition, fact extraction, sentiment analysis), эффективное вычисление softmax, feature engineering/selection, quality estimation, Manning/Jurafsky/McCallum/Koehn, latent topics (LDA, chineese restaurant, pLSI), parallel coordinates, vowpal wabbit, NLTK, structured learning, EM-алгоритм, contrastive divergence, optimal brain surgery, belief propagation, semi-supervised learning, inductive vs transductive learning, kernel trick, discriminative/generative pairs (as seen by Ng & Jordan), sequence to sequence learning, bagging, анализ социальных графов, рекомендательные системы/collaborative filtering, multimodal learning
ОБЩИЕ ПРИНЦИПЫ НАПИСАНИЯ ПРОГРАММ
• Архитектура и стиль кода, Макконнелл/Фаулер/Лебланк/Гамма/Александ
• Методологии разработки, Waterfall/RUP/Agile/Scrum/Kanban/XP, TDD/BDD, CASE
• Инструментальные средства разработки, IDE, IntelliSense, отладчики (VS/Olly/WinDbg/kdb/gdb) и трейсеры (strace/ltrace), DWARF debug information format, дизассемблеры и декомпиляторы (IDA/HexRays/Reflector), системы контроля версий (SVN, GIT), merge/branch/trunk, системы именования файлов и бранчей, continuous integration, ant, code coverage, статический анализ (lint, cppcheck), динамический анализ (valgrind, фаззинг), верификация и валидация ПО (Frama-C, RAISE (RSL), Coq), профайлинг, багтрекеры, документирование кода, системы сборки (CMake), пакетные менеджеры (NuGet)
• Фреймворки, Qt, moc и метаинформация, концепция слот-сигнал, Саммерфилд-Бланшет/Шлее, PoCo, промышленные библиотеки: GMP, i18n, lapack, fftw, pcre
• Проектирование GUI и представление информации, Раскин/Тафти, юзабилити, основы дизайна и типографики, закон Фиттса, основы верстки, LaTeX, алгоритмы визуализации данных (as seen in d3), subpixel rendering
• Тестирование, юнит-тесты, функциональное, нагрузочное, интеграционное тестирование, тестирование UI, mocks/stubs/spies, fixture, запахи и паттерны тестов (Osherove/Meszaros)
ЯЗЫКИ ПРОГРАММИРОВАНИЯ
• Общее представление об языках программирования, грамматики, иерархия Хомского, теорема Майхилла-Нероуда, лемма о накачке и лемма Огдена, алгебра Клини, НДКА → ДКА, алгоритмически неразрешимые задачи в формальных языках, Драгонбук, Фридл, регекспы и их сложность, PCRE, БНФ, Boost.Spirit + Karma + Qi/Ragel, LL, LR/SLR/LALR/GLR, PEG/packrat, yacc/bison/flex/antlr, статический анализ кода, компиляция/декомпиляция/обфускация/деобф
• Язык ассемблера, Зубков/Хайд/Дреппер/Касперски/Фог/Абраш,
• C++, стандарт, Comeau, 1TBS, Страустрап/D&E/Джосаттис/Вандервуд, Дьюхэрст/Мейерс/Саттер, RAII/copy-and-swap/exception-safety, правило пяти, Александреску/Абрахамс-Гуртовой, type erasure, CRTP, NVI, SFINAE, Koenig lookup, Duff's device, Boost, Сик-Ламсдейн/Карлссон, TR on C++ performance, тест Степанова, forwarding problem/move semantics, SPECS, GotW, Meyer's singleton, cppgm
• Компиляторы С++, особенности реализации стандарта, ограничения реализации, интринсики, отличия стандартных библиотек (контейнеры, rand), ABI, реализация виртуальных функций, виртуального наследования, исключений, RTTI, switch, указателей на функции и методы; оптимизации, copy elision (RVO, NRVO), sizeof на различных платформах, дефайны компилятора и среды, __declspec, ключи компилятора, empty-base optimization, статическая и динамическая линковка, манглинг, распределенная компиляция, precompiled header, single compilation unit, (strict) aliasing/restrict, inline/_forceinline, volatile, быстрое вычисление математических функций через битхаки, linkers & loaders by Levine
• Прикладное программирование, C#/F#, Шилдт/Троелсен/Рихтер, генерики, yield, linq/plinq, рефлексия, AST, WCF, WinForms/WPF/Silverlight, AOP, фреймворки логгирования, .NET assembly, Scala, Хорстманн/Одерски, pattern matching, макросы/квазицитаты
• Функциональное программирование, Haskell/Ocaml/Scheme/Alice или Oz, SICP/TaPL/YAHT/Purely Functional Data Structures/Харрисон-Филд, HOF (map/fold/filter), система типов Хиндли-Милнера, монады, тайпклассы, АТД, dependent types, ленивость/энергичность, логическое программирование (Prolog или Mercury), конкурентное программирование (Erlang или Oz)
• Веб-программирование и скриптовые языки, Фланаган/Zend PHP5 Certification Course + Study Guide, Apache/nginx, CGI/FastCGI, PHP/Zend Framework/ReactPHP/Zend Engine/Doctrine или Propel/CodeIgniter или Symphony или Yii, Python/Django/Twisted, Ruby/RoR, ASP.NET MV*, JavaScript/jQuery/React/Google Closure/ExtJS/node.js, ООП в JavaScript, HTML5, CSS3/табличная и блочная верстка, RSS, canvas/WebGL, Ajax/WebSockets, вопросы безопасности (XSS, SQL injection, CSRF), highload, C10k problem, SWIG, CDN, shadow DOM, квирки браузеров, real time bidding/trading, anomaly detection, архитектура single page apps, устройство веб-краулеров, web/social graph random walk, asm.js и компиляция в js, v8/spidermonkey internals, PaaS/IaaS, SPDY
БАЗЫ ДАННЫХ
• Базы данных/Распределенные системы, Грубер/Дейт, ANSI SQL, T-SQL, ODBC, MySQL/PostgreSQL/MS SQL/BDB/SQLite/Sphinx, хранимые процедуры, триггеры, алгебра Кодда/А, Tutorial D, нормальные формы, оптимизация и выполнение запросов, структуры данных индексов, транзакции и ACID, CAP-теорема Брюера, graph DB, document store, wide column store, key-value storage, теория распределенных систем, CRDT, net split проблема, протоколы консенсуса, теория шардинга/репликации, ORM (C++ ODB), ERD, OLAP, семантическая сеть, triplestore, RDF/Turtle, SPARQL, OWL, Semanticscience Integrated Ontology, reasoner, DBpedia, big table/hbase vs. dynamodb/cassandra/riak, 2/3PC, chubby/zoo keeper, leader election (paxos/raft), hdfs/gfs/glusterfs, deduplication problem, causality detection (vector clock/stamps), R/W quorum, load balancing, устройство индексов поисковых систем, event sourcing, CRDT, дизайн протоколов и принципы коммуникации, с точки зрения эволюции, расширяемости, надежности, дизайн программных интерфейсов (API)
ОПЕРАЦИОННЫЕ СИСТЕМЫ
• Операционные системы, Silberschatz/Рихтер/Соломон-Руссинович/Р
• Форматы, XML/XSLT/XPath/XMLStarlet/DOM/SAX, RTF/ODF, JSON/BSON/bencode, YAML, JPEG/PNG/WebP, AVI/MPEG/RIFF/WAV/MP3/OGG/WebM, SVG, Unicode, кодировки однобайтные/UTF-8/UTF-16/UCS-2/UTF-32, проблемы длины и сравнения Unicode-строк, base64, markdown
• Компонентно-ориентированные модели, Роджерсон/Таварес, COM/OLE/ActiveX/COM+/DCOM RPC, ATL, апартменты, моникеры, MIDL, XPCOM, CORBA, TAO, D-Bus
• Сеть, Стивенс, OSI model/Internet model, Ethernet, TCP/IP, TCP window, алгоритм Нейгла, сокеты, Protocol buffers/Thrift/Avro/ASN.1, AMQP, ICMP, роутинг/BGP/OSPF, ARP, атака Митника, syn flood, HTTP/FTP, P2P/DHT, DHCP, SMB/NBNS, IRC/XMPP, POP3/SMTP/ESMTP/IMAP, DNS, WiFi/WiMax/GSM/CDMA/EDGE/Bluetooth/GPS, ACE, Wireshark
АППАРАТНОЕ ОБЕСПЕЧЕНИЕ
• Аппаратное обеспечение, Хоровиц-Хилл/Титце-Шенк, полупроводниковая электроника/спинтроника/фотоника, транзистор, триггер, схемотехника, микрокод, технология создания процессоров, logic synthesis, static timing analysis, FPGA, Verilog/VHDL/SystemC, SISAL, Arduino, устройства памяти (ROM → EEPROM, RAM, SSD, HDD, DVD), RISC/CISC, Flynn's taxonomy ([SM]I[SM]D), принстонский и гарвардский подход, архитектуры процессоров, архитектуры x86, VID/PID
• Процессоры, конвейеризация, hyper-threading, алгоритм Томасуло, спекулятивное исполнение, static/dynamic branch prediction, префетчинг, множественный ассоциативный кэш, кэш-линия/кэш-промах, такты, кольца защиты, память в мультипроцессорных системах (SMP/NUMA), тайминг памяти, intel optimization manuals, performance counters
___________________________________
Ну как, впечатляет? Интересно, есть в мире хоть ОДИН ЧЕЛОВЕК, который реально все это знает?
Journal information