Differences between revisions 12 and 13
Revision 12 as of 2015-06-18 17:00:53
Size: 12822
Editor: FrBrGeorge
Comment:
Revision 13 as of 2015-06-18 17:15:55
Size: 12884
Editor: FrBrGeorge
Comment:
Deletions are marked like this. Additions are marked like this.
Line 27: Line 27:
 . <!> — новая тема  . <!> — полностью переработанная / другая тема
Line 35: Line 35:
-----
Line 37: Line 36:
|| Алгоритмические языки /* Характеристика алгоритмических языков. Понятие трансляции. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм. */ || Алгоритмические языки || ||
|| Язык Паскаль /* Язык Паскаль (стандартная версия). Алфавит, служебные слова и стандартные имена. Структура программы: заголовок программы и блок, разделы описаний и операторов. */ || Язык Python || +Понятие исполнителя ||
|| Типы данных, переменные, присваивание, выражения /* Типы данных, их классификация. Переменные и константы, разделы переменных и констант. Стандартные простые типы (числовые, логический, символьный). Выражения. Оператор присваивания. Стандартные процедуры ввода-вывода. */ || Типы объектов, выражения, понятие о связывании объектов. Именование. || Не все типы объектов (но последовательности нужны) и не все их конструкторы ||
|| Управление потоком вычислений /* Операторы, их классификация. Пустой, составной и условный операторы. Оператор перехода, раздел меток. Операторы цикла. */ || Управление потоком вычислений || Исключения описываются не здесь, в цикле `for` рассказать про «вычислимые последовательности», например `xrange()`||
|| Алгоритмические языки /* Характеристика алгоритмических языков. Понятие трансляции. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм. */ || (./) Алгоритмические языки || ||
|| Язык Паскаль /* Язык Паскаль (стандартная версия). Алфавит, служебные слова и стандартные имена. Структура программы: заголовок программы и блок, разделы описаний и операторов. */ || <!> Язык Python || +Понятие исполнителя ||
|| Типы данных, переменные, присваивание, выражения /* Типы данных, их классификация. Переменные и константы, разделы переменных и констант. Стандартные простые типы (числовые, логический, символьный). Выражения. Оператор присваивания. Стандартные процедуры ввода-вывода. */ || <!> Типы объектов, выражения, понятие о связывании объектов. Именование. || Не все типы объектов (но последовательности нужны) и не все их конструкторы ||
|| Управление потоком вычислений /* Операторы, их классификация. Пустой, составной и условный операторы. Оператор перехода, раздел меток. Операторы цикла. */ || {2} Управление потоком вычислений || Исключения описываются не здесь, в цикле `for` рассказать про «вычислимые последовательности», например `xrange()`||

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

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

Концепция

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

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

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

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

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

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

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

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

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

Курс Паскаля

Курс Питона

Замечания

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

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

(./)

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

(./)

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

(./)

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

(./)

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

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

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

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

Язык Паскаль

<!> Язык Python

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекурсия

Рекурсия

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

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

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

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

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

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

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

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

Списки.

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

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

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

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

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

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

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

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

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

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

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

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

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