Differences between revisions 6 and 7
Revision 6 as of 2015-06-17 07:10:41
Size: 11157
Editor: FrBrGeorge
Comment:
Revision 7 as of 2015-06-17 07:42:23
Size: 11333
Editor: FrBrGeorge
Comment:
Deletions are marked like this. Additions are marked like this.
Line 43: Line 43:
|| Списки. /* Представление списков и реализация основных операций на ними в языке Паскаль. Варианты списков (с заглавным звеном, циклические, двунаправленные). */ || Варианты последовательностей /* Динамические массивы vs. связанные чписки */ || Генераторы? ||
Line 46: Line 47:
    Списки. Представление списков и реализация основных операций на ними в языке Паскаль. Варианты списков (с заглавным звеном, циклические, двунаправленные).

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

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

Концепция

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

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

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

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

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

Курс Паскаля

Курс Питона

Замечания

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

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

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

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

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

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

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

Язык Паскаль

Язык Python

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекурсия

Рекурсия

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

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

Что-нибудь ещё? Например, циклические конструкторы?

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

Счётчик связей.

Что-то ещё?

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

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

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

Списки.

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

Генераторы?

/!\

  • Стек, очередь. Векторное и списковое представления их, реализация операций на ними. Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов. Таблицы, операция поиска по ключу. Последовательные таблицы (неупорядоченные и упорядоченные). Понятие о (временнóй) оценке сложности алгоритмов в худшем случае и в среднем. Оценка сложности оптимального алгоритма поиска по ключу. Бинарный поиск в упорядоченных таблицах. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке. Представление таблиц в виде деревьев поиска (сравнений), оценки сложности поиска по ключу в таких таблицах. АВЛ-деревья, оценки сложности поиска, алгоритм вставки. Перемешанные таблицы (хэш-таблицы). Функции расстановки. Устранение коллизий методами закрытого хеширования (линейных проб) и открытого хеширования (цепочек).

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