авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 ||

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ...»

-- [ Страница 3 ] --

8.1. Алгоритмически неразрешимые проблемы. Задачи о нахождении алгоритмов для вычисления функций (предикатов) называют алгоритмическими проблемами. Если нет алгоритмов для вычисления некоторых функций, то говорят, что соответствующая проблема алгоритмически неразрешима. Актуален вопрос: «Существует ли МТ, решающая любую массовую проблему?». Установлено, что существует класс задач, которые являются невычислимыми по Тьюрингу.

1) Неразрешимая проблема распознавания выводимости в математической логике (пример Черча, 1936 г.).

В математической логике актуальна задача: по любым двум формулам A и B найти логический вывод формулы B из формулы A. Такой вывод – цепочка формул, каждая из которых есть аксиома, гипотеза A или непосредственное следствие по одному из правил вывода из предыдущих формул цепочки.

Проблема: Существует ли алгоритм, однозначно определяющий эту цепочку для любых двух формул?

Теорема Черча. Проблема распознавания выводимости алгоритмически неразрешима (т.к. бесконечен перебор вариантов всех возможных цепочек вывода).

2) Неразрешимая проблема распознавания самоприменимости машины Тьюринга.

Машина Тьюринга называется самоприменимой, если она применима к слову, являющемуся ее программой, закодированному во внешнем алфавите.

Проблема: Существует ли такая МТ, которая умеет распознавать самоприменимость любой другой МТ Теорема. Проблема распознавания самоприменимости машины Тьюринга алгоритмически неразрешима.

3) Проблема остановки. Проблема, возникающая после запуска МТ, когда могут возникнуть две ситуации: машина может остановиться через конечное число шагов или будет работать бесконечно.

Доказано, что проблема остановки МТ алгоритмически неразрешима.

Т.о., отвечая на вопрос «Что такое алгоритм?», можно дать простой ответ:

«Алгоритм- это машина Тьюринга».

Говорят, что существует Тьюрингов алгоритм решения класса задач Z, если существует такая МТ с внешним алфавитом A, такая что:

1) для условия любой задачи z Z существует слово u z над A, кодирующее условие задачи z ( дающее его запись на ленте машины);

2) машина T применима к слову u z ;

3) u z u z является словом, кодирующим ответ задачи z.

Сама работа машины над словом u z называется применением алгоритма, заданного машиной, к задаче z.

Класс задач Z, для которого существует решающий его алгоритм Тьюринга, называется алгоритмически разрешимой по Тьюрингу проблемой Z.

Так, разрешимы по Тьюрингу проблемами являются, например, проблема сложения натуральных чисел, проблема удвоения натурального числа.

8.2. Меры сложности алгоритмов. В общей теории алгоритмов изучается лишь принципиальная возможность алгоритмического решения задачи. При решении задач бывает важно оценить число элементарных операций или время, необходимое компьютеру для выполнения всего алгоритма. Порой возникает необходимость учитывать не только временные ресурсы, но и точность вычислений, объем входных данных, возможности памяти, т.е. результативность работы алгоритма. Однако принципиальная разрешимость не означает, что решение задачи уже получено. Поэтому с практической точки зрения важно определить (уточнить) понятие алгоритмической разрешимости.

Выбор алгоритмической модели, реализующей алгоритмы, существенно влияет на сложность задачи. В теории алгоритмов вычислительные ресурсы есть временные или пространственные характеристики процесса вычисления (абстрактные или конкретные).

Сложность S алгоритма решения задачи называется функция f, ставящая в соответствие каждому числу n максимальное время f(n) работы алгоритма по всем входным словам заданной задачи, имеющим длину n. Сложность алгоритма есть число шагов (элементарных действий), необходимых для получения окончательного результата.

Т.о., сложность это трудоемкость решения, измеренная в терминах некоторого ресурса.

Анализ эффективности алгоритма заключается в поиске ответа на вопрос о том, насколько быстро растет функция f(n) с ростом n.

Пусть область определения функций f и g – множество целых положительных чисел, а множество их значений – множество действительных чисел. Говорят, что функция f имеет асимптотический порядок функции g, если существует положительное число k и целое число m, такие, что |f (n)| k|g(n)| для всех nm. Это записывается: f = О(g) и читается «f – порядка О-большого от g».

Если k1, то g мажорирует функцию f или «функция f ограничена функцией g».

Смысл введения такого сравнения заключается в том, чтобы оценить (с точностью до постоянного множителя) скорость роста функции f сложного вида функцией простого вида g. Например:

n – при больших n f (n) имеет порядок O( ln n) ;

i 1 i – пусть n – неотрицательное целое число, т.к. n 2n, то n=О(2n).

