7899
Комментарий:
|
8102
|
Удаления помечены так. | Добавления помечены так. |
Строка 19: | Строка 19: |
/!\ TODO Расписать по часам или по парам 1. (введение) Интуитивное понятие алгоритма. Свойства алгоритмов. 1. (введение) Пример исполнителя (программируемый калькулятор): данные, команды, последовательное, условное и циклическое выполнение. 1. (введение) Алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Нормальные алгоритмы Маркова. Тезис Тьюринга и принцип нормализации, их обоснование. 1. (введение) Алгоритмически неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов. 1. (введение) ИКС и неформальное использование питона как калькулятора. 1. (типы данных) Константы-конструкторы объектов. Операции над объектами. Интерпретация выражения: конструирование и удаление объектов. 1. (типы данных) Последовательности. Доступ к элементу и секционирование. Множественный оператор именования, распаковка последовательностей. 1. (пространство имён) Ссылки на объекты: имена; ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение. 1. (операторы) Условный оператор. Блок операторов. Оператор цикла с условием. Каноническая схема цикла. Вложенные операторы. 1. (операторы) Старшинство операций. Логические операции. Нулевой объект типа. 1. (пространство имён) Функции: задание и оператор вызова. Локальное пространство имён. Позиционные и именованные параметры. Рекурсия. 1. (пространства имён) Пространство имён объекта: поля и методы объекта. Методы последовательностей, строк и словарей. 1. (алгоритмы) Хеширование. Хеш-функция, её назначение и свойства. 1. (типы данных) Хешируемые объекты. Словари. Косвенная передача параметров функции. Функции с произвольным количеством и именами параметров. 1. (операторы) Цикл с итерируемым объектом. Циклические конструкторы объектов. 1. (типы данных) Генераторы: выражения-генераторы, повторно входимые функции (функции-генераторы). Работа цикла с итерируемым объектом. 1. (пространства имён) Модуль как контейнер имён. Стандартные модули. 1. (пространства имён) Класс как конструктор пространства имён. Экземпляр класса: динамические поля и поля класса. Методы. Вызов метода. 1. (пространства имён) Спецметоды. Реализация операций над объектами путём задания спецметодов. |
1. Интуитивное понятие алгоритма. Свойства алгоритмов. 1. Пример исполнителя (программируемый калькулятор): данные, команды, последовательное, условное и циклическое выполнение. 1. Алгоритм как преобразование слов из заданного алфавита. Нормальные алгоритмы Маркова. 1. Машина Тьюринга. Тезис Тьюринга и принцип нормализации, их обоснование. 1. Алгоритмически неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов. 1. Характеристика алгоритмических языков. Понятие трансляции. Компилируемые и интерпретируемые языки. Понятие исполнителя. 1. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм. 1. История Python. ИКС и неформальное использование Python как калькулятора. 1. Константы-конструкторы основных скалярных объектов. Операции над объектами. Интерпретация выражения: конструирование и удаление объектов. 1. Основные типы последовательностей. Индексирование и секционирование. Множественный оператор именования, распаковка последовательностей. 1. Ссылки на объекты: имена; ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение. 1. Условный оператор. Блок операторов. Оператор цикла с условием. Каноническая схема цикла. Вложенные операторы. 1. Старшинство операций. Логические операции. Нулевой объект типа. 1. Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён. Позиционные и именованные параметры. 1. Оформление исходного кода: комментарии, строки документации, договорённости об именовании. Модернизация языка Python сообществом, 1. Пространство имён объекта: поля и методы объекта. Методы последовательностей. Использование списка в качестве стека и очереди. Строковые методы. 1. Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях. 1. Рекурсия. Достоинства, недостатки, критерий применения в Python. Замещение рекурсии стеком контекстов. 1. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке. 1. Задача хеширования. Открытое и закрытое хеширование. Требования к функции расстановки. 1. Хешируемые объекты Python. Словари. Методы словарей. 1. Упаковка и распаковка параметров функции. Функции с произвольным количеством и именами параметров. Словари-пространства глобальных и локальных имён. 1. Цикл с итерируемым объектом. Циклические конструкторы объектов. 1. Генераторы: выражения-генераторы, повторно входимые функции (функции-генераторы). Работа цикла с итерируемым объектом. 1. Модуль как контейнер имён. Использование модуля. Стандартные модули. Файл как модуль. Строки документации. 1. Класс как конструктор пространства имён. Экземпляр класса: динамические поля и поля класса. Методы. Вызов метода. Строки документации. 1. Спецметоды. Реализация операций над объектами путём задания спецметодов. |
Строка 42: | Строка 49: |
1. (алгоритмические языки) Характеристика алгоритмических языков. Понятие трансляции. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм. 1. (алгоритмические языки) Оформление исходного кода: комментарии, строки документации, договорённости об именовании. Модернизация языка (PEP-ы). 1. (алгоритмы) Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях. 1. (типы данных) Множества, байтовые массивы. Константные (хешируемые) варианты. Операции над множествами. 1. (алгоритмы) Эффективность операций над структурами данных. Индексация в последовательностях и индексация в массивах. Эффективность итераторов в последовательностях. 1. (алгоритмы) Моделирование списков. Двунаправленные и циклические списки. Моделирование графов. Деревья. 1. (алгоритмы) Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов. 1. (алгоритмы) Сбалансированные деревья, их свойства. Вставка и удаление элементов. 1. (алгоритмы) Куча 1. (алгоритмы) Замыкание транзитивного бинарного отношения. 1. (типы данных) Моделирование многомерных массивов. 1. (операторы) Исключения как средство управления потоком вычислений |
1. Множества, байтовые массивы. Константные (хешируемые) варианты. Операции над множествами. 1. Эффективность операций над структурами данных. Индексация в последовательностях и индексация в массивах. Эффективность итераторов в последовательностях. 1. Моделирование списков. Двунаправленные и циклические списки. Моделирование графов. Деревья. 1. Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов. 1. Сбалансированные деревья, их свойства. Вставка и удаление элементов. 1. Куча 1. Замыкание транзитивного бинарного отношения. 1. Моделирование многомерных массивов. 1. Исключения как средство управления потоком вычислений |
Алгоритмы и алгоритмические языки: альтернативная версия
Аннотация
TODO
Концепция
- Цели курса:
- Заложить основы алгоритмического мышления
- Дать эффективный язык описания алгоритмов и структур данных
- Дать универсальный инструмент программирования
- Задачи курса:
- Познакомить с основами теории алгоритмов
- Привить представление об ЭВМ как алгоритмическом исполнителе команд, и о языке программирования как о формализации таких команд
- Развить навыки составления алгоритмов и отлаживания программ на языке Python3
- Познакомить с алгоритмами и структурами данных, используемыми при решении типовых задач
Лекции
- Интуитивное понятие алгоритма. Свойства алгоритмов.
- Пример исполнителя (программируемый калькулятор): данные, команды, последовательное, условное и циклическое выполнение.
- Алгоритм как преобразование слов из заданного алфавита. Нормальные алгоритмы Маркова.
- Машина Тьюринга. Тезис Тьюринга и принцип нормализации, их обоснование.
- Алгоритмически неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов.
- Характеристика алгоритмических языков. Понятие трансляции. Компилируемые и интерпретируемые языки. Понятие исполнителя.
- Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм.
- История Python. ИКС и неформальное использование Python как калькулятора.
- Константы-конструкторы основных скалярных объектов. Операции над объектами. Интерпретация выражения: конструирование и удаление объектов.
- Основные типы последовательностей. Индексирование и секционирование. Множественный оператор именования, распаковка последовательностей.
- Ссылки на объекты: имена; ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение.
- Условный оператор. Блок операторов. Оператор цикла с условием. Каноническая схема цикла. Вложенные операторы.
- Старшинство операций. Логические операции. Нулевой объект типа.
- Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён. Позиционные и именованные параметры.
- Оформление исходного кода: комментарии, строки документации, договорённости об именовании. Модернизация языка Python сообществом,
- Пространство имён объекта: поля и методы объекта. Методы последовательностей. Использование списка в качестве стека и очереди. Строковые методы.
- Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях.
- Рекурсия. Достоинства, недостатки, критерий применения в Python. Замещение рекурсии стеком контекстов.
- Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке.
- Задача хеширования. Открытое и закрытое хеширование. Требования к функции расстановки.
- Хешируемые объекты Python. Словари. Методы словарей.
- Упаковка и распаковка параметров функции. Функции с произвольным количеством и именами параметров. Словари-пространства глобальных и локальных имён.
- Цикл с итерируемым объектом. Циклические конструкторы объектов.
- Генераторы: выражения-генераторы, повторно входимые функции (функции-генераторы). Работа цикла с итерируемым объектом.
- Модуль как контейнер имён. Использование модуля. Стандартные модули. Файл как модуль. Строки документации.
- Класс как конструктор пространства имён. Экземпляр класса: динамические поля и поля класса. Методы. Вызов метода. Строки документации.
- Спецметоды. Реализация операций над объектами путём задания спецметодов.
TODO: что ещё должно быть: выбрать и подсунуть в нужное место Ещё:
- Множества, байтовые массивы. Константные (хешируемые) варианты. Операции над множествами.
- Эффективность операций над структурами данных. Индексация в последовательностях и индексация в массивах. Эффективность итераторов в последовательностях.
- Моделирование списков. Двунаправленные и циклические списки. Моделирование графов. Деревья.
- Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов.
- Сбалансированные деревья, их свойства. Вставка и удаление элементов.
- Куча
- Замыкание транзитивного бинарного отношения.
- Моделирование многомерных массивов.
- Исключения как средство управления потоком вычислений