Differences between revisions 6 and 15 (spanning 9 versions)
Revision 6 as of 2015-06-17 07:10:41
Size: 11157
Editor: FrBrGeorge
Comment:
Revision 15 as of 2015-06-22 12:54:51
Size: 13911
Editor: FrBrGeorge
Comment:
Deletions are marked like this. Additions are marked like this.
Line 8: Line 8:
  * Организовать практику по МТ и НАМ   * Организовать практику по МТ и НАМ (на основе реализаций МТ и НАМ, в идеале — скрещенных c edjuge)
Line 12: Line 12:
  * Использовать классы как конструкторы пространства имён (строго без ООП)
  * Подробно описывать достаточное подмножество языка, остальное тезисно (спецкурс? 4-й семестр?)
  * Использовать классы только в качестве конструкторов пространств имён (строго без ООП)
  * Подробно описывать минимально достаточное подмножество языка, остальное давать тезисно (спецкурс? 4-й семестр?)
Line 17: Line 17:
  * Возможно, хватит времени для большего числа алгоритмов   * Возможно, хватит времени для большего числа хороших, представительных алгоритмов
Line 19: Line 19:
К лекциям (!) прилагаются задания в EJudge. К лекциям (sic!) прилагаются небольшие задания в EJudge.
Line 22: Line 22:
''В таблице для краткости используются урезанные формулировки, полные формулировки забраны в комментарии (для просмотра нажать на ссылку «комментарии» в шапке страницы). В таблице для краткости используются урезанные формулировки, полные формулировки забраны в комментарии (для просмотра нажать на ссылку «комментарии» в шапке страницы).

Обозначения:
 . (./) — тема практически не меняется
 . {2} — тему придётся частично переработать/дополнить
 . <!> — полностью переработанная / другая тема
