C.Ю.Соловьев

Объявление
Консультация по курсу "Алгоритмы и алгоритмические языки"
для студентов 2 потока состоится 16 января 2018 г. в 14:00,
аудитория П-6.

Методические материалы
по курсу
"Алгоритмы и алгоритмические языки"

1. Программа курса
2. Программирование в машинных кодах
3. Примеры-1
4. Примеры-2
5. Пример "большой" программы
6. Нисходящее программирование
7. Ссылочные типы
 8. Структуры данных
 9. Очереди и стеки
10. Деревья поиска
11. AVL-деревья
12. Таблицы
13. Хеш-таблицы
14. Динамические страницы
•  Учебно-методический комплекс "Алгоритмы и алгоритмические языки"
•  Методические материалы М.О.Проскурни
Хорошая толстая книга:
Круз Р. Структуры данных и проектирование программ.
- М.: БИНОМ. Лаборатория знаний, 2008. - 765с.

Программа курса


Лекция 1. АЛГОРИТМЫ
1. Вводная часть
2. Интуитивное определение алгоритмов (понятие алгоритма, примеры алгоритмов, свойства алгоритмов)
3. Неформальные способы записи алгоритмов (словесная запись, блок-схемы)
4. Необходимость и способы уточнения понятия алгоритма (символы и слова )

Лекция 2. МАШИНА ТЬЮРИНГА
1. Машина Тьюринга (структура, такт работы, запись программы, правила выполнения программы, применимость и неприменимость алгоритма к слову, соглашения для сокращения записи программы)
2. Возможности МТ (композиция, разветвление и повторение МТ)
3. Тезис Тьюринга

Лекция 3. НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА
1. Нормальные алгоритмы Маркова (операция подстановки и формулы подстановки, запись НАМ, два вида стрелок, правила выполнения, тезис Маркова)
2. Алгоритмически неразрешимые проблемы (определение алгоритмически разрешимых и неразрешимых задач, понятия записи алгоритма и самоприменимости, теорема об алгоритмической неразрешимости проблемы самоприменимости)

Лекция 4. МОДЕЛЬНАЯ ЭВМ
1. Структура ЭВМ (схема, устройства ввода и вывода, внутренняя и внешняя память, центральный процессор)
2. Оперативная память (ячейки, адреса ячеек, размер ячеек)
3. Машинное представление данных (представление целых чисел и вещественных чисел, о точности представления целых и вещественных чисел, представление символьной информации)
4. Машинная программа (смысл и формат трехадресных команд, система команд
5. Пример машинной программы

Лекция 5. АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ. МЕТАЯЗЫКИ
1. Об алгоритмических языках (достоинства и недостатки машинного языка, алгоритмические языки высокого уровня и их достоинства, разнообразие АЯ, трансляция с АЯ)
2. Металингвистические формулы (БНФ) (основные понятия БНФ, рекурсивные формулы, расширение БНФ)
3. Синтаксические диаграммы (правила перевода БНФ --> синтаксические диаграммы)
4. Запись целых и вещественных чисел в Паскале

Лекция 6. ЯЗЫК ПАСКАЛЬ. ЧИСЛОВЫЕ ТИПЫ
1. Алфавит, идентификаторы (синтаксис и назначение идентификаторов, служебные слова, стандартные имена и просто имена)
2. Типы данных. Переменные (перечень всех типов данных Паскаля, стандартные типы; переменные и типы данных, контроль за использованием переменных; синтаксис раздела переменных)
3. Числовые типы данных
   3.1 Целый тип (запись целых чисел, описание переменных целого типа, операции над целыми числами, стандартные функции для целых чисел, maxint)
   3.2 Вещественный тип (запись вещественных чисел, описание вещественных переменных, операции и стандартные функции для вещественных чисел)
   3.3 Арифметические выражения (тип выражения, тип результата, правила записи арифметических выражений, правила вычисления выражений и определения их типа)
4. Оператор присваивания (синтаксис, семантика и прагматика оператора присваивания)

Лекция 7. ЛОГИЧЕСКИЙ И СИМВОЛЬНЫЙ ТИПЫ
1. Логический (булевский) тип (высказывания в логике, запись условий в виде высказываний, простые логические выражения: константы, переменные и их описание, отношения, стандартные функции odd, succ и pred); логические операции (not, and, or) и их свойства; логические выражения (синтаксис "на пальцах") и правила их вычисления; оператор присваивания)
2. Символьный тип (запись символов, набор символов и их упорядоченности, описание переменных, операции, стандартные функции (ord, chr, succ, pred), символьные выражения, оператор присваивания)
3. Процедуры ввода (процедура read: синтаксис и семантика, допустимые типы параметров ввода, буфер ввода и возможность досрочного ввода, readln)

