Теоретичен минимум за програмиста Crosspost

Sharpitz продължава да ни радва с прекрасни публикации в LJ.
Нека обсъдим този епичен пост:
http://sharpc.livejournal.com/67583.html

Много начинаещи програмисти, особено тези, които учат в провинциални университети, често не знаят в каква посока да се развиват и какво трябва да знаят, за да работят ефективно по своята специалност. Изненадващо е, че всеки ден, използвайки продукти и технологии, създадени от други програмисти, базирани на развити области на знанието, те дори не знаят как работят.

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

° С++

Мултитретиране, философи за хранене, блокиране/състояние на състезание/гладуване, атомност, инструкции за заключване на процесора, CAS или LL/SC, изчакване/заключване/без препятствия, проблем с ABA, писане на контейнери без заключване, спин-заключване, TLS/на нишка OpenMP, MPI, намаление на карта, критична секция/mutex/семафор/променлива на състоянието, WaitForSingleObject/WaitForMultipleObjects, зелена нишка/съпрограма, pthreads

Асемблерен език X86, Зубков/Hyde/Drapper/Kaspersky/Fog/Abrash, синтаксис AT&T и Intel, masm32, макроси, стек, мениджъри на купчина/купчина, конвенции за извикване, шестнадесетични кодове, машинно представяне, IEEE754, малко/голям ендиан, SIMD, хардуерни изключения, прекъсвания, виртуална памет, обръщане, прекъсвания на стека и купчината, програмиране, ориентирано към връщане, буквено-цифров код, L1/L2/RAM/страница грешка и тяхното време

Хардуер, Хоровиц Хил, полупроводникова електроника/спинтроника/фотоника, транзистор, верига, микрокод, технология на процесора, VID/PID, Verilog/VHDL/SystemC, Arduino, устройства с памет (ROM → EEPROM, RAM, SSD, HDD, DVD), RISC/CISC, Таксономия на Flynn ([SM] I [SM] D), подход на Принстън и Харвард, архитектури на процесори, архитектури x86

Процесори, конвейер, хипер-резби, изпълнение извън поръчка, спекулативно изпълнение, предсказване на клон, предварително извличане, множество асоциативен кеш, кеш линия/пропуск на кеша, цикли на часовника, защитни пръстени, памет в многопроцесорни системи, време

Дискретна математика, K2, теорема на Пост, вериги, крайни автомати, клетъчни автомати, автомат Калашников, DFA и NDKA

Изчислимост, Машина на Тюринг, нормални алгоритми на Марков, пощенска машина, уравнения на Диофантин Матиясевич, функции на Church of lambda, частично рекурсивни функции на Kleene, комбинаторно програмиране на Scheinfinkel, Brainfuck, еквивалентност на блата на Turing, проблем със спиране и самоприложимост, преброяване на набора от изчислими функции, RAM машина, алгоритъм на Tarski, решаватели на SAT/SMT, теория на формалните системи

Програмни езици, граматики, йерархия на Хомски, теорема на Myhill-Nerode, лема за изпомпване и лема на Огден, алгебра на Kleene, NDKA -> DFA, алгоритмично неразрешими проблеми в официални езици, Dragonbook, Friedl, регулярни изрази и тяхната сложност, PCRE/POSIX RE, BNF, Boost. + Karma + Qi/Ragel, LL, LR/SLR/LALR/GLR, PEG/packrat, yacc/bison/flex/antlr, анализ на статичен код, компилация/декомпилация/запушване/деобфускация, Clang/LLVM/XMLVM, GCCXML, OpenC ++, изграждане на виртуални машини, JiT/AoT/GC, DSL/DSEL

Алгоритми и комбинативна оптимизация, Cormen/Skiena/Sedgwick/Knut/Aho-Hopcroft-Ullman/Papadimitriu/Shriver-Goldberg/Preparata-Sheimos, структури от данни, алгоритми, сложност и символи на Landau, класове на сложност, NP-пълни проблеми, графики и дървета, потоци в мрежи, Матрица на Kirchhoff, дървета за търсене (особено RB-дърво и B-дърво), откриване на оклузия, купчина, хеш таблици и идеален хеш, мрежи на Петри, руски селянски алгоритъм, метод на Карацуба и умножение на матрица на Виноград-Щрасен, сортове, алчни алгоритми и матроиди, динамично програмиране, линейно програмиране, различни алгоритми, рандомизирани и размити алгоритми за търсене, псевдослучайни числа, размита логика