Line 26: Line 31:
|| Интуитивное понятие алгоритма /* Интуитивное понятие алгоритма. Свойства алгоритмов. */ || || … ||
|| Алгоритм как преобразование слов в алфавите, МТ, НАМ, … /* Уточнение понятия алгоритма, алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Нормальные алгоритмы Маркова. Основные схемы объединения алгоритмов (композиция, разветвление, цикл). Тезис Тьюринга и принцип нормализации, их обоснование. */ || || ||
|| Алгоритмически неразрешимые проблемы /* Алгоритмически неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов. */ || || ||
|| Модельная ЭВМ /* Модельная ЭВМ. Машинное представление данных. Машинный язык как практический формальный способ записи алгоритмов. Недостатки машинных языков. */ || || ||
|| Интуитивное понятие алгоритма /* Интуитивное понятие алгоритма. Свойства алгоритмов. */ || (./) || … ||
|| Алгоритм как преобразование слов в алфавите, МТ, НАМ, … /* Уточнение понятия алгоритма, алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Нормальные алгоритмы Маркова. Основные схемы объединения алгоритмов (композиция, разветвление, цикл). Тезис Тьюринга и принцип нормализации, их обоснование. */ || (./) || ||
|| Алгоритмически неразрешимые проблемы /* Алгоритмически неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов. */ || (./) || ||
|| Модельная ЭВМ /* Модельная ЭВМ. Машинное представление данных. Машинный язык как практический формальный способ записи алгоритмов. Недостатки машинных языков. */ || (./) || На мой взгляд, это половина второго семестра :( . Или достаточно показать, что машинные языки адаптированы к возможностям процессора, а не к требованиям человека, и поэтому нужны АЯ? ||
Line 31: Line 36:
|| Алгоритмические языки /* Характеристика алгоритмических языков. Понятие трансляции. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм. */ || || ||
|| Язык Паскаль /* Язык Паскаль (стандартная версия). Алфавит, служебные слова и стандартные имена. Структура программы: заголовок программы и блок, разделы описаний и операторов. */ || Язык Python || +Понятие исполнителя ||
|| Типы данных, переменные, присваивание, выражения /* Типы данных, их классификация. Переменные и константы, разделы переменных и констант. Стандартные простые типы (числовые, логический, символьный). Выражения. Оператор присваивания. Стандартные процедуры ввода-вывода. */ || Типы объектов, выражения, понятие о связывании объектов. Именование. || Не все типы объектов (но последовательности нужны) и не все их конструкторы ||
|| Управление потоком вычислений /* Операторы, их классификация. Пустой, составной и условный операторы. Оператор перехода, раздел меток. Операторы цикла. */ || Управление потоком вычислений || Исключения описываются не здесь, в цикле `for` рассказать про «вычислимые последовательности», например `xrange()`||
|| Структурное программирование и комментарии /* Способы повышения наглядности программы: комментарии, структурная запись программ, структурное программирование. */ || Структурное программирование. Строки документации и комментарии || Перенести на после функций ||
|| Нестандартные типы данных, /* Нестандартные типы данных, раздел типов. Перечислимые и ограниченные типы. Оператор варианта. */ || Стандартные типы данных || Выдержать баланс разумного при выборе (словари точно не надо) ||
|| Процедуры и функции /* Процедуры и функции. Формальные и фактические параметры. Локализация имен и меток. Способы передачи параметров. Побочные эффекты функций. Параметры-функции и параметры-процедуры. */ || Функции. Пространства имён: видимость и время жизни. || Упаковка/распаковка параметров, видимо, не здесь. А `lambda`? Было бы уместно в контексте «параметров-функций» ||
|| Рекурсия /* Рекурсивные процедуры и функции. Итерация и рекурсия. Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. */ || Рекурсия || ||
|| Сложные типы данных /* Сложные типы данных. Массивы, строки. Записи; оператор присоединения. Множества. Файлы, текстовые файлы, внешние и внутренние файлы. */ || Подробнее о последовательностях, множествах и пр. Файлы, сериализация. || Что-нибудь ещё? Например, циклические конструкторы? ||
|| Динамические переменные. Ссылочные типы данных. ||
Счётчик связей. /* Уникальный идентификатор объекта. Операция `is` */ || Что-то ещё? ||
|| Методы разработки программы /* Методы разработки программы (пошаговая детализация и др.). Тестирование и отладка программ. */ || Методы разработки программы || ||
|| Алгоритмические языки /* Характеристика алгоритмических языков. Понятие трансляции. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм. */ || (./) Алгоритмические языки || ||
|| Язык Паскаль /* Язык Паскаль (стандартная версия). Алфавит, служебные слова и стандартные имена. Структура программы: заголовок программы и блок, разделы описаний и операторов. */ || {2} Язык Python /* Алфавит, служебные слова и знаки, операции, имена */ || +Понятие исполнителя ||
|| Типы данных, переменные, присваивание, выражения /* Типы данных, их классификация. Переменные и константы, разделы переменных и констант. Стандартные простые типы (числовые, логический, символьный). Выражения. Оператор присваивания. Стандартные процедуры ввода-вывода. */ || <!> Типы объектов, выражения, понятие об именовании и связывании объектов. Имена. || Не все типы объектов (но последовательности нужны) и не все их конструкторы ||
|| Управление потоком вычислений /* Операторы, их классификация. Пустой, составной и условный операторы. Оператор перехода, раздел меток. Операторы цикла. */ || {2} Управление потоком вычислений || Исключения описываются не здесь; в цикле `for` рассказать про «вычислимые последовательности», например `xrange()`, и вчерне — про «протокол последовательностей»||
|| Структурное программирование и комментарии /* Способы повышения наглядности программы: комментарии, структурная запись программ, структурное программирование. */ || (./) Структурное программирование. Строки документации и комментарии || Перенести на после функций ||
|| Нестандартные типы данных, /* Нестандартные типы данных, раздел типов. Перечислимые и ограниченные типы. Оператор варианта. */ || <!> Стандартные типы данных /* Скалярные типы данных, константные и изменяемые последовательности, … */ || Выдержать баланс разумного при выборе (словари точно не надо) ||
|| Процедуры и функции /* Процедуры и функции. Формальные и фактические параметры. Локализация имен и меток. Способы передачи параметров. Побочные эффекты функций. Параметры-функции и параметры-процедуры. */ || {2} Функции. Пространства имён: видимость и время жизни. || Упаковка/распаковка параметров, видимо, не здесь. А `lambda`? Было бы уместно в контексте «параметров-функций» ||
|| Рекурсия /* Рекурсивные процедуры и функции. Итерация и рекурсия. Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. */ || (./) Рекурсия || ||
|| Сложные типы данных /* Сложные типы данных. Массивы, строки. Записи; оператор присоединения. Множества. Файлы, текстовые файлы, внешние и внутренние файлы. */ || {2} Классы как констукторы пространств имён. Экземпляры классов || Файл не является типом данных, темы «Строки. Множества, …» можно переместить сюда ||
|| Динамические переменные. Ссылочные типы данны
х. || <!> Счётчик связей. Строки. Множества. Файлы. /* Уникальный идентификатор объекта. Операция `is`. */ || Много небольших тем, которые можно поделить с предыдущим разделом. «Файлы» не вписываются никуда, но в для них есть хорошая тема «сериализация» ||
|| Методы разработки программы /* Методы разработки программы (пошаговая детализация и др.). Тестирование и отладка программ. */ || (./) Методы разработки программы || ||
Line 43: Line 48:

/!\

    Списки. Представление списков и реализация основных операций на ними в языке Паскаль. Варианты списков (с заглавным звеном, циклические, двунаправленные).
    Стек, очередь. Векторное и списковое представления их, реализация операций на ними.
   
Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов.
    Таблицы, операция поиска по ключу. Последовательные таблицы (неупорядоченные и упорядоченные). Понятие о (временнóй) оценке сложности алгоритмов в худшем случае и в среднем. Оценка сложности оптимального алгоритма поиска по ключу. Бинарный поиск в упорядоченных таблицах. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке.
    Представление таблиц в виде деревьев поиска (сравнений), оценки сложности поиска по ключу в таких таблицах. АВЛ-деревья, оценки сложности поиска, алгоритм вставки.
    Перемешанные таблицы (хэш-таблицы). Функции расстановки. Устранение коллизий методами закрытого хеширования (линейных проб) и открытого хеширования (цепочек).
|| Списки. /* Представление списков и реализация основных операций на ними в языке Паскаль. Варианты списков (с заглавным звеном, циклические, двунаправленные). */ || <!> Варианты последовательностей и их свойства. || Генераторы, очень уж к месту? ||
|| Стек, очередь /* Стек, очередь. Векторное и списковое представления их, реализация операций на ними. */ || {2} Реализация списков: динамические массивы vs. связанные списки vs. вложенные пары. Тип `deque`. || ||
|| Двоичные деревья /* Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов. */ || (./) Двоичные деревья || ||
|| Таблицы, бинарный поиск, оценка сложности, сортировка /* Таблицы, операция поиска по ключу. Последовательные таблицы (неупорядоченные и упорядоченные). Понятие о (временнóй) оценке сложности алгоритмов в худшем случае и в среднем. Оценка сложности оптимального алгоритма поиска по ключу. Бинарный поиск в упорядоченных таблицах. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке. */ || (./) Таблицы, бинарный поиск, оценка сложности, сортировка /* Функция `sort()` и её параметры */ || Мне кажется, или это довольно объёмный раздел, много больше, чем на 2 часа?||
|| Деревья поиска, АВЛ-деревья /* Представление таблиц в виде деревьев поиска (сравнений), оценки сложности поиска по ключу в таких таблицах. АВЛ-деревья, оценки сложности поиска, алгоритм вставки. */ || (./) Деревья поиска, АВЛ-деревья || ||
|| Перемешанные таблицы /* Перемешанные таблицы (хэш-таблицы). Функции расстановки. Устранение коллизий методами закрытого хеширования (линейных проб) и открытого хеширования (цепочек). */ || {2} Перемешанные таблицы, функция расстановки. Словари и их свойства || ||

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

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

Концепция

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

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

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

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

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

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

  • (./) — тема практически не меняется

  • {2} — тему придётся частично переработать/дополнить

  • <!> — полностью переработанная / другая тема

Курс Паскаля

Курс Питона

Замечания

Часть 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)