Лекция 8. ПРОГРАММА. ОПЕРАТОРЫ
1. Процедуры вывода (процедура write, три формы параметра вывода: e, e:n, e:n:m, вывод целых, логических и символьных данных, особенности вывода вещественных чисел, процедура writeln)
2. Паскаль-программа (структура программы, синтаксис и назначение заголовка, раздела описаний и раздела операторов, правила выполнения программы, правила расстановки пробелов и перевода строк)
3. Операторы (классификация всех операторов: пустой оператор, составной оператор, условный оператор, оператор перехода, метки, раздел меток)

Лекция 9. ОПЕРАТОР ЦИКЛА. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
1. Оператор цикла: с предусловием (while), с постусловием (repeat), с параметром (for), ограничения на for-цикл
2. Как сделать программу понятной: комментарии структурная запись программы, структурное программирование

Лекция 10. ПЕРЕЧИСЛИМЫЕ И ОГРАНИЧЕННЫЕ ТИПЫ
1. Константы (их отличие от переменных, раздел описания констант, стандартные константы: maxint, true, false)
2. Раздел типов (раздел описания типов, переименование типов, два варианта описания переменных нестандартных типов: с заданием имени для нового типа или с использованием безымянного типа)
3. Перечислимые типы (конструктор ПТ, нумерация и упорядоченность имен в ПТ, стандартные функции и операции для ПТ: ord, succ, pred, сравнение, присваивание, for-цикл) 3
4. Оператор варианта (синтаксис и семантика оператора case)
5. Ограниченные типы (особенности присваивание переменным ОТ, отличие этих переменных от переменных базового типа)

Лекция 11. РЕГУЛЯРНЫЕ ТИПЫ (МАССИВЫ)
1. Простые массивы (перечень сложных типов Паскаля; понятие массива, переменных с индексами, отличие x1 от x[1], описание регулярных типов (РТ), присваивание массивов, об именной идентичности РТ)
2. Упакованные массивы
3. Многомерные массивы (матрицы = массив массивов, доступ к строкам и элементам матриц, возможное сокращение описания).
4. Строки (определение, тип строки, строки-константы, сравнение строк равной длины, вывод строк)

Лекция 12. ПРОЦЕДУРЫ
1. Назначение процедур (формальные и фактические параметры, параметры-значения и параметры-переменные)
2. Описание процедур (синтаксис, назначение заголовка и тела, возможные сокращения в описании формальных параметров)
3. Принцип локализации (понятие о вложенных блоках и области видимости имени/метки; принцип локализации, глобальные и локальные имена процедуры)
4. Оператор процедуры (синтаксис)

Лекция 13. ФУНКЦИИ
1. Передача параметров по значению и по ссылке
2. Функции (отличие функций от процедур, синтаксис описания функции и указателя функции)
3. Побочные эффекты функций

Лекция 14. РЕКУРСИВНЫЕ ФУНКЦИИ
1. Рекурсивные функции и процедуры (особенности вычисления рекурсивных функций и их описания, рекурсия и циклы предварительные описания)
2. Алгоритмы поиска (перебора) с возвратами и их рекурсивная реализация
3. Параметры-функции и параметры-процедуры