Машинно обучение, машинно зрение, OpenCV, обработка на изображения, OCR, филтри на Sobel, каскада на Hoare, въведение в психофизиологията на зрението, TreeNet, невронни мрежи, мрежи Kohonen, генетични алгоритми, алгоритми на мравки, извличане на информация/обработка на данни/обработка на естествен език, алгоритми за оптимизация, SVM, усилване на градиента, метод на отгряване, изкачване на хълм, подходи за моделиране на AI

Числени методи, Метод на Гаус, интер- и екстраполация, сплайни, OLS, метод на Ойлер и Рунге-Кута, метод на дихотомия/Нютон, метод на Симпсън, метод на Монте Карло, метод на Галеркин, QR и LU-разлагане, FFT/STFT, конвергенция и стабилност

Теория на информацията, компресия, Huffman, RLE, LZ, кодове за корекция на грешки, информационна ентропия, формула на Шанън, сложност на Колмогоров

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

Математика, Knut-Graham-Patashnik/Zorich/Vinberg, matan, linal, komplan, funkan, diffgem, теория на числата, difura/intura/urchpy/вариационно смятане/оптимален контрол, генериращи функции, серии, комбинаторика, theorver/matstat/контури/теория на масово обслужване, вериги на Марков, интегрални трансформации (Фурие, Лаплас, вейвлет), NZQRCHOS, matpackets (Mathematica, Maple)

Физика, Правила на Кирххоф, сложно съпротивление, скорост и честота на светлината, лагранжиан

Химия, стехиометрия, силициева химия:)

Архитектура и стил на кода, McConnell/Fowler/LeBlanc/Gamma/Alexandrescu-Sutter, защитно програмиране, модели, GRASP, UML, OOP/OOD/OOA, правило на Лисков, кодови метрики

Методологии за развитие, Водопад/RUP/Agile/Scrum/Kanban/XP, TDD/BDD, CASE

Тестване, модулни тестове, функционални, товарни, интеграционни тестове, тестване на потребителския интерфейс

Инструменти за разработка, IDE, IntelliSense, програми за отстраняване на грешки (VS/Olly/WinDbg/kdb/gdb) и трасери (strace/ltrace), valgrind, системи за контрол на версиите (SVN, GIT), обединяване/клон/багажник, системи за имена на файлове и клонове, непрекъсната интеграция, мравка, покритие на код, статичен анализ, профилиране, влакна, следи за грешки, документация на код, конструктори на код като cmake

Рамки, Qt, moc и метаинформация, концепция за слот-сигнал, Summerfield-Blanchet/Schlee, PoCo, индустриални библиотеки: GMP, i18n, lapack, fftw, pcre

операционна система, Рихтер/Соломон-Русинович/Робачевски/Вахалия/Стивънс/Вътрешни ядра на Linux, мениджър на паметта, мениджър на купчина и неговото устройство (LAL/LFH/плоча), мениджър на процеси, превключвател на контекст, реален и защитен режим, изпълними файлове (PE/ELF/Mach), обекти на ядрото, механизми за отстраняване на грешки (strace/ptrace/dtrace/pydbg, Debug API) и минидумпи, bash, мрежов стек и сървъри с висока производителност, netgraph, CR0, IPC, подсистема за прозорци, система за сигурност: ACE/ACL и права за достъп, технологии за виртуализация, RTOS (QNX), програмиране на драйвери, IRQL, IRP, файлови системи, BigTable, NDIS/минипорт/FS драйвери/драйвер за филтър, Mm-, Io-, Ldr функции, DKOM и руткити, GDT/IDT/SDT, Windows/Linux/BSD ядра, POSIX

COM, OLE/ActiveX/COM +, ATL, Rogerson/Tavares, апартаменти, имена, допълнителни ключови думи VC ++, DCOM RPC, CORBA, TAO

Мрежа, OSI, Ethernet, TCP/IP, TCP прозорец, алгоритъм на Nagle, сокети, буфери на протокола/Thrift/Avro/ASN.1, AMQP, ICMP, маршрутизация, ARP, атака на Mitnick, синхронна наводнение, HTTP/FTP, P2P, DHCP, SMB/NBNS, IRC/XMPP, POP3/SMTP/ESMTP/IMAP, DNS, WiFi/WiMax/GSM/CDMA/EDGE/Bluetooth, ACE, Wireshark

