Раздел «Образование».FirstTermSuggestions:

Предложения по содержанию курса первого семестра

Начало курса — введение в теорию алгоритмов

Предлагается переместить курс информатики с фундамента "теории вычислений, вычислительных машин" на фундамент "теория алгоритмов".

Заметьте, что хоть курс и называется "Алгоритмы и алгоритмические языки", его содержание ему не соответствует и скорее должно носить заголовок "Введение в теорию вычислимых функций, формальные языки, язык программирования C/Pascal".

Предлагается же ограничится двумя темами — Алгоритмы (больше на лекциях) и язык программирования C (больше на семинарах).

Первые лекции посвятить тому, что студенты должны были проходить в школе, а потом перейти к более серьезным вещам:

Более подробно смотрите программу первого семестра нацеленную на алгоритмы AlgoBasedFirstTerm.

Суть в том, что алгоритмы представляют собой нечто действительно фундаментальное -- их можно изучать на уровне псевдокода и блок схем (хотя безусловно практикум необходим — студенты должны знать язык пограммирования).

Целью курса будет развитие алгоритмического мышления и знакомство с фундаментальными идеями, обогащающими инструментарий мышления: рекурсия, "разделяй и властвуй", жадность, динамическое программирование, амортизационный анализ и др.

Относительно машины Тьюринга и др.

Безусловно, о машине Тьюринга должно быть рассказано на лекциях и семинарах. Но необходимо существенно сменить контекст, в котором она упоминается. При этом необходимо сильно уменьшить объем материала, связанного с ней.

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

Теория сложности вычислений естественным образом идет после того, как человек разберется с человеческим понятием алгоритма и научится писать напишет мало-мальски сложные программы -– есть такой неофициальный критерий: рассказывать о сложности вычислений и понятии вычислимости можно только после того, как ученик напишет алгоритм работающий N log N и разберется, почему у него такая асимптотика. Только после того, как студент узнает (или придумает) алгоритм сортировки работающий N log N (как в среднем так и в худшем случае) и сможет доказывает, что быстрее чем за N log N без дополнительной информации о данных сортировать нельзя — только после этого имеет смысл рассказывать о машине Тьюринга как об основном понятии в теории вычислимых функций. Не стоит упоминать о машине Тьюринга в контексте теории алгоритмов.

Уважаемые лектора! Помните, что ФУПМы проходят такие предметы как Дискретная математика, Теория и реализация языков программирования и Теория сложности вычислимых систем, где очень много рассказывается с необходимым уровнем подробности и строгости.

Какая либо глубокая философия на первом семестре выбивает студента из колеи. Особенно печальная история про "самоприменимые алгоритмы". Осмелевший студент подошел к лектору и спросил "Что же это такое самоприменимые алгоритмы?" На что лектор ответил — это алгоритмы, которые применяются сами к себе. Эта преждевременно погружение в серьезную науку о вычислимых функциях с неадекватными лекциями сильно увеличивает и без того высокую энтропию энтропию в головах студентов. (Тем, кто дествительно хочет узнать зачем нужны самоприменимые алгоритмы и с чем их едят, прошу на эту страничку).

Практика программирования под машину Тьюринга может кому-то показаться занимательной, интересной и даже полезной. Это действительно так, но эта полезность этой практики заключена просто в "развития логического мышления" — с тем же успехом можно решать математические задачи на смекалку.