Лекция 15. КОМБИНИРОВАННЫЕ И МНОЖЕСТВЕННЫЕ ТИПЫ
1. Комбинированные типы (отличие записей от массивов, описание КТ и переменных-записей, присваивание записей, обозначение поля)
2. Оператор присоединения (простейший и общий вариант оператора, конфликт имен)
3. Множественные типы (особенности множеств в Паскале: конечность, однотипность, описание МТ и переменных-множеств, оператор присваивания для множеств, операции над множествами: отношения, объединение, пересечение, разность)

Лекция 16. ФАЙЛОВЫЕ ТИПЫ
1. Файлы (базовый тип, маркер, буферная переменная, отличие от массивов, описание ФТ и переменных-файлов, запрет присваивания файлов, режимы работы с файлами, операции в режиме чтения: reset, eof, get, read и в режиме записи: rewrite, put, write)
2. Текстовые файлы (стандартный тип text, деление текстов на строки, понятие "конец строки", операции для работы со строками: eoln, readln, writeln)
3. Внутренние и внешние файлы

Лекция 17. ПРОГРАММИРОВАНИЕ СВЕРХУ ВНИЗ. ТЕСТИРОВАНИЕ. ОТЛАДКА
1. Программирование сверху вниз (достоинства и недостатки)
2. Тестирование (правильная программа, понятие теста и тестирования программы, цель тестирования, методы тестирования)
3. Отладка

Лекция 18. ССЫЛОЧНЫЕ ТИПЫ. СПИСКИ
1. Ссылочные типы (понятие ссылки и динамической переменной, графическое изображение ссылок, описание ссылочных типов и ссылочных переменных, пустая ссылка nil, операции над ссылками)
2. Динамические структуры данных
3. Списки (графическое изображение, описание типа списоков, проблема косвенной рекурсии в описании типов,)

Лекция 19. СТЕК. ОЧЕРЕДЬ
1. Варианты списков (однонаправленные списки без заглавного и с заглавным звеном, циклические списки, двунаправленные списки): достоинства и недостатки
2. Стек (определение, векторное представление стека и реализация операций, списковое представление и реализация операций)
3. Очередь (определение, списковое представление и реализация операций векторное представление и реализация операций)

Лекция 20. ДВОИЧНЫЕ (БИНАРНЫЕ) ДЕРЕВЬЯ
1. Определение, представление (понятия вершины, ветви, корня, листьев двоичные деревья и их описание в Паскале)
2. Просмотр дерева
3. Деревья поиска (сравнений) (определение, реализация операций построения дерева по заданной последовательности элементов, поиск, вставка и удаление)

Лекция 21. ПОСЛЕДОВАТЕЛЬНЫЕ ТАБЛИЦЫ
1. Таблицы (= набор записей + операция поиска по ключу)
2. Оценка сложности алгоритмов (оценка в худшем случае и в среднем; оптимальный алгоритм поиска и его оценка в худшем случае)
3. Последовательные таблицы (неупорядоченные таблицы, поиск и вставка, оценки сложности) (упорядоченные таблицы, бинарный поиск и вставка, оценки сложности)
4. Сортировка: постановка задачи, наилучшие оценки методов сортировки по числу сравнений и перестановок

Лекция 22. ТАБЛИЦЫ-ДЕРЕВЬЯ
1. Таблицы-деревья (оценки сложности для поиска и вставки, выровненные деревья)
2. АВЛ-деревья (понятия уровня вершины и высоты (глубины) дерева, определение АВЛ-дерева, дерева и высотой дерева Фибоначчи, алгоритм вставки в АВЛ-дерево)

Лекция 23. ПЕРЕМЕШАННЫЕ ТАБЛИЦЫ (ХЭШ-ТАБЛИЦЫ)
1. Основная идея (ключ --> адрес, функция расстановки (ФР), вставка в таблицу с учетом ФР)
2. Закрытое хеширование (метод линейных проб) (основной принцип, первичная и вторичная ФР, реализация операций вставки и поиска)
3. Открытое хеширование (метод цепочек) (основная идея, операции поиска и вставки, оценки)
4. Функции расстановки
5. Программирование динамических страниц в сети Интернет.

Вопросы?