Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Московский государственный открытый университет
Кафедра
Информационные системы и измерительные технологии
КУРСОВОЙ ПРОЕКТ
Дисциплина:
Теория вычислительных процессов
Тема:
Сложность вычислений (алгоритмов)
Студент: Блыщак С.Б.
Группа: ПОВТ/с
Москва, 2012 гСодержание
Введение
1. Алгоритмы и их сложность
1.1 Классы сложности задач
1.1.1 Класс P
1.1.2 Класс NP
1.2 Проблема P = NP
1.3 Класс NPC (NP – полные задачи)
2. Основы теории сложности вычислений
2.1 Машина Тьюринга
2.2 Нормальные алгорифмы Маркова
Литература
Введение
С понятием алгоритма были знакомы еще ученые древних цивилизаций. Алгоритм Евклида нахождения наибольшего общегоделителя двух целых чисел был описан в книге VII «Начал» Евклида, датирующейся 330-320 гг. до н.э. Прообраз метода исключения Гаусса был описан в китайском источнике «Девять книг по арифметике» (202 г. до н.э. — 9 г.н.э.). Эратосфен (приблиз. 276–194 гг. до н.э.) предложил алгоритм проверки простоты числа, получивший впоследствии название решета Эратосфена.
Тем не менее, различные формализации понятияалгоритма были предложены только в середине 30-х годов прошлого столетия, когда и стала складываться современная теория алгоритмов. Ее возникновение связано с точным математическим определением такого, казалось бы, интуитивно ясного понятия как алгоритм. Потребность в этом определении была вызвана внутренними тенденциями развития математики, поскольку некоторые открытые проблемы заключались ввыяснении существования (или несуществования) алгоритма для решения конкретных задач. Например, знаменитая 10-я проблема Гильберта заключалась в вопросе о существовании процедуры нахождения целочисленных корней произвольного многочлена от нескольких переменных с целыми коэффициентами.
Именно потенциальная возможность несуществования алгоритмов решения некоторых проблем потребовала формального определенияалгоритма. Почти одновременно в 30-х годах XX века независимо (и в разных формах) рядом крупных математиков того времени — А. Тьюрингом, А. Черчем, Э. Постом, К. Геделем, С. Клини и др. — было формализовано понятие вычислимости.
Э. Пост и А. Тьюринг определили алгоритм как вычисление на абстрактных машинах. При этом вычислимость функции понималась как вычислимость на машинах Тьюринга. К. Гедель, А. Черч и С.Клини определили понятие вычислимости по-другому, на языке введенных ими арифметических функций, которые теперь называются частично рекурсивными функциями. Позднее А.А. Марков ввел понятие нормального алгорифма. Однако выяснилось, что все эти определения, совершенно различные по форме, описывают некое единое математическое понятие — понятие алгоритма.
Доказательство алгоритмической неразрешимостимногих известных задач и получение ряда других отрицательных результатов послужило хорошим стимулом развития классической теории алгоритмов.
По-видимому, не случайно эти исследования непосредственно предшествовали появлению первых компьютеров в 40-х годах прошлого века, поскольку теория алгоритмов явилась теоретическим фундаментом для создания и использования вычислительных машин. В рамкахклассической теории алгоритмов задаются вопросами о разрешимости различных задач, при этом вычислительная сложность алгоритмов принципиально не исследуется. Однако многие дискретные задачи, очевидно, алгоритмически разрешимы с помощью переборных алгоритмов. Такие прямые переборные алгоритмы уже при небольших исходных параметрах вынуждены просматривать огромное (обычно экспоненциальное) число вариантов.
Спрактической же точки зрения часто нет никакой разницы между неразрешимой задачей и задачей, решаемой за экспоненциальное от длины входа время.
В связи с актуальными потребностями в анализе алгоритмов и задач с точки зрения вычислительной сложности с 50-х годов XX века — с момента создания вычислительной техники — начала активно развиваться теория сложности...
Федеральное агентство по образованию
Московский государственный открытый университет
Кафедра
Информационные системы и измерительные технологии
КУРСОВОЙ ПРОЕКТ
Дисциплина:
Теория вычислительных процессов
Тема:
Сложность вычислений (алгоритмов)
Студент: Блыщак С.Б.
Группа: ПОВТ/с
Москва, 2012 гСодержание
Введение
1. Алгоритмы и их сложность
1.1 Классы сложности задач
1.1.1 Класс P
1.1.2 Класс NP
1.2 Проблема P = NP
1.3 Класс NPC (NP – полные задачи)
2. Основы теории сложности вычислений
2.1 Машина Тьюринга
2.2 Нормальные алгорифмы Маркова
Литература
Введение
С понятием алгоритма были знакомы еще ученые древних цивилизаций. Алгоритм Евклида нахождения наибольшего общегоделителя двух целых чисел был описан в книге VII «Начал» Евклида, датирующейся 330-320 гг. до н.э. Прообраз метода исключения Гаусса был описан в китайском источнике «Девять книг по арифметике» (202 г. до н.э. — 9 г.н.э.). Эратосфен (приблиз. 276–194 гг. до н.э.) предложил алгоритм проверки простоты числа, получивший впоследствии название решета Эратосфена.
Тем не менее, различные формализации понятияалгоритма были предложены только в середине 30-х годов прошлого столетия, когда и стала складываться современная теория алгоритмов. Ее возникновение связано с точным математическим определением такого, казалось бы, интуитивно ясного понятия как алгоритм. Потребность в этом определении была вызвана внутренними тенденциями развития математики, поскольку некоторые открытые проблемы заключались ввыяснении существования (или несуществования) алгоритма для решения конкретных задач. Например, знаменитая 10-я проблема Гильберта заключалась в вопросе о существовании процедуры нахождения целочисленных корней произвольного многочлена от нескольких переменных с целыми коэффициентами.
Именно потенциальная возможность несуществования алгоритмов решения некоторых проблем потребовала формального определенияалгоритма. Почти одновременно в 30-х годах XX века независимо (и в разных формах) рядом крупных математиков того времени — А. Тьюрингом, А. Черчем, Э. Постом, К. Геделем, С. Клини и др. — было формализовано понятие вычислимости.
Э. Пост и А. Тьюринг определили алгоритм как вычисление на абстрактных машинах. При этом вычислимость функции понималась как вычислимость на машинах Тьюринга. К. Гедель, А. Черч и С.Клини определили понятие вычислимости по-другому, на языке введенных ими арифметических функций, которые теперь называются частично рекурсивными функциями. Позднее А.А. Марков ввел понятие нормального алгорифма. Однако выяснилось, что все эти определения, совершенно различные по форме, описывают некое единое математическое понятие — понятие алгоритма.
Доказательство алгоритмической неразрешимостимногих известных задач и получение ряда других отрицательных результатов послужило хорошим стимулом развития классической теории алгоритмов.
По-видимому, не случайно эти исследования непосредственно предшествовали появлению первых компьютеров в 40-х годах прошлого века, поскольку теория алгоритмов явилась теоретическим фундаментом для создания и использования вычислительных машин. В рамкахклассической теории алгоритмов задаются вопросами о разрешимости различных задач, при этом вычислительная сложность алгоритмов принципиально не исследуется. Однако многие дискретные задачи, очевидно, алгоритмически разрешимы с помощью переборных алгоритмов. Такие прямые переборные алгоритмы уже при небольших исходных параметрах вынуждены просматривать огромное (обычно экспоненциальное) число вариантов.
Спрактической же точки зрения часто нет никакой разницы между неразрешимой задачей и задачей, решаемой за экспоненциальное от длины входа время.
В связи с актуальными потребностями в анализе алгоритмов и задач с точки зрения вычислительной сложности с 50-х годов XX века — с момента создания вычислительной техники — начала активно развиваться теория сложности...
Поделиться рефератом
Расскажи своим однокурсникам об этом материале и вообще о СкачатьРеферат