Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979)
Текст из файла
Курс «Алгоритмы и алгоритмические языки»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Машина Тьюринга (МТ)Пример.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
