18804
Комментарий:
|
18795
|
Удаления помечены так. | Добавления помечены так. |
Строка 37: | Строка 37: |
* приобретение практического опыта работы на ЭВМ, в системах программирования. | * приобретение практического опыта работы на ЭВМ, в системах программирования. |
Строка 72: | Строка 72: |
1. Программируемый калькулятор: данные, команды, последовательное, условное и циклическое выполнение. | 1. Программируемый калькулятор: данные, команды, последовательное, условное и циклическое выполнение. |
Строка 100: | Строка 100: |
* Есть много вариантов, но у нас уже есть готовое решение: условный переход, ничего придумывать не надо. | * Есть много вариантов, но у нас уже есть готовое решение: условный переход, ничего придумывать не надо. |
Строка 102: | Строка 102: |
1. Алгоритм как преобразование слов из заданного алфавита. Нормальные алгоритмы Маркова. | 1. Алгоритм как преобразование слов из заданного алфавита. Нормальные алгоритмы Маркова. |
Строка 105: | Строка 105: |
1. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов. | 1. Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов. |
Строка 108: | Строка 108: |
1. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм. | 1. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм. |
Строка 120: | Строка 120: |
1. (!) Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке. 1. Стандартные модули. Основные функции стандартных модулей `math`, `random`, `os`, `sys` и т. п. |
1. (!) Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке. 1. Стандартные модули. Основные функции стандартных модулей `math`, `random`, `os`, `sys` и т. п. |
Строка 141: | Строка 141: |
1. (!) Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. | 1. (!) Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. |
Строка 162: | Строка 162: |
Семестровый проект: простейший эмулатор МТ, НАМ, ПК и т.п. | Семестровый проект: простейший эмулятор МТ, НАМ, ПК и т.п. |
Алгоритмы и алгоритмические языки
текст содержит несколько поясняющих комментариев, для их показа надо нажать «Комментарии» в начале или в конце страницы
Аннотация
TODO общее описание
- Цели курса:
- Заложить основы алгоритмического мышления
- Дать эффективный язык описания алгоритмов и структур данных
- Дать универсальный инструмент программирования
- Задачи курса:
- Познакомить с основами теории алгоритмов
- Привить представление об ЭВМ как алгоритмическом исполнителе команд, и о языке программирования как о формальной системе таких команд
- Развить навыки составления алгоритмов и отлаживания программ на языке Python3
- Познакомить с алгоритмами и структурами данных, используемыми при решении типовых задач
Курс состоит из пяти неравных по объёму тематических разделов:
- Введение в теорию алгоритмов. Алгоритмические языки.
- Теоретическая база алгоритмизации и примеры реализующих её формализмов
- Обзор языка программирования и исполнителя Python
- Одно занятие, посвящённое поверхностному знакомству с языком и интерпретатором командной строки
- Основы ЯП Python
- Базовый набор операторов и структур данных, необходимых для того, чтобы составлять и изучать алгоритмы
- Возможности ЯП Python
- Подмножество ЯП, достаточное для эффективного програмирования, семантика работы исполнителя
Алгоритмы и структуры данных.
- Классические алгоритмы и структуры данных, в них используемые
Темы последнего раздела идут не отдельно в конце семестра, а появляются после изучения подходящей конструкции ЯП или приёма программирования. Помечены значком .
Практическую поддержку курсу обеспечивает «Практикум на ЭВМ». Основные цели практикума:
- практическое изучение алгоритмического языка Python;
- приобретение навыков разработки, тестирования и отладки программ для ЭВМ;
- приобретение практического опыта работы на ЭВМ, в системах программирования.
Практикум включает в себя:
- аудиторные семинарские занятия, направленные на закрепление лекционного теоретического материала и разбор дополнительного;
- лабораторные занятия в компьютерном зале, предназначенные для постановки практических навыков и приёмов программирования;
выполнение домашних заданий с обязательной проверкой решений в системе проверки домашних заданий
.
Лекции
примерный почасовой план
Введение в теорию алгоритмов. Алгоритмические языки
- Интуитивное понятие алгоритма: преобразование данных исполнителем на основании команд. Свойства алгоритмов.
- Программируемый калькулятор: данные, команды, последовательное, условное и циклическое выполнение.
- Алгоритм как преобразование слов из заданного алфавита. Нормальные алгоритмы Маркова.
- Машина Тьюринга. Тезис Тьюринга и принцип нормализации, их обоснование.
- Алгоритмически неразрешимые проблемы.
- Неразрешимость проблем самоприменимости, останова и эквивалентности алгоритмов.
…
- Характеристика алгоритмических языков. Понятия исполнителя и трансляции. Компилируемые и интерпретируемые языки.
- Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул (БНФ) и синтаксических диаграмм.
Обзор языка программирования и исполнителя Pyton
- История Python. Интерпретатор командной строки. Использование Python в качестве калькулятора.
- Неформальное введение в Python. Работа со справочным материалом.
Основы ЯП Python
- Константы-конструкторы основных скалярных объектов. Операции над объектами. Интерпретация выражения: конструирование и удаление объектов. Именование объектов, оператор связывания.
- Основные типы последовательностей. Индексирование и секционирование. Множественный оператор связывания, распаковка последовательностей.
- Логические выражения. Условный оператор. Блок операторов. Вложенные операторы.
Оператор цикла с условием. Каноническая схема цикла. Оператор цикла с последовательностью.
- Функции: задание и оператор вызова. Контекст выполнения, глобальное и локальное пространства имён, их перекрытие.
- Оформление кода. Строки документации, комментарии, соглашение об именах. Модернизация языка Python сообществом.
Понятие вычислительной сложности алгоритмов в худшем случае и в среднем. Поиск и бинарный поиск в упорядоченных последовательностях.
Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке.
Стандартные модули. Основные функции стандартных модулей math, random, os, sys и т. п.
- Конструирование пространства имён: модули и классы. Экземпляры классов.
- Интерактивный и файловый ввод-вывод. Параметры командной строки.
Рекурсия. Достоинства, недостатки, критерий применения в Python.
Возможности ЯП Python
- Референция объектов: имена и ссылки из составных объектов. Счётчик ссылок. Идентификаторы объектов и их сравнение.
- Старшинство операций. Логические операции. Нулевой объект типа.
Скалярные типы данных. Что ещё?
Пространство имён объекта: поля и методы объекта.
Методы последовательностей. Использование последовательностей в качестве стека.
Алгоритмы поиска с возвратами (backtracking), реализация их с помощью рекурсии. Замещение рекурсии стеком контекстов.
- Строковые методы. Байтовые массивы.
Z-функция, π-функция и поиск подстроки
- Исключения как средство управления потоком вычислений
Задача хеширования. Открытое и закрытое хеширование. Требования к функции расстановки.
Хешируемые объекты Python. Словари. Методы словарей.
Моделирование многомерных массивов. Модуль array.
- Множества и операции с ними. Циклические конструкторы различных объектов.
- Позиционные и именованные параметры функции, значение по умолчанию. Упаковка и распаковка параметров функции.
- Функции с произвольным количеством и именами параметров. Словари-пространства глобальных и локальных имён.
Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии.
Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов.
- Генераторы: выражения-генераторы, повторно входимые функции (функции-генераторы). Работа цикла с итерируемым объектом.
- Спецметоды. Реализация операций над объектами путём задания спецметодов.
Дополнительные главы
TODO: что ещё должно/может быть: выбрать нужное и подсунуть в нужное место
eval() / exec()
Куча
Замыкание транзитивного бинарного отношения.
- Сериализация и бинарные данные
- Элементы функционального программирования.
- Объектное планирование в разработке программ. ООП.
- Наследование и полиморфизм
- Полезные модули !. Внутреннее устройство исполнителя: байт-код, стек-машина, словари имён и т. п.
Ещё, см., например курс для Московской Биржи
Практикум
TODO
…
Семестровый проект: простейший эмулятор МТ, НАМ, ПК и т.п.