Рабочая программа дисциплины «Алгоритмы и анализ сложности»
Скачать 0.5 Mb.
|
| Тема 7. Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. - 2 ЧАСА ЛЕКЦИЙ, 2 ЧАСА ПРАКТИЧЕСКИХ ЗАНЯТИЙ. Запись на предельно упрощенном рефале (запись УА для НА). Программа НА вида x[1] - e[1] y[1] ... x[n] - e[n] y[n] кодируется выражением (((x[1])(e[1])y[1])...((x[n])(e[n])y[n]), где x[i], y[i] - слова в рабочем алфавите алгоритма, e[i]=. или e[i] пусто. Например, алгоритм |*| - * * -. кодируется выражением ((('|*|')()'*')(('*')('.'))) ПрограммаУА для НА на упрощенном рефале: U((p((u)(e)v)q)x u y)=V((e)(p((u)(e)v)q)x v y); U((p)x)=x; V(()z)=U(z); V(('.')(p)x)=x. Машины Джонса. Универсальная машина Джонса Команды МД: x:=E [v:=E] if E1=E2 then S1 else S2 while E1#E2 do S Выражения (E1.E2), nil, x, lE, rE. Тема 8.Программа машины Джонса как структура данных- 2 часа лекций, 2 часа практических занятий. Элементы программы машины Джонса как структуры данных: (':='.E), ('.'.(E1.E2)), ('l'.E), ('r'.E), ('if'.((E1.E2).(S1.S2))), ('nil'.nil) ('while'.((E1.E2).S)). Контрольный вопрос: Напишите программу, выполняющую преобразование (nil.(nil. ... (nil.((E1.E2).E3))...)) в((E1.E2).E3). Тема 9.Разрешимые и неразрешимые множества.Перечислимые и неперечислимые множества- 2 ЧАСА ЛЕКЦИЙ, 2 ЧАСА ПРАКТИЧЕСКИХ ЗАНЯТИЙ. Определение класса разрешимых множеств Множество разрешимо в том и только в том случае, когда его характеристическая функция вычислима. X – характеристическая функция множества M элементов пространства U, если X отображает U в {0,1} и для любого x из U равенство X(x)=1 эквивалентно принадлежности элемента x множеству M. (Примечание: в качестве пространства U можно брать, например, множество натуральных чисел, множество слов в конечном алфавите, множество конечных последовательностей натуральных чисел, множество бинарных конечных деревьев (или n-арных конечных деревьев или конечных упорядоченных деревьев), термов в конечном функциональном базисе и т.д.). Свойства разрешимых множеств - Пустое множество разрешимо. - Пространство U разрешимо. - Любое конечное множество разрешимо. - Пересечение любого конечного числа разрешимых множеств разрешимо. - Объединение любого конечного числа разрешимых множеств разрешимо. - Разность двух разрешимых множеств разрешима. - Пример неразрешимого множества - область определения универсального алгоритма. Определение класса перечислимых множеств Перечислимыми множествами называются области определения вычислимых функций. Свойства класса перечислимых множеств - Класс перечислимых множеств совпадает с классом множеств значений вычислимых функций. - Все разрешимые множества перечислимы. - Пересечение любого конечного числа перечислимых множеств перечислимо. - Объединение любого конечного числа перечислимых множеств перечислимо. - Если дополнение перечислимого множества перечислимо, то это множество разрешимо. - Следствие: дополнение области определения универсального алгоритма не перечислимо. Контрольный вопрос Выделите перечислимые и разрешимые множества среди следующих множеств: 1) множество программ, не применимых к пустому слову, 2) - -, применимых ..., 3) множество (p,n,x), для которых p не останавливается за n шагов на x, 4) - -, - - - останавливается - - - - пустом слове, 5) - (p,n), - - - не останавливается ..., 6) - -, - - - останавливается ..., 7) - программ, не останавливающихся за 1000000 шагов на пустом слове, 8) - -, останавливающихся ..., 9) можно ли определить, выполняется ли когда-либо некоторая команда в программе. Иерархия Клини-Мостовского Тема 10.Элементарные по Кальмару функции - 2 часа лекций, 2 часа практических занятий. Определение, свойства и примеры функций, множеств и отношений, элементарных по Кальмару. Контрольный вопрос Элементарна ли по Кальмару характеристическая функция множества совершенных чисел? Тема 11.Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности - 2 часа лекций, 2 часа практических занятий. Определение, свойства и примеры классов функций, множеств и отношений, основанных на ограниченной рекурсии. Контрольный вопрос Определить с помощью ограниченной рекурсии функцию f(x,y,z) = [x/y**z] Классы функций и предикатов ограниченной вычислительной сложности Если Compl - мера сложности какой-то модели вычислений, а Bounds- класс верхних границ сложности для этой меры сложности, то сложностным классом BoundCompl называется класс множеств, для которых существуют разрешающие алгоритмы на данной модели вычислений удовлетворяющие некоторым границам из Bound для меры сложности Compl. Примеры Compl: - Space - требуемый объем памяти (например в битах), - Time - требуемое время вычисления (например, в тактах процессора), Функции класса Bound, как правило - функции длины записи аргумента вычисляемой (характеристической) функции. Примеры Bound: - Log - логарифмические функции (натуральнозначные приближения, объем памяти, занимаемой аргументом не считается, требуется произвольный (прямой) доступ к элементам аргумента, если так ограничено время), - Lin - линейные функуции, - Poly - многочлены, - Exp - показательные функции. Примеры сложностных классов: - P=PolyTime - PSPACE=PolySpace Известные соотношения между некоторыми сложностными классами (теоремы): - LogSpace - подмножество P (строгость включения неизвестна), - LogSpace - строгое подмножество LinSpace (иерархия), - P не равно LinSpace (детали не известны), - P - строгое подмножество ExpSpace (иерархия), - LinSpace - подмножество ExpTime (строгость включения неизвестна), - LinSpace - строгое подмножество PSPACE (иерархия), - ExpTime - подмножество ExpSpace (строгость включения неизвестна), - ExpTime не равно PSPACE (детали неизвестны), - PSPACE - строгое подмножество ExpSpace (иерархия). Тема 12.Методы оценки сложности вычислений и алгоритмов. Доказуемо трудные задачи. Полные переборные задачи - 2 часа лекций, 2 часа практических занятий. В качестве доказуемо трудных задач рассматриваются задачи установления принадлежности произвольного элемента заданному множеству, то есть задачи вычисления характеристических функций этих множеств. Доказуемая трудность такой задачи есть доказуемая трудность соответствующего множества. Множество называется доказуемо трудным относительно сложностнокласса C, если можно доказать что это множество не принадлежит классу C. Примеры доказуемо трудных задач относительно класса P: - ограниченная арифметика Беннета (арифметика в сигнатуре: - переменные x[i], - 0, 1, - +, *, =, меньше, &, или, - для всех ..., меньших ..., выполнено ... - для некоторых ..., меньших ..., выполнено ...) - ограниченная теория слов в конечном алфавите (теория Смульяна):то же, что и в предыдущем случае, но константы - алфавит, а единственная операция - сцепление слов, вместо "меньше" -"короче"), - теория логических функций (переменные и константы для логических значений и n-местных логических функций, применения функций к формулам, кванторы по логическим значениям и функциям). Полные переборные задачи Классом переборных задач называется класс NP?, определенный ниже. Множество M принадлежит NP, если найдется такое множество M' из класса P и такой многочлен p, что принадлежность произвольного элемента x длины n множеству M эквивалентна существованию такого y длины p(n), что xy принадлежит M'. Пусть A - некоторое множество слов. Вычислительной машиной с оракулом A называется вычислительная машина РАМ с дополнительной командой TEST(A) a, которая проверяет за 1 шаг, принадлежит ли содержимое ячейки a множеству A, помещая результат в виде значения соответствующей характеристической функции в сумматор. Аналог класса P, определенный с помощью такой машины обозначается через P[A]. Если A принадлежит NP и NP=P[A], то A называется NP-полным или полной переборной задачей. Пример полной переборной задачи - множество выполнимых пропозициональных формул. Полные переборные задачи также образуют класс трудных задач. Контрольный вопрос Какова временная сложность (простая и взвешенная) и зонная (лог. взвеш., макс. сумма длин ячеек)вычисления суммы входных чисел. Тема 13.Online-вычисления, вычисления в реальное время - 2 часа лекций, 2 часа практических занятий. Определение, основные свойства и примеры on-line-вычислений и вычислений в реальное время. Контрольный вопрос Написать on-line RAM для нахождения НОК чисел, оценить временную сложность алгоритма (в простом времени). Тема 14.Автоматные вычисления. Регулярные множества - 2 часа лекций, 2 часа практических занятий. Определение и основные свойства конечных автоматов-распознавателей и конечных преобразователей. Автоматы Мили и Мура. Автоматные множества. Определение класса регулярных множеств. Тема 15.Регулярность автоматных и автоматность регулярных множеств - 2 часа лекций, 2 часа практических занятий. Теоремы об автоматности регулярных множеств и регулярности автоматных множеств. Дополнительный вопрос: Классы функций и предикатов, рудиментарные по Р.Смульяну. Тема 16.Связь логики и вычислимости - 2 часа лекций, 2 часа практических занятий. Традиционные конструктивные логические теории. Пример: формальная конструктивная (интуиционистская) арифметика. Вычислительная интерпретация логических формул. Вычислительная интерпретация доказательств. Тема 17.Логический синтез алгоритмов ограниченной вы-числительной сложности. - 2 часа лекций, 2 часа практических занятий. Теории с ограничениями на применение индукции и их приложения в дедуктивно-логическом синтезе алгоритмов ограниченной вычислительной сложности. Практический раздел (к темам теоретического раздела, осуществляется на практических занятиях) Краткое описание технологии занятий. Занятия проводятся с группой под руководством преподавателя и состоят в решении задач по каждой теме и разбором их. Тема 1. Математическая логика и теория алгоритмов Задачи на построение алгоритмов в простейших моделях. Тема 2. Виды алгоритмов Задачи на построение алгоритмов КУ, К-алгоритмов. Тема 3. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины Задачи на построение магазинных автоматов, нормальных алгоритмов и регистровых машин. Тема 4. Равнодоступные адресные машины (РАМ) Задачи на построение РАМ. Тема 5. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции Задачи на построение примитивно рекурсивных, частично рекурсивных и общерекурсивных функций. Тема 6. Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов Задачи на построение примитивно рекурсивных предикатов, множеств и отношений. Тема 7. Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале Задачи на программирование на Упрощённом Рефале. Тема 8. Программа машины Джонса как структура данных Задачи на кодирование программ МД. Тема 9. Разрешимые и неразрешимые множества. Перечислимые и не перечислимые множества Задачи на построение определений разрешимых и перечислимых множеств. Тема 10. Элементарные по Кальмару функции Задачи на построение функций, элементарных по Кальмару. Тема 11. Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности Задачи на построение функций с помощью ограниченной рекурсии. Тема 12. Методы оценки сложности вычислений и алгоритмов. Доказуемо трудные задачи. Полные переборные задачи Задачи на построение оценок сложности алгоритмов. Тема 13. On-line - вычисления, вычисления в реальное время Задачи на программирование вычислений в реальное время. Тема 14. Автоматные вычисления. Регулярные множества Задачи на построение автоматных и регулярных множеств. Тема 15. Регулярность автоматных и автоматность регулярных множеств Задачи на взаимное преобразование регулярных и автоматных определений. Тема 16. Связь логики и вычислимости Задачи на построение конструктивных доказательств с синтезом алгоритмов. Тема 17. Логический синтез алгоритмов ограниченной вычислительной сложности Задачи на дедуктивный синтез алгоритмов контролируемой вычислительной сложности. Задания для лабораторных работ 1. Машина Тьюринга с одной одномерной двусторонней лентой и одной головкой. 2. Машина Тьюринга с одной одномерной односторонней лентой и одной головкой. 3. Машина Тьюринга с двумя двусторонними одномерными лентами по одной головке на каждой ленте. 4. Машина Тьюринга с одной двумерной лентой. 5. Двухмагазинный автомат. 6. Нормальный алгоритм Маркова. 7. К-алгоритм. 8. Равнодоступная адресная машина. 9. Равнодоступная адресная машина с сохраняемой программой. 10. Машина Джонса. 11. Частично-рекурсивные функции. 12. Словарные рекурсивные функции. 13. Рекурсивные функции на бинарных деревьях. 14. Рекурсивные функции на термах. 15. Алгоритм Колмогорова-Успенского на бинарных деревьях. 16. Алгоритм Колмогорова-Успенского на термах. 17. Регистровая (счетчиковая) машина. 18. Машина Тьюринга с лентой в виде бинарного дерева. 19. Двухголовочная машина Тьюринга с лентой в виде бинарного дерева. 20. Машина Минского (счетчиковая машина). Раздел 3. Самостоятельная работа Самостоятельная работа выполняется студентами на компьютерах и состоит в решении задач с помощью специальных учебных программных комплексов. Тематика задач:
Выполненные работы по электронной почте присылаются преподавателю и автоматически проверяются специальными программными средствами (см. ссылки в следующей таблице).
График контроля СРС
Условные обозначения: кр – контрольная работа, к – коллоквиум, р – реферат, д – доклад, ди – деловая игра, рз – решение задач, кур – курсовая работа. Программа самостоятельной работы студента Самостоятельная работа выполняется в виде заданий к соответствующим лабораторным работам. Задания сдаются раз в 2 недели по следующим неделям: Неделя 2. Математическая логика и теория алгоритмов. Виды алгоритмов Неделя 4. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины. Равнодоступные адресные машины (РАМ) Неделя 6. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции. Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов Неделя 8 Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Машины Джонса. Универсальная машина Джонса. Программа машины Джонса как структура данных Неделя 10. Разрешимые и неразрешимые множества. Перечислимые и не перечислимые множества. Элементарные по Кальмару функции Неделя 12. Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности. Методы оценки сложности вычислений и алгоритмов. Доказуемо трудные задачи. Полные переборные задачи Неделя 14. On-line - вычисления, вычисления в реальное время. Автоматные вычисления. Регулярные множества Неделя 16. Регулярность автоматных и автоматность регулярных множеств. Неделя 18. Нетрадиционные конструктивные теории |
Похожие:
 | Радиофизический факультет Дисциплина «Алгоритмы и анализ сложности» относится к дисциплинам базовой части профессионального цикла основной образовательной... |  | Рабочая программа дисциплины «Алгоритмы и процессоры цифровой обработки сигналов» ... |
| Рабочая программа дисциплины «экономический анализ» Рабочая программа предназначена для преподавания общепрофессиональной дисциплины федерального компонента опд. Ф. 06 «Экономический... | | Рабочая программа дисциплины «финансовый анализ» Рабочая программа предназначена для преподавания специальной дисциплины вузовского компонента студентам заочной формы обучения (сокращенный... |
| Рабочая программа Наименование дисциплины Охватывают основные сведения по данной дисциплине. Варианты сбалансированы по сложности и равноценны по трудоемкости | | Рабочая программа дисциплины «инвестиционный анализ» Рабочая программа предназначена для преподавания специальной дисциплины вузовского компонента студентам очной и заочной форм обучения... |
| Реферат по информатике и икт по теме: «Алгоритмы» Я выбрал тему учебно-методического комплекса «Алгоритмы», так как она является одной из главной тем в информатике | | Реферат по информатике и икт по теме: “ Разветвляющиеся алгоритмы” Я выбрал тему: «Разветвляющиеся алгоритмы», потому что они очень часто применяются в алгоритмизации и программировании. Без знания... |
| Программа по формированию навыков безопасного поведения на дорогах... Иметь представление об алгоритмах, свойствах алгоритмов и записи алгоритмов. Приводить примеры алгоритмов из жизни. Применять готовые... | | Урока Тема урока Количество часов «Зарождение и предмет кибернетики», «Компьютер и управление», «Управление и алгоритмы», «Линейные алгоритмы управления без обратной... |
| Рабочая программа дисциплины «Иностранный язык» Рабочая программа предназначена для преподавания дисциплины специальности 080109. 65 "Бухгалтерский учет, анализ и аудит" в 1- 4... | | Рабочая программа дисциплины «Иностранный язык» Рабочая программа предназначена для преподавания дисциплины специальности 080109. 65 "Бухгалтерский учет, анализ и аудит" в 1- 4... |
| Рабочая программа дисциплины «Иностранный язык» Рабочая программа предназначена для преподавания дисциплины специальности 080109. 65 "Бухгалтерский учет, анализ и аудит" в 1- 4... | | Рабочая программа дисциплины «информатика» Рабочая программа предназначена для преподавания общематематической и естественнонаучной дисциплины студентам очной формы обучения... |
| Рабочая программа по дисциплине В. В экономический анализ Целью освоения дисциплины «Экономический анализ» является изучение теоретических основ и приобретение студентами практических навыков... | | Еще с девятого класса мы изучаем алгоритмы. И вот перейдя из десятого... Целью нашей работы является раскрыть, что такое алгоритмы, их виды и назначения, в чем заключается смысл работы с алгоритмом |
