|
Размер: 12508
Комментарий:
|
Размер: 12822
Комментарий:
|
| Удаления помечены так. | Добавления помечены так. |
| Строка 32: | Строка 32: |
| || Алгоритм как преобразование слов в алфавите, МТ, НАМ, … /* Уточнение понятия алгоритма, алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Нормальные алгоритмы Маркова. Основные схемы объединения алгоритмов (композиция, разветвление, цикл). Тезис Тьюринга и принцип нормализации, их обоснование. */ || || || || Алгоритмически неразрешимые проблемы /* Алгоритмически неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов. */ || || || || Модельная ЭВМ /* Модельная ЭВМ. Машинное представление данных. Машинный язык как практический формальный способ записи алгоритмов. Недостатки машинных языков. */ || || || |
|| Алгоритм как преобразование слов в алфавите, МТ, НАМ, … /* Уточнение понятия алгоритма, алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Нормальные алгоритмы Маркова. Основные схемы объединения алгоритмов (композиция, разветвление, цикл). Тезис Тьюринга и принцип нормализации, их обоснование. */ || (./) || || || Алгоритмически неразрешимые проблемы /* Алгоритмически неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов. */ || (./) || || || Модельная ЭВМ /* Модельная ЭВМ. Машинное представление данных. Машинный язык как практический формальный способ записи алгоритмов. Недостатки машинных языков. */ || (./) || На мой взгляд, это половина второго семестра :( . Или достаточно показать, что машинные языки адаптированы к машинному хранению и выполнению, и поэтому нужны АЯ? || ----- |
Алгоритмы и алгоритмические языки
Предполагается адаптация курса на базе Паскаля, в котором сохранить структуру изложения, а темы адаптировать к Питону. При необходимости добавить / преобразовать / удалить подтемы.
Концепция
- Введение в теорию алгоритмов
- В основном без изменений
- Организовать практику по МТ и НАМ (на основе реализаций МТ и НАМ, в идеале — скрещенных c edjuge)
- Увеличить в объёме тему УМ, организовать практику и построить обучение второго семестра на этой базе (примерно наполовину)
- Алгоритмические языки. Язык Python
- Выделить тематические составляющие и построить большую часть курса аналогично
- Использовать классы только в качестве конструкторов пространств имён (строго без ООП)
- Подробно описывать минимально достаточное подмножество языка, остальное давать тезисно (спецкурс? 4-й семестр?)
![/!\](/moin_static197/modernized/img/alert.png "/!\")
- Динамические структуры данных
- «Динамические структуры данных» — это не «то, что можно сконструировать», а «то, что удобно использовать в алгоритмах» ⇒ конструируем сами, изучаем, некоторые берём готовые
- Возможно, хватит времени для большего числа хороших, представительных алгоритмов
-
К лекциям (sic!) прилагаются небольшие задания в EJudge.
Сравнительная таблица
В таблице для краткости используются урезанные формулировки, полные формулировки забраны в комментарии (для просмотра нажать на ссылку «комментарии» в шапке страницы).
Обозначения:
— тема практически не меняется 
— тему придётся частично переработать/дополнить 
— новая тема
Курс Паскаля |
Курс Питона |
Замечания |
Часть 1. Введение в теорию алгоритмов |
||
Интуитивное понятие алгоритма |
|
… |
Алгоритм как преобразование слов в алфавите, МТ, НАМ, … |
|
|
Алгоритмически неразрешимые проблемы |
|
|
Модельная ЭВМ |
|
На мой взгляд, это половина второго семестра |
. Или достаточно показать, что машинные языки адаптированы к машинному хранению и выполнению, и поэтому нужны АЯ?
Часть 2. Алгоритмические языки. Язык Паскаль |
||
Алгоритмические языки |
Алгоритмические языки |
|
Язык Паскаль |
Язык Python |
+Понятие исполнителя |
Типы данных, переменные, присваивание, выражения |
Типы объектов, выражения, понятие о связывании объектов. Именование. |
Не все типы объектов (но последовательности нужны) и не все их конструкторы |
Управление потоком вычислений |
Управление потоком вычислений |
Исключения описываются не здесь, в цикле for рассказать про «вычислимые последовательности», например xrange() |
Структурное программирование и комментарии |
Структурное программирование. Строки документации и комментарии |
Перенести на после функций |
Нестандартные типы данных, |
Стандартные типы данных |
Выдержать баланс разумного при выборе (словари точно не надо) |
Процедуры и функции |
Функции. Пространства имён: видимость и время жизни. |
Упаковка/распаковка параметров, видимо, не здесь. А lambda? Было бы уместно в контексте «параметров-функций» |
Рекурсия |
Рекурсия |
|
Сложные типы данных |
Классы как констукторы пространств имён. Экземпляры классов |
|
Динамические переменные. Ссылочные типы данных. |
Счётчик связей. Строки. Множества. Файлы. |
Много небольших тем. |
Методы разработки программы |
Методы разработки программы |
|
Часть 3. Динамические структуры данных |
||
Списки. |
Варианты последовательностей и их свойства. |
Генераторы, очень уж к месту? |
Стек, очередь |
Реализация списков: динамические массивы vs. связанные списки vs. вложенные пары. Тип deque. |
|
Двоичные деревья |
Двоичные деревья |
|
Таблицы, оценка сложности |
Оценка сложности. Методы сортировки. |
|
Деревья поиска, АВЛ-деревья |
Деревья поиска, АВЛ-деревья |
|
Перемешанные таблицы |
Перемешанные таблицы, функция расстановки. Словари и их свойства |
|