01 (1106238)
Текст из файла
Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 1Курс «Алгоритмы и алгоритмические языки»ЛекторыГайсарян Сергей СуреновичБелеванцев Андрей АндреевичЛекции 2 раза в неделю: среда/суббота, 8.45Практические и лабораторные занятия 2 раза в неделюСтруктура курса:Элементы теории алгоритмовЯзык СиАлгоритмы и структуры данныхВ конце курса зачет с оценкой и письменный экзамен2Курс «Алгоритмы и алгоритмические языки»Сайт курса: http://algcourse.cs.msu.su/Новости и объявленияМатериалы лекцийВопросы к экзаменуРекомендуемая литератураСреда разработки программ и опции компилятораСтиль кодированияПрактические и лабораторные занятияКонтрольные и коллоквиумы(по лекциям - 2, по семинарам - 3)Анкета студента: заполните и верните лектору3Курс «Алгоритмы и алгоритмические языки»Рекомендуемая литература:По алгоритмам и машинам Тьюринга1.Г.
Эббинхауз, К. Якобс, Ф. Манн, Г. Хермес.Машины Тьюринга и рекурсивные функции. «Мир», М. – 19722.М.Минский. Вычисления и автоматы. «Мир», М. – 1971По языку Си1.Б. Керниган, Д. Ритчи. Язык программирования Си.Издание 2-е, «Вильямс» – 20102.Г. Шилдт. Полный справочник по Си.Издание 4-е, «Вильямс» – 20103.Стандарт языка Си С99 + TC{1,2,3}http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf4.Stephen Prata. C Primer Plus. Fifth Edition. Sams Publishing 2004.http://www.9wy.net/onlinebook/CPrimerPlus5/main.htmlПо алгоритмам и структурам данныхТ.
Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн.Алгоритмы. Построение и анализ. Издание 2-е, «Вильямс» – 20114Курс «Алгоритмы и алгоритмические языки»Методические пособия: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Машина Тьюринга (МТ)Пример. Проверка правильности скобочных выражений:МТ должна записать на ленту для правильного скобочного выражениярезультат 1 (для неправильного 0) и остановиться.Рабочий алфавит: S = {(, ), 0, 1} ∪ {Λ, X} (X – маркер)Алфавит состояний Q = {q0, q1, q2, q3, qs}:q0 – начальное состояние МТ: поиск закрывающей скобки;qs – состояние останова;q1 – поиск парной открывающей скобки;q2 – стирание маркеров, запись результата 1 и переход в qs;q3 – стирание маркеров, запись результата 0 и переход в qs.В начальном состоянии УГ обозревает самый левыйсимвол входного слова18Машина Тьюринга (МТ)Пример.
Проверка правильности скобочных выражений:МТ должна записать на ленту для правильного скобочного выражениярезультат 1 (для неправильного 0) и остановиться.Программаq0, ( → q0, (, R;q0, ) → q1, X, L;q0, X → q0, X, R;q0, Λ → q2, Λ, L;q1, ( → q0, X, R;q1, ) → q1, ), L;q1, X → q1, X, L;q1, Λ → q3, Λ, R;q2, ( → q3, Λ, L;q2, ) невозможна;q2, X → q2, Λ, L;q2, Λ → qs, 1, H;q3, ( → q3, Λ, R;q3, ) невозможна;q3, X → q3, Λ, R;q3, Λ → qs, 0, H;19Машина Тьюринга (МТ)Пример.
Проверка правильности скобочных выражений:МТ должна записать на ленту для правильного скобочного выражениярезультат 1 (для неправильного 0) и остановиться.Программа (другой способ записи)qi ↓ \ sj →q0q1q2q3(q0, (, Rq0, X, Rq3, Λ, Lq3, Λ, R)q1, X, Lq1, ), L——XΛq0, X, R q2, Λ, Lq1, X, L q3, Λ, Rq2, Λ, L qs, 1, Hq3, Λ, R qs, 0, H20.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
