Различия между версиями 2 и 9 (по 7 версиям)
Версия 2 от 2015-06-16 15:58:42
Размер: 7082
Редактор: FrBrGeorge
Комментарий:
Версия 9 от 2015-06-17 15:58:51
Размер: 12046
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 2: Строка 2:
Предполагается адаптация [[PascalAAL|курса на базе Паскаля]], в котором сохранить структуру изложения, а темы адаптировать к Питону. При необходимости добавить / преобразовать / удалить подтемы.
Строка 21: Строка 22:
''В таблице для краткости используются урезанные формулировки, полные версии см. в [[PascalAAL]]. ''В таблице для краткости используются урезанные формулировки, полные формулировки забраны в комментарии (для просмотра нажать на ссылку «комментарии» в шапке страницы).
Строка 25: Строка 26:
|| Интуитивное понятие алгоритма. Свойства алгоритмов. || || ||
|| Алгоритм как преобразование слов из заданного алфавита. МТ. НАМ || || ||
|| Композиция алгоритмов, тезис Тьюринга || || ||
|| Алгоритмически неразрешимые проблемы|| || ||
|| Модельная ЭВМ || || ||
|| Интуитивное понятие алгоритма /* Интуитивное понятие алгоритма. Свойства алгоритмов. */ || … || … ||
|| Алгоритм как преобразование слов в алфавите, МТ, НАМ, … /* Уточнение понятия алгоритма, алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Нормальные алгоритмы Маркова. Основные схемы объединения алгоритмов (композиция, разветвление, цикл). Тезис Тьюринга и принцип нормализации, их обоснование. */ || || ||
|| Алгоритмически неразрешимые проблемы /* Алгоритмически неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов. */ || || ||
|| Модельная ЭВМ /* Модельная ЭВМ. Машинное представление данных. Машинный язык как практический формальный способ записи алгоритмов. Недостатки машинных языков. */ || || ||
Строка 31: Строка 31:
|| АЯ, БНФ ||

/!\ '''TODO'''

   
Язык Паскаль (стандартная версия). Алфавит, служебные слова и стандартные имена. Структура программы: заголовок программы и блок, разделы описаний и операторов.
    Типы данных, их классификация. Переменные и константы, разделы переменных и констант. Стандартные простые типы (числовые, логический, символьный). Выражения. Оператор присваивания. Стандартные процедуры ввода-вывода.
    Операторы, их классификация. Пустой, составной и условный операторы. Оператор перехода, раздел меток. Операторы цикла.
    Способы повышения наглядности программы: комментарии, структурная запись программ, структурное программирование.
    Нестандартные типы данных, раздел типов. Перечислимые и ограниченные типы. Оператор варианта.
    Процедуры и функции. Формальные и фактические параметры. Локализация имен и меток. Способы передачи параметров. Побочные эффекты функций. Параметры-функции и параметры-процедуры.
    Рекурсивные процедуры и функции. Итерация и рекурсия. Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии.
    Сложные типы данных. Массивы, строки. Записи; оператор присоединения. Множества. Файлы, текстовые файлы, внешние и внутренние файлы.
    Динамические переменные. Ссылочные типы данных.
    Методы разработки программы (пошаговая детализация и др.). Тестирование и отладка программ.

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

   
Списки. Представление списков и реализация основных операций на ними в языке Паскаль. Варианты списков (с заглавным звеном, циклические, двунаправленные).
   
Стек, очередь. Векторное и списковое представления их, реализация операций на ними.
    Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов.
    Таблицы, операция поиска по ключу. Последовательные таблицы (неупорядоченные и упорядоченные). Понятие о (временнóй) оценке сложности алгоритмов в худшем случае и в среднем. Оценка сложности оптимального алгоритма поиска по ключу. Бинарный поиск в упорядоченных таблицах. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке.
    Представление таблиц в виде деревьев поиска (сравнений), оценки сложности поиска по ключу в таких таблицах. АВЛ-деревья, оценки сложности поиска, алгоритм вставки.
    Перемешанные таблицы (хэш-таблицы). Функции расстановки. Устранение коллизий методами закрытого хеширования (линейных проб) и открытого хеширования (цепочек).
