Симферополь, 2004
ПО ДИСЦИПЛИНЕ Теория сложности вычислений
для студентов 2 курса дневной (заочной) и экстернатной
формы обучения
направления 0802 Прикладная математика
специальностей 6.080200 Информатика,
6.080200 Прикладная математика
Составитель:доктор физико-математических наук, профессор Донской В.И. | |
Рассмотрены и рекомендованы на заседании кафедры ……………………………. от «__» _____200_г. (протокол №_) |
Лекция 1. Предмет и задачи теории сложности вычислений
1) Что такое категория сложность и зачем она нужна? Сложность и прикладные проблемы [1,2,3,4,5,6,7,8,9]
Теория вычислимых функций (по сути дела, таких, значения которых при заданных аргументах могут быть найдены при помощи компьютеров, не имеющих ограничений на объем памяти) появилась в 30-хх годах ХХ века, когда компьютеров еще не было. Удалось сформулировать строгое определение вычислимой функции, ставшее базовым понятием для фундаментальных исследований в области дискретной математики и математической логики. Согласно принятой в математике гипотезе, называемой обобщенным тезисом Черча, для вычислимых функций и только для них существуют реализующие их алгоритмы, понимаемые интуитивно как конечные последовательности достаточно простых (элементарных) действий.
|
|
Вычислимые функции, таким образом, понимаются как алгоритмические отображения. Доказана эквивалентность ряда различных форм представления алгоритмических отображений. К таким формам представления (алгоритмическим моделям) относятся машины Тьюринга, нормальные алгоритмы Маркова, класс частично-рекурсивных функций с операциями суперпозиции, примитивной рекурсии и минимизации и некоторые другие. Эквивалентность алгоритмических моделей понимается в том смысле, что всякое алгоритмическое отображение (вычислимая функция) может быть реализовано в одной модели тогда и только тогда, когда оно может быть реализовано и в другой модели.
На основе строгого определения алгоритмических моделей и вычислимых функций удалось получить результаты о существовании функций, которые не могут быть реализованы алгоритмом (невычислимые функции и алгоритмически неразрешимые проблемы). Для развития математики открытие способов доказательства алгоритмической неразрешимости имеет фундаментальное значение. Можно отметить полученное в 1952 г. П. С. Новиковым отрицательное решение классической проблемы тождества для конечно определенных групп, решение в 10-й проблемы Гильберта о разрешимости диофантовых уравнений (1970 г. Ю. В. Матиясевич доказал алгоритмическую неразрешимость этой проблемы).
Выяснилась связь между разрешимостью в исчислениях и существованием алгоритмов вывода теорем; алгоритмический подход к изучению исчислений повлек создание логического программирования и непроцедурных языков.
|
|
С появлением компьютеров алгоритмические методы решения задач стали развиваться еще более стремительно и вызвали появление ряда новых, ярких теоретических направлений в математике. Стало понятно, что различие внутри класса алгоритмически разрешимых проблем между труднорешаемыми (требующими чрезвычайно большого числа шагов вычислений) и решаемыми с использованием приемлемого числа шагов задачами еще более важно для изучения, чем исследования в области алгоритмической разрешимости. Возникла теория сложности решения дискретных задач, основания которой были заложены в работах С. Кука (1971), Р. Карпа (1972) и А.А. Левина (1973)
Только после возникновения этой теории (основанной на понятиях NР- полных и NР- трудных задач) многие математики-исследователи осознали бесперспективность поиска эффективных (существенно отличных от переборных) алгоритмов решения многих важных задач: минимизации дизъюнктивных нормальных форм логических функций, задачи коммивояжера, раскраски графа, существования в заданном конечном графе k -полного подграфа, нахождения корней полиномов над полем GР(2) и многих других. Оказалось, что указанные задачи являются универсальными переборными задачами в том смысле, что эффективное решение хотя бы одной из них повлечет открытие эффективных алгоритмов решения для всех остальных.
В монографии К. Гэри и Д. Джонсона [1] приведен впечатляющий список таких универсальных переборных (NР-полных задач), связанных с теорией графов, математической логикой, алгеброй, дискретной оптимизацией и другими разделами математики.
Изучив теорию NР-полных задач, математик получает на вооружение замечательный аппарат, с помощью которого, приступая и решению новой задачи, во многих случаях можно заранее оценить ее сложность и целесообразность поиска точного алгоритма ее решения за приемлемое число шагов.
2) Алгоритмическая сложность и ее значение в теоретической и прикладной информатике [1,2,3,4,5,6,7,8,9]
Теория NР-полных задач достаточно сложна для понимания, и ее изложение связано с трудностями методического характера. Данное небольшое учебное пособие предназначено для первоначального изучения основ теории сложности, но для освоения материала понадобится знакомство с теорией функций алгебры логики, алгеброй, теорией алгоритмов, элементами теории графов и исследования операций. Поэтому пособие предназначается, прежде всего, для студентов старших курсов и аспирантов математического факультета.
Учитывая важность простых приближенных алгоритмов решения дискретных экстремальных задач и различных эвристических методов, при изучении теории сложности полезно ознакомиться с возможностями алгоритмов «пожирающего» типа (GREEDY). Поэтому в пособии изложены основы теории матроидов и теорема Радо-Эдмондса.
Литература:
1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. – 416 с.
2. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. – 536 с.
3. Грэхем Р., Кнут Д., Паташник О. Конкретная математика (основание информатики). М.: Мир, 1998. – 703 с.
4. Донской В. И. Дискретная математика. –Симферополь: Сонат, 2000. –356 с.
5. Липский В. Комбинаторика для программистов. М.: Мир, 1988. – 215 с.
6. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физико-математическая литература, 1995. – 256 с
7. Линдон Р. Заметки по логике. М.: Мир, 1968. – 128 с.
8. Оре О. Теория графов. М.: Наука, 1980. – 336 с.
9. Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980. – 400 с.