Графика, Алгоритъм на Bresenham, цветни модели, проследяване на лъчи срещу многоъгълна графика, OpenGL/GLSL/Open Inventor, DirectX/DirectShow/DirectAudio/HLSL, шаблон/дълбочина/алфа-тест, графичен конвейер в DirectX 11, шейдъри, модели на осветление (Phong), честотна лента способност, запълване, OpenCL/CUDA, пейзажи, светлини, сенки, текстуриране и филтриране, сглаждане, HDR, картографиране на тонове

Формати, XML/XSLT/XPath/XMLStarlet/DOM/SAX, RTF/ODF, JSON/BSON, торент, YAML, JPEG/PNG/WebP, AVI/MPEG/RIFF/WAV/MP3/OGG/WebM, SVG, Unicode, единичен байт кодиране/UTF-8/UTF-16/UCS-2/UTF-32

База данни, Gruber, ANSI SQL, T-SQL, ODBC, MySQL/PostgreSQL/MS SQL/BDB/SQLite/Sphinx, съхранени процедури, тригери, Codd/A алгебра, урок D, нормални форми, оптимизация и изпълнение на заявки, индексиране на структури от данни, транзакции и ACID, теорема за ОСП на Brewer, NoSQL, съхранение на ключ-стойност, рязкост, ORM (C ++ ODB), ERD, OLAP

Приложно програмиране, C #/F #/Nemerle, Schildt/Troelsen/Richter, генерични продукти, доходност, linq/plinq, отражение, AST, WCF, WinForms/WPF/Silverlight, AOP, регистрационни рамки, .NET монтаж

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

Функционално програмиране, Haskell/Ocaml/Scheme/Alice or Oz, SICP/TaPL/YAHT/Чисто функционални структури от данни/Харисън поле, HOF (карта/сгъване/филтър), монади, типови класове, ADT, система от тип Хиндли-Милнър, мързелив/енергичен, логика програмиране (Prolog или Mercury), едновременно програмиране (Erlang или Oz)

GUI дизайн, Ръскин, използваемост, основи на дизайна и типографията, закон на Фитс, основи на оформлението, LaTeX

Много значителна доза критика към теорията среща и хората, които се смятат за програмисти, които вярват в това всичко това е невъзможно да се знае, учи твърде дълго и в някои абстрактни тесни практики по-голямата част от тях не се използва. Тези хора, за съжаление, просто не разбират каква е разликата между ерудицията/паметта и знанието. Стойността за програмиста не е запомнянето на точния формат на който и да е от пакетите NBNS, а овладяване на подходите, използвани при разработката, с други думи, не способността за възпроизвеждане, а способността за пресъздаване или идентифициране, включително в друг ■ площ. Способността на човека да анализира и синтезира (което все още не е извадено от нищото, но се постига чрез активна когнитивна работа) го отличава от Google, който дори в много далечно бъдеще няма да се научи да решава дори div2 250 . Развитието на тази способност е насочено към теоретичния минимум, който в процеса на работа определено ще трябва да бъде допълнен със специфични за дадена област знания, независимо дали това са характеристиките на физиката на игрите, развитието на операционните системи в Java или създаването на истински микросхеми.

В отделен параграф си струва да се открои въпросът от онези, които се съмняват в способността им да овладеят Theormin или вярват, че способността да се прилага рядко ще бъде търсена и ще отслабва. Като цяло теоретичният минимум в повечето точки донякъде отстъпва на учебната програма на CS факултетите на нормалните университети, така че е напълно възможно да го овладеете за 5 години, дори да го комбинирате с работа. По-конкретно при разработването на игри, активно се използват от 1/3 до 2/3 от изброените елементи (според различни оценки в дискусиите). Липсващата дейност може да бъде запълнена, например, като се консултирате с други в Stack Overflow.

„И тук сме добре нахранени“. Този аргумент среща своето опровержение във втората най-активна дискусия на статията в метаклас:
Всичко, което програмистът трябва да знае, за да не може след 40 години да бъде изхвърлен в кошчето, където са бездомните.
Всъщност на около 45-годишна възраст деградацията на мозъка започва активно да се проявява, което води до значителни проблеми в разбирането и способността да се работи с код с обикновена цикломатична сложност. Загубата на способността за писане на код, съчетана с неспособността поради липса на обучение по анализ/синтез, е гарантиран начин да отидете там. Някои хора запазват способността си да работят с нормална цикломатична сложност в напреднала възраст, но само за сметка на надвишаване на нормата в младостта. Можете да проверите дали сте в рисковата зона на TopCoder.

Освен това искам да благодаря на онези, които помогнаха да се поправят досадните грешки в тази теория, особено на моите колеги, които не само притежават по-голямата част от нея, но и направиха най-ценните коментари по нейното завършване.