Третья
|| Алгоритмические языки /* Характеристика алгоритмических языков. Понятие трансляции. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм. */ || Алгоритмические языки || ||
|| Язык Паскаль /* Язык Паскаль (стандартная версия). Алфавит, служебные слова и стандартные имена. Структура программы: заголовок программы и блок, разделы описаний и операторов. */ || Язык Python || +Понятие исполнителя ||
|| Типы данных, переменные, присваивание, выражения /* Типы данных, их классификация. Переменные и константы, разделы переменных и констант. Стандартные простые типы (числовые, логический, символьный). Выражения. Оператор присваивания. Стандартные процедуры ввода-вывода. */ || Типы объектов, выражения, понятие о связывании объектов. Именование. || Не все типы объектов (но последовательности нужны) и не все их конструкторы ||
|| Управление потоком вычислений /* Операторы, их классификация. Пустой, составной и условный операторы. Оператор перехода, раздел меток. Операторы цикла. */ || Управление потоком вычислений || Исключения описываются не здесь, в цикле `for` рассказать про «вычислимые последовательности», например `xrange()`||
|| Структурное программирование и комментарии /* Способы повышения наглядности программы: комментарии, структурная запись программ, структурное программирование. */ || Структурное программирование. Строки документации и комментарии || Перенести на после функций ||
|| Нестандартные типы данных,  /* Нестандартные типы данных, раздел типов. Перечислимые и ограниченные типы. Оператор варианта. */ || Стандартные типы данных || Выдержать баланс разумного при выборе (словари точно не надо) ||
|| Процедуры и функции /* Процедуры и функции. Формальные и фактические параметры. Локализация имен и меток. Способы передачи параметров. Побочные эффекты функций. Параметры-функции и параметры-процедуры. */ || Функции. Пространства имён: видимость и время жизни. || Упаковка/распаковка параметров, видимо, не здесь. А `lambda`? Было бы уместно в контексте «параметров-функций» ||
|| Рекурсия /* Рекурсивные процедуры и функции. Итерация и рекурсия. Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. */ || Рекурсия || ||
|| Сложные типы данных  /* Сложные типы данных. Массивы, строки. Записи; оператор присоединения. Множества. Файлы, текстовые файлы, внешние и внутренние файлы. */ || Классы как констукторы пространств имён. Экземпляры классов || ||
|| Динамические переменные. Ссылочные типы данных. || Счётчик связей. Строки. Множества. Файлы. /* Уникальный идентификатор объекта. Операция `is` */ || Много небольших тем. ||
|| Методы разработки программы  /* Методы разработки программы (пошаговая детализация и др.). Тестирование и отладка программ. */ || Методы разработки программы || ||
|||||| Часть 3. Динамические структуры данных ||
|| Списки. /* Представление списков и реализация основных операций на ними в языке Паскаль. Варианты списков (с заглавным звеном, циклические, двунаправленные). */ || Варианты последовательностей и их свойства. || Генераторы, очень уж к месту? ||
|| Стек, очередь /* Стек, очередь. Векторное и списковое представления их, реализация операций на ними. */ || Реализация списков: динамические массивы vs. связанные списки vs. вложенные пары. Тип `deque`. || ||
|| Двоичные деревья /* Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов. */ || Двоичные деревья || ||
|| Таблицы, оценка сложности /* Таблицы, операция поиска по ключу. Последовательные таблицы (неупорядоченные и упорядоченные). Понятие о (временнóй) оценке сложности алгоритмов в худшем случае и в среднем. Оценка сложности оптимального алгоритма поиска по ключу. Бинарный поиск в упорядоченных таблицах. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке. */ || Оценка сложности. Методы сортировки. /* Функция `sort()` и её параметры */ || ||
|| Деревья поиска, АВЛ-деревья /* Представление таблиц в виде деревьев поиска (сравнений), оценки сложности поиска по ключу в таких таблицах. АВЛ-деревья, оценки сложности поиска, алгоритм вставки. */ || Деревья поиска, АВЛ-деревья || ||
|| Перемешанные таблицы /* Перемешанные таблицы (хэш-таблицы). Функции расстановки. Устранение коллизий методами закрытого хеширования (линейных проб) и открытого хеширования (цепочек). */ || Перемешанные таблицы, функция расстановки. Словари и их свойства || ||

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

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

Концепция

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

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

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

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

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

Курс Паскаля

Курс Питона

Замечания

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

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

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

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

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

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

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

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

Язык Паскаль

Язык Python

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

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

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

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

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

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

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

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

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

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

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

Стандартные типы данных

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

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

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

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

Рекурсия

Рекурсия

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

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

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

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

Много небольших тем.

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

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

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

Списки.

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

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

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

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

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

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

Таблицы, оценка сложности

Оценка сложности. Методы сортировки.

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

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

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

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

Python/PythonAlgorithmCourse (последним исправлял пользователь FrBrGeorge 2015-06-22 15:54:51)