Например, трудоемкость О(1) означает, что время работы соответствующего алгоритма не зависит от длины входящего слова.

Алгоритм с трудоемкостью О(n) называется линейным. Линейный алгоритм ограниченное константой число раз просматривает входную информацию и для подавляющего числа практических задач является неулучшаемым по порядку. Поэтому алгоритмическое решение некоторой массовой задачи чаще всего заканчивается отысканием линейного алгоритма (если он существует).

Алгоритм, сложность которого равна О(nc), где c – константа, называется полиномиальным. Говорят, что задача решается эффективно, если для ее решения существует алгоритм, имеющий полиномиальную сложность. Так, алгоритм Дейкстры нахождения кратчайшего маршрута во взвешенном графе, содержащем n вершин, имеет полиномиальную сложность вида О(n2), алгебраическая задача решения системы n линейных уравнений методом Гаусса имеет сложность S=O(n3), задача умножения двух квадратных матриц n–го порядка стандартным алгоритмом имеет сложность S=O(n3).

Сложность алгоритма нахождения остова минимального дерева во взвешенном графе, содержащем n вершин, равна О(nlog2n). Задача коммивояжера поиска гамильтонова цикла в графе является трудноразрешимой задачей. Предлагаемые методы требуют почти полного перебора вариантов, S=O(n!).

Алгоритм, сложность которого равна О(cn), где c2, называется экспоненциальным.

Такую сложность имеет алгоритм решения задач на совпадение булевых функций.

8.3. Классы сложности – способ группировки алгоритмов или вычислимых функций в соответствии с их сложностью. Задачи одного и того же класса имеют одинаковую сложность. Разобьем все задачи по сложности на три большие класса:

– класс полиномиальной сложности P – класс легко решаемых задач;

– класс экспоненциальной сложности N – класс трудноразрешимых задач;

– класс N-P сложности – класс переборных задач (неизвестной сложности).

При такой классификации сложность легко решаемых задач не превосходит некоторый полином (многочлен) P от размерности задачи. Сложность труднорешаемых задач превосходит любой полином от n. Говорят, что сложность труднорешаемых задач имеет экспоненциальный рост от n. Третий класс N-P объединяет те задачи, которые пока не отнесены ни к одному из двух других классов, но между собой эти задачи имеют соизмеримую (эквивалентную) сложность. Если одни задачи в процессе решения удается свести к другим с помощью алгоритма полиномиальной сложности, то эти задачи составляют класс задач, эквивалентных по сложности.

В частности задача нахождения сокращенной ДНФ сводится к задаче покрытия множества клеток карт Карно минимальной системой некоторого заданного подмножества (символов «1», которые соответствуют элементарным конъюнктам в СДНФ этой булевой функции).

Любая эффективно решаемая задача является переборной, т.е. принадлежит классу N-P сложности. N-P полнота задачи Z означает, что она не проще, чем любая задача из класса N-P. Т.к. большинство массовых задач входит в класс задач N-P сложности, то проблема совпадения классов P и N-P сложности признана одной из важнейших. Эта проблема относится к числу проблем, не решенных до настоящего времени.

Математический институт Клэя включил эту проблему в список проблем тысячелетия, предложив награду размером в один миллион долларов США за её решение.

Задачи, эквивалентные по сложности, которые не удалось свести к одному из полиномиальных или экспоненциальных классов, называют N-P полными задачами.

Если удастся доказать, что некоторая задача класса N-P сложности, то разработчик алгоритма получает достаточно убедительные основания для отказа от поиска эффективного и точного алгоритма.

Если про одну из таких задач известно, что удается доказать ее трудноразрешимость, то и вся цепочка задач, к ней сводимых, тоже автоматически будет относиться к трудноразрешимым задачам.

Введение сложностной характеристики алгоритма приводит к двум направлениям исследования: поиску для данной легкорешаемой задачи алгоритма с еще меньшей сложностью, проверке задачи на труднорешаемость или N-P полноту.

Т.о., задачи бывают четырех типов: алгоритмически неразрешимые, алгоритмически разрешимые полиномиальной сложности, алгоритмически разрешимые экспоненциальной сложности, N-P полные задачи.

Под критерием сложности понимают средство измерения объема ресурсов, используемых в процессе вычислений. Классификации по сложности обычно подвергаются формальные языки, распознаваемые машиной Тьюринга. Пусть МТ вычисляет некую словарную функцию f(u).

Временной сложностью называется функция T(u), равная числу шагов МТ, выполненному при вычислении f(u), если f(u) определена.

