Тема 0: Введение

Симферополь, 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 с.