7082
Комментарий:
|
11333
|
Удаления помечены так. | Добавления помечены так. |
Строка 2: | Строка 2: |
Предполагается адаптация [[PascalAAL|курса на базе Паскаля]], в котором сохранить структуру изложения, а темы адаптировать к Питону. При необходимости добавить / преобразовать / удалить подтемы. | |
Строка 21: | Строка 22: |
''В таблице для краткости используются урезанные формулировки, полные версии см. в [[PascalAAL]]. | ''В таблице для краткости используются урезанные формулировки, полные формулировки забраны в комментарии (для просмотра нажать на ссылку «комментарии» в шапке страницы). |
Строка 25: | Строка 26: |
|| Интуитивное понятие алгоритма. Свойства алгоритмов. || || || || Алгоритм как преобразование слов из заданного алфавита. МТ. НАМ || || || || Композиция алгоритмов, тезис Тьюринга || || || || Алгоритмически неразрешимые проблемы|| || || || Модельная ЭВМ || || || |
|| Интуитивное понятие алгоритма /* Интуитивное понятие алгоритма. Свойства алгоритмов. */ || … || … || || Алгоритм как преобразование слов в алфавите, МТ, НАМ, … /* Уточнение понятия алгоритма, алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Нормальные алгоритмы Маркова. Основные схемы объединения алгоритмов (композиция, разветвление, цикл). Тезис Тьюринга и принцип нормализации, их обоснование. */ || || || || Алгоритмически неразрешимые проблемы /* Алгоритмически неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов. */ || || || || Модельная ЭВМ /* Модельная ЭВМ. Машинное представление данных. Машинный язык как практический формальный способ записи алгоритмов. Недостатки машинных языков. */ || || || |
Строка 31: | Строка 31: |
|| АЯ, БНФ || | || Алгоритмические языки /* Характеристика алгоритмических языков. Понятие трансляции. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм. */ || || || || Язык Паскаль /* Язык Паскаль (стандартная версия). Алфавит, служебные слова и стандартные имена. Структура программы: заголовок программы и блок, разделы описаний и операторов. */ || Язык Python || +Понятие исполнителя || || Типы данных, переменные, присваивание, выражения /* Типы данных, их классификация. Переменные и константы, разделы переменных и констант. Стандартные простые типы (числовые, логический, символьный). Выражения. Оператор присваивания. Стандартные процедуры ввода-вывода. */ || Типы объектов, выражения, понятие о связывании объектов. Именование. || Не все типы объектов (но последовательности нужны) и не все их конструкторы || || Управление потоком вычислений /* Операторы, их классификация. Пустой, составной и условный операторы. Оператор перехода, раздел меток. Операторы цикла. */ || Управление потоком вычислений || Исключения описываются не здесь, в цикле `for` рассказать про «вычислимые последовательности», например `xrange()`|| || Структурное программирование и комментарии /* Способы повышения наглядности программы: комментарии, структурная запись программ, структурное программирование. */ || Структурное программирование. Строки документации и комментарии || Перенести на после функций || || Нестандартные типы данных, /* Нестандартные типы данных, раздел типов. Перечислимые и ограниченные типы. Оператор варианта. */ || Стандартные типы данных || Выдержать баланс разумного при выборе (словари точно не надо) || || Процедуры и функции /* Процедуры и функции. Формальные и фактические параметры. Локализация имен и меток. Способы передачи параметров. Побочные эффекты функций. Параметры-функции и параметры-процедуры. */ || Функции. Пространства имён: видимость и время жизни. || Упаковка/распаковка параметров, видимо, не здесь. А `lambda`? Было бы уместно в контексте «параметров-функций» || || Рекурсия /* Рекурсивные процедуры и функции. Итерация и рекурсия. Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. */ || Рекурсия || || || Сложные типы данных /* Сложные типы данных. Массивы, строки. Записи; оператор присоединения. Множества. Файлы, текстовые файлы, внешние и внутренние файлы. */ || Подробнее о последовательностях, множествах и пр. Файлы, сериализация. || Что-нибудь ещё? Например, циклические конструкторы? || || Динамические переменные. Ссылочные типы данных. || Счётчик связей. /* Уникальный идентификатор объекта. Операция `is` */ || Что-то ещё? || || Методы разработки программы /* Методы разработки программы (пошаговая детализация и др.). Тестирование и отладка программ. */ || Методы разработки программы || || |||||| Часть 3. Динамические структуры данных || || Списки. /* Представление списков и реализация основных операций на ними в языке Паскаль. Варианты списков (с заглавным звеном, циклические, двунаправленные). */ || Варианты последовательностей /* Динамические массивы vs. связанные чписки */ || Генераторы? || |
Строка 33: | Строка 45: |
/!\ '''TODO''' | /!\ |
Строка 35: | Строка 47: |
Язык Паскаль (стандартная версия). Алфавит, служебные слова и стандартные имена. Структура программы: заголовок программы и блок, разделы описаний и операторов. Типы данных, их классификация. Переменные и константы, разделы переменных и констант. Стандартные простые типы (числовые, логический, символьный). Выражения. Оператор присваивания. Стандартные процедуры ввода-вывода. Операторы, их классификация. Пустой, составной и условный операторы. Оператор перехода, раздел меток. Операторы цикла. Способы повышения наглядности программы: комментарии, структурная запись программ, структурное программирование. Нестандартные типы данных, раздел типов. Перечислимые и ограниченные типы. Оператор варианта. Процедуры и функции. Формальные и фактические параметры. Локализация имен и меток. Способы передачи параметров. Побочные эффекты функций. Параметры-функции и параметры-процедуры. Рекурсивные процедуры и функции. Итерация и рекурсия. Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. Сложные типы данных. Массивы, строки. Записи; оператор присоединения. Множества. Файлы, текстовые файлы, внешние и внутренние файлы. Динамические переменные. Ссылочные типы данных. Методы разработки программы (пошаговая детализация и др.). Тестирование и отладка программ. |
|
Строка 46: | Строка 48: |
Часть 3. Динамические структуры данных Списки. Представление списков и реализация основных операций на ними в языке Паскаль. Варианты списков (с заглавным звеном, циклические, двунаправленные). |
|
Строка 54: | Строка 53: |
Третья |
Алгоритмы и алгоритмические языки
Предполагается адаптация курса на базе Паскаля, в котором сохранить структуру изложения, а темы адаптировать к Питону. При необходимости добавить / преобразовать / удалить подтемы.
Концепция
- Введение в теорию алгоритмов
- В основном без изменений
- Организовать практику по МТ и НАМ
- Увеличить в объёме тему УМ, организовать практику и построить обучение второго семестра на этой базе (примерно наполовину)
- Алгоритмические языки. Язык Python
- Выделить тематические составляющие и построить большую часть курса аналогично
- Использовать классы как конструкторы пространства имён (строго без ООП)
- Подробно описывать достаточное подмножество языка, остальное тезисно (спецкурс? 4-й семестр?)
- Динамические структуры данных
- «Динамические структуры данных» — это не «то, что можно сконструировать», а «то, что удобно использовать в алгоритмах» ⇒ конструируем сами, изучаем, некоторые берём готовые
- Возможно, хватит времени для большего числа алгоритмов
К лекциям прилагаются задания в EJudge.
Сравнительная таблица
В таблице для краткости используются урезанные формулировки, полные формулировки забраны в комментарии (для просмотра нажать на ссылку «комментарии» в шапке страницы). Курс Паскаля Курс Питона Замечания Часть 1. Введение в теорию алгоритмов Интуитивное понятие алгоритма … … Алгоритм как преобразование слов в алфавите, МТ, НАМ, … Алгоритмически неразрешимые проблемы Модельная ЭВМ Часть 2. Алгоритмические языки. Язык Паскаль Алгоритмические языки Язык Паскаль Язык Python +Понятие исполнителя Типы данных, переменные, присваивание, выражения Типы объектов, выражения, понятие о связывании объектов. Именование. Не все типы объектов (но последовательности нужны) и не все их конструкторы Управление потоком вычислений Управление потоком вычислений Исключения описываются не здесь, в цикле for рассказать про «вычислимые последовательности», например xrange() Структурное программирование и комментарии Структурное программирование. Строки документации и комментарии Перенести на после функций Нестандартные типы данных, Стандартные типы данных Выдержать баланс разумного при выборе (словари точно не надо) Процедуры и функции Функции. Пространства имён: видимость и время жизни. Упаковка/распаковка параметров, видимо, не здесь. А lambda? Было бы уместно в контексте «параметров-функций» Рекурсия Рекурсия Сложные типы данных Подробнее о последовательностях, множествах и пр. Файлы, сериализация. Что-нибудь ещё? Например, циклические конструкторы? Динамические переменные. Ссылочные типы данных. Счётчик связей. Что-то ещё? Методы разработки программы Методы разработки программы Часть 3. Динамические структуры данных Списки. Варианты последовательностей Генераторы?