Какие знания необходимы программисту - часть 1

Очень часто на различных программистских форумах, да и просто в разговорах возникает вопрос: а что должен знать и уметь программист для того чтобы быть достойным высокого звания программиста ;-) Ну естественно тут у каждого свое мнение. Один скажет мол главное иметь голову на плечах, а остальное само приложится. Другой же скажет что без знания MFC и шагу ступить нельзя, третий скажет что знать надо то, чем пользуешься, четвертый расскажет, что если не понимаешь что несколько if-else - это на самом деле система линейных уравнений, но тебе и к компьютеру подходить не стоит, ну и так далее.

У меня тоже свое мнение есть :-) Хочу только сразу сказать, я не буду рассуждать про голову на плечах. Голова, она для любой профессии нужна. Тем не менее некоторый набор базовых знаний, как мне кажется, программистам необходим. Вот этот набор, вернее то, каким он мне видится я и хочу описать. Замечу, что я пытаюсь описать знания, которые совершенно необходимо каждому программисту, независимо от того, какие именно программы и в какой предметной области он или она пишет. (Да тут есть некоторая размытость - ведь не дано точного определения программиста. Нужно ли обладать знаниями о которых я буду говорить в дальнейшем бухгалтеру, который пишет макрос в Excel? А является ли программистом художник, рисующий Flash-анимацию? Как это часто уже бывало в этом блоге, оставляю ответ на "программистскую интуицию" и здравый смысл. Возможно этот вопрос - кого считать программистом- это тема отдельного поста? )


Математические основы

Начать хочу с самого для многих неприятного - математики. Есть много мнений - нужна ли математика программистам? А что если я рисую формы - нужна ли мне математика? Вот мой глубоко личный взгляд. В скобках к названию темы я буду давать некоторые ключевые слова, которые на мой взгляд позволяют быстро понять о чем идет речь, даже если название само по себе не помогло. Заметим - в скобках вовсе не делается попытка "раскрыть" тему - просто приводятся некоторые ключевые слова.

• системы счисления (общие принципы, двоичные, восьмеричные и т.п. числа)
  
• способы представления чисел (всевозможные "дополнения до", представление вещественных чисел, числа со знаком и без)
  
• математическая логика (исчисление высказываний, логические операции, правила де-Моргана, булева алгебра)
  
• анализ алгоритмов (O(n), анализ сложности, NP-полнота)
• комбинаторика (перестановки, сочетания, размещения)
• теория вероятностей (мера, нормальное распределение, дисперсия)
• линейная алгебра (векторы, матрицы, системы линейных уравнений)
• теория множеств (множества, пересечения множеств , объединения множеств, мощность)
• основы алгебры (бинарные отношения, изоморфизмы, группы, кольца, поля)
• теория чисел (факториал, простые числа, делимость)
• основы теории графов
  

Алгоритмы и структуры данных

Тоже сложная тема. Зачем нам знать алгоритм сортировки если есть qsort? (вместо qsort
подставить свой алгоритм) . Как можно не знать сортировки? А сколько раз в жизни тебе пришлось руками написать сортировку? Все эти и подобные им вопросы сразу же возникают, когда вспоминаешь про алгоритмы и структуры данных.

• Структуры данных
• стек
• очередь
• списки
• хэш-таблицы
• деревья
  
  
• Алгоритмы
• сортировка :-) (быстрая, вставками, пирамидальная, "пузырьком" :-) )
• поиск подстроки, сопоставление с образцом (алгоритм Кнута-Морриса-Пратта)
• алгоритмы на графах (поиск кратчайшего пути, алгоритм Дейкстры)

Теория автоматов и формальных языков

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

• конечные автоматы
• автоматы с магазинной памятью
  
• грамматики (КС-грамматики, LL и LR грамматики)
• регулярные языки
• формы представления языков (форма Хомского, формы Бэкуса-Наура)
• машины Тьюринга
• рекурсивные функции

Устал. А до конца ещё далеко. Посему обзываю все что успел написать первой частью :-) и выкладываю.