Слайды лекций - 2014 (лектор - Белеванцев А. А.)

Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Содержание1. Вводная лекция. Цели и задачи курса. Характеристика разделов курса – введениев алгоритмы, язык программирования, структуры данных. Алгоритмы. Формализацияпонятия алгоритма.2. Машина Тьюринга (МТ). Примеры МТ. Нормальные МТ. Диаграммы Тьюринга: диаграммыэлементарных МТ, правила композиции диаграмм, примеры диаграмм.3. Диаграммы Тьюринга: построение таблицы МТ по диаграмме. Построение языка описанияМТ. Моделирование МТ. Универсальная МТ. Проблемы останова и самоприменимости.4. Нормальные алгоритмы Маркова. Примеры других алгоритмических систем. Основнаягипотеза теории алгоритмов. Тезис Тьюринга-Черча. Общая классификация ихарактеристики языков программирования. Место языка Си в современной индустрии ПО.Стандарты и роль стандартизации.

Язык программирования Си. Первая программа на Си.5. Описание Си-машины: процессор, классы памяти (регистровые, автоматические истатические переменные), структура программного файла. Системные библиотеки и ихиспользование.Типы данных языка Си: целые, логические, символьные, с плавающейточкой, беззнаковые целые.6. Арифметические и логические выражения. Старшинство операций. Операции присваивания.Форматный ввод-вывод. Приведение типов при вычислении выражений (явное и неявное).Операторы.

Символьный тип и обработка символьных данных.7. Массивы. Многомерные массивы. Строки. Обработка строк. Системная библиотека работысо строками.Содержание8. Указатели. Адресная арифметика. Массивы и указатели. Функции. Определение иобъявление функции. Передача параметров. Рекурсия. Хвостовая рекурсия.9. Представление данных с плавающей точкой. Стандарт IEEE 754. Вычисление сумм ипроизведений данных с плавающей точкой. Потеря точности при вычитании. Выборправильной последовательности вычислений.10. Побитовая обработка данных. Беззнаковые целые типы. Абстрактный тип данных«множество» и его реализация. Структуры.

Указатели на структуры.11. Составные инициализаторы структур. Объединения. Анонимные объединения и структуры.Битовые поля. Перечисления.12. Динамическое выделение и освобождение памяти. VLA-массивы и их выделение вдинамической памяти. Массив переменного размера в составе структуры.13. Схема компиляции программ на языке Си. Препроцессор. Директивы препроцессора.Компоновка. Классы памяти и компоновки. Отладка программ. Понятие об отладчике gdb.14. Организация типа данных «стек» на динамической памяти.

Использование стека дляпостроения обратной польской записи. Очередь.15. Алгоритм топологической сортировки Вирта.16. Алгоритм топологической сортировки Вирта (окончание). Понятие о сложностиалгоритмов. Сортировка.17. Простейшие алгоритмы сортировки. Оценка сложности алгоритмов сортировки.Быстрая сортировка.18. Поиск подстроки по образцу. Простейший алгоритм. Алгоритм Кнута – Морриса – Пратта(КМП). Префикс-функция и ее вычисление. Сложность вычисления префикс-функции иалгоритма КМП.19. Двоичные деревья. Обход двоичного дерева (сначала в глубину, сначала в ширину).Нерекурсивный обход двоичного дерева.

«Прошитое» двоичное дерево и его обход.Содержание20. Двоичные деревья поиска и операции над ними (поиск элемента, минимальный имаксимальный элементы, следующий элемент, вставка и удаление элемента). ДеревьяФибоначчи. Оценка высоты дерева Фибоначчи. АВЛ-деревья. Базовые операции над АВЛдеревьями. Балансировка АВЛ-дерева. Вставка и удаление элемента в/из АВЛ-дерева.Оценка высоты АВЛ-дерева по дереву Фибоначчи.21. Красно-черные деревья. Структура данных «куча» (heap) и сортировка heapsort(пирамидальная сортировка).22.

Хеш-таблицы. Хеширование. Хеширование цепочками. Хеширование с открытой адресацией.23. Цифровой поиск. Задача цифрового поиска. Деревья цифрового поиска. Вставка в деревоцифрового поиска.Самоперестраивающиеся деревья (splay trees). Операция splay (перестраивание).Реализация словарных операций через операцию splay. Реализация операции splay.Сложность словарных операций в splay-деревьях.Обобщение сбалансированных деревьев поиска: ранговые деревья, понятие ранга иранговой разницы. Ранговые правила для АВЛ-деревьев и красно-черных деревьев.Слабые АВЛ-деревья.Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекции 1-2Курс «Алгоритмы и алгоритмические языки»ЛекторБелеванцев Андрей Андреевичкафедра СПЛекции 2 раза в неделю: среда/суббота, 8.45Практические и лабораторные занятия 2 раза в неделюСтруктура курса:Элементы теории алгоритмовЯзык СиАлгоритмы и структуры данныхВ конце курса зачет с оценкой и письменный экзамен2Курс «Алгоритмы и алгоритмические языки»Сайт курса: http://algcourse.cs.msu.su/Новости и объявленияМатериалы лекцийВопросы к экзаменуРекомендуемая литератураСреда разработки программ и опции компилятораСтиль кодированияПрактические и лабораторные занятияКонтрольные и коллоквиумы(по лекциям - 2, по семинарам - 3)Анкета студента: заполните и верните лектору3Курс «Алгоритмы и алгоритмические языки»Рекомендуемая литература:По алгоритмам и машинам Тьюринга1.Г.

Эббинхауз, К. Якобс, Ф. Манн, Г. Хермес.Машины Тьюринга и рекурсивные функции. «Мир», М. – 19722.М.Минский. Вычисления и автоматы. «Мир», М. – 1971По языку Си1.Б. Керниган, Д. Ритчи. Язык программирования Си.Издание 2-е, «Вильямс» – 20132.Стандарт языка Си С99 + TC{1,2,3}http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf3.Stephen Prata. C Primer Plus. Fifth Edition. Sams Publishing 2004.http://www.9wy.net/onlinebook/CPrimerPlus5/main.html4.Г. Шилдт.

Полный справочник по Си. Издание 4-е, «Вильямс» – 2010По алгоритмам и структурам данных1.Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы.Построение и анализ. Издание 2-е, «Вильямс» – 20112.Harry R. Lewis, Larry Denenberg. Data Structures andTheir Algorithms.

HarperCollins, 1991.4Курс «Алгоритмы и алгоритмические языки»Методические пособия:1.А.А. Белеванцев, С.С. Гайсарян, Л.С. Корухова,Е.А. Кузьменкова, В.С. Махнычев.Семинары по курсу “Алгоритмы и алгоритмические языки”(учебно-методическое пособие для студентов 1 курса).М., 2012: Изд. отдел ф-та ВМК МГУ имени М.В. Ломоносова.2.А.А. Белеванцев, С.С. Гайсарян, В.П.

Иванников,Л.С. Корухова, В.А. Падарян. Задачи экзаменов по вводному курсупрограммирования (учебно-методическое пособие).М., 2012: Изд. отдел ф-та ВМК МГУ имени М.В. Ломоносова.3.К.А. Батузов, А.А. Белеванцев, Р.А. Жуйков, А.О. Кудрявцев,В.А. Падарян, М.А. Соловьев. Практические задачи по вводному курсупрограммирования (методическое пособие).М., 2012: Изд. отдел ф-та ВМК МГУ имени М.В. Ломоносова.5Неформальное (интуитивное) определение алгоритма.Под алгоритмом (или эффективной процедурой) вматематике понимаютточное предписание, задающее вычислительныйпроцесс, ведущий от начальных данных, которыемогут варьироваться, к искомому результату.Алгоритм должен обладать следующими свойствами:(1)Конечность (результативность). Алгоритм должензаканчиваться за конечное (хотя и не ограниченное сверху)число шагов.(2)Определенность (детерминированность). Каждый шагалгоритма и переход от шага к шагу должны быть точноопределены и каждое применение алгоритма к одним и тем жеисходным данным должно приводить к одинаковому результату.6Неформальное (интуитивное) определение алгоритма.Под алгоритмом (или эффективной процедурой) вматематике понимаютточное предписание, задающее вычислительныйпроцесс, ведущий от начальных данных, которыемогут варьироваться, к искомому результату.Алгоритм должен обладать следующими свойствами:(3)Простота и понятность.

Каждый шаг алгоритмадолжен быть четко и ясно определен, чтобы выполнениеалгоритма можно было «поручить» любому исполнителю(человеку или механическому устройству).(4)Массовость. Алгоритм задает процесс вычисления длямножества исходных данных (чисел, строк букв и т.п.), онпредставляет общий метод решения класса задач.7Неформальное (интуитивное) определение алгоритма.Пример: Алгоритм Евклида нахождения наибольшего общегоделителя двух целых положительных чисел НОД(а, b)(в геометрической форме это алгоритм нахождения общей меры двухотрезков).Даны два целых числа а и b.Выполнить следующие шаги:(0)Если а < b, то поменять их местами.Разделить нацело а на b; получить остаток r.(1)(2)Если r = 0, то НОД(а, b) = b(3)Если r ≠ 0, заменить: а на b, b на r и вернуться к шагу (1).8Почему необходимо формальное определение алгоритма.Не имея такого определения, невозможно доказать, чтозадача алгоритмически неразрешима, т.е.

алгоритм еерешения никогда не удастся построить.Тезис Тьюринга – Черча. Для любой интуитивно вычислимойфункции существует вычисляющая её значения машинаТьюринга.Тезис Тьюринга – Черча невозможно строго доказать или опровергнуть, так какон устанавливает эквивалентность между строго формализованным понятиемчастично вычислимой функции и неформальным понятием вычислимости.9Формализация понятия алгоритмаАлфавиты и отображения.Алфавит Ap = {a1, a2, …, ap}.Символы aiСлова ai ai ...ai12mПустое словоεМножество всех слов над алфавитом ApA*p = {ε }∪ Ap ∪ A2p ∪ ...

∪ Amp ∪ ... =∞mA pm =0Длина слова w обозначается |w|, в частности |ε | = 010Формализация понятия алгоритмаКодированиеДля любой пары алфавитов A и Bсуществует простой алгоритм, определяющийвзаимно-однозначное отображение.Утверждение.Кодирование позволяет ограничитьсяодним алфавитом.

Обычно рассматриваютсяA1 или A2.Следствие.11Формализация понятия алгоритмаОбработка информации.Задача обработки информации – это задачапостроения частичного отображения (функции)F : A* → A*Утверждение. Существуетвзаимно-однозначноеотображение (функция) # : A* → N , гдеN – множество целых неотрицательных чисел,которое любому слову w ∈ A* ставит в соответствиеего номер n ∈ N.12Формализация понятия алгоритмаОбработка информации.A*FA*#-1#NfNТаким образом:(1) Каждый алгоритм определяет частичновычислимую функцию;(2) Каждая частично вычислимая функцияопределяет алгоритм.13Машина Тьюринга (МТ)Вычислимость по ТьюрингуМашина-автомат: предъявляется исходное словоw ∈ A*, в результате обработки получаетсяслово v = F(w).Каждая частичная функция F, для которой можнопостроить МТ, называется вычислимой поТьюрингу.14Машина Тьюринга (МТ)Алфавит состояний Q = {q0, q1, q2, …, qn}Рабочий алфавит S = A ∪ A':A – алфавит входных символов,A' – алфавит вспомогательных символов (маркеров).Лента, размеченная на ячейки (пустая ячейка - Λ)Управляющая головка (УГ)Рабочая ячейка (РЯ)Начальное состояние q0, состояние останова qs.Начальные данные – слова из A*.15Машина Тьюринга (МТ)...ΛΛΛ0010111001011100000ΛΛΛΛΛΛ...qКонфигурация МТ: 〈n, F, q〉, где F: Z → SТакт работы МТ:〈состояние, символ〉 → 〈состояние, символ, направление〉16Машина Тьюринга (МТ)Пример.

Проверка правильности скобочных выражений:МТ должна записать на ленту для правильного скобочного выражениярезультат 1 (для неправильного 0) и остановиться.Правильное скобочное выражение:(1) число открывающих скобок равно числузакрывающих,(2) каждая открывающая скобка предшествуетпарной ей закрывающей скобке.(( ))( ) – правильное скобочное выражение)( или (( ) – неправильные скобочные выражения17Машина Тьюринга (МТ)Пример.