Презентация на тему "Введение Элементарные булевы функции"

Презентация: Введение Элементарные булевы функции
Включить эффекты
1 из 181
Ваша оценка презентации
Оцените презентацию по шкале от 1 до 5 баллов
  • 1
  • 2
  • 3
  • 4
  • 5
3.0
4 оценки

Комментарии

Нет комментариев для данной презентации

Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.


Добавить свой комментарий

Аннотация к презентации

Посмотреть и скачать презентацию по теме "Введение Элементарные булевы функции", включающую в себя 181 слайд. Скачать файл презентации 0.43 Мб. Средняя оценка: 3.0 балла из 5. Большой выбор powerpoint презентаций

  • Формат
    pptx (powerpoint)
  • Количество слайдов
    181
  • Слова
    другое
  • Конспект
    Отсутствует

Содержание

  • Презентация: Введение Элементарные булевы функции
    Слайд 1

    Введение Элементарные булевы функции

  • Слайд 2

    Основные логические операции и их свойства Функции алгебры логики Формулы Интерпретация Логическое следование и логическая эквивалентность Подстановки

  • Слайд 3

    Основные логические операции и их свойства

    конъюнкция, дизъюнкция, импликация, отрицание

  • Слайд 4

    Функции алгебры логики

    , где Булева функция f существенно зависитот переменной xi, если существует такой набор значений a1, …, ai-1, ai+1, …, an, что f(a1, …, ai-1, 0, ai+1, …, an)≠ f(a1, …, ai-1, 1, ai+1, …, an).

  • Слайд 5

    Пример

  • Слайд 6

    Булевы функции одной переменной отрицание Булевы функции двух переменных конъюнкция дизъюнкция сложение по модулю 2 импликация эквивалентность

  • Слайд 7

    Высказывания

    простые высказывания составные высказывания

  • Слайд 8

    Формулы

    ::= И|Л| | ¬) &| \/| | (формула)
  • Слайд 9

    Интерпретация

    А(х1,…,xn) – пропозициональная формула, где х1,…,xn–пропозициональные переменные. Конкретный набор истинностных значений, приписанных переменным х1,…,xn, называется интерпретацией формулы А.

  • Слайд 10

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

  • Слайд 11

    Теорема 1.Пусть А – некоторая формула. Тогда: если А – тавтология, то ¬А – противоречие, и наоборот; если А – противоречие, то ¬А – тавтология, и наоборот; если А – тавтология, то неверно, что А – противоречие, но не наоборот; если А – противоречие, то неверно, что А – тавтология, но не наоборот.

  • Слайд 12

    Теорема 2. Если формулы А и АВ – тавтологии, то формула В – тавтология.

  • Слайд 13

    Логическое следование и логическая эквивалентность

    Формула В логически следует из формулы А (АВ), если формула В имеет значение И при всех интерпретациях, при которых формула А имеет значение И. Формулы А и В логически эквивалентны (АВ), если они являются логическим следствием друг друга.

  • Слайд 14

    Теорема 3. (PQ)(¬P\/Q).

  • Слайд 15

    Теорема 4. Если А, В, С – любые формулы, то имеют место следующие логические эквивалентности: A\/A=A A&A=A A\/B=B\/A A&B=B&A A\/(B\/C)=(A\/B)\/C A&(B&C)=(A&B)&C A\/(B&C)=(A\/B)&(A\/C) A&(B\/C)=(A&B)\/(A&C) (A&B)\/A=A (A\/B)&A=A A\/Л=A A&Л=Л A\/И=И A&И=A ¬(¬A)=A ¬(A&B)=¬A\/¬B ¬(A\/B)=¬A&¬B A\/¬A=И A&¬A=Л

  • Слайд 16

    Теорема 5. P1&…&PnQ тогда и только тогда, когда (P1&…&Pn)Q - тавтология. Теорема 6. P1&…&PnQ тогда и только тогда, когда P1&…&Pn&¬Q – противоречие.

  • Слайд 17

    Подстановки

    Теорема 7. Если А(…х…) – тавтология и В- любая формула, то А(…х…){В//x} – тавтология.

  • Слайд 18

    Раздел 1. Логические исчисления1. Исчисление высказываний

  • Слайд 19

    Классическое определение исчисления высказываний Частный случай формулы Алгоритм унификации Производные правила вывода Дедукция Некоторые теоремы теории α Другие аксиоматизации исчисления высказываний

  • Слайд 20

    Характеристики логического исчисления

  • Слайд 21

    Классическое определение исчисления высказываний

    Алфавит: ¬ и  - связки (, ) – служебные символы a,b,…,a1,b1,… - пропозициональные переменные Формулы: 1) переменные суть формулы 2) если А, В - формулы, то (¬А) и (АВ) –формулы. Аксиомы: А1: (А(ВА)) А2: ((А(ВС))((АВ)(АС))) А3: ((¬В¬А)((¬ВА)В)) Правило:

  • Слайд 22

    Определения: A&B:=¬(A¬B), A\/B:=¬AB

  • Слайд 23

    Частный случай формулы

    В:=A(…,xi,…){Bi//xi}i=1..n {Bi//xi}i=1..n– унификатор С=A(…,xi,…){Хi//xi}i=1..n & C=B(…,xi,…){Хi//xi}i=1..n С - совместный частный случай формул А и В {Хi//xi}i=1..n- общий унификатор Формулы, которые имеют совместный частный случай, называются унифицируемыми.

  • Слайд 24

    Алгоритм унификации

    Вход: формулы А и В. Выход: false, если формулы не унифицируемы; true и общий унификатор S в противном случае. Алгоритм унификации – рекурсивная функция Unify. if f(A) – переменная then begin v:=f(A); {переменная} if S[v]= then begin S[v]:=B; return true {т.е. добавляем подстановку {B//v}} end else return (S[v]≠B) {либо эта подстановка уже есть, либо унификация невозможна} end; if f(A)≠f(B) then return false; {главные операции различны, унификация невозможна} if f(A)=’¬’ then return Unify(r(A),r(B)); {пытаемся унифицировать операнды отрицаний} if f(A)=’’ then return Unify(l(A),l(B))&Unify(r(A),r(B)); {пытаемся унифицировать операнды импликаций}

  • Слайд 25

    Производные правила вывода

    Выводом формулыА из конечного или бесконечного множества формул Т в исчислении α называется конечная последовательность формул А1, А2, …, An,в которой An = A и каждая из формул Ai, i1..n является или аксиомой, или формулой из Т (исходной формулой), или получается по некоторому правилу вывода из предыдущих формул последовательности. Если существует вывод формулы А из множества формул Т исчисления α, то говорят, что в α А выводима из Т. Т ├αА, или В1, В2, …, ВК ├αА, если Т = {В1, В2, …, ВК}. Формулы из Т - посылки вывода. Формула из А языка α, выводимая в исчислении α из пустого множества формул, называется доказуемой формулой, или теоремой исчисленияα, а сам вывод формулы А из пустого множества формул называется ее доказательством. ├αА.

  • Слайд 26

    Теорема 1.1.├αАА Теорема 1.2.А├αВА (правило введения импликации)

  • Слайд 27

    Дедукция

    Теорема 1.3 (дедукции) Если Т,А├αВ, то Т├αАВ и обратно.   Следствие 1. Если А├αВ, то ├αАВ и обратно.   Следствие 2.(правило транзитивности) АВ, ВС ├αАС.   Следствие 3.(правило сечения) А(ВС), В ├αАС.

  • Слайд 28

    Некоторые теоремы теории α

    Теорема 1.4. В теории α выводимы следующие теоремы: А) ├ᬬАА Б) ├αА¬¬А В) ├α¬А(АВ) Г) ├α(¬В¬А)(АВ) Д) ├α(АВ)( ¬В¬А) Е) ├αА(¬В¬(АВ)) Ж) ├α(АВ)((¬АВ)В)

  • Слайд 29

    Другие аксиоматизации исчисления высказываний

    Гильберт и Аккерман, 1938г. Связки: \/, ¬ (AB:=¬A\/B) Аксиомы: A\/AA AA\/B A\/BB\/A (BC)(A\/BA\/C) Правило: Modus ponens Россер, 1953г. Связки: &, ¬ (AB:=¬(A&¬B)) Аксиомы: AA&A A&BA (AB)(¬(B&C)¬(C&A)) Правило: Modus ponens   Клини, 1952г. Связки: ¬, &, \/,  Аксиомы: A(BA) (A(BC))((AB)(AC)) A&BA A&BB A(B(A&B)) A(A\/B) B(A\/B) (AC)((BC)((A\/B)C)) (AB)((A¬B)¬A) ¬¬AA Правило: Modus ponens

  • Слайд 30

    Раздел 1. Логические исчисления2. Исчисление предикатов

  • Слайд 31

    Предикаты и операции над ними Основные понятия формальной теории исчисления предикатов Логическое следование и логическая эквивалентность Использование равносильностей для упрощения формул Семантика исчисления предикатов

  • Слайд 32

    Предикаты и операции над ними

    Любое отображение Р: Мn называется n-местным предикатом на множестве М. М – произвольное непустое множество, n N  {0}, Мn — n-нная декартова степень множества М. Р(x1, …,xn) – обозначение n-местного предиката

  • Слайд 33

    Примеры

    «Х есть простое число» Р(х) = и, если х простое число, л, если х – не является простым числом. «Число z является суммой чисел x, y» P(x,y,z) = и, если z = x + y, л, если z  x + y

  • Слайд 34

    Получение из одних предикатов на множестве М других на том же множестве

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

  • Слайд 35

    P(x, y) =и, если x делит y, л, если x не делит y у P(x, y)  и, если x = 1, л, если x 1, хP(x, y) = л хP(x, y) и у P(x, y)  и

  • Слайд 36

    Основные понятия формальной теории исчисления предикатов

    Алфавит: связки основные ¬, дополнительные &,\/ служебные символы кванторывсеобщности существования  предметные константы a,b,…,a1,b1,… переменные x,y,…,x1,y1,… предметные предикаты P,Q,… функторы f,g,…

  • Слайд 37

    Синтаксис формулы: ::= | ¬| ()| |  ::= () ::= |, ::= | | ()

  • Слайд 38

    Вхождения переменных в атомарную формулу называются свободными. Вхождения переменной х в формулы х А и х А называются связанными. Формула, не содержащая свободных вхождений переменных, называется замкнутой.

  • Слайд 39

    Система аксиом: I. 1) A(BA) 2) (A(BC))((AB)(AC)) II. 1) ABA 2) ABB 3) (AB) ((AC) (ABC)) III. 1) AAvB 2) BAvB 3) (AC) ((BC) (AvBC)) IV. 1) A¬¬A 2) ¬¬AA 3)(AB) (¬B¬A) V. 1)x A(x) A(t) 2) A(t) x A(x).

  • Слайд 40

    Правила: I. Правило заключения: , где А, В – любые формулы. II. Правило -введения: , где А содержит, а В не содержит свободные вхождения переменной х. III. Правило -удаления: , где А содержит, а В не содержит свободные вхождения переменной х.

  • Слайд 41

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

  • Слайд 42

    Логическое следование и логическая эквивалентность

    ¬х А(х) = х ¬А(х) ¬х А(х) = х ¬А(х) х (А(х)&В(х))=х А(х) & x B(x) х (А(х)\/В(х))=х А(х) \/ x B(x) х (А(х)&В(х))х А(х) & x B(x) х А(х) \/ x B(х)х(А(х)\/B(x)) xy A(x,y) = yx A(x,y) xy A(x,y) = yx A(x,y) x (A(x)&C) = x A(x) & C x (A(x)\/C) = x A(x) \/ C x (A(x)&C) = x A(x) & C x (A(x)\/C) = x A(x) \/ C Cx A(x) = x (CA(x)) Cx A(x) = x (CA(x)) x A(x) C x (A(x) C) x A(x) C x (A(x) C) где формула С не содержит никаких вхождений переменной х.

  • Слайд 43

    Пусть А – формула алгебры предикатов, не содержащая операции . Формула, полученная из А заменой всех вхождений  на , на, на, на, называется двойственной к А (обозначение А*). Утверждение(Принцип двойственности.) Для любых формул А, В алгебры предикатов: A  B  A*  B*

  • Слайд 44

    Использование равносильностей для упрощения формул

    Формула алгебры предикатов называется приведенной, если в ней не используется операция , а отрицание или не используется совсем, или относится лишь к элементарным формулам. Предваренной(или нормальной) формулой алгебры предикатов называется любая формула вида δ1xi1δ2xi2…δkxikA, где δ1, …, δk– кванторы, а А приведенная формула, не содержащая кванторов.

  • Слайд 45

    Теорема2.1.Для всякой формулы А алгебры предикатов существует равносильная ей приведенная формула. Теорема 2.2. Для всякой формулы А алгебры предикатов существует равносильная ей предваренная формула.

  • Слайд 46

    Семантика исчисления предикатов

    ИнтерпретацияI (прикладного) исчисления предикатов  с областью интерпретации М – это набор функций, которые сопоставляют каждой предметной константе а некоторые элементы I(a) из М; каждому n-местному функтору fоперацию I(f), определенную на множестве М; каждому n-местному предикату Р отношение I(P) на М.

  • Слайд 47

    Теорема 2.3.Если каждая формула множества формул Т истинна в некоторой интерпретации исчисления  и T├ A, то А – истинна.   Следствие 1. Всякая доказуемая формула исчисления предикатов  является истинной в любой интерпретации исчисления . Следствие 2. Исчисление предикатов непротиворечиво, т.е. в нем не может быть доказуемой никакая формула А вместе с ее отрицанием, или никакая формула вида А&¬А.    

  • Слайд 48

    Теорема 2.4.(Геделя о полноте исчисления предикатов). Если формула исчисления предикатов истинна во всех его интерпретациях, то она доказуема в исчислении предикатов. Множество формул Т исчисления  называется полным, если для каждой замкнутой формулы языка  имеет место Т├ А или Т ├ А.

  • Слайд 49

    Раздел 1. Логические исчисления3. Автоматическое доказательство теорем

  • Слайд 50

    Постановка задачи. Метод резолюций Правило резолюции для исчисления высказываний Правило резолюции для исчисления предикатов Опровержение методом резолюций Алгоритм метода резолюций

  • Слайд 51

    Постановка задачи. Метод резолюций

    Алгоритм, который проверяет отношение Т├τS для формулы S, множества формул Т, и теории τ называется алгоритмом автоматического доказательства теорем.

  • Слайд 52

    Основа метода резолюций:

    Теорема 3.1.Если Т,¬S├F, где F –любое противоречие (тождественно ложная формула), то T├S.

  • Слайд 53

    Правило резолюции для исчисления высказываний

    С1и С2– предложения в исчислении высказываний, С1=Р\/C1’ C2=¬P\/C2’, где Р – пропозициональная переменная, C1’ и C2’- любые предложения. Предложения С1 и С2 называются резольвируемыми, предложение С1’\/C2’ – резольвентой(является предложением), формулы Р и ¬Р – контрарнымилитералами.

  • Слайд 54

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

  • Слайд 55

    Правило резолюции для исчисления предикатов

    С1и С2 – два предложения в исчислении предикатов. С1=Р1\/C1’ C2=¬P2\/C2’, атомарные формулы Р1 и Р2унифицируемы унификатором σ. Предложение (C1’\/C2’)σ– резольвента - получено из предложения C1’\/C2’ применением унификатора σ.

  • Слайд 56

    Опровержение методом резолюций

    Задача: установить выводимость S├G. Каждую формулу множества S и формулу ¬G независимо преобразовать в множество предложений. Отыскать резольвируемые предложения, к ним применить правило резолюций и резольвенту добавить в множество до тех пор, пока не будет получено пустое предложение. Если среди текущего множества предложений нет резольвируемых, то теорема опровергнута. Если в результате очередного применения правила резолюции получено пустое предложение, то теорема доказана. Если процесс не заканчивается, то это ничего не означает.

  • Слайд 57

    Пример

    Доказать методом резолюций теорему ├α(((АВ)А)А).

  • Слайд 58

    Алгоритм метода резолюций

    Задача: проверить выводимость формулы G из множества формул S. Вход: множество предложений С, полученных из множества формул S и формулы ¬G. Выход: 1 - если G выводимо из S, 0 – в противном случае. Алгоритм: M:=C; {M – текущее множество предложений} while пустое предложение  M do begin Choose(M,c1,c2,p1,p2,σ); {выбор родительских предложений} ifc1,c2 не найдены then return 0; {нечего резольвировать} c:=R(c1,c2,p1,p2,σ); {вычисление резольвенты} M:=M{c} {пополнение текущего множества} end; return1; {теорема доказана}

  • Слайд 59

    Раздел 3. Теория алгоритмов9. Формализация понятия алгоритм

  • Слайд 60

    Необходимость уточнения понятия алгоритма Формализации Черча, Тьюринга и Маркова

  • Слайд 61

    Возможные случаи протекания алгоритмического процесса:

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

  • Слайд 62

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

  • Слайд 63

    Необходимость уточнения понятия алгоритма

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

  • Слайд 64

    Формализации Черча, Тьюринга и Маркова

    Варианты определения алгоритма: А.Черч и С. Клини: в алгоритмическом процессе вычисляется значение некоторой функции f(x1, x2, . . . , xn), определенной на множестве натуральных чисел. А.Тьюринг: алгоритмический процесс—это работа некоторой воображаемой вычислительной машины—машины Тьюринга. 3) А.А.Марков: алгоритмический процесс – это переработка слов некоторого алфавита с помощью точно описанных правил переработки.

  • Слайд 65

    Раздел 3. Теория алгоритмов10. Рекурсивные функции

  • Слайд 66

    Конструктивные объекты Алгоритмы и функции Частичные функции Примитивно рекурсивные функции Частично рекурсивные функции. Тезис Черча

  • Слайд 67

    Конструктивные объекты

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

  • Слайд 68

    Алгоритмы и функции

    Алгоритм A вычисляет некоторую n-арную функцию f(x1, x2, . . . , xn), определенную на множестве N.

  • Слайд 69

    Частичные функции

    Частичной n-арной функцией f, заданной на множестве натуральных чисел, называется правило, которое некоторым наборам (x1, x2, ...,xn)натуральных чисел ставит в соответствие однозначно определенное число f(x1, x2, . . . , xn)N. Множество X, состоящее из всех наборов (x1, x2, . . . , xn), для которых существует значение функции, называется областью определения функции f (Dom(f)). Множество всех значений функции fназывается областью значений функции f (Ran(f)).

  • Слайд 70

    Замечание 10.1. Пусть f —n-арная частичная функция с условием Dom(f). Тогда число n определено однозначно. Функция fвсюду определена, если ее значение определено при любом наборе аргументов.

  • Слайд 71

    Функцияf(x1, x2, . . . , xn)называется вычислимой, если существует алгоритм A, вычисляющий функцию f.

  • Слайд 72

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

    Исходные функции: Функция следования s(x)=x+ 1 для всех x N Нулевая функция on(x1, x2, . . . , xn )= 0 для всех x1, x2, . . . , xn N Функция проектирования Inm(x1, x2, . . . , xn) =xm, n 1 и 1 mn

  • Слайд 73

    Утверждение 10.1Следующие простейшие функции вычислимы. Функция следования s(x)= x + 1. Нулевая функция on(x1, x2, . . . , xn) = 0. Функция проектирования Inm(x1, x2, . . . , xn)= xm.

  • Слайд 74

    Способы построения из имеющихся вычислимых функций новых вычислимых функций:

    Оператор суперпозиции S f(x1, x2, …, xn)= h(g1(x1, x2, …, xn), g2(x1, x2, …, xn), …, gm(x1, x2, …, xn)) Оператор примитивной рекурсии R f(x1, x2, . . . , xn, 0)= g(x1, x2, . . . , xn) f(x1, x2, . . . , xn, y+ 1)= h(x1, x2, . . . , xn, y, f(x1, x2, . . . , xn, y))

  • Слайд 75

    Функцияf называется примитивно рекурсивной, если она может быть получена из простейших функций s(x)=x+ 1, on(x1, x2, . . . , xn)= 0, Inm(x1, x2, . . . , xn)=xmс помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

  • Слайд 76

    Утверждение 10.2. Функция f(x) = x примитивно рекурсивна. Утверждение 10.3 Функция g(x)= x+2 примитивно рекурсивна. Утверждение 10.4. Постоянная унарная функция f(x)=a примитивно рекурсивна. Утверждение 10.5. Нульарная функция примитивно рекурсивна.

  • Слайд 77

    Способы построения из имеющихся вычислимых функций новых вычислимых функций (продолжение):

    Операция введения фиктивных переменных Утверждение 10.6. Функция сложения f(x, y)=x +y примитивно рекурсивна. Утверждение 10.7. Функция умножения f(x, y)=xy примитивно рекурсивна.

  • Слайд 78

    Примеры

    Примитивно-рекурсивными являются следующие функции: f(x,y)=|x-y|; min(x,y); max(x,y); r(x,y) – остаток от деления y на x q(x,y) =[y/x] – целая часть дроби y/x

  • Слайд 79

    «Арифметизированные» логические функции (числовые функции, которые на множестве {0,1} ведут себя как логические функции), примитивно-рекурсивны: ¬x; X\/y; X&y. Вывод: логические функции примитивно-рекурсивны.

  • Слайд 80

    Отношение R(x1,…,xn) называют примитивно-рекурсивным, если примитивно-рекурсивна его характеристическая функция χR: Предикат называют примитивно-рекурсивным, если его характеристическая функция примитивно-рекурсивна. Если предикаты P1,… Pk примитивно-рекурсивны, то и предикат, полученный из них с помощью логических операций, примитивно-рекурсивен.

  • Слайд 81

    Примеры

    Следующие предикаты и отношения примитивно рекурсивны: предикат «x делится на n» предикат «x делится на n и m» отношение x1>x2 если функции f(x) и g(x) примитивно-рекурсивны, то предикат «f(x)=g(x)» также примитивно рекурсивен

  • Слайд 82

    Примитивно-рекурсивные операторы

    Оператор называется примитивно-рекурсивным (ПР-оператор), если он сохраняет примитивную рекурсивность функции. Например, оператор суперпозиции оператор примитивной рекурсии В – оператор условного перехода. По функциям q1(x1,…,xn) и q2(x1,…,xn) и предикату P(x1,…,xn) строит функцию f(x1,…,xn)=B(q1,q2,P):

  • Слайд 83

    Функции Аккермана

    Обозначения: P0(a,x)=a+x (действие 0-ой ступени); P1(a,x)=a*x (действие 1-ой ступени); P2(a,x)=ax(действие 2-ой ступени). P1(a,x+1)=P0(a,P1(a,x)); P1(a,1)=a; P1(a,0)=0; P2(a,x+1)=P1(a,P2(a,x)); P2(a,1)=a; P2(a,0)=1; Для n=2,3,… Pn+1(a,0)=1; Pn+1(a,1)=a; Pn+1(a,x+1)=Pn(a,Pn+1(a,x)). При n=2: P3(a,0)=1; P3(a,1)=a; P3(a,2)=aa; P3(a,3)=aa^a. Обозначения: B(n,x)=Pn(2,x); A(x)=B(x,x). Функции B(n,x) называют функциями Аккермана, а функцию A(x) – диагональной функцией Аккермана. B(0,x)=2+x; B(n+1,0)=sg(n); B(n+1,x+1)=B(n,B(n+1,x)). Рекурсия ведется сразу по двум переменным.

  • Слайд 84

    Теорема. Функция Аккермана A(x) растет быстрее, чем любая примитивно-рекурсивная функция, и, следовательно, не является примитивно-рекурсивной.

  • Слайд 85

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

    Оператор минимизации M Пусть g—функция от n + 1 переменной. Функция f от n переменных получена из функции g с помощью оператора минимизации, если равенство f(x1, . . . , xn,)=yверно тогда и только тогда, когда f(x1, . . . , xn, y)= 0, а значения f(x1, . . . , xn, 0), . . . , f(x1, . . . , xn, y-1)определены и не равны нулю.

  • Слайд 86

    Пример

    Найти функцию f, полученную из функции o(x) применением оператора минимизации.

  • Слайд 87

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

  • Слайд 88

    Примеры

    [z/x]=μyyz) [√x]= μyyx) [logkx]= μyyx)

  • Слайд 89

    Функцияf называется частично рекурсивной функцией, если она может быть получена из следующих простейших функций: 1) функции следования s(x)=x + 1, 2) нулевой функции on(x1, x2, . . . , xn)=0, 3) функции проектирования Inm(x1, x2, . . . , xn)=xm с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации.

  • Слайд 90

    Утверждение 10.8. Всякая частично рекурсивная функция f является вычислимой функцией. Тезис Черча.Каждая вычислимая функция частично рекурсивна.

  • Слайд 91

    Раздел 3. Теория алгоритмов11. Машины Тьюринга

  • Слайд 92

    Машина Поста Машина Тьюринга

  • Слайд 93

    Машина Поста

    Пример программы: (0, 0, 0, L, 1) (0, 1, 0,R, 1) (1, 0, 0, L, 1) (2, 0, 0, L, 1)

  • Слайд 94

    Условия вычисления функции f машиной Поста:

    Пусть строка (x1, x2, . . . , xn) содержится в области определения функции f. Тогда машина M, начиная работать и обозревая левую единицу строки (x1, x2, . . . , xn), на некотором шаге останавливается, обозревая левую единицу строки f(x1, x2, . . . , xn). Пусть строка (x1, x2, . . . , xn) не содержится в области определения функции f. Тогда машина M работает бесконечно.

  • Слайд 95

    Пример

    Указать машину Поста, вычисляющую функцию f(x, y) = x +y.

  • Слайд 96

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

  • Слайд 97

    Машина Тьюринга

    A ={a0, a1, . . . , an} — символы в ячейках (внешний алфавит), Q ={q0, q1, . . . , qm} — состояния машины (внутренний алфавит). Виды команд: qiajqkal, qiajqkalL, qiajqkalR, где 1imи 0jn.

  • Слайд 98

    Условия вычисления функции f(x1, x2, . . . , xn) машиной M:

    1. Если f(x1, x2, . . . , xn) существует, то машина, начиная работу с конфигурации q11x1. . . 01xn0, останавливается и при этом имеет конфигурацию qz1f(x1, x2, . . . , xn)0 . . . 0. 2. Если f(x1, x2, . . . , xn) не существует, то машина работает бесконечно.

  • Слайд 99

    Примеры

    Построить машины Тьюринга для: вычисления функции f(x)=x+1 сложения двух чисел переработки слова α в α*α вычисления функции f(x)= 2x Теорема 11.1. Если функции f1(x) и f2(y) вычислимы по Тьюрингу, то их композиция g(x)=f2(f1(x)) также вычислима по Тьюрингу.

  • Слайд 100

    Вычисление предикатов на машинах Тьюринга

    Говорят, что машина Т вычисляет предикат P(α) (α – слово в алфавите A*), если T(α)=ω, где ω=T (true), когда P(α) истинно, ω=F (false), когда P(α) ложно. Если P(α) не определен, то машина Т не останавливается. Говорят, что машина Т вычисляет P(α) с восстановлением, если Т(α)=ωα.

  • Слайд 101

    Пример

    На машине Тьюринга вычислить предикат «α – четное число».

  • Слайд 102

    Пусть функция f(α) задана описанием: «если P(α) истинно, то f(α)=g1(α), иначе f(α)=g2(α)». Функция f(α) называется развилкой или условным переходом к g1(α) и g2(α) по условию P(α). Теорема 11.2. Если функции g1(α) и g2(α) и предикат P(α) вычислимы по Тьюрингу, то развилка g1(α) и g2(α) по P(α) также вычислима.

  • Слайд 103

    Пусть функция f(α) задана описанием: «пока истинно P(α) вычислять g1(α), иначе f(α)=g2(α)». Функция f(α) называется повторением или циклом от g1(α) и g2(α) по условию P(α). Теорема 11.3. Если функции g1(α) и g2(α) и предикат P(α) вычислимы по Тьюрингу, то цикл g1(α) и g2(α) по P(α) также вычислим.

  • Слайд 104

    Пример

    Построить машину Тьюринга для сложения n чисел.

  • Слайд 105

    Машина Тьюринга U, вычисляющая функцию от двух переменных и такая, что для любой машины Т с системой команд ΣТ U(ΣТ,α)=T(α), если T(α) определена (или останавливается), U(ΣТ,α)=T(α) не останавливается, если Т(α) не останавливается, называется универсальной машиной Тьюринга. Теорема 11.4. Универсальная машина Тьюринга существует. Теорема 11.5. Не существует машины Тьюринга, решающей проблему остановки для произвольной машины Тьюринга.

  • Слайд 106

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

  • Слайд 107

    Раздел 3. Теория алгоритмов12. Машины с неограниченными регистрами

  • Слайд 108

    Команды МНР Вычисление функций на МНР. Вычислимость частично рекурсивных функций на МНР Подпрограммы

  • Слайд 109

    МНР

    Регистры R1,R2,R3, . . ., Программа машины

  • Слайд 110

    Условие остановки. Машина останавливается тогда и только тогда, когда невозможно выполнить очередную предписанную команду. Результат вычислений. Если выполнение программы завершилось, то число r1 из регистра R1 считается результатом применения алгоритма к исходному набору чисел r1, r2, . . . .

  • Слайд 111

    Вычисление функций на МНР

    Пример №1. Составить программу для МНР, которая вычисляет функцию f(x)=x + 2. Пример №2. Составить программу для МНР, которая вычисляет функцию f(x, y)=x +y. Пример №3. Пример №4.

  • Слайд 112

    Пусть М(x1,x2,…,xn) - n-местный предикат на натуральных числах. характеристическая функция предиката Предикат М(х) разрешим, если функция СМ вычислима; Предикат М(х) неразрешим, если функция СМневычислима. Пример. Следующие предикаты разрешимы: «x≠y» «x=0»

  • Слайд 113

    Теорема 12.1 Следующие функции вычислимы на МНР. 1) Функция следования s(x). 2) Нулевая функция on(x1, x2, . . . , xn). 3) Функция проектирования Inm(x1, x2, . . . , xn).

  • Слайд 114

    Вычислимость частично рекурсивных функций на МНР

    Теорема 12.2. Пусть функция f получена из функций h, g1, g2, . . . , gm с помощью оператора суперпозиции f(x1, x2, . . . , xn)=h(g1(x1, x2, . . . , xn), g2(x1, x2, . . . , xn), . . . , gm(x1, x2, . . . , xn)). Если функции h, g1, g2, . . . , gm МНР вычислимы, то и функция f также МНР вычислима. Теорема 12.3. Пусть функция f получена с помощью оператора примитивной рекурсии из функций g и h. Если функции g и h МНР вычислимы, то и функция f также МНР вычислима. Теорема 12.4.Пусть функция f получена из функции g с помощью оператора минимизации. Если функция g является МНР вычислимой, то и функция f также МНР вычислима.

  • Слайд 115

    Рассмотрим функцию f(x1,…,xn)=B(g1,g2,P) B(g1,g2,P) - оператор развилки или перехода. Теорема 12.5. Пусть функции g1(x1,…,xn) и g2(x1,…,xn) и предикат P(x1,…xn) вычислимы, тогда вычислима и функция f(x1,…,xn)=B(g1,g2,P).

  • Слайд 116

    Рассмотрим функцию h(x)=D(g1,g2,P), где h(x) задана следующим образом: «пока P(x) истинно, вычислять g1(x), иначе вычислять g2(x)». D(g1,g2,P) называется оператором повторения или цикла. Теорема 12.6. Пусть функции g1(x), g2(x) и предикат P(x) вычислимы, тогда вычислима и функция h(x)=D(g1,g2,P).

  • Слайд 117

    Следствие 1. Всякая частично рекурсивная функция вычислима на некоторой МНР. Следствие 2.Функция f является вычислимой функцией тогда и только тогда, когда функция f вычислима на некоторой МНР.

  • Слайд 118

    Правила взаимодействия подпрограмм

    Пусть дана программа для МНР, состоящая из s команд. Программа имеет стандартный вид, если во всякой команде условного перехода J(m, n, q) данной программы выполняется неравенство qs + 1. Стандартизацией программы I1, I2, . . . , Is называется замена в данной программе всех команд J(m, n, q), где q>s + 1, на команды J(m, n, s + 1). Соединением программ P и Q называется программа из s +t команд вида где команды Is+1, Is+2, . . . , Is+t получены из команд I’1, I’2, . . . , I’tпрограммы Q приращением номеров на число s. При этом каждая команда условного перехода J(m, n, q)из Q заменена на команду вида J(m, n, q+s).

  • Слайд 119

    Выделение регистров для подпрограммы

    Пусть ρ = ρ(P) число с условием, что действие программы P меняет лишь регистры R1, . . . , Rρи не затрагивает регистры Rl для l> ρ. Отводим регистры R1, . . . , Rρдля работы подпрограммы P, и выделяем регистры Rl при l> ρ в качестве рабочих регистров для остальных команд основной программы Q.

  • Слайд 120

    Вставка подпрограммы

    1) Распределение памяти. Вычисляется число ρ =ρ(P) и выделяется память R1, . . . , Rρ, достаточная для работы подпрограммы P. Задается регистр Ri, где i >ρ, для хранения результата работы подпрограммы. 2) Извлечение аргументов. Записываются команды: T(i1, 1), . . . , T(in, n) для передачи аргументов из места их хранения в регистры R1, . . . , Rn. 3) Очистка регистров. Записываются следующие команды: Z(n+ 1), . . . , Z(ρ). 4) Вставка команд подпрограммы P. 5) Пересылка результата на хранение. Добавляется команда T(1, i).

  • Слайд 121

    Доказательство утверждения 12.2

    Начало Пересылаем аргументы x1, x2, . . . , xnна хранение в регистры Rρ+1, . . . , Rρ+n y1 =G1(x1, x2, . . . , xn) → Rρ+n+1 Ym =Gm(x1, x2, . . . , xn) → Rρ+n+m H(y1,…,ym) → R1 Остановка

  • Слайд 122

    Доказательство утверждения 12.3

    Начало x1, x2, . . . , xn, y →Rρ+1, . . . , Rt+1 g(x1, x2, . . . , xn) → Rt+3 Остановка Rt+2=Rt+1 (k=y) Rt+3→ R1 h(x1, x2, . . . , xn,k,f(x1, x2, . . . , xn)) → Rt+3 k:=k+1 да нет

  • Слайд 123

    Доказательство утверждения 12.4

    Начало x1, x2, . . . , xn→Rρ+1, . . . , Rρ+n g(x1, x2, . . . , xn,k) → R1 Остановка g(x1, x2, . . . , xn,k) =0 k=y k→ R1 k:=k+1 да нет

  • Слайд 124

    Раздел 3. Теория алгоритмов13. Нумерация программ и функций

  • Слайд 125

    Нумерация множеств Нумерация программ МНР Нумерация множества вычислимых функций

  • Слайд 126

    Теория нумераций — раздел теории алгоритмов, в котором изучаются свойства классов объектов, занумерованных с помощью натуральных чисел. Перечислением или нумерациеймножества X называется отображение f:Z0→X множества Z0 (целые неотрицательные числа) на множество X.

  • Слайд 127

    Геделевская нумерация

    Множество X называется эффективно счетным, если существует функция f:Z0→X, устанавливающая взаимно однозначное соответствие между множествами Z0 и X такая, что и f--1 - вычислимые функции, 1) Существует алгоритм A1, вычисляющий по элементу его номер. 2) Существует алгоритм A2, устанавливающий по номеру элемент с данным номером. Функции fи f-1вычислимы.

  • Слайд 128

    Теорема 13.1. Следующие множества являются эффективно счетными: а) Z0×Z0; б) Z0×Z0×Z0; в) - множество всех конечных последовательностей целых неотрицательных чисел.

  • Слайд 129

    Отображение α2:Z0×Z0→ Z0 α2(m, n)=2m*(2n + 1)-1 α2-1(z)=(α21(z), α22(z)), где α21(z) - число двоек в каноническом разложении числа z+1;

  • Слайд 130

    Отображение α3:Z0×Z0×Z0→ Z0 α3(m,n,q)= α2(α2(m,n),q). α3-1(z)=( α21(α21(z)), α22(α21(z)), α22(z)).

  • Слайд 131

    Эффективная счетность множества всех конечных последовательностей целых неотрицательных чисел: α(a1,a2,…,ak)=2a1+2a1+ a2+1+2a1+ a2+ a3+2+…+2a1+ a2+…+ ak+(k-1)-1 в двоичной системе счисления:

  • Слайд 132

    Теорема 13.2.Множество всех команд МНР является эффективно счетным. отображение β:K→Z0 β(Z(n)) = 4 (n - 1); β(S(n)) = 4 (n - 1) + 1; β(T(m,n))=4*α2(m-1,n-1)+2; β(J(m,n,q))=4*α3(m-1,n-1,q-1)+3; Теорема 13.3.Множество P, состоящее из всевозможных программ МНР, является эффективно счетным. Число γ(P) называется геделевым номеромпрограммыP или просто номером программыP

  • Слайд 133

    Пример 1 Найти геделев номер программы P: I1: S(1) I2: S(1) вычисляющей функцию f(x) = x + 2. Пример 2 Вычислить программу Pmпо ее геделеву номеру m (m=0,1,2,3).

  • Слайд 134

    Нумерация вычислимых функций

    Пусть f - n-местная функция, вычислимая по программе P с геделевым номером m (fmn). Числоm называют индексом функции f. Отображение θ : F  N Пусть f—n-арная вычислимая функция, где n 0. Пусть m—номер места fв последовательности f0, f1, f2,… Тогда θ(f)=α2(m, n).

  • Слайд 135

    Теорема 13.4. Множество всех вычислимых функций счетно.

  • Слайд 136

    Теорема 13.5. Существует невычислимая всюду определенная функция.

  • Слайд 137

    Раздел 3. Теория алгоритмов14. Нормальные алгорифмы

  • Слайд 138

    Алгоритмический процесс—это процесс переработки слов некоторого алфавита.

  • Слайд 139

    Алфавит и схема нормального алгорифма

    некоторая конечная совокупность символов A ={a1, . . . , am} конечная упорядоченная последовательность формул подстановок

  • Слайд 140

    Работа нормального алгорифма

    Среди левых частей u1, u2, . . . , ukв этой схеме нужно отыскать первое по порядку слово ui, которое входит в слово P. Заменить найденное слово uiв слове P на слово vi, и получить некоторое слово P1. Возможно несколько вхождений uiв слово P. Тогда заменяется на viпервое вхождение uiв слове P. Если при замене применялась заключительная формула, то переработка слова P завершена и алгоритм останавливается. Полученное слово P1—результат переработки слова P. Если при замене применялась незаключительная формула, то слово P1 заново обрабатывается схемой Z и алгоритм продолжает работу. Возможно, что при проходе по схеме Z вообще не обнаружено ни одного вхождения слов u1, u2, . . . , ukв слово P. Тогда результат переработки—само слово P и алгоритм останавливается.

  • Слайд 141

    Условие остановки и результат работы

    I. Процесс переработки слов обрывается и получено слово Q = A(P), т.е. получен результат применения нормального алгорифма A к слову P. II. Процесс переработки слов бесконечен. Тогда нет результата Q = A(P) и алгорифм A неприменим к слову P.

  • Слайд 142

    Пусть А – алфавит, а М1 и М2 – алгоритмы над алфавитом А. М1 и М2 эквивалентны относительно А, если для любых слов P и Q в алфавите А выполняются условия: Если М1: P=>Q, то М2: P=>Q Если М2: P=>Q, то М1: P=>Q

  • Слайд 143

    Примеры нормальных алгорифмов

    Алгорифм сложения натуральных чисел. Вычисление остатка при делении на 4. Тождественный алгорифм. Аннулирующий алгорифм. Алгорифм, применимый лишь к пустому слову. Удваивающий алгорифм Вычислить функцию в унарной системе счисления Приписать любое слово Q в конец исходного слова из алфавита A={a,b,c}.

  • Слайд 144

    Пусть заданы алфавиты A и A1. Если AA1, то алфавит A1называется расширением алфавита A . Нормальный алгорифм в каком-либо расширении A1 алфавита A называется нормальным алгорифмом над алфавитом A .

  • Слайд 145

    Принцип нормализации. Пусть задан произвольный вербальный алгорифмA в алфавите A. Тогда существует расширение A1алфавита A и нормальный алгорифмA1в алфавите A1с условием: произвольное слово P в алфавите A перерабатывается нормальным алгорифмомA1в тот же самый результат, в который слово P перерабатывается исходным вербальным алгорифмомA.

  • Слайд 146

    Операции над алгорифмами Маркова

    Два алгоритма М1 и М2 над алфавитом А называются вполне эквивалентными относительно А, если для любого слова Р в алфавите А выполняется М1(Р) М2(Р). Назовем функцию ϕ частично вычислимой по Маркову, если существует нормальный алгорифм М над К (К={*,1} ), вполне эквивалентный Мϕ (Мϕалгоритм в К) относительно К. Если функция ϕ определена всюду, то есть для любого набора из n натуральных чисел, и является частично вычислимой по Маркову, то назовем ее вычислимой по Маркову.

  • Слайд 147

    Пусть М – некоторый нормальный алгорифм в алфавите А, В – некоторое расширение А. В начало схемы алгорифма М добавим всевозможные формулы подстановки вида b→b, где b – буква из В\А. Полученная таким образом схема определяет некоторый нормальный алгорифм МВ в алфавите В, которые неприменим ни к одному слову, содержащему буквы из В\А, и такой, что МВ(Р) М(Р) для любого слова Р в А. Алгорифм МВ вполне эквивалентен алгорифму М относительно А и называется формальным распространением алгорифма М на алфавит А. Если М1 – нормальный алгорифм в алфавите А, и В есть расширение А, то нормальный алгорифм М2 в алфавите В, задаваемый схемой алгорифма М1, назовем естественным распространением алгорифма М1 на алфавит В.

  • Слайд 148

    Теорема14.1. Пусть М1,…,Mk – нормальные алгорифмы и А – объединение их алфавитов. Тогда существует нормальный алгорифм М над А, называемый соединением алгорифмов М1,…,Mk, такой, что М(Р) М1#(P)М2#(Р)…Mk#(P) для любого слова Р в алфавите А, где Mi# - естественное распространение Mi на А.

  • Слайд 149

    Теорема 14.2. Пусть М1, М2 и М3 – нормальные алгорифмы и А – объединение их алфавитов. Тогда существует нормальный алгорифм М над А такой, что: применимый к тем и только тем словам в А, к которым применим М3.

  • Слайд 150

    Теорема 14.3. Пусть М1 и М3 – нормальные алгорифмы и А – объединение их алфавитов, М11 и М33 – формальные распространения соответственно М1 и М3 на А. Тогда существует нормальный алгорифм М2 над А, являющийся повторением алгорифма М11, управляемым алгорифмом М33.

  • Слайд 151

    Раздел 3. Логические исчисления15. Логические связки

  • Слайд 152

    Высказывания Формулы Интерпретация Логическое следование и логическая эквивалентность Подстановки

  • Слайд 153

    Высказывания

    простые высказывания составные высказывания

  • Слайд 154

    Формулы

    ::= И|Л| | ¬) &| \/| | (формула)
  • Слайд 155

    Интерпретация

    А(х1,…,xn) – пропозициональная формула, где х1,…,xn–пропозициональные переменные. Конкретный набор истинностных значений, приписанных переменным х1,…,xn, называется интерпретацией формулы А.

  • Слайд 156

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

  • Слайд 157

    Теорема 15.1.Пусть А – некоторая формула. Тогда: если А – тавтология, то ¬А – противоречие, и наоборот; если А – противоречие, то ¬А – тавтология, и наоборот; если А – тавтология, то неверно, что А – противоречие, но не наоборот; если А – противоречие, то неверно, что А – тавтология, но не наоборот.

  • Слайд 158

    Теорема 15.2. Если формулы А и АВ – тавтологии, то формула В – тавтология.

  • Слайд 159

    Логическое следование и логическая эквивалентность

    Формула В логически следует из формулы А (АВ), если формула В имеет значение И при всех интерпретациях, при которых формула А имеет значение И. Формулы А и В логически эквивалентны (АВ), если они являются логическим следствием друг друга.

  • Слайд 160

    Теорема 15.3. (PQ)(¬P\/Q).

  • Слайд 161

    Теорема 15.4. Если А, В, С – любые формулы, то имеют место следующие логические эквивалентности: A\/A=A A&A=A A\/B=B\/A A&B=B&A A\/(B\/C)=(A\/B)\/C A&(B&C)=(A&B)&C A\/(B&C)=(A\/B)&(A\/C) A&(B\/C)=(A&B)\/(A&C) (A&B)\/A=A (A\/B)&A=A A\/Л=A A&Л=Л A\/И=И A&И=A ¬(¬A)=A ¬(A&B)=¬A\/¬B ¬(A\/B)=¬A&¬B A\/¬A=И A&¬A=Л

  • Слайд 162

    Теорема 15.5. P1&…&PnQ тогда и только тогда, когда (P1&…&Pn)Q - тавтология. Теорема 15.6. P1&…&PnQ тогда и только тогда, когда P1&…&Pn&¬Q – противоречие.

  • Слайд 163

    Подстановки

    Теорема 15.7. Если А(…х…) – тавтология и В- любая формула, то А(…х…){В//x} – тавтология.

  • Слайд 164

    Раздел 3. Теория алгоритмов15. Неразрешимые алгоритмические проблемы

  • Слайд 165

    Различные виды проблемы разрешения Проблемы, связанные с номерами функций Проблема остановки МНР Проблема самоприменимости Алгоритмические проблемы в логике и математике

  • Слайд 166

    Различные виды проблемы разрешения

    Разрешающим методом для подмножества A в множестве E называется такой метод (алгоритм), с помощью которого для каждого элемента x из E мы можем определить, принадлежит элемент x множеству A или нет. Разрешающим методом для функции f называется такой метод (алгоритм), с помощью которого вычисляется функция f.

  • Слайд 167

    Теорема 15.1 Подмножество A из E является разрешимым в E тогда и только тогда, когда его представляющая функция χ(x) является рекурсивной.

  • Слайд 168

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

  • Слайд 169

    Проблемы, связанные с номерами функций

    1. Даны номера xи yфункций φxи φy. Найти алгоритм, который по номерам xи yопределяет равенство функций φxи φy. 2. Найти алгоритм, который по номеру xопределяет, является ли функция φxпостоянной функцией. 3. Найти алгоритм, который по номеру xопределяет, будет ли бесконечным множество значений функции φx. 4. Найти алгоритм, который по номерам xи yопределяет, входит ли число yв область значений функции φx. 5. Найти алгоритм, который по числам x, y, zопределяет равенство φx(y)=z. 6. Найти алгоритм, который по номеру xопределяет, будет ли функция φxвсюду определенной функцией. 7. Найти алгоритм для определения включения xDx.

  • Слайд 170

    Теорема 15.2. Проблема распознавания всюду определенности функции φxпо ее номеру x алгоритмически неразрешима. Теорема 15.3. Проблема xDx алгоритмически неразрешима.

  • Слайд 171

    Проблема остановки МНР

    Теорема 15.4. Не существует алгоритма, который по машине Mx и ее начальным данным y определяет, остановится или нет машина Mx.

  • Слайд 172

    Проблема самоприменимости

    АлгорифмA называется самоприменимым, если он применим к своему изображению AИ. Теорема 15.5. Не существует алгоритма B для определения самоприменимости.

  • Слайд 173

    Алгоритмические проблемы в логике и математике

    Теорема 15.6. (А.Черч, 1936 г.). Не существует алгоритма, позволяющего для произвольной формулы F исчисления предикатов установить, является ли она тождественно истинной или нет. Теорема 15.7 (Ю.В.Матиясевич). Не существует алгоритма для распознавания по произвольному диофантовому уравнению, разрешимо ли это уравнение в целых числах.

  • Слайд 174

    Раздел 3. Теория алгоритмов16. Меры сложности алгоритмов

  • Слайд 175

    Понятие сложности алгоритмов Временная сложность алгоритмов NP-полные задачи

  • Слайд 176

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

  • Слайд 177

    Меры сложности алгоритмов:

    статическая сложность; динамическая сложность; временная сложность (вычислительная сложность); емкостная сложность.

  • Слайд 178

    Фундаментальные классы алгоритмов

    алгоритмы, сложность которых оценивается полиномом от размерности задачи (kn, kn2,kn3,...); алгоритмы с экспоненциальной оценкой сложности(2n, nn, n!...).

  • Слайд 179

    NP-полные задачи

    Свойства класса NP-полных задач: Никакую NP-полную задачу нельзя решить никаким известным алгоритмом полиномиальной сложности; Если будет найден полиномиальный алгоритм для какой-нибудь NP-полной задачи, то существуют полиномиальные алгоритмы для всех NP-полных задач.

  • Слайд 180

    Примеры NP-полных задач Задача о выполнимости булевых формул Кратчайшее решение «пятнашек» размера Задача коммивояжёра Проблема раскраски графа Задача о вершинном покрытии Задача о покрытии множества Задача о клике Задача о независимом множестве

  • Слайд 181

    Теорема 16.1 Если некоторая NP-полная задача разрешима за полиномиальное время, то P = NP. Другими словами, если в классе NP существует задача, не разрешимая за полиномиальное время, то все NP-полные задачи таковы.

Посмотреть все слайды

Сообщить об ошибке