Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Теория алгоритмов. формальное доказательство алгоритмической неразрешимости задач,

формальное доказательство алгоритмической неразрешимости задач,

асимптотический анализ сложности алгоритмов

классификация алгоритмов в соответствии с классами сложности,

разработка критериев сравнительной оценки качества алгоритмов

 

1. алгоритмической неразрешимости задач

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

Изначально вопрос разрешимости решали простым нахождением алгоритма. Если же алгоритм не находится, возможно его не существует и это тогда требуется строго доказать. А для этого нужно точно знать, что такое алгоритм.

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

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

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

Гильберта Гёдель впервые описал класс так называемых рекурсивных функций. Впоследствии был введён ряд других формализмов, таких как машина Тьюринга, λ-исчисление, оказавшихся эквивалентными рекурсивным функциям.

К примеру задача определяется какой то функцией f. Эту задачу программирования называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, является функция f вычислимой или нет.

Тезис Чёрча — Тьюринга

формулируется как совпадение классов вычислимых и частично рекурсивных функций

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

физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга;

Сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

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

Теоре́ма Гёделя о неполноте́ и втора́я теоре́ма Гёделя— две теоремы математической логики о принципиальных ограничениях формальной арифметики

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

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

примитивно рекурсивные функции;

частично рекурсивные функции.

общерекурсивные функции;

Множество частично рекурсивных функции включает в себя множество общерекурсивных функции, а общерекурсивные функции включают в себя примитивно рекурсивные функции. Частично рекурсивные функции иногда называют просто рекурсивными функциями.

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

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

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

Общерекурсивная функция — частично рекурсивная функция, определённая для всех значений аргументов

 

 

временная сложность - время работы алгоритма (минимальное среднее или максимальное)

пространственная сложность - объем используемой памяти

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

Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф-ия g(n) т.е. существует такая "с" что для все n c*g(n) >=f(n)

Таким образом O – означает верхнее ограничение сложности алгоритма.

f(n) = O(1) константа

f(n) = O(log(n)) логарифмический рост

f(n) = O(n) линейный рост

f(n) = O(n*log(n)) квазилинейный рост

f(n) = O(n^m) полиномиальный рост

f(n) = O(2^n) экспоненциальный рост

 

Правила для определения сложности

1. O(k*f) = O(f)

2. O(f*g) = O(f)*O(g) или O(f/g) = O(f)/O(g)

3. O(f+g) равна доминанте O(f) и O(g)

Здесь k обозначает константу, a f и g - функции.

<== предыдущая лекция | следующая лекция ==>
Математические проблемы реализации алгоритмов на ЭВМ | Современные проблемы развития элементной базы
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 521; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.