Алгоритмы и алгоритмические языки

Предполагается адаптация курса на базе Паскаля, в котором сохранить структуру изложения, а темы адаптировать к Питону. При необходимости добавить / преобразовать / удалить подтемы.

Концепция

  1. Введение в теорию алгоритмов
    • В основном без изменений
    • Организовать практику по МТ и НАМ (на основе реализаций МТ и НАМ, в идеале — скрещенных c edjuge)
    • Увеличить в объёме тему УМ, организовать практику и построить обучение второго семестра на этой базе (примерно наполовину)
  2. Алгоритмические языки. Язык Python
    • Выделить тематические составляющие и построить большую часть курса аналогично
    • Использовать классы только в качестве конструкторов пространств имён (строго без ООП)
    • Подробно описывать минимально достаточное подмножество языка, остальное давать тезисно (спецкурс? 4-й семестр?)
    • /!\

  3. Динамические структуры данных
    • «Динамические структуры данных» — это не «то, что можно сконструировать», а «то, что удобно использовать в алгоритмах» ⇒ конструируем сами, изучаем, некоторые берём готовые
    • Возможно, хватит времени для большего числа хороших, представительных алгоритмов
    • /!\

К лекциям (sic!) прилагаются небольшие задания в EJudge.

Сравнительная таблица

В таблице для краткости используются урезанные формулировки, полные формулировки забраны в комментарии (для просмотра нажать на ссылку «комментарии» в шапке страницы).

Обозначения:

Курс Паскаля

Курс Питона

Замечания

Часть 1. Введение в теорию алгоритмов

Интуитивное понятие алгоритма

(./)

Алгоритм как преобразование слов в алфавите, МТ, НАМ, …

(./)

Алгоритмически неразрешимые проблемы

(./)

Модельная ЭВМ

(./)

На мой взгляд, это половина второго семестра :( . Или достаточно показать, что машинные языки адаптированы к возможностям процессора, а не к требованиям человека, и поэтому нужны АЯ?

Часть 2. Алгоритмические языки. Язык Паскаль

Алгоритмические языки

(./) Алгоритмические языки

Язык Паскаль

{2} Язык Python

+Понятие исполнителя

Типы данных, переменные, присваивание, выражения

<!> Типы объектов, выражения, понятие об именовании и связывании объектов. Имена.

Не все типы объектов (но последовательности нужны) и не все их конструкторы

Управление потоком вычислений

{2} Управление потоком вычислений

Исключения описываются не здесь; в цикле for рассказать про «вычислимые последовательности», например xrange(), и вчерне — про «протокол последовательностей»

Структурное программирование и комментарии

(./) Структурное программирование. Строки документации и комментарии

Перенести на после функций

Нестандартные типы данных,

<!> Стандартные типы данных

Выдержать баланс разумного при выборе (словари точно не надо)

Процедуры и функции

{2} Функции. Пространства имён: видимость и время жизни.

Упаковка/распаковка параметров, видимо, не здесь. А lambda? Было бы уместно в контексте «параметров-функций»

Рекурсия

(./) Рекурсия

Сложные типы данных

{2} Классы как констукторы пространств имён. Экземпляры классов

Файл не является типом данных, темы «Строки. Множества, …» можно переместить сюда

Динамические переменные. Ссылочные типы данных.

<!> Счётчик связей. Строки. Множества. Файлы.

Много небольших тем, которые можно поделить с предыдущим разделом. «Файлы» не вписываются никуда, но в для них есть хорошая тема «сериализация»

Методы разработки программы

(./) Методы разработки программы

Часть 3. Динамические структуры данных

Списки.

<!> Варианты последовательностей и их свойства.

Генераторы, очень уж к месту?

Стек, очередь

{2} Реализация списков: динамические массивы vs. связанные списки vs. вложенные пары. Тип deque.

Двоичные деревья

(./) Двоичные деревья

Таблицы, бинарный поиск, оценка сложности, сортировка

(./) Таблицы, бинарный поиск, оценка сложности, сортировка

Мне кажется, или это довольно объёмный раздел, много больше, чем на 2 часа?

Деревья поиска, АВЛ-деревья

(./) Деревья поиска, АВЛ-деревья

Перемешанные таблицы

{2} Перемешанные таблицы, функция расстановки. Словари и их свойства

Python/PythonAlgorithmCourse (last edited 2015-06-22 12:54:51 by FrBrGeorge)