Активной зоной МТ на слове «u» называется множество всех ячеек ленты, которые содержат непустые символы, либо посещались СЗУ машины в процессе вычисления f(u).

Пространственной или емкостной сложностью называется функция S(u), равная длине активной зоны МТ при работе со словом u, если функция f(u) определена.

Примеры:

1) технологическая операция «вскопать грядку» требует затрат времени, линейно зависящих от ее площади, т.е. на грядку, площадь которой в три раза больше, уйдет затрат времени в три раза больше. Аналогично, при увеличении размера грядки в 10 раз, объем работы увеличивается в 10 раз;

2) технологическая операция «найти имя в телефонной книге» требует затрат времени, логарифмически зависящих от количества записей (O(log2(n))). Так, открыв книгу примерно в середине, мы уменьшаем количество проверяемых страниц вдвое (за счет сортировки имен по алфавиту). Тогда в книге, толщиной в 1000 страниц, любое имя находится не больше чем за log2100010 раз (открываний книги).

8.4. Сложность алгоритмов.

Примеры определения числа арифметических операций, необходимых для осуществления некоторых алгоритмов.

– Алгоритм сложения матриц. Сложение матриц выполняется для каждого их элемента i и каждого j, где 1 i m, 1 j n, то выполняется mn операций сложения. Пусть N=max{m,n}. Тогда число арифметических операций, необходимых для осуществления сложения матриц имеет порядок O(N 2).

– Алгоритм умножения матрицы A размерности m p на матрицу B размерности p n. В процессе умножения матриц необходимо выполнить p операций сложения и p операций умножения для каждого их элемента i и каждого j, где 1 i m, 1 j n, т.о.

выполняется mnp операций сложения и mnp операций умножения. Значит, всего выполняется 2mnp операций. Пусть N=max{m,n,p}. Тогда число арифметических операций, необходимых для осуществления умножения матриц имеет порядок O(N 3).

Литература: [6], п.4.6;

[7], гл.2, ч.3;

[8], гл.12.

Математические символы и обозначения включение, принадлежность элемента множеству, непринадлежность элемента множеству, объединение множеств, пересечение множеств, суммирование, декартово произведение, квантор общности, квантор существования, E универсальное множество, Ai объединение множеств Ai, i Аi пересечение множеств Ai i кортеж, A\B разность множеств A и B, a, а отрицание a,,, конъюнкция, дизъюнкция,, строгая дизъюнкция, сумма по модулю два, частичный порядок, пустое множество, импликация,, эквиваленция, логическое следование, равносильность высказывательных форм, |= непосредственная выводимость |– выводимость, Bn n-ая декартова степень множества B множество натуральных чисел множество натуральных чисел, дополненное 0.

Математические сокращения:

ДНФ дизъюнктивная нормальная форма, КНФ конъюнктивная нормальная форма, СДНФ совершенная дизъюнктивная нормальная форма, СКНФ совершенная конъюнктивная нормальная форма, СПИСОК ЛИТЕРАТУРЫ 1. Галушкина Ю.И., Марьямов А.Н. Конспект лекций по дискретной математике. – М.

Айрис-пресс, 2008. – 176с.

2. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. – 5-е изд. М.:

Вузовская книга, 2002. – 268с.: ил.

3. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов.:

учеб. пособие для студ. высш. учеб. заведений. – М.: Издательский центр «Академия», 2007. – 304с.

4. Карпов Ю.Г. Теория автоматов. – СПб.: Питер, 2002. – 224 с.: ил.

5. Круглов В.В., Дли М.И. Интеллектуальные информационные системы. – М.:

Физматлит, 2002. – 256с.

6. Куликов.В.В. Дискретная математика: учебное пособие. – М.: РИОР, 2007. – 174 с.

7.Лавров И.А. Математическая логика. – М: Издательский центр Академия, 2006. – 240 с.

8. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях.: учебное пособие. – М.: Логос, 2002. – 240с.,ил.

9. Соболева Т.С., Чечкин А.В. Дискретная математика. – М.: Издательский центр Академия, 2006. – 256 с.

10. Просветов Г.И. Дискретная математика: задачи и решения: учебное пособие. – М.:

БИНОМ. Лаборатория знаний, 2008. – 222с.

11. Спирина М.С. Дискретная математика. Учебно-методическое пособие для проведения практических занятий по математике для студентов специальности 351400. – Тольятти, ТГУС, 2006. – 88 с.

12. Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов:

Учебник. – М.: ИНФРА-М;

Новосибирск: Изд-во НГТУ, 2008. – 224с.

13. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.:

ИНФРА-М;

Новосибирск: Изд-во НГТУ, 2003. – 280с.



Pages:     | 1 | 2 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.