WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

Pages:   || 2 |

«Кафедра информатики В.А. СТЕНЮШКИНА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Рекомендовано Ученым советом Государственного ...»

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Кафедра информатики

В.А. СТЕНЮШКИНА

МАТЕМАТИЧЕСКАЯ ЛОГИКА

И ТЕОРИЯ АЛГОРИТМОВ

Рекомендовано Ученым советом Государственного образовательного учреждения высшего профессионального образования «Оренбургский государственный университет»в качестве учебного пособия для студентов экономических и естественнонаучных специальностей Оренбург 2004 ББК 22.12я7 С 79 УДК [510.5+510.6](075.8) Рецензент кандидат технических наук, доцент Ю.Н.Пивоваров Стенюшкина В.А.

C 79 Математическая логика и теория алгоритмов: Учебное пособие.Оренбург: ГОУ ОГУ, 2004. – 106 с.

ISBN Пособие предназначено студентам экономических и естественнонаучных специальностей для выработки конструктивных знаний в области формальной логики и алгоритмизации ББК 22.12я7 ISBN © Стенюшкина В.А., 2004 © ГОУ ОГУ, 2004

ЧАСТЬ 1 МАТЕМАТИЧЕСКАЯ ЛОГИКА

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

Логика как искусство рассуждений зародилась в глубокой древности.

Начало формальной логики как науки о структуре суждений и умозаключений связано с именем Аристотеля (IV в. до н. э.).



Дедуктивные умозаключения, в которых из двух суждений следует новое суждение – силлогизмы – были проведены Аристотелем на категорических суждениях – суждениях типа:

А – общеутвердительное суждение «Всякое S суть Р»;

Е – общеотрицательное суждение «Никакое S не суть Р»;

I – частноутвердительное суждение «Некоторые S суть Р»;

О – частноотрицательное суждение «Некоторые S не суть Р».

Пример «первой фигуры» силлогизма: «Все люди смертны. Кай – человек. Следовательно, Кай смертен.»

Первый этап развития формальной логики – традиционная логика – длился два тысячелетия. Второй этап – современная логика - длится поныне. Другие имена этого этапа – символическая логика или математическая логика. Основы современной формальной логики заложили (середина XIX – начало XXв.в.) Дж. Буль, О. Морган, Г. Фреге, Дж. Пеано.

Традиционная логика опиралась на естественный язык, который из-за многозначности и аморфности требований к построению выражений и придания им смысла приводит к парадоксам. В средние века был распространен парадокс: “Сказанное Платоном – ложно, - говорит Сократ. – Сказанное Сократом

– истинно, - говорит Платон”. Современная логика использует формальные теории (ФТ), или исчисления.

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

Исчисление называется разрешимым, если существует алгоритм, позволяющий для любого высказывания определить, выводимо оно в этом исчислении или нет. Формальные теории являются развитием аксиоматического метода, приобретшего известность благодаря «Началам» Евклида (около 330 – 320 гг. до н.

э.). Предпринятое во второй половине XIX в. исследование аксиом евклидовой геометрии (ЕГ) показало, что система аксиом, данная в «началах» не полна. В 1899 г. Дж. Гильберт предложил первую достаточно строгую аксиоматику ЕГ.

К 1922 г. у Гильберта сложился план обоснования всей математики путем ее полной формализации и последующим «метаматематическим» доказательством непротиворечивости формализованной математики. А в 1931 году К. Геделем была доказана теорема о неполноте арифметики, из которой следовало, что для достаточно богатых по содержанию математических теорий не существует адекватных формализаций. Тем не менее, вся дальнейшая работа над логическими основаниями математики в большой мере идет по путям, намеченным Гильбертом. Дело в том, что на практике формальные теории, описывающие содержательные объекты, задаются с помощью собственных аксиом, которые наряду с собственно предикатами и функторами содержат предикаты и функторы, свойства которых аксиомами не описываются, а считаются известными в данной теории.

Язык, который мы изучаем (в данном случае язык ФТ), называется языком–объектом, а язык, на котором мы формулируем и доказываем различные результаты об этом языке – объекте, называется метаязыком. (Этот метаязык сам мог бы быть формализован и стать предметом исследования, которое, в свою очередь, проводилось бы на некотором метаязыке, и т. д.). Различию между «выводом в языке–объекте» и «доказательством в метаязыке» соответствует различие между теоремой языка – объекта и метатеоремой языка. Слово «метаматематика» употребляется, в частности, как название исследований логических и математических языков–объектов.

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

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

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

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

1.1 Высказывания. Логические операции Под высказыванием понимается любое предложение (естественного или формализованного языка), содержание которого оценено либо как истинное, либо как ложное.

Пример – Высказывание «Вода – продукт горения водорода» естественно считать истинным, а высказывание «Все числа вида 2n+1 – простые» - ложным.

В логике высказываний каждое высказывание отождествляется с его истинностным значением: «истина» (1) или «ложь» (0). Само установление истинностного значения отдельно взятого высказывания в логике высказываний не производится.

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

Рассмотрим наиболее распространенные логические операции /1/.

Отрицание – одноместная логическая операция («не») – по высказыванию А определяет высказывание A («не А» или «неверно, что А»), которое считается истинным тогда и только тогда, когда А – ложно.

Пример – А:=«Число 10 делится на 5», А:=«Неверно, что число 10 делится на 5».

Отрицание обозначается также символом « ¬ » или надчёркиванием.

Конъюнкция – двухместная логическая операция («и») – по высказываниям А, В определяет высказывание А В («А и В»), которое считается истинным тогда и только тогда, когда оба высказывания А, В истинны.





Дизъюнкция – двухместная логическая операция («или») – по высказываниям A, B определяет высказывание AВ («A или B»), которое считается истинным тогда и только тогда, когда хотя бы одно из высказываний A, B – истинно.

Пример – A:= «Дождь кончился», B:= «Птицы запели», A B:= «Дождь кончился, или птицы запели».

Импликация – двухместная логическая операция («если…, то…») – по высказываниям А, В определяет высказывание АВ («если А, то В»), которое считается ложным тогда и только тогда, когда А - истинно, В – ложно.

Пример – Пусть А:= «2*2=5» - ложно, В:= «Рим столица Италии» - истинно. Тогда A:=”Если 22=5, то Рим – столица Италии” – истинно.

В импликации АВ высказывание А называется посылкой, высказывание В – заключением. Из определения импликации следует, что в случае истинности обоих высказываний А, АВ высказывание В – истинно. Это соответствует основному из применяемых в математике правил вывода - Modus Ponens (Правило отделения).

Эквиваленция – двухместная логическая операция («если и только если…, то…») определяет высказывание А В («если и только если А, то В»), которое считается истинным тогда и только тогда, когда А, В имеют одинаковые истинностные значения (оба истинны или оба ложны).

Пример – «Квадратная матрица имеет обратную (А) если и только если определитель матрицы отличен от нуля (В)». Это высказывание истинно, если считать, что А, В истинны.

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

Пример – Пусть А, В – ложны, тогда высказывание (АВ)(АВ) ложно.

<

1.2 Булевы функции. Истинностные таблицы

Булева функция – n-местная функция из {0,1}n в {0,1}. Каждой nместной логической операции взаимно однозначно соответствует n-местная булева функция y=f(x1,…,xn), x1,…,xn, y{0,1}, где двоичные переменные

x1,…,xn, y соответствуют высказываниям (операндам и результанту) и называются пропозициональными переменными. Другие названия булевых функций:

логические функции, функции истинности.

Булеву функцию n переменных можно задать, таблицей истинности (таблица 1.1):

–  –  –

Булевы функции одной переменной: yi=fi(x), i=0..3 (таблица 1.2).

Булевы функции двух переменных: yi=fi(x1,x2), i=0..15. Приведём таблицы некоторых двухместных булевых функций (таблица 1.3).

Таблица 1.2

–  –  –

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

Пример – Составить таблицу истинности для высказывания А В Решение даётся таблицей 1.4.

–  –  –

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

Нормальная форма

–  –  –

Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций.

Путем тождественных преобразований любую булеву функцию можно привести к дизъюнктивной или конъюнктивной нормальным формам.

Если исходная функция содержит только основные связки (,,,, ), то сначала нужно элиминировать связки с помощью равенств:

x y = x y, x y = ( x y ) ( x y ) = ( x y ) ( x y );

затем продвинуть знак отрицания к переменным с учетом равенств

x y = x y, x y = x y;

устранить двойное отрицание, x = x. так как, Затем, используя одно из равенств: x(yz)=(xy)(xz), x(yz)=(xy)(xz) непосредственно получить дизъюнктивную или конъюнктивную нормальную форму.

Пример – Дана булева функция: ( x1 x 2 ) x3.

Выполним последовательно указанные преобразования:

–  –  –

Выражение справа есть совершенная дизъюнктивная нормальная форма.

Существование совершенной дизъюнктивной нормальной формы доказано.

Единственность доказывается от противного.

Для булевой функции f(x1,…,xn) по тождеству (1) имеем:

–  –  –

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

Пример –Пусть булева функция y=f(x1,x2,x3) задана таблицей 1.5.

–  –  –

2.3 Применение алгебры высказываний к описанию релейноконтактных схем (РКС) Под релейно-контактными схемами понимают схематическое изображение какого-либо устройства, состоящего из соединенных между собой двухпозиционных переключателей. Двухпозиционные переключатели могут находиться в двух состояниях: в замкнутом (ток проходит) и в разомкнутом (ток не проходит). Такие схемы можно описать в терминах алгебры высказываний. Каждому переключателю ставиться в соответствие высказывание, истинное при замкнутом переключателе и ложное – при разомкнутом. При этом удобно переключатели обозначать теми же буквами, что и высказывания. Если два переключателя работают так, что один из них замкнут, когда другой разомкнут, и наоборот, то они обозначаются соответственно А и.

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

Пример – Упростить схему (рисунок 2.1).

А1 А2 А3 А1 А2 А3 А1 А2 А3

–  –  –

Упрощенная схема (рисунок 2.2) имеет три переключателя вместо девяти в исходной.

А1 А2 А3

–  –  –

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

–  –  –

N-местным предикатом на множестве M называется n-местная функция Р(x1,…, xn), аргументы которой принимают значение из множества M, а сама функция принимает значения из множества {0(«ложь»), 1(«истина»)}. При n=1 предикаты называются унарными, n=2 – бинарными, n=3 - тернарными и т.д.

Нульместный предикат рассматривается как высказывание. Предикат задает отношение нам.

Примеры 1 M={1,2,3,…} – множество натуральных чисел;

а) Р(x):= «x делится на 2». Р(2)= «истина», Р(3)= «ложь»;

б) Р(x1, x2): «x1 x2». Р(1,2)= «ложь», Р(3,2)= «истина».

2 M=R=(-,+) – множество действительных чисел :

Р(x1, x2, x3)= «истина», x1+x2+x3=1, «ложь», в противном случае;

Р(1,0,0)=«истина»,Р(0,0,0)=«ложь» и т.д.

Предикат Р(x1,…, xn), определенный на M, называется тождественно истинным на M, если определяющая его функция Р(x1,…, xn)1; тождественно ложным, если Р(x1,…, xn)0, выполнимым, если Р(x1,…, xn) 0.

Пример – Предикат Р(x):= «|х|0», определенный на R, тождественно истинен на R.

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

Определенные элементы a1, a2,… из M называются предметными постоянными, а неопределенные элементы x1,…, xn из M – предметными переменными. При замещении предметной переменной хк, к1..n, предметной постоянной аM n-местный предикат Р(x1,…, xn) превращается в (n-1) местный предикат Р(х1,…,хк-1,a,хк+1,…,хn) и от хк уже не зависит. Если заместить все переменные постоянными, то получится высказывание, или нульместный предикат.

Пример - Р(x1, x2, x3):= «x1+x2=x3» - трехместный предикат; Р(x1, x2, 5):=

«x1+x2=5» - двухместный предикат; Р(2,3,5):= «2+3=5» - высказывание.

N-местным функтором на множестве M называется n-местная функция f(x1,…, xu), принимающая, как и аргументы, значения из множества M (то есть n-местный функтор задает n-местную операцию на M).

3.2 Операции над предикатами. Кванторы

Пусть Р(х), Q(x), хМ, для которых предикат Р(х) ложен.

Отрицанием предиката Р(х) на множестве M называется предикат Р(х) на том же множестве, истинный для тех и только тех значений хМ, для которых предикат Р(х) ложен.

Конъюнкцией предикатов Р(х), Q(x) на множестве M называется предикат Р(х)Q(x) на том же множестве, истинный для тех и только тех значений хМ, для которых оба предиката Р(х), Q(x) истинны.

Дизъюнкцией предикатов Р(х), Q(x) на множестве M называется предикат Р(х)Q(x) на том же множестве, истинный для тех и только тех значений хМ, для которых истинен хотя бы один из предикатов Р(х), Q(x).

Подобным образом вводятся предикаты Р(х) Q(x), Р(х)Q(x).

Пример – Даны предикаты: Р(х):= «х5», Q(x):= «х2», х{1,2,3,4,5} =М. Тогда Р(х):= «х5», Р(х)Q(x):=«2х5»; Р(1)Q(1)=0, Р(2)Q(2)=1.

Над многоместными предикатами операции определяются аналогичным образом. Так, отрицанием n-местного предиката на некотором множестве М называется n-местный предикат Р(x1,…, xn) на том же множестве М, истинный для тех и только тех наборов значений аргументов, для которых предикат Р(x1,…, xn) ложен.

Для предикатов вводится также специфические логические операции, или кванторы, - («каждый» или «для всех») – квантор общности и («существует» или «для некоторых») – квантор единичности.

Пусть Р(х), хМ – одноместный предикат. Тогда запись х Р(х) («для любого х Р(х)») означает высказывание, истинное, если Р(х) – тождественно истинен на М, и ложное, если Р(х) не является тождественно истинным на М;

запись х Р(х) («существует х такой, что Р(х)») означает высказывание, истинное, если Р(х) выполним на М, и ложное, если Р(х) невыполним на М.

Пример – Если Р(х):= «х2=1», хМ=(-,+), то х Р(х)=0, х Р(х)=1.

хР( х) = х Р( х), хР( х) = х Р( х).

Специфические равносильности:

Дадим определение квантификации для многоместных предикатов.

Пусть Р(х, х1,…,хn) – (n+1) – местный предикат, определенный на множестве M (n0). Тогда запись х Р(х, х1,…,хn) означает n – местный предикат на М, зависящий от х1,…,хn (и не зависящий от х) и принимающий значение «истина» для тех и только тех значений а1,…,аnМ переменных х1,…,хn, для которых одноместный предикат Р(х, а1,…,аn) является тождественно истинным на М; запись х Р(х, х1,…,хn) означает n-местный предикат на М, зависящий от х1,…,хn (и независящий от х) и принимающий значение «истина» для тех и только тех значений а1,…,аnМ переменных х1,…,хn, для которых одноместный предикат Р(х, а1,…,аn) является выполнимым на М. Предикат Р в записях х Р х Р называется областью действия квантора.

Пример – Пусть Р(х,у):= «ху», х, уR – двухместный предикат на множестве действительных чисел. Тогда предикаты х (xy), у (xy), х (xy), у (xy) - одноместные предикаты (первые два – тождественно ложные, вторые два – тождественно истинные), а предикаты х у (xy), у х (xy), xy(хy), y(xy) нульместные (ложные). Ещё можно составить четыре нульместных предиката (они окажутся истинными).

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

Примеры 1 Пусть предикат Р(х) задан таблицей на множестве М={1, 2}:Р(1)=1, Р(2)=0. Тогда высказывание хР(х) имеет значение «истина».

2 Определить истинностные значения высказывания х(Р(х) Q(f(х), а) если х{1,2}=М, а=1, а предикаты и функтор заданы таблицами 2.1 и 2.2.

–  –  –

Решение В результате подстановки значения константы получаем высказывание х(Р(х) Q(f (х), 1). Строим вспомогательную таблицу 2.3.

Таблица 2.3

–  –  –

Константы, переменные или функторы называются термами. Предикат, аргументами которого являются термы, называется также атомом.

3.4 Свободные и связанные вхождения переменных Вхождения переменных в атом называются свободными. Свободные вхождения переменных в предикаты Р и Q остаются свободными в предикатах Р, РQ. Вхождение переменой в предикат хР и хР называются связанными.

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

1 В предикате х(Р(х,у)уQ(у)R(х) первое и второе вхождения переменной х связаны, третье - свободно, переменная у связана.

2 Дан предикат х(Р(х,у,z)уQ(х,у)Q(х,у) S. Здесь Р(х,у,z) - трехместный, Q(х,у) - двухместный, S - нульместный предикаты. Требуется определить истинностное значение данного предиката при условиях: М={a, b}; S = 0; свободные вхождения переменных заменяются значениями -х=b, у=а, z=a; предикаты Р, Q заданы таблицей 2.4.

–  –  –

Решение Подставляя значение свободных предметных переменных и значение предиката S, получим высказывание х(Р(х,а,а) уQ(х,у)Q(b,а) 1, которое в силу Q(b, а)=0 заменяется на высказывание х(Р(х,а,ау Q(х,у).

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

–  –  –

4.1 Определение формальной теории Формальная теория (ФТ) - это четверка Т = (S, F, А, R) /2/, где S - алфавит - множество символов;

F - множество формул - множество правильно построенных цепочек символов из S;

А - множество аксиом подмножество множества F;

R - множество правил вывода - множество отношений на множестве F.

Множество S может быть конечным или бесконечным. Множество F чаще всего бесконечно, задается синтаксическими правилами. S и F в совокупности определяют язык формальной теории. Множество А может быть конечным или бесконечным; если бесконечно, то задается схемами и правилами их конкретизации. Множество R обычно конечно; будет предполагаться, что F n+1 (при некотором n), где Fn+1 - (n+1)-ая декартова степень множества F.

4.2 Выводимость. Разрешимость

Пусть F1,..., Fn, G- формула формальной теории Т, то есть F1,..., Fn,GF и пусть имеется правило R такое, что (F1, …, Fn, G). Тогда формула G называется непосредственно выводимой из формул F1,..., Fn по правилу.

F,..., Fn, при этом формулы F1,...., Fn называются посылками, Запись: 1 G а формула G - заключением.

Формула G называется выводимой из формул F1,..., Fn, в формальной теории Т, если существует последовательность формул Е1,...., Ek такая, что Еk= G, а любая из Еi, i = 1...(k - 1), есть либо аксиома, либо одна из исходных формул F1,...,Fn, либо непосредственно выводима из подмножества ранее полученных формул Ej1,…, Ej1, j1,...,jl i. Последовательность Е1,...., Еk называется при этом выводом формулы G из формул F1,..., Fn в теории Т.

Запись: F1,...,Fn |…G; формулы F1,..., Fn, называются гипотезами, формула G - тезисом. Знак теории Т можно опускать.

Формула, выводимая только из аксиом, называется теоремой теории Т.

Запись: | G (множество гипотез пусто).

При добавлении гипотез выводимость сохраняется, то есть если Г («гамма») и («дельта») - множества формул, причем Г| TG, то есть Г, | T G.

Примечание - По отношению к теоремам формальной теории теоремы о формальной теории называются метатеоремами.

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

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

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

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

Интерпретация I называется моделью формальной теории Т, если все теоремы этой теории выполняются в интерпретации I (то есть для всех выводимых из аксиом формул теории Т соответствующие высказывания в области истинны).

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

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

Формула называется выполнимой, если она истинна в некоторой интерпретации.

4.4 Непротиворечивость. Полнота. Независимость Формальная теория называется непротиворечивой, если в ней не являются одновременно выводимыми формула F и F.

Формальная теория называется полной, если каждому истинному высказыванию в соответствует теорема теории Т.

Система аксиом непротиворечивой теории Г называется независимой, ес ли никакая из аксиом не выводима из остальных по правилам вывода теории Т.

5 Исчисление высказываний Задача исчисления высказываний (ИВ) - описание всех тождественно истинных формул.

–  –  –

Теорема Если Г, А |L...В1, то Г |L... А В и обратно. Здесь Г - некоторое множество формул.

Доказательство прямой теоремы. Пусть Е1..., Еn – вывод - В из Г, А. При этом Еn =В. Применяя метод математической индукции по i (1 i n), то есть покажем, что Г|L АЕi; тогда при i =n прямая теорема будет доказана. Итак, пусть i = 1 (база индукции).

Рассмотрим вывод:

1) Е1; аксиома или посылка:

2) Е1 (А Е1); А1:{А/В, Е1 /А};

3) А Е1; МР: 1,2.

То есть Г|LА Е1 Далее по методу предположим, что Г|LА Еi для всех i k и рассмотрим Ek.. Здесь возможны случаи: либо Ek аксиома или посылка, тогда доказательство повторяет предыдущее, либо Еk получена по правилу МР из Ei, Ej;

причем i, j k, и Ej: = Еi Еk. В последнем случае, так как i, j k, то для Ei, Ej имеются выводы Г|LА Еi и Г|LА (Еi Еk ). Объединим эти выводы в один и достроим его до требуемого вывода:

1) A Ei;

2) A (Ei Ek);

3) (A (Ei Ek)) ((A Ei) (A Ek)); A2: {Ej./В, Ek /Сj};

4) (А Еi) (А Аk); МР: 2 3;

5) A Ek МР: 1 4.

Итак, для Ek вывод построен. Тогда по методу математической индукции заключаем, что для любого n имеет место выводимость Г|LА Еn. Поскольку Еn:=В, то Г|LАB. Прямая теорема доказана.

Доказательство обратной теоремы. Пусть имеем вывод Г|LА B, состоящий из формул. Достроим его:

1) А В;

2) А; гипотеза;

3) В; МР: 2, 3.

Таким образом, имеет место выводимость Г|LАB. Обратная теорема доказана. Теорема доказана.

Cледствие Если А|LВ, то |L A В и обратно. Доказательство Г: =.

–  –  –

Интерпретация ИВ в алгебру высказываний задается приписыванием в качестве значений:

-каждой пропозициональной переменной конкретного высказывания (с его истинным значением);

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

В результате интерпретации формула ИВ становится высказыванием, истинностное значение которого вычисляется в соответствии со структурой формулы и определением логических операций. «Лишние» скобки можно опускать.

Формула называется истинной в данной интерпретации, если соответствующее ей высказывание истинно; ложное - в противном случае.

6.2 Равносильные формулы

Две формулы ИВ называются равносильными, если они имеют одинаковые истинностные значения во всех интерпретациях.

Запись: А=В («А равносильно В»).

Имеют место следующие равносильности:

1 Коммутативность конъюнкции, дизъюнкции:

А В = В А, А В= В А.

2 Ассоциативность конъюнкции, дизъюнкции:

А (В С)= (А B) C, А (В С) = (А В) С.

3 Дистрибутивность конъюнкции относительно дизъюнкции, дизъюнкции относительно конъюнкции:

А(ВС) = (АВ)(АC)=(A(ВС)=(АD)(АС).

4 Законы де Моргана:

–  –  –

Формула в ЛВ называется тождественно-истинной, или тавтологией, если она истинна в любой интерпретации Формула ЛВ называется тождественно-ложной, или противоречием, если она ложна в любой интерпретации.

Очевидно, формула тождественно истинна тогда и только тогда, когда А тождественно ложна.

Формула ЛВ называется выполнимой если она истинна хотя бы в одной интерпретации.

Пример – Формула Р P выполнима, так как, например 0 1 = 1.

Основные примеры тавтологий:

Р Р (закон тождества);

P P (закон исключенного третьего);

P P (закон противоречия);

P P (закон двойного отрицания);

P (Q Р) (истина из чего угодно);

P (P Q) (из лжи что угодно);

(Р Q) Р Q (Modus Ponens);

(Р Q) Q P (Modus Tollens);

(Р Q) (Q R) (Р R) (закон силлогизма);

(Р Q) (Q P ) (закон контрапозиции).

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

Пример - Составить таблицу истинности для следующего высказывания:

(P Q) (Q P). Решение даётся таблицей 7.1.

7.2 Логическое следствие. Логическая эквивалентность Формула ЛВ называется логическим следствием формулы А, если В истинна во всех интерпретациях, в которых А истинна. Запись: А В («из А логически следует В»).

Пример - Имеет место логическое следование Р (Q Р) (Таблица 7.1).

Доказательство. Если Р=1, то как известно, QР=1 при любом Q (01=1,11=1).Тогда имеем очевидное следование 1 1.

Теорема Для того, чтобы А В необходимо и достаточно, чтобы формула А В были тавтологией.

Доказательство Необходимость Пусть А В. Тогда по определению логического следствия, если А = 1, то В = 1, то есть невозможен набор (А, В) = (1, 0). Это означает по определению импликации, что А В - тавтология.

Таблица 7.1 Р Р ( P Q) (Q Q Q Q Достаточность Пусть А В – тавтология.

Это означает, что (А, В) (1, 0), то есть, если А = 1, то В = 1. Тогда по определению логического следствия А В. Теорема доказана.

Формула В называется логическим следствием формул А1, …Аn, если В является логическим следствием формулы А1 … Аn, то есть А1 … Аn В.

Запись: А1,..., Аn В.

Теорема Для того, чтобы А1 … Аn В, необходимо и достаточно, чтобы формула А1 … Аn В была противоречием.

7.3 Подстановка

Если А - некоторая формула, в которую входит подформула В, то применяется запись: А (...В...).

Если С - некоторая формула, которую подставляют формулу А вместо всех вхождений В, то применяется запись: А (...В...) {С//В}. В случае подстановки необязательно всех вхождений символ «//» заменяется на «/».

Теорема 7.1 Если А (.

..х...) – тавтология и С - любая формула, то А (...х...) {С//х } – тавтология. Здесь В: =х).

Теорема 7.2 Если А (.

..В...) и С = В («равносильно»), то А (...В...) = А (...В...) {С/ В }.

Доказательство проводится путем анализа интерпретаций формул.

Две формулы логики высказываний называются логически эквивалентными, если каждая из них является логическим следствием другой. Запись: А В («А логически эквивалентно В»).

Теорема Для того, чтобы А В необходимо и достаточно, чтобы формула А В была тавтологией.

Доказательство. Если А = 1, то из А В следует, что В = 1. Если В = 1, то из В А следует, что А = 1 (по одной из двух предыдущих теорем). Это означает, что А = 1, тогда и только тогда, когда В = 1, то есть А = В во всех интерпретациях, и по определению эквиваленции А В = 1 во всех интерпретациях. Теорема доказана.

Следствие Для того чтобы две формулы логики высказываний были эквивалентными, необходимо и достаточно, чтобы они были равносильными.

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

–  –  –

8.1 Теоремы прямая и обратная Теоремы вида А В и В А называются взаимно-обратными. В конкретной ситуации одну из них называют прямой, другую – обратной. Очевидно, обратная обратной есть исходная теорема. Это означает, что если взять, например, за исходную теорему А В, то обратная ей будет В А, обратная к последней будет снова А В.

Для любой пары взаимно- обратных теорем может наблюдаться один из случаев:

а) обе теоремы верны;

б) прямая теорема верна, обратная неверна;

в) прямая неверна, обратная верна;

г) обе теоремы неверны.

Примеры 1 Пусть А:=«Число делится на 4»; В:=«Число делится на 2». Тогда прямая теорема А В верна, обратная В А неверна.

2 Пусть А: = «Фигура есть квадрат», В: = «Фигура есть ромб». Тогда и прямая и обратная теоремы неверны.

Если теорема А В верна, то А называется достаточным условием для В, а В – необходимым условием для А.

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

Пример - Если А:=«Число делится на 3», В:=«Сумма цифр числа делится на 3», то А есть необходимое и достаточное условие для В.

Теоремы противоположная и обратная противоположной

Теоремы вида А В и В А называются взаимно противоположными.

Пример - Если А В:=«Если функция дифференцируема (А), то она непрерывна (В)», то А В:=«Если функция не является дифференцируемой (А), то она не является непрерывной (В)». Как известно, в данном случае теорема АВ верна, теорема АВ неверна.

Закон контрапозиции Пусть А В – прямая теорема. Ей соответствуют теоремы: В А – обратная теорема, А В – противоположная, B A обратная противоположной.

Теорема Если прямая теорема верна, то верна обратная противоположной. Обратно, если теорема, обратная противоположной верна, то прямая верна.

Доказательство Известна тавтология (А В) (В А) – (закон контрапозиции, - то есть (А В) ( B A ), и первая часть теоремы доказана.

Для B, A эта часть теоремы принимает вид B A (АВ) – тавтология, и вторая часть, а вместе с ней теорема доказана.

Примечание - Теорема о теоремах называется метатеоремой по отношению к этим теоремам.

Методы математических доказательств

–  –  –

Основанием для такого перехода служат равносильности: А1 … Аn (А В)= A1 … An A B = А1 … Аn А В.

По способу проведения доказательства в математике делятся на два вида:

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

9 Свойства исчисления высказываний

9.1 Полнота

Имеют место следующие метатеоремы.

Теорема 9.1 Всякая теорема исчисления высказываний есть тавтология.

Теорема 9.2 Всякая тавтология является теоремой исчисления высказываний.

Таким образом, теоремами теории L являются тождества - истинные формулы и только они. А это означает, что формальная теория L, то есть классическое исчисления высказываний, является полной.

9.2 Непротиворечивость

Из теоремы 9.1 следует, что теория L непротиворечива. Действительно.

Любая теорема в L есть тавтология. Отрицание тавтологии не есть тавтология, то есть в L нет одновременной выводимости теоремы и ее отрицания, что соответствует определению непротиворечивости формальной теории.

9.3 Разрешимость

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

9.4 Исследование системы аксиом ИВ. Независимость

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

Известно, что каждая из схем аксиом А1, А2, А3 независима. Эта система аксиом предложена П.С. Новиковым; она весьма проста, но существует много других систем, работающих тоже хорошо.

Примеры 1 Гильберт, Аккерман, 1938:

- связки:, ;

- аксиомы: АА А; А АВ; АВ ВА, (В С) (АВ АС);

-правило: Modus Ponens.

2 Россер, 1953:

- связки:, ;

- аксиомы: А А А; А А В А; (А В) ( ( В С) (С А);

-правило: Modus Ponens.

3 Клини, 1952:

связки:,,, ;

- аксиомы:

А (В А) ;

А (ВС)) ((АВ) (А С);

А В А;

А В А;

А (В (АВ));

А (А В) ;

В (А В);

А С) ( (ВС) ( ( А В) С ));

(А В) ( ( А В) А ) ;

АА;

-правило: Modus Ponens.

10 Исчисление предикатов Задача исчисления предикатов (ИП) – описание всех тождественно- истинных предикатных формул.

10.1 Определение исчисления предикатов

–  –  –

Определение свободного и связанного вхождения переменных в формулы ИП аналогично (по синтаксису) определению для предикатов и рассмотрено в алгебре предикатов. То же относится и к понятию области действия кванторов.

Формула ИП, не содержащая свободных вхождений переменных, называется замкнутой.

Пусть F – формула, t – терм. Если никакое свободное вхождение переменной x в формулу F не лежит в области действия никакого квантора по переменной, входящей в терм t, то терм t называется свободным для переменной x в формуле F.

Примеры 1 Пусть F: = y Р(x)- формула; t: = y – терм. Тогда терм t является несвободным для переменной x в формуле F.

2 Терм f(x,z) свободен для переменной xв формуле yР(x,y)Q(x), но тот же терм f(x,z) не свободен для переменной x в формуле zy Р(x, y) Q (x).

11 Интерпретация исчисления предикатов

11.1 Интерпретация исчисления предикатов в алгебру высказываний Интерпретация ИП в алгебру высказываний определяется заданием множества M - области интерпретации и последующим приписыванием в качестве значений:

каждой предметной константе и каждой свободной переменной конкретного элемента из M;

каждой n – местной предикатной или функциональной переменной конкретного n – местного предиката или соответственно функтора на M;

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

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

Формула называется истинной в данной интерпретации, если соответст вующее ей высказывание истинно; ложной – в противном случае.

Заметим, что истинностное значение формулы зависит от выбора множества M. Так, формула (x1Р(x1)x2Р(x2)) истинна во всех интерпретациях, где M - одноэлементное множество, и не во всех, в противном случае.

11.2 Равносильности

Две формулы ИП называются равносильными, если они имеют одинаковые истинностные значения во всех интерпретациях. Запись: F = G («F равносильно G»).

Имеет место следующие равносильности:

1) x F(x) = x F(x), x F(x)= x F(x);

2) x(F(x) G(x)) = xF (x) xG(x), x(F(x) G(x))=F(x) xG(x);

3)x y F(x, y) =y x F(x, y), x y F(x, y)= y x F(x, y);

4)x (F(x)С) = x F(x) С, x (F(x) С)= x F(x) С;

5)x (F(x)С) = x F(x) С, x (F(x) С) = x F(x) С;

6)С x F(x) = x ( С F(x)), С x F(x) = x (С F(x)).

Эти равносильности называются также законами логики предикатов. Формула С не содержит вхождений переменной x.

Применяются, как и прежде. синтаксические сокращения: FG: = (F G) (G F), F G: = F С.

Раннее отмеченные законы F=F, (FС)=FG, (FG)= FG здесь тоже имеют место и используются.

С помощью равносильностей можно преобразовывать формулы.

12 Классификация формул логики предикатов

12.1 Тавтология. Противоречие. Выполнимая формула

Формула ЛП называется тождественно истинной, или тавтологией, если она истинна в любой интерпретации.

Пример - Формула (x1 Р(x1) x2 Р(x2)) не является тавтологией.

Формула ЛП называется тождественно ложной, или противоречием, если она ложна в любой интерпретации.

Формула ЛП называется выполнимой, если она истинна хотя бы в одной интерпретации.

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

Формула ЛП G называется логическим следствием формулы F, если G истинна во всех интерпретациях, в которых F истинна. Запись: F G.

Имеют место логические следования:

7)x(F(x)G(x)) xF(x)xG(x), x F(x) xG(x)x(F(x)G(x)) ;

8) xF(x) H x(F(x) H), xF(x) H x(F(x) H), где формула Н не содержит вхождений переменной х.

Формулы F и G называются логически эквивалентными, если они являются логическими следствиями друг друга. Запись: F G.

12.3 Подстановка

Пусть F(x) – формула, t – терм. Положим по определению F(t):= F(…x …) t//xТогда имеют место следующие теоремы.

Теорема 12.1 Формула xF(x)F(t),где t – терм, свободный для перемен ной x в формуле F, есть тавтология.

Теорема 12.2 Формула F(t) x F(x), где t – терм, свободный для переменной x в формуле F, есть тавтология.

12.4 Предваренная нормальная форма В логике высказываний были введены нормальные формы – конъюнктивная и дизъюнктивная. В логике предикатов первого порядка также имеется нормальная форма, называемая предваренной нормальной формой (ПНФ).

Формула ЛП F называется находящейся в ПНФ, если она имеет вид:

–  –  –

где Qi, i,= 1..n – один из кванторов (,), x i xj, если ij, F0 – формула, не имеющая кванторов.

Цепочка Q1 x1 … Qn xn называется предикатом, F0 – матрицей.

Пример - Формула xyz (Q(x,y) R(z)) находится в ПНФ.

Для любой формулы ЛП существует логически эквивалентная ей формула, находящаяся в ПНФ.

Приведение данной формулы ЛП к ПНФ можно произвести с помощью равносильностей (1-6) и следований (7-8).

Пример - Привести формулу x Р(x) x Q(x) к ПНФ.

Решение - x Р(x) x Q(x)= ((x Р(x)) x Q(x)= x ((x Р(x)) x Q(x)= x((Р(x)) Q(x)).

Следовательно, ПНФ для исходной формулы есть x(( Р(x)) Q(x)).

12.5 Скулемовская стандартная форма

Доказательство теорем сопутствует основной задаче логики предикатов – описание всех тождественно – истинных формул. Согласно методу резолюций вместо доказательства тавтологичности формулы доказывается, что отрицание формулы противоречиво. Для этого формула приводится к скулемовской стандартной форме, или стандартной форме. Ранее обсуждалось, как свести формулу ЛП к ПНФ. Дальнейшее преобразование касается матрицы и префикса. Техника сведения бескванторной формулы (здесь - матрицы) к конъюнктивной нормальной форме также показана ранее. Теперь займемся элиминацией (устранением) кванторов.

Пусть формула F находится в предваренной нормальной форме Q1 x1 … Qn xn F0, где F0 есть конъюнктивная нормальная форма.

Если Qr, 1 r n, есть квантор единичности в префиксе Q1x1…Qn xn, рассмотрим случаи:

1) никакой квантор общности не стоит в префиксе левее Qr. Тогда выбираем новую ( не встречавшуюся в формуле) константу с и заменяем все xr в F0 на с; вычеркиваем Qr xr из префикса;

2) имеется непустой список Qr1, …, Qrm, 1 r1 …rm r, всех кванторов общности, встречающихся в префиксе левее Qr. Тогда выбираем новый ( не встречавшийся в формуле функциональный символ f, заменяем все xr в F0 на f(xr1, …, xrm).

Выполняем эту процедуру для всех кванторов существования в префиксе.

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

Пример – Указать ССФ формулы x y z uv w P(x,y,z,u,v, w).

Ответ - y zv P(x, y, z, f(y, z), v,g(y, z, v)).

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

Пример – Имеется формула x y z (( Р (x, y) Q (x, z)) R (x, y, z).

Ее ССФ может выглядеть так: x (( Р(x, f(x) ) R (x), g(x))) Q (x, g(x)) R (x, f(x), g(x)))), которую можно представить множеством Р (x, f(x)) R (x, f(x), g(x)), Q (x, g(x)) R (x, f(x), g(x)).

Следующая теорема – основа метода.

Теорема Пусть S – множество дизъюнктов, которые представляют стандартную форму формулы F. Тогда F противоречива тогда и только тогда, когда S противоречива.

13 Применения логики предикатов

13.1 Строение математических теорем

Рассмотрим следующую теорему: «Если точка лежит на биссектрисе угла, то она равноудалена от сторон этого угла». Предусловием этой теоремы является предложение «Точка лежит на биссектрисе угла», а постусловием – предложение «Точка равноудалена от сторон угла». Оба условия являются предикатами. Обозначим их соответственно А(x) и В (x), xР, где Р –множество точек плоскости. Тогда рассматриваемая теорема состоит в том, что импликация предикатов А(x) В (x), то есть предикат «Если точка x лежит на биссектрисе угла, то она равноудалена от сторон этого угла», обращается в истинное высказывание при всех x из множества Р.

При помощи квантора общности это можно записать так:

x (А(x) В (x)), xР (13.1) Заметим, что словесная формулировка теоремы содержат описание множества объектов, о которых идет речь в теореме.

13.2 Методы доказательства теорем Приведем формулировку принципа математической индукции.

Пусть А(n) – произвольный предикат, заданный на множестве всех натуральных чисел. Высказывание n А(n) истинно, если истинно высказывание А(1) (k) (А (k) А(k+1)). (Этот принцип, заметим, является одной из аксиом, определяющих натуральный ряд чисел).

Под методом математической индукции понимают следующий способ доказательства. Сначала проверяют истинность высказывания А(1). Затем, предположив истинность высказывания А(k), доказывают истинность высказывания А (k+1). Если доказательство верно для любого натурального k, то в соответствии с принципом математической индукции высказывание А(n) признается истинным для всех n.

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

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

Имеют место следующие метатеоремы.

Теорема 14.1 Всякая теорема классического исчисления предикатов первого порядка есть тавтология.

Теорема 14.2 Всякая тавтология является теоремой классического исчисления предикатов первого порядка.

Вторая из этих теорем доказана К. Геделем (1930) и является утверждением о полноте классического исчисления предикатов первого порядка.

14.2 Непротиворечивость Теория К непротиворечива. Доказательство следует из теоремы 14.1 и аналогично доказательству о теории L.

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

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

15 Автоматическое доказательство теорем

15.1 Постановка задачи Алгоритм, проверяющий отношение

–  –  –

называется автоматическим доказательством теорем (АДТ). Здесь - множество посылок, S – заключение (формулы); T-формальная теория, - знак выводимости В общем случае такого алгоритма не существует, то есть не существует алгоритма, который для любых S, Г, T выдавал бы ответ «Да», если выводимость (15.1) имеет место, и ответ «Нет», в противном случае. В некоторых случаях подобные алгоритмы существуют. Например, в случае исчисления высказываний. Поскольку в ИВ теоремами являются общезначимые формулы (и только они), то для проверки выводимости достаточно построить таблицы истинности.

Частичным алгоритмом АДТ (из наиболее известных) является метод резолюций (МР). Для любого прикладного ИП первого порядка МР дает ответ «Да», если (15.1) имеет место, и дает ответ «Нет» или не дает никакого ответа («зависает»), в противном случае. (Напомним, прикладное ИП есть ИП, которое содержит предметные константы и или функторы, иили предикаты и связывающие их собственные аксиомы. ИП, не содержащее предметных констант, функторов, предикатов и собственных аксиом, называется чистым.)

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

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

Эта теорема лежит в основе МР, то есть используется идея «доказательства от противного».

В качестве противоречия принято использовать так называемую «пустую» формулу и обозначать «пустым» квадратом:.

15.3 Правило резолюции

Метод резолюций работает с предложениями. Напомним, предложение – бескванторная дизъюнкция литералов, а литералы – это формулы вида А, А, где А – атом. Далее будет показана методика перехода от формулы ИП к множеству предложений.

Правило резолюции для ИВ: пусть С1, С2 – предложения в ИВ, причем С1 = Р С1, С2 = Р С2, где Р – пропозициональная переменная, С1, С2 - предC1, C 2 ложения (в том числе, пустые); тогда правило вывода Rназывается C1'C 2' правилом резолюции. Здесь С1, С2 – резольвируемые предложения; С1С2 резольвента; R – название правила; Р, Р – контрарные литералы.

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

Правило резолюции для ИП: пусть С1, С2 – предложения в ИП, причем С1 = Р С1, С2 = Р С2, где P1, Р2 – литералы, имеющие наиболее общий унифи C1, C 2 катор ; тогда правило вывода R называется правилом резолюции.

C1'C 2' Здесь резольвента (С1С2) получена из предложения (С1С2) применением унификатора.

Напомним, формулы А (…, хi, …), В (…, хi, …) называются унифицируемыми, если существует набор подстановок хi хii =1, в результате которых будет выполняться равенство А (…, хi, …) = В (…, хi, …). Указанный набор называется общим унификатором, наименьший набор из возможных называется наиболее общим унификатором (НОУ). В подстановках используются обозначения хi – для переменных, хi – для формул, i =1 …n.

–  –  –

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

При повторных действиях возможны случаи:

1) В результате очередного применения правила резолюции получено пустое предложение. Это означает, что выводимость (15.2) установлена (теорема доказана);

2)Среди текущего множества предложений С нет резольвируемых. Это означает, что выводимости (2) нет ( теорема опровергнута);

3) Процесс продолжается, множество С пополняется, пустых предложений нет. Здесь не ясно.

Пример – Доказать теорему: L (((АВ) А) А) Решение: Проведем тождественные преобразования: (((АВ) А) А) = ( ( ( А В) А) А)= (((А В) А) А) = (А А) ( В А ) А.

Разбиваем на приложения и последовательно применяем правило резолюции:

1) А А

2) В А 3)..А

4) А (1, 3) 5) (3,4) Получена пустая формула. Теорема доказана.

15.5 Сведение формулы к множеству предложений

–  –  –

15.6 Обоснование метода резолюций Теорема Если Г – множество предложений, полученных из формулы S, то S является противоречием тогда и только тогда, когда множество Г невыполнимо.

Напомним, невыполнимость множества формул означает, что не существует интерпретации, в которой все формулы множества имеют значение «истина».

Пример – Даны высказывания F, G. Доказать, что F G.

F: = «Каждый, кто хранит деньги, получает проценты».

G:= «Если нет процентов, то никто не хранит деньги».

Решение Введем предикаты: М(х):= «х есть деньги»; I(х):= «х есть проценты»; S (х,y): = «х хранит y»; Е (х, y):= «х получает y». Перейдем к предложениям. При этом, очевидно, F=х (y (М(y) S(х, y)) z(I(z) Е (х, z)));

G = (х I(х)) (y z(М(y) S(z, y)))= х (I(х)) (y z (М(y) S(z, y)));

G=х ( I(х)) y z (М(y) S(z, y))= y zх ( I(х)) М(y) S(z, y)) z (I(z) М (а) S(b,а)), а/ y,b/ z.

Множество предложений:

1 ¬М(у) ¬S (х,y) I (f(х)), {F} 2 М(у) ¬S (х,y) Е (х, f(х)) { F} 3 ¬I(z) {G} 4 М(а) {G} 5 S (b,а) {G}

Вывод:

6 ¬S (х,а) I (f(х)), (1,4), а/ y 7 I (f(b)), (5,6), b/х 8, (3,7) f(b)/ z Получена пустая формула. Выводимость доказана.

Пример – Даны высказывания: F1:= « Том не может быть хорошим студентом, если неверно, что он способный и отец помогает ему»; F2 =«Том хороший студент только если его отец помогает ему». Доказать что F1F2.

Решение Пусть H(x) - «x-хороший студент» S(x)- «x-способный студент»;Р (х, y) – «y помогает х». Тогда F1: = (S(а) Р (а,b)) (Н(а)); F2: = Р(аb) Н (а)

Метод резолюций дает:

1 S(а) ¬Н (а) 2 Р (а, в) ¬Н (а) 3 ¬Р (а, в) 4 Н (а) 5 Выводимость доказана.

Задачи 1 Дать истинностную оценку высказываний:

а) В каждом ромбе диагонали взаимно перпендикулярны;

б) Число 3 есть делитель числа 19;

в) Число 1+28 – простое;

г) Картины Рериха загадочны;

д) Найдется число х, удовлетворяющее уравнению х2+1=0.

2 Из высказываний А:= «Испытания проведены», В:= «Программа выполнена» составьте высказывания:

а) АВ; б) АВ; в) АВ; г) АВ.

3 Данные высказывания: х1:= «Идет дождь», х2:= «Очень жарко». Запишите символически составные высказывания:

а) Неверно, что идет дождь и очень жарко;

б) Если не идет дождь, то очень жарко.

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

а) Давление падает, и система не работает;

б) Вычисления выполнены точно или конструкция несовершенна;

в) Проект разработал Андрей или Петр, а эксперимент выполнил Иван;

г) Если я поеду на автобусе, то опоздаю на работу, или я воспользуюсь такси;

д) Программа будет выполнена если и только если материалы поступят своевременно;

е) Андрей помогает Петру или Петр помогает Петру, или они помогают друг другу.

5 Даны высказывания: А:= «Все кошки серы» и В:= «Число 6-простое число». Определите истинное значение высказываний:

а)¬A;

б)AВ;

в)¬АВ;

г) А¬В;

д) АВ;

е) В.

6 Составить таблицу истинности для высказываний;

а) ¬х1х2;

б)(ху)х;

в) ¬(ху);

г)(ху)(yz)(xz).

7 Проверьте с помощью таблицы тождества:

а) xy=¬xy

б) x(xy)=x

в) x¬xy=xy

г)xyzxy¬zx¬y=x 8 Упростите следующее выражения:

а)¬xyzx¬y¬zxy¬z;

б)(xy)( ¬(xy) z)¬z(xy)(uv).

9 Составить нормальные формы для булевых функций:

а)y=x1x2;

б)y=x1/x2;

в)y=x1x2;

г) ¬(x(¬xz))(y¬z);

д) ¬(xy¬z)(xy);

е) (xy¬yz) ¬ (¬x u).

10 Выразить через,, операции:

а) ;

б) ;

с) ;

д).

11 Постройте переключательные схемы по формулам:

а) (х1 х2 ¬х3) (х1 х2 х3 х4);

б) (¬х1 (х2 ¬х3) ¬ х4) х1.

12 Запишите формулу, соответствующую переключательной схеме рисунка 16.1. Упростите эту формулу и постройте более простую схему:

А В С В А

–  –  –

13 Изобразите схематически множества истинности предикатов А(х), В(х) и покажите штриховкой множества истинности следующих предикатов:

а)¬А(х) ¬В(х);

б)¬ (А(х) В(х));

в) ¬А(х) ¬В(х);

г) ¬ (А(х) В(х)).

14 Контрольную работу, содержащую 3 задачи, выполняли 105 студентов.

Первую задачу решили 70 человек, вторую – 59, третью – 62. 90 студентов решили первую или вторую задачу, вторую или третью – 89, а первую или третью решили 91 студент. Сколько студентов решили все три задачи, если 6 студентов не решили ни одной задачи.

15 Пусть Е = е - множество европейцев. Рассматривается четыре предиката:

А (е): = «Европеец – гражданин Швейцарии»;

В (е): = «Европеец владеет немецким языком»;

С (е): = «Европеец владеет французским языком»;

Д (е): = «Европеец владеет итальянским языком»;

Тогда что означает высказывание: е (А (е) В (е) С (е) Д (е)).

16 Рассмотрим два определения легкой контрольной:

1) Контрольная называется легкой, если каждую задачу решил хотя бы один студент.

2) Контрольная называется легкой, если хотя бы один ученик решил все задачи.

Ответим на вопросы:

а) Может ли быть контрольная легкой в смысле первого определения и не легкой в смысле второго?

б) Может ли работа быть легкой в смысле второго определения и не легкой в смысле первого.

17 Имеется два конечных числовых множества А и В и некоторые высказывания о них:

1) Любое число из А больше любого числа из В;

2) Самое большое число из А больше самого большего числа из В;

3) Для любого числа из А найдется число из В, меньшее этого числа;

4) Каждое число из В меньше хотя бы одного числа из А;

5) Среднее арифметическое чисел из А больше среднего арифметического чисел из В.

Найдите среди этих высказываний эквивалентные.

18 Граф G = (V, E) определяется заданием непустого множества вершин V, множества ребер Е и трехместного предиката Р(х,е,у): = «Ребро е соединяет вершины х и у», который определен на всех упорядоченных тройках (х,е,у), причем х,у V, е Е. Для орграфа х считается начальный, а у – конечный вершинами дуги е.

Запишите предикаты, задающие:

а)подмножество дуг орграфа, исходящих из вершины а;

б)подмножество дуг орграфа, входящих в вершину b;

в)подмножество ребер графа, инцидентных вершине а;

г)подмножество ребер графа, соединяющих вершины а и b.

19 В соответствии с определением графа в задаче 18 расшифруйте высказывания:

а)ху ((ху) Р(х,е,у) Р (у,е,х)); б)х Р(х,е,х).

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

20 На множестве натуральных чисел определены предикаты: Р(х):= «Число х делится на 8» и Q(x): = «х – четное число»

Прочитайте следующие высказывания и выясните, какие из них истинны:

а) х Р(х);

б) х Р(х);

в) х Q(x);

г) х ¬Q(x);

д) х ¬Q(x);

е) х (Р(х) Q(x));

з) х (Q(x) Р(х)).

21 Пусть х – множество прямых на плоскости. На этом множестве определены предикаты: R (х,у): = «Прямая х пересекается с прямой у», S(х,у):= «Прямая х параллельна прямой у», причем х,у Х.

Прочитайте следующие высказывания и определите их истинность:

а) х у R(х,у);

б) ху ¬S (х,у));

в) ху (R (х,у) ¬S (х,у));

г) ху (R (х,у) S (х,у)).

22 На множестве натуральных чисел определены предикаты: Р(х):= «х – простое число», Q(x): = «х - четное число», R (х,у): = « х- не равно у». Переведите на русский язык высказывание:

х (Р(х) Q(x)) ¬х (Р(х) Q(x) у (R (х,у) Р(у) Q(у))).

23 Запишите предикаты для высказываний:

а) Каждый студент изучает (один язык) или английский, или немецкий, или французский язык;

б) Некоторые устройства укомплектованы осциллографами;

в) Не все телевизоры работают хорошо;

г) Ни один прибор не оказался забракованным.

24 Установите истинностное значение предикатов:

а) Если некоторые транзисторы негодные и все транзисторы проверяются, то среди проверенных транзисторов найдутся негодные;

б) Никто из спортсменов не изучает иностранных языков, если все инженеры изучают иностранный язык и некоторые из них – спортсмены.

25 Дан предикат х (Р(х,у,z) у Q(x,у)) Q(x,у) ¬S. Здесь Р(х,у,z) – трехместный, Q(x,у) – двухместный, S – нульместный предикат. Требуется определить истинностное значение данного предиката при условиях: М = а, в, S = 0; х=b, у=а, z=а; предикаты Р, Q имеют таблицу 1:

xуz Р (х, у, z) Q(x, у) ааа 0 0 ааb 1 аbа 1 0 аbb 0 bаа 0 0 bаb 1 bbа 0 1 bbb 1

в) L¬А (АВ);

г) L (¬В ¬А) (А В);

д) L(АВ) (¬В ¬А);

е) LА(¬В ¬(АВ)) 27 В теории L доказать выводимость:

а) АВ, ВС, А С;

б) АВ, В С А С;

в) D, АВ, D С, С В, А С;

г) РQ R, Q P, Q R.

28 Дано высказывание: «Для того, чтобы матрица имела обратную, необходимо чтобы ее определитель был отличен от нуля. Какие из приведенных ниже высказываний логически следует из данного?

а) Для того, чтобы матрица имела обратную, достаточно, чтобы ее определить был равен нулю.

б) Для того, чтобы определитель матрицы был отличен от нуля, достаточно, чтобы эта матрица имела обратную.

в) Для того, чтобы определитель матрицы был равен нулю, необходимо, чтобы эта матрица не имела обратной.

г) Матрица имеет обратную тогда и только тогда, когда её определитель не равен нулю.

29 Докажите логическое следствие (Р Q) (R S) (S Q T) T ¬ P R через соответствующую тавтологию; с помощью правил вывода; дедуктивным способом.

30 Докажите равносильность высказываний Х (Х ¬ (Y Z)) и ¬X Y Z. Представьте эту равносильность в виде логических следствий.

31 Упростите следующую систему высказываний: А (В С); В ¬ (А С); С (А В); А (В С); ¬A¬CB;А В С. Приняв для А, В, С некоторые высказывания, сформулируйте сложное высказывание исходной и упрощенной систем.

32 Исследуйте каждую из приведенных ниже систем высказываний на противоречивость:

а) А ¬В ¬С; (D Е) F; F¬ (G H); ¬С Е F;

б) (А В) С D; D Е F; А ¬F;

в) (А В) (С D); (В D) (¬С А); (Е F) (F ¬ D); ¬ Е Е;

г) (А В С) (D В Е); (F А) G Н; (G Н) F D; ¬(С Е);

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

33 Запишите в символической форме и установите логичность следующих рассуждений:

а) Если заменить лампу (А), телевизор будет работать (В) при условии, что напряжение подключено (С). Лампа заменена, а напряжение не подключено. Следовательно, телевизор не будет работать.

б) Если поднять давление (А) или увеличить температуру (В), то реакция произойдет быстрее (С), но опасность повысится (Д). Если опасность повысится, то необходимо принять меры защиты (Е). Меры защиты не приняты. Следовательно, давление поднимать нельзя.

в) Если упростить схему (А), стоимость снизится (В), и если применить новые элементы (С), надежность увеличится (Д). Можно или упростить схему, или применить новые элементы. Однако, если упростить схему, то надежность не увеличится, а если применить новые элементы, то стоимость не снизится.

Итак, надежность увеличится тогда и только тогда, когда стоимость снизится.

34 Свободен ли терм f (х1,х2) для х1 в формулах А1 (х1,х2) х2 А2 (х2), х2А(х2,а1)) х2А(х1,х2)?

35 Указать свободные и связанные вхождения переменных в следующие формулы:

х3 (х1А (х1,х2) А (х3,х1));

1) х2А (х3,х2) х3А(х3,х2);

2) (х2 х1А1 (х1,х2, f1 (х1,х2))) х1А2 (х2, f2(х1)).

3) 36 Даны формулы:

1) А1^2 (f1^2 (x1,x2),a1);

А1^2 (x1,x2) А1^2 (x2,x1);

2) х1 х2 х3 (А1^2 (x1,x2) А1^2 (x2,x3) А1^2 (x1,x3).

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

а) Область интерпретации – множество всех целых положительных чисел;

А1 (y,z), f12(x,z), a1 интерпретируется соответственно как y z, yz, 1.

б) Область интерпретации – множество всех множеств целых чисел, А12 (y, z), f12(y, z), а1 интерпретируются соответственно как yz, z y, (пустое множество).

37 Показать, что следующие формулы не являются общезначимыми:

а) ((х1А11(х1) х 1А21(х1)) ((х1(А11(х1) А21(х1)));

б) (х1(А11(х1) А21(х1))) ((х1 А11(х1)) (х1 А21(х1))).

38 Показать, что следующие формулы логически общезначимы:

а) хi хj F хj хi F;

б) хi хj F хj хi F;

в) хi F хi F;

г) хi F хi F.

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

а) Для любого множества х существует множество у такое, что мощность у больше мощности х. Если х включено в у, то мощность х не больше мощности у. Всякое множество включено в V. Следовательно, V – не множество.

б) Если всякий предок предка данного индивидуума есть также предок того же индивидуума, и никакой индивидуум не есть предок самого себя, то должен существовать некто, не имеющий предков.

40 Даны высказывания:

F: = «Каждый, кто хранит деньги, получает проценты»;

G: = «Если нет процентов, то никто не хранит денег»

Доказать: F G.

41Записать в виде категорических высказываний:

а) «Не все телевизоры работают хорошо»;

б) «Ни один прибор не оказался забракованным».

42Имеются посылки:

F1: = «Таможенные чиновники обыскивают каждого, кто въезжает в страну, кроме высокопоставленных лиц», F2: = «Некоторые люди, способствующие провозу наркотиков, въезжали в страну и были обысканы исключительно людьми, способствующими провозу наркотиков»;

F3: = «Никто из высокопоставленных лиц не способствовал провозу наркотиков».

Предполагаемое заключение G: = «Некоторые из таможенников способствовали провозу наркотиков. Доказать: F1, F2, F3 G.

Указание - Применить метод резолюций.

43 Король думает, что королева думает, что она не в своем уме. В своем ли уме король?

44 Посылка: «Студенты – граждане». Заключение: «Голоса студентов – голоса граждан». Вывести методом резолюций.

45 Пусть F1 и F2 таковы:

F1: х (Р(х)Q(x)), F2: Q(a).

Доказать, что Р (а) есть логическое следствие F1 и F2.

46 Восстановить скобки в выражениях:

а) х2 А11(х1) А23(х1,х2,х3) х1 А21(х1);

б) х1 А11(х1) х2 А21(х2) А12(х1,х2) А11 (х2).

47 Перевести следующие предложения на язык формул:

а) Все рыбы, кроме акул, добры к детям;

б) Не все птицы могут летать;

в) Ты можешь обманывать кое-кого все время, ты можешь обманывать всех некоторое время, но ты не можешь обманывать всех все время;

г) Если кто- нибудь может сделать это, то и Джон может.

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

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

Построить по возможности простую электрическую цепь, через которую ток проходил бы тогда и только тогда, когда не менее двух членов комитета голосуют «за»;

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

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

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

б) Люди могут мыслить. Машины - не люди. Следовательно, машины не могут мыслить.

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

а) Если вечер скучен, то или Алиса начинает плакать, или Анатоль рассказывает смешные истории. Если Сильвестр приходит на вечер, то или вечер скучен, или Алиса начинает плакать. Если Анатоль рассказывает смешные истории, то Алиса не начинает плакать. Сильвестр приходит на вечер тогда и только тогда, когда Анатоль не рассказывает смешные истории. Если Алиса начинает плакать, то Анатоль рассказывает смешные истории.

б) Если курс ценных бумаг растет или процентная ставка снижается, то либо падает курс акций, либо налоги не повышаются. Курс акций понижается тогда и только тогда, когда растет курс ценных бумаг и налоги растут. Если процентная ставка снижается, то либо курс акций не понижается, либо курс ценных бумаг не растет. Либо повышаются налоги, либо курс акций понижается и снижается процентная ставка.

ЧАСТЬ 2 ТЕОРИЯ АЛГОРИТМОВ

Введение

Понятие алгоритма занимает одно из центральных мест в современной математике.

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

Слово «алгоритм» происходит, по мнению многих, от имени узбекского математика ал – Хорезми, который в IX веке разработал правила четырех арифметических действий над числами в десятичной системе счисления. С другой стороны, вычислительные процессы, с помощью которых искомые величины определялись из известных величин по заданным правилам, стали возникать в математике на самых ранних ступенях ее развития (Древний Египет, Вавилон, Древняя Греция). В книге Евклида «Начала» (около 300 г до н. э.) имеется алгоритм нахождения наибольшего общего делителя двух чисел, который, не исключено, был известен и ранее. Представим его в виде рекурсивной процедуры.

Вход: неотрицательные целые числа а, b (аb).

Выход: НОД (а,b).

Евклид (а, b) 1 если b=0 2 то НОД а 3 иначе НОД Евклид (b, а mod b) Реализация: Евклид (30,21) = Евклид (21,9) = Евклид (9,3) = Евклид (3,0)=3; НОД (3,21)=3.

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

Отметим несколько общих свойств алгоритмов.

1) Всякий алгоритм применяется к входным данным и имеет результатом выходные данные. На элементарных шагах появляются промежуточные данные. Данные должны быть специфицированы, в частности, указан алфавит данных и способы построения сложных данных из простых. Примерами данных могут быть числа, массивы чисел, изображения на экране и т. д.

2) Единицы объема данных и памяти ЭВМ должны быть согласованы. В прикладных алгоритмических моделях объем данных можно измерять числом ячеек памяти, в которых данные размещены. При этом исходят из того, что память ЭВМ состоит из одинаковых ячеек, каждая из которых может содержать один или несколько символов алфавита данных.

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

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

5) Если способ получения результата на каком-либо шаге неприменим, то должно быть указано, что считать результатом выполнения алгоритма.

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

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

6) Начальная система величин может выбираться из некоторого потенциально бесконечного множества, что должно являть массовость алгоритма.

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

Имеется три крупных класса алгоритмов: вычислительные (работают с числами, числовыми матрицами и другими числовыми структурами); информационные (работают с большими объемами данных – базами данных – решают задачи поиска, записи, сортировки записей); управляющие (формируют управленческие воздействия на внешние процессы в соответствии с поступающей от них информацией).

Еще следует сказать о детерминированности и корректности алгоритма.

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

Приведенное толкование понятия «алгоритм» называется интуитивным.

Оно хотя и нестрогое, но практически не требовало уточнения до двадцатых годов ХХ века, когда возникли так называемые массовые проблемы. Массовая проблема – проблема, когда требуется найти единый метод для бесконечной серии однотипных задач. Пример: построить алгоритм для выяснения имеются ли целые корни у уравнения Р(х1,…,хm)=0, где Р (х1,…,хm)- произвольный многочлен с целыми коэффициентами от любого числа m переменных. Задача точного определения алгоритма стала одной из центральных математических проблем. Возникла теория алгоритмов, изучаются общие свойства алгоритмов.

В 1936 году А. Черч опубликовал первое уточнение вычислимой функции, а А. Тьюринг и Э. Пост дали первые уточнения понятия алгоритма в терминах идеализированных вычислительных машин. В дальнейшем А.А. Марков предложил ввести понятие «нормального алгоритма». В рамках этих уточнений упомянутая ранее алгоритмическая проблема, известная как 10-я проблема Гильберта, оказалась неразрешимой.

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

Приложения теории алгоритмов имеются во всех областях математики.

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

–  –  –

1.1 Понятие вычислимой функции. График вычислимой функции Вычислимые функции (ВФ) – одно из основных понятий теории алгоритмов. Функция f называется вычислимой, если существует алгоритм, перерабатывающий всякий объект х, для которого определена функция f, в объект f(х) и не приводящий к результату ни для какого х, для которого f не определена /3/.

Графиком ВФ называется множество пар вида (х, f(х)).

Примеры 1 х – любое натуральное число, f(х)=х2;

2 х – пара рациональных чисел х1, х2, f(х)=х1:х2 (эта функция определена лишь для тех х, у которых х20);

3 X – пара матриц X1, X2 с целочисленными элементами, f(X)=X1*X2 (эта функция определена лишь для тех X, у которых число столбцов в X1 равно числу строк в X2) Аргументами и значениями вычислимых функций могут быть лишь конструктивные объекты, так как только такими объектами могут манипулировать алгоритмы.

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

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

1.2 Разрешимые и перечислимые множества

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

Про алгоритм А говорят, что он:

- «вычисляет функцию f», если его область применимости совпадает с областью определения f, и А перерабатывает любой х из своей области применимости в f(х);

- «разрешает множество М относительно множества Х», если он применим к любому х из Х и перерабатывает любой х из ХМ в слово «да», а любой х из Х\М – в слово «нет»;

- «перечисляет множество М», если его область применимости есть натуральный ряд, а совокупность результатов есть М.

Множество называется разрешимым относительно Х, если существует разрешающий его относительно Х алгоритм. Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм.

Обнаружены результаты (путем анализа понятия «алгоритм»):

- область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества;

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

Теорема 1 Функция f вычислима тогда и только тогда, когда перечислим ее график.

Теорема 2 Подмножество М перечислимого множества Х тогда и только тогда разрешимо относительно Х, когда М и Х\М перечислимы.

Теорема 3 Если Р, Q перечислимы, то Р Q, Р Q также перечислимы.

Теорема 4 В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением. (В силу теоремы 2 это перечислимое подмножество будет неразрешимым относительно Х).

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

Теоремы 4, 5 в совокупности дают пример алгоритма с неразрешимой областью применимости.

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

2 Формальная теория вычислимости

2.1 Рекурсивные функции.

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

2.1.1 Операции над числовыми функциями

Здесь под числами понимаются натуральные числа или ноль. Обозначим эту совокупность через N={0, 1, 2,...}. Пустое множество обозначается. Частичные функции из N…N=N(k) в N называются k - местными числовыми функциями. Операции над числовыми функциями называются операторами.

Определение Пусть f1,...,fn - частичные функции переменных x1,...,xm, определенные на множестве A со значениями в множестве B, f - частичная функция n переменных, определенная на множестве B, со значениями в множестве C. Тогда говорят, что частичная функция g m переменных, определенная на множестве A со значениями в множестве C равенством g(x1,...,xm) = f(f1(x1,...,xm),...,fn(x1,...,xm)), получается операцией суперпозиции из функций f, f1, …, fn. Обозначение операции суперпозиции: Sn+1 (индекс вверху означает число функций).

Определение Числовые функции s1(x)=x+1, оn(x1,…,xn)=0, Inm(x1,…,xn)=xm (1mn, n=1,2,…) называются простейшими. (Индекс 1 иногда будем опускать).

Пример - I23(I12, I13, I22) = I13.

Определение Пусть заданы числовые частичные функции: g - n -местная, h - (n+2) - местная, f - (n+1) - местная, причем

–  –  –

Равенства (2.1) или (2.2) позволяют последовательно вычислять значения функции в точках y=0, 1, 2,... по значениям функций g и h.

Обозначение операции рекурсии:

f = R(g, h), (2.3) где операция R - двуместная операция, определенная на множестве F всех частичных функций. Если g, h определены всюду, то f определена всюду.

–  –  –

2.1.4 Операция минимизации. Частично рекурсивные функции Пусть f - n-местная частичная числовая функция, и известен механизм ее вычисления (в интуитивном смысле), причем механизм работает бесконечно тогда и только тогда, когда значение функции не определено.

Рассмотрим относительно y уравнение f(x1,...,xn-1,y)=xn Будем давать переменной y значения 0,1,2,... последовательно и вычислять значения функции f соответственно (при фиксированных x1,...,xn). Определим частичную функцию Mf аргументов x1,...,xn следующим образом.

Положим ее значение y=a, если выполнены условия:

1) значение f(x1,...,xn-1,y) определено для y=0,1,...,a-1, и f(x1,...,xn-1,y)xn ;

2) f(x1,...,xn-1,a)=xn.

Если для набора (x1,...,xn) числа a, удовлетворяющего указанным условиям, не существует, значение y будем считать неопределенным.

Определение Оператор M, переводящий функцию f в функцию Mf, называется оператором минимизации. Если заданная функция f одноместна то функция Mf называется обратной функцией для f и обозначается f-1.

Примеры 1 Для функций sg и s обратными будут функции x, x = 0, 1 x 1, x 0 sg 1 x = ; s 1 ( x) =.

не существует, x 1 не существует, x = 0 2 Рассмотрим функцию y+z. Составим уравнение y+z=x и будем давать переменной z значение 0,1,.... Получим частичную функцию x-y, определенную для xy;

Определение Частичная функция f называется частично рекурсивной, если она может быть получена из простейших функций o, s, Imn конечным числом операций суперпозиции, примитивной рекурсии и минимизации.

Примечание - Класс частично рекурсивных функций шире класса примитивно рекурсивных. (Хотя бы потому, что примитивно рекурсивные функции всюду определены, а среди частично рекурсивных встречаются неопределенные всюду).

2.1.5 Тезис Черча

Значение понятия частично рекурсивной функции состоит в следующем.

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

ТЕЗИС ЧЕРЧА Класс алгоритмически (или машинно) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций.

2.1.6 Общерекурсивные функции

Определение Операция Ml, определяемая соотношением Mf, если Mf определена всюду, Ml f = не определена, в противном случае, называется слабой минимизацией функции f.

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

Примечание - Общерекурсивные функции всюду определены.

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

Доказательство следует из определения слабой минимизации.

Теорема Каждая всюду определенная частично рекурсивная функция общерекурсивна.

Доказательство этой теоремы очень тонкое и здесь не приводится.

Лемма 1 Каждая примитивно рекурсивная функция является общерекурсивной.

Доказательство следует из определения общерекурсивной функции.

Лемма 2 Класс общерекурсивных функций шире класса примитивно рекурсивных функций.

Доказательство следует из построения общерекурсивных функций, не являющихся примитивно рекурсивными. Примером такой функции является функция Аккермана /3/.

2.2 Регистровые машины. Машина Тьюринга

Регистр – это типовой блок в ЭВМ, используемый для хранения одного машинного слова, а также для некоторых манипуляций с этим словом. Регистры всегда входят в состав арифметического устройства, устройства управления, памяти ЭВМ и многие другие блоки. Регистр состоит из линейной цепочки отдельных разрядов, каждый из которых может хранить один бит информации. В зависимости от того, как работают эти цепи, выделяются много типов регистров: адресный, буферный, индексный, регистр команды и другие. Наиболее важными моделями вычислительных устройств регистрового типа являются машина с произвольным доступом к памяти (РАМ – равнодоступная адресная машина) и машина Тьюринга (МТ). В ходе развития теории алгоритмов у А.

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

1 ) Внешняя память – конечная лента, разбитая на конечное число ячеек.

–  –  –

В процессе работы машины к существующим ячейкам машина может пристраивать новые ячейки, так что лента может считаться потенциально неограниченной в обе стороны. Каждая ячейка ленты может находиться в одном из конечного множества состояний. Совокупность их называется внешним алфавитом А={а0,а1,…,аm}. Пустые состояния обозначаются а0. В процессе работы машины ячейки ленты могут изменять свои состояния. Просмотр ленты осуществляется слева направо. В каждый такт времени лента имеет некоторую длину r, то есть r ячеек. Состояние ленты описывается словом aj1 aj2 … ajk …ajr, где aj1

– состояние первой слева ячейки, aj2 – второй и т.д. Пустые символы слева и справа можно опускать.

2) Внутренняя память машины – устройство, о котором известно, что в каждый такт времени оно находится в некотором состоянии. Алфавит внутренних состояний, или внутренний алфавит Q = q0,q1,…,qn, где q0 – стоп-символ, или символ заключительного состояния, q1, как правило, - символ начального состояния.

3) Указатель – устройство, которое может перемещаться вдоль ленты так, что в каждый такт времени оно указывает на определенную ячейку ленты.

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

4) Устройство управления – воображаемый механизм, который в зависимости от состояния воспринимаемой ячейки и состояния внутренней памяти может изменить состояние воспринимаемой ячейки и положение указателя, сдвинув его на соседнюю ячейку влево или вправо. При этом, если необходимо, пристраиваются новые ячейки. Если в некотором такте времени внутренняя память машины приходит в заключительное состояние q0, то дальнейших изменений в машине не происходит, и машина называется остановившейся.

Состоянием машины Тьюринга, или конфигурацией, называется слово aj1 aj2 … qi ajk …ajr, образованное вставкой символа внутреннего состояния перед символом обозреваемой ячейки в слове состояния ленты. Это слово конфигурации называется машинным словом.

Работа машины состоит в том, что из данного состояния по истечении такта времени она переходит в следующее состояние и так далее. При этом, если машина, имея внутреннее состояние qi и воспринимая ячейку в состоянии aj, переводит внутреннюю память в состояние qs, изменяет aj на аt и передвигает указатель, то говорят, что машина выполняет команду qiaj qsаt D, где D – один из символов: L – сдвиг влево, R – сдвиг вправо, Е – нет сдвига. Совокупность всех команд, которые может выполнять машина, называется ее программой.

Предполагается, что для каждой пары qi aj имеется не более одной команды.

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

Пример - Пусть А = 0,1, Q = q0, q1, q2, программа Р = q10 q20 R, q20 q01Е, q11 q11 R, q21 q21R, начальное слово µ0 = q111. Тогда, применяя символ перехода состояний =, имеем: q11= 1 q11= 11 q10= 110 q20= 110 q01. Обозначая заключительное слово через µ и символ перехода с произвольным числом тактов, можно записать: µ0 P µ. Если за конечное число шагов внутреннее состояние переходит в q0, то говорят, что машина Тьюринга применима к данному слову. В противном случае машина Тьюринга называется «работающей вечно», или неприменимой к данному слову. В частности, возможно зацикливание или отсутствие подходящей команды. Существует много модификаций машин Тьюринга, в том числе, многоленточные МТ, имеющие по одному или несколько указателей на каждой из лент. Есть основания считать, что уточнение общего представления об алгоритме в алфавите, произведенное с помощью МТ, является адекватным. В теории алгоритмов известно следующее соглашение.

ТЕЗИС ТЬЮРИНГА Для всякого алгоритма А в каком- либо алфавите может построен тьюринговый алгоритм, дающий при одинаковых исходных данных те же результаты, что и алгоритм А.

Согласно этому тезису, всякая вычислимая в интуитивном смысле функция вычислима с помощью некоторой МТ. Принятие тезиса Тьюринга равносильно принятию тезиса Черча для частично рекурсивных функций.

2.3 Нормальные алгоритмы Наряду с рекурсивными функциями и машинами Тьюринга нормальные алгоритмы (НА) получили известность в качестве одного из наиболее удобных уточнений общего интуитивного представления об алгоритме. Понятие НА было выработано А.А. Марковым (1947).

Нормальные алгоритмы оперируют со словами конечной длины, преобразуя их друг в друга с помощью подстановок, то есть замены одних частей слова на другие. Любой нормальный алгоритм в фиксированном алфавите А вполне определяется указанием его схемы – упорядоченного конечного списка подстановок типа UV (U заменяется на V), где U, V – слова в алфавите А. Заключительная подстановка записывается в виде U • V.

Нормальный алгоритм работает следующим образом. Пусть Р – заданное слово в фиксированном алфавите. Принимаем его за начальное слово Р0 и строим следующее слово Р1. Если слово Рi (i 0) построено и работа алгоритма не закончена, то просматриваются подстановки (слева направо) и первая подходящая применяется. Если эта подстановка заключительная, работа заканчивается успешно, если не заключительная, то построено слово Рi +1 и процесс продолжается. Если нет подходящей подстановки, алгоритм не применим к данному слову. Возможна также бесконечная работа алгоритма – неуспех.

Пример - Дан алфавит русского языка и схема S = я у, л у, с м, в б, р m, m•р, о х, н а. Тогда, имея слово «слон», можно получить слово «муха». (Проверьте!) В теории алгоритмов строго доказано, что по своим возможностям преобразования нормальных алгоритмов эквивалентны частичным рекурсивным функциям и машинам Тьюринга. Соглашение о том, что для всякого алгоритма А в каком – либо алфавите может быть построен нормальный алгоритм, носит название принципа нормализации. Этот принцип равносилен тезису Черча и тезису Тьюринга.

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

Алгоритмическая проблема (АП) – проблема, в которой требуется найти единый метод (алгоритм) для решения бесконечной серии однотипных единичных задач.

Примеры 1 Найти алгоритм для выяснения, имеются ли целые корни у данного алгебраического уравнения а0 xn + a1 x n-1 +…+ a n = 0, где а0, a1,…, a n - целые числа. Искомый алгоритм существует и основан на факте, что, если такое уравнение имеет целый корень p, то p должно быть делителем числа a n, и для данного уравнения можно найти все делители числа a n, и все их по очереди проверить.

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

2 Аналогичная проблема для для уравнения P(x 1,…, x m) = 0, где P(x 1,…, x m ) – произвольный многочлен с целыми коэффициентами от любого числа m неизвестных (10 – я проблема Гильберта) неразрешима.

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

Неразрешимой является «проблема остановки»: по описанию алгоритма A и аргументу x выяснить, остановится ли алгоритм, если исходные данные – x.

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

Теорема Райса Никакое нетривиальное свойство вычислимых функций не является разрешимым.

Смысл этой теоремы: какое бы свойство вычислимых функций ни взять (периодичность, ограниченность, равенство другой, наперёд заданной функции и т. д.), нельзя построить общий алгоритм, например, машину Тьюринга, который по произвольному алгоритму A определял бы, обладает вычисляемая им функция fA этим свойством или нет.

Приведём ещё пример невычислимой функции. Пусть выбрано некоторое уточнение алгоритма. Тогда все алгоритмы, предназначенные для вычисления числовых функций, можно закодировать натуральными числами, Пусть Ai обозначает алгоритм с номером i, а i - функцию, вычисляемую алгоритмом Ai.

Требуется построить алгоритм, вычисляющий функцию f(n) = n(n)+1, если алгоритм применим к числу n, и f(n)=0 в противном случае. Эта проблема неразрешима. Действительно, если такой алгоритм Ak существует, то должно быть f(k)=k(k) и f(k)=k(k)+1, что невозможно.

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

3.1 Характеристики сложности вычислений Сложность алгоритма (СА) – величина, характеризующая длину описания или громоздкость процессов его применения к исходным данным /8/.

Сложность описания алгоритма зависит от выбора того или иного способа задания алгоритмов. Если такой способ зафиксирован, то СА обычно понимают как длину записи, количество встречающихся в ней выражений определенного типа и т. п. Например, под сложностью описания машины Тьюринга понимают общее число символов внешнего и внутреннего алфавитов, или число команд в программе данной машины. Сложность нормального алгоритма понимают как длину слова, полученного записыванием друг за другом всех формул подстановки в том порядке, как они встречаются в схеме данного алгоритма (между формулами помещается специальный символ). Сложность процесса применения алгоритма к исходным данным называется сложностью вычислений. Сложность вычислений данного алгоритма есть функция, которая каждому объекту из области применимости данного алгоритма сопоставляет число, характеризующее сложность процесса применения этого алгоритма к данному объекту. Сложность работы алгоритма характеризуется длительностью алгоритмического процесса во времени и объемом промежуточных результатов. Для машины Тьюринга – это соответственно число тактов работы машины от исходного слова до результата и количество ячеек ленты, в которых хотя бы раз побывал указатель при работе над словом. Для нормальных алгоритмов аналогичными характеристиками является число применений формул подстановки при работе над исходным словом и максимальная длина слов, появляющихся в процессе применения алгоритма к данному слову.

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

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

Оценивая сложность различных алгоритмов, следует исходить из некоторой модели исполнителя. Здесь используется модель 1RAM – однопроцессорная машина с равнодоступной памятью /4/.

3.2 Размер входа. Время работы При исследовании сложности вычислений обычно изучают зависимость времени работ от размера входа /5/.

Рассмотрим задачу сортировки.

Вход: Последовательность n чисел (а1, …, а n).

Выход: Последовательность n чисел (а1, …, аn), являющаяся перестановкой входной последовательности и удовлетворяющая условию: а1 … а n.

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

Пример – Вход : (1,3,2, 4). Выход (1,2,3,4).

Сортировка вставками для этого примера описывается последовательностью: (1, 3, 2,4) = (1, 3, 2, 4) = (1, 2, 3, 4) =(1, 2, 3, 4).

Запишем в псевдокоде процедуру Sort_Ins, соответствующую сортировке вставками Sort_Ins (А) 1 for j2 to length (A) do k A (j) i j-1 while i 0 and A (i) k do A(i+1) A (i) i i-1 A (i+1) k End {Sort_Ins} Здесь n = length (A), j – очередной элемент вставки; А (1.. (j –1)) – отсортированный участок, А ((j + 1).. n) – осталось вставить; k – дублер элемента А (j). Процедура работает следующим образом. В цикле for индекс j пробегает массив слева направо. Извлекается элемент А(j) и вправо сдвигаются элементы, большие его. Освободившееся место этот элемент и занимает. Обратим внимание на то, что отступы соответствуют уровню вложенности операций.

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

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

Имеем таблицу:

–  –  –

Общее время Т(n)=с1n+с2(n-1)+с3(n-1)+с4tj+с5(tj-1)+с6(tj-1)+с7 (n-1); tj– число раз исполнения строки 4, j =2..n.

Если массив на входе уже отсортирован, то цикл в строке 4 завершается после первой проверки. Общее время минимально: Т(n)=с1n+с2(n-1)+с3(n-1)+с4 (n-1)+с7(n-1)=аn+b; а=с1+с2+с3+с4+с7, b=-(с2+с3+с4+с7) и является линейной функцией размера входа.

Если массив на входе отсортирован в обратном порядке, то tj = j. Общее время максимально: Т(n) = с1n+ с2 (n-1)+с3 (n-1)+с4 (n(n-1)/2 – 1)+ с5 (n-1)/2 + с6(n-1)/2 +с7(n-1)=аn2+bn+c; а=с5/2+с6/2, в=с1+с2+с3+с4/2–с5/2–с6/2+с7, с=-(с2+с3+ с4 с7); учтено, что j=2 n j = n(n=1)/2 – 1, j=1 n (j–1)=n(n=1)/2. Сама функция Т(n) уже квадратичная.

Итак, мы рассмотрели худший и лучший случаи. В промежуточном случае, если считать, что в среднем около половины элементов массива А (1..(j–1)) больше А(j), и в строке 4 взять tj = j/2, то окажется, что среднее время квадратично зависит от размера входа – как и в худшем случае (конечно, коэффициенты другие). Среднее время зависит от распределения вероятностей, которое может не быть равномерным. Худшее время – максимальное время по всем входам.

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

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

3.3 Асимптотика роста функций

Определение 1 Если f(n), g(n), nN – некоторые функции, то запись f(n) =(g(n)) означает, что существуют числа с1, с2 0 и n0N такие, что 0с1g(n) f(n) с2g(n) для всех nn0 (здесь символ “=“ читается как “ есть “).

Пример – Проверить, что (1/4)n2-3n=(n2).

Проверка – Требуемое неравенство имеет вид с1n2(1/4)n2-3nс2n2, nn0.

Это неравенство эквивалентно следующему: с11/4-3/nс2, n n0. Второе неравенство, очевидно, выполняется при с2=1/4 и любого n0N. Первое неравенство можно записать в виде n 3/(1/4-с1). Если с1=1/5, то достаточно взять n0 = 60.

Если f(n)=((n)), то g(n) называется асимптотически точной оценкой для f(n). Заметим, далее, что если f(n) = (g(n)), то и g(n)= (f(n)).

Определение 2 Если f(n), g(n), nN – некоторые функции, то запись f(n) = О(g(n)) означает, что существуют числа с 0 и n0 N такие, что 0 f(n) с g(n) для всех n n0.

Определение 3 Если f(n), g(n), nN – некоторые функции, то запись f(n) = (g(n)) означает, что существуют числа с 0 и n0 N такие, что 0 сg(n) f(n) для всех n n0.

Таким образом, – обозначение используется для двусторонней оценки (снизу и сверху), а О- и - обозначения используются для односторонних оценок. Для любых двух функций f(n), g(n), nN свойства f(n)= О(g(n)) и g(n)= (f(n)) равносильны. (Символ «О» читается как «О- большое», символ «» - как «» - большое».) Асимптотические обозначения, О, могут использоваться внутри формул. Например, если имеется запись Т(n) = 2Т(n/2) + (n), то имеется в виду, что функция (n) не меньше с1n и не больше с2n для некоторых констант с1, с2 и достаточно больших n. А цепочка равенств типа 2n2+3n+1 =n2+(n)=(n2) понимается как последовательная асимптотическая оценка функции.

Определение 4 Если f(n) = О(f(n)) и lim n(f(n)/g(n))=0, то применяется обозначение f(n)=о(g(n)) (« f от n есть о – малое от g от n»). При этом предполагается, что f(n) и g(n) неотрицательны для достаточно больших n.

Определение 5 Если g (n)=o(f(n)), то говорят также, что f(n)= (g(n)) («f от n есть - малое от g от n»). При этом уже предположено, что f(n) и g (n) неотрицательны для достаточно больших n.

Итак, запись f(n)=о(g(n)) означает, что для любого 0 существует n0 N такое, что 0 f(n) g(n) для всех n n0, а запись f(n)= (g(n)) означает, что для любого с 0 существует n0 N такое, что 0 сg(n) f(n) для всех n n0.

Примеры 2n = о (n2), 2n2 о (n2) n2/2=(n), n2/2 (n2) Введенные характеристики асимптотического поведения функций обладают некоторыми стандартными свойствами. Так, отношения,O,, о, транзитивны,, О, рефлексивны, симметрично. Пары отношений О и, а также о и взаимно обратимы.

3.4 Оценки роста стандартных функций

3.4.1 Полином от переменной n имеет вид р(n) = i=0dаini. Будем предполагать, что d – степень полинома. Тогда полином р(n)=О(nd). Говорят, что функция f(n) полиномиально ограничена, если f(n) = n O(1), или f(n) = О(nk) для некоторой константы k.

3.4.2 Экспонента от переменной n определяется как функция n а n, а

0. При а1 экспонента растет быстрее любого полинома, то есть nb = o(an). Для вещественных х выполнено неравенство ех1+х; если х1, то имеет место оценка 1+хех1+х+х2. Кроме того, можно отметить, что ех=1+х+(х2), х0.

Напомним, что е =2,71828…; ех = k=0х k/ k!.

3.4.3 Логарифмы – это функции nlogbn, b0.Используются обозначения: log(n)=log2(n), ln(n)=loge(n). Напомним, что при х1 выполняется равенство ln(1+х)=х-х2/2+х3/3-…. Для х-1 справедливо: х/(1+ х)ln(1+х)х. Говорят, что функция f(n) ограничена полилогарифмом, если f(n)=logO(1)n. Любой полином растет быстрее любого полилогарифма, то есть log bn=o (nс), с0.

3.4.4 Факториалы – это функции nn!= n(n–1)!, n=1, 2,…. Полагают 0!=1. Очевидно, n!nn. Более точно, n! = 2n (n/е)n(1+(1/n)), - формула Стирлинга. Из этой формулы следует, что n!=o(nn), n!=(2n), log(n!)= (n log n).

Наконец, 2n (n/е)nn! 2n (n/е) ne1/12n.

3.4.5 Пример - Числа Фибоначчи Ф(0)=0; Ф(1)=1; Ф(n+1)=Ф(n)+Ф(n-1), n=2, растут экспоненциально с ростом n. (Начало последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…).

3.5 Рекуррентные соотношения

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

Например, время работы процедуры, выполняющей сортировку слиянием, удовлетворяет рекуррентному соотношению:

Т(n)=2Т(n/2)+(n), n1. Решить рекуррентное соотношение – значит с его помощью найти функцию или установить ее асимптотическое поведение. Здесь n

– размер входа; для простоты считаем, что n – степень числа 2. Рассмотрим некоторые приемы решения рекуррентных соотношений.

3.5.1 Метод подстановки

Пример – Т(n)=2Т(n/2)+n, где n – степень двойки. Зададимся видом Т(n)=О (n log n) (это нужно суметь), то есть предположим, что Т(n)сnlogn для некоторого с. Так как достаточно выполнения оценки, начиная с некоторого n, позаботимся, чтобы с обеспечивало требуемое неравенство при n=2. Предположим теперь, что оценка верна для n/2, то есть Т(n/2)с(n/2)log(n/2). Подставим ее в соотношение; получим Т(n)с(n/2)log(n/2)+nсnlog(n/2)+n=сnlog(n)сnlog(2)+n+с nlog(n)-сn+nсnlog(n) (последний переход – при условии с1).

Итак, Т(n)сnlog(n), то есть метод индукции прошел. Делаем вывод:

Т(n)=O(nlog(n)).

–  –  –

Пример – Т(n)=3Т([n/4])+n, где [] - целая часть. Подставляя соотношение в себя, получим Т(n)=n+3Т([n/4])=n+3([n/4])+3Т([n/16])=n+3([n/4])+3([n/16])+ 3Т([n/64])))= … n+3n/4+9n/16+27n/64+ … + 3log n(1)ni=0(3/4)i+(nlog43) =4n+o(n)=O(n). Здесь использовано равенство [ [ n/4 ]/4] = [ n/16 ] и подобные.

Впрочем, округление здесь не влияет на результат. Поскольку после i -ой итерации справа будет содержаться Т([n/4i]) до Т(1) чтобы дойти, нужно [ n/4i] приравнять 1, то есть получить ilog4n. Но заметив, что [ n/4i] n/4i, можно оценить наш ряд геометрической прогрессией со знаменателем (3/4) плюс слагаемое 3 log4n, относящееся к задачам ограниченного размера, и заменить указанное слагаемое на nlog43, что есть o(n).

3.5.3 Основной результат Имеет место теорема: Пусть а 1, b 1 – константа, f(n) – функция и рекуррентное соотношение Т(n)=аТ(n/b)+f(n), где под n/b понимается одно из двух ближайших целых чисел. Тогда:

-для f(n)=O(nlogbа-), 0 верно, что Т(n)=(nlogbа);

-для f(n)=(nlogbа) верно, что Т(n)=(nlogbа log(n));

-для f(n)=( nlogbа+), 0, причем аf(n/b)сf(n) для некоторой константы с 1 и достаточно больших n, верно, что Т(n)=(f(n)).

Суть теоремы – в сравнении функции f(n) с nlogbа, если одна из функций растет быстрее другой, то она и определяет порядок роста Т(n). Если функции одного порядка, появляется логарифмический множитель.

3.6 NР – полнота

Если время работы алгоритма на входе длины n составляет О(nк) при некотором к, не зависящем от n, то алгоритм называется полиномиальным. Задача называется полиномиально разрешимой, если для нее существует полиномиальный алгоритм. Для некоторых задач алгоритмы не полиномиальны. Есть также неразрешимые задачи. Классическая задача – выяснить, останавливается ли данная программа на данном входе, - не может быть решена никаким алгоритмом. Специалисты считают полиномиальные алгоритмы практически приемлемыми, а алгоритмы, требующие времени, «большего», чем полиномиальное, представляющими лишь теоретический интерес. К характеристике полиномиальных алгоритмов следует добавить их замкнутость: композиция (последовательное выполнение) полиномиальных алгоритмов есть полиномиальный алгоритм. Достаточно полное изложение вопросов сложности алгоритмов имеется в /5/. Здесь приводятся лишь некоторые сведения.

3.6.1 Задачи разрешения. Класс P

Рассмотрим абстрактную задачу – бинарное отношение между элементами множества условий U и множества решений V. Например, в задаче обхода графа условиями являются матрицы смежностей, а решениями – последовательности вершин. Задачами разрешения называются задачи, в которых требуется ответить («да» или «нет») на поставленный вопрос, то есть построить функцию f с областью определения U и множеством значений V= 0,1. Если предполагать, что входные данные для алгоритма представлены последовательностью битов (или последовательностью символов другого алфавита мощности 2), то абстрактная задача переходит в так называемую строковую задачу. Строковая задача называется полиномиальной, если существует алгоритм, который решает ее при длине входа n за время О (nк) для некоторого к.

Множество полиномиальных строковых задач разрешения называется сложностным классом Р. Функция f: 0,1*0, 1 называется вычислимой за полиномиальное время, если существует полиномиальный алгоритм, переводящий х0,1* в y0, 1. Если существуют две вычислимые за полиномиальное время функции f12, f21, переводящие два представления множества U друг в друга, то эти представления называются полиномиально связанными. Справедливо следующее утверждение.

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

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

3.6.2 Допускающие и распознающие языки

Языком L над алфавитом А называется некоторое множество последовательностей символов (слов) алфавита А (построенных по определенным правилам) Пример –L =, 0, 1, 0110, 11, 001, … A={0,1}.

Символ означает пустое слово, символ Ф означает пустой язык. Язык, состоящий из всех возможных слов над заданным алфавитом А обозначается через А*. Таким образом L А* для любого языка L над алфавитом А.

На примере языков L0,1* введём ещё несколько понятий из теории формальных языков. Говорят, что алгоритм A допускает слово x{0, 1}*, если А (х) = 1; отвергает, - если А(х) = 0. Алгоритм называется допускающим язык L, если алгоритм допускает все слова L и только их. Если алгоритм допускает все слова из L и не допускает слова из СL, то говорят, что этот алгоритм распознает язык. Язык L допускается распознается за полиномиальное время если каждое слово языка допускается распознается за время не большее O(nк) (n – длина слова х, к не зависит от х, соответствующим допускающим распознающим языком. На основании введенных понятий можно определить класс Р следующим образом: Р = L 1 * существует алгоритм А, распознающий язык 0, за полиномиальное время. Имеет место теорема: Р = L L допускается за полиномиальное время. Таким образом, в рассмотренной ситуации допускающие и распознающие за полиномиальное время языки эквивалентны.

3.6 3 Проверяющие алгоритмы Рассмотрим задачу разрешения, связанную с задачей поиска кратчайшего пути в графе. Дан неориентированный граф G = (X, Y), X – множество вершин, Y – множество ребер. Требуется для двух вершин графа построить кратчайший путь между ними. Это задача о кратчайшем пути. Здесь условием u является тройка (G, x1, x2),x1, x2 а решением v – последовательность (x1, …,x2) верX, шин графа, составляющих требуемый путь. Одна из задач разрешения: по двум вершинам графа и числу k определить, существует ли в графе путь, связывающий заданные вершины, длина которого k. Теперь условием u является (G, x1, x2, k), а решение v {0, 1}, причём`v =1, если такой путь есть; v = 0 в противном случае. Существует алгоритм поиска в ширину на графе, с помощью которого сформулированная задача решается за полиномиальное время.

Рассмотрим теперь задачу о гамильтоновом цикле. Напомним, гамильтоновым циклом в неориентированном графе называется простой цикл, который проходит через все вершины графа. Задача о гамильтоновом цикле состоит в ответе на вопрос, имеет ли данный граф гамильтонов цикл. Если в качестве решения организовать перебор перестановок вершин и проверку этих перестановок на гамильтоновость, то, как и следует ожидать, время работы не будет полиномиальным; более точно, время работы такого алгоритма равно (2 n), где n – длина представления графа. ( Напомним, что число перестановок из m элементов равно m!. («эм – факториал»). Имеет место теорема: задача о гамильтоновом цикле является NP – полной. К раскрытию понятия NP – полноты мы и переходим в следующих пунктах.

Проверяющим алгоритмом называется алгоритм А, имеющий два параметра; первый – входная строка, второй – образец (или сертификат). Такой алгоритм считаем допускающим вход u, если существует образец v, для которого А (и, v) = 1. Языком, проверяемым алгоритмом А, называется язык L =u 0,1 * (v 0,1 * А (u, v) = 1).

Итак, алгоритм А проверяет язык L, если для любого слова uСL найдется образец v, с помощью которого А может проверить принадлежность слова и языку L, а для строки не принадлежащей языку такого образца нет. В задаче о гамильтоновом цикле образцами могут быть последовательности вершин, образующие гамильтонов цикл. Гамильтоновость цикла в графе можно проверить за полиномиальное время.

3.6.4 Класс NP

Множество языков, для которых имеются работающие полиномиальное время проверяющие алгоритмы ( с образцами, ограниченными по длине некоторыми многочленами) называется сложностным классом NP. Заметим, что проверка языка в данном контексте несколько отличается от проверки языка как таковой. А именно: для U L могут существовать длинные образцы, которые в данном контексте отбрасываются (и потому остаются непроверенными в прежнем смысле). Очевидно, всякую задачу из Р можно считать входящей в NP: полиномиальный алгоритм, распознающий язык, в этом случае уже существует, и для этого языка строится проверяющий алгоритм, не учитывающий второй параметр. Итак, Р NP. Совпадают ли классы Р и NP?. Большинство специалистов полагают, что в NP есть задачи, не решаемые за полиномиальное время.

3.6.5 Сводимость языков. NP – полнота языков Обычно мы полагаем, что одна задача сводится к другой, если (возможно) преобразованные входы первой задачи являются входами другой. Говорят, что язык L1 сводится к языку L2, если существует такая функция f: 0,1 *0,1*, что для любого x 0,1* свойства x L1 и f(х) L2 эквивалентны.

Функция f называется сводящей функцией, а алгоритм, вычисляющий функцию f, – сводящим алгоритмом. Если функция f вычислима за полиномиальное время, то говорят, что язык L1 сводится к языку L2 за полиномиальное время и используют запись: L1 р L2. Сводящая функция переводит любое слово x L1 в слово f(х) L2, а слово х L1 – в слово f(х) L2. Поэтому по ответу на вопрос: «f(х) 2?» мы получаем ответ на вопрос «х L1?». Справедливо утверждение: Если языки L1, L2 0,1*, и L1 р L2, то из L2 Р следует, что L1 Р. При этом запись L1 р L2 можно интерпретировать так, что сложность языка L1 не более чем полиномиально превосходит сложность языка L2.

Основное определение Язык L1 0, 1* называется NP – полным, если выполняются условия:

1) L1 NP;

для любого L2 NP выполняется отношение L2 р L1.

2) Язык L1 0,1* называется NP – трудным, если выполнено условие 2), а условие 1) может выполняться или не выполняться.

Основная теорема Если некоторая NP – полная задача разрешима за полиномиальное время, то Р = NP. Иначе говоря, если в классе NP есть задача, не разрешимая за полиномиальное время, то все NP – полные задачи таковы.

Доказательство Если некоторый язык L1 является NP – полным и в то же время разрешимым за полиномиальное время, то для любого языка L2 NP из свойства 2) основного определения следует, что L2 р L1. Последнее означает, что L2Р. Утверждение в первой формулировке доказано. Вторая формулировка теоремы эквивалентна первой. В соответствии с этой теоремой предположение о том, что Р NP означает, что NP – полные задачи не могут быть решены за полиномиальное время. Пока никто не предъявил полиномиальный алгоритм для решения NP – полной задачи, и никто не доказал N NP.

3.6.6 Примеры NP – полных задач

Имеется множество NP – полных задач в различных разделах математики: логике, графах, алгебре и так далее. Рассмотрим несколько примеров.

1 Задача о выполнимости схемы Дана схема, состоящая из элементов «и», «или», «не». Требуется выяснить, является ли эта схема выполнимой. При этом схема из функциональных элементов с несколькими входами и одним выходом называется выполнимой, если существует входной булев вектор, для которого выходной скаляр есть единица. Как уже известно, эта задача сводится к задаче о выполнимости пропозициональной формулы ((х1х2) ((х1 х3) х4 )) х2 имеет выполняющий набор (х1, х2, х3, х4) = (0, 0, 1, 1). (проверьте!) Выполнимость можно проверить, перебрав все наборы значений переменных (для формулы с n переменными их 2n). В данном случае достаточно проверку провести для представленного образца. Переборный алгоритм как видно, не является полиномиальным. Имеет место теорема: задача о выполнимости формулы NР полна. Предупреждение: естественный способ построение формулы, которая вычисляет туже функцию, что и заданная схема, состоящий в последовательной записи подформул, отвечающих тому или иному элементу (например, для выхода элемента «и» формула имеет вид 1 2, где 1, 2 – формулы, соответствующие входам элемента), не является полиномиальным. Общая идея составления формулы, которую строит «нужный» сводящий алгоритм – в том, что вводится дополнительная переменная для каждого провода в схеме (а не только ее входов). Например, схеме (рисунок 3.1) соответствует формула = х8 (х8 (х7 х6)) (х7 (х4 х5)) (х6 (х2 х3) (х5 х3) (х4 (х1 х2)). Такое построение приводит к схеме полиномиального размера и выполняется за полиномиальное время.

–  –  –

2 Задача о клике Дан граф. Найти максимальный размер клики в этом графе.

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

3 Задача о суммах подмножеств Требуется выяснить, существует ли подмножество данного множества с заданной суммой элементов.

4 Разработка алгоритмов и программ

4.1 Основные технологии

Программа – это запись алгоритма на языке, понятном исполнителю. С массовым внедрением вычислительных машин процесс программирования для них превращается в промышленное изготовление программ. Для этой цели создаются разнообразные технологии программирования. Основные из них: нисходящее программирование и восходящее программирование. Нисходящее программирование (программирование «сверху – вниз») основывается на идее декомпозиции исходной задачи на ряд подзадач: строится программа, в которой эти подзадачи выступают как некоторые именованные процедуры и к ним организуется обращение. Те подзадачи, которые еще не обработаны. Временно заменяются «заглушками». Затем по отношению к подзадачам применяется такой же прием. Выходящее программирование (программирование «сверху – вниз») основано на противоположном процесс: сначала пишутся и отлаживаются программы самого нижнего уровня; затем они собираются в блоки, все более крупные. Наконец, идет сборка всей программы, и программа отлаживается.

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



Pages:   || 2 |


Похожие работы:

«Министерство образования Республики Беларусь Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ УТВЕРЖДАЮ Проректор по учебной и воспитательной работе _ С.К. Дик 25 апреля 2016г. ПРОГРАММА вступительного экзамена в магистратуру по специальности 1-31 80 10 Теоретические основы инф...»

«Аннотации к рабочим программам дисциплин направления 02.03.02 Фундаментальная информатика и информационные технологии Аннотация рабочей программы по дисциплине "Иностранный язык (английский)" Общая трудоемкость дисц...»

«Пояснительная записка Основу рабочей программы составляет авторская программа А.В. Горячева "Программа по информатике и ИТ,1-4 начальной общеобразовательной школы".Программа рассчитана на 34 часа, в неделю 1 час.Цели программы: формирование общих пр...»

«ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011 Управление, вычислительная техника и информатика № 1(14) УДК 681.32 О.В. Климова ЭВОЛЮЦИЯ СПОСОБОВ ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ ДЛЯ ОПЕРАЦИЙ ЦИФРОВОЙ ОБРАБОТКИ СИГНА...»

«Лекция 4. Организация процесса тестирования программного обеспечения. Структурное, функциональное и объектно-ориентированное тестирование ПО Материалы: Образовательные программы и курсы Курс: Прогр.техн.раз...»

«МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "НОВОСИБИРСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ" (НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ, НГУ) Кафедра общей информатики ВЫПУСКНАЯ КВАЛИФИКАЦИОНН...»

«ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ВСЕСИБИРСКОЙ ОТКРЫТОЙ ОЛИМПИАДЫ ШКОЛЬНИКОВ ПО ИНФОРМАТИКЕ 18 марта 2012 года Для всех задач: Входной файл: input.txt Выходной файл: output.txt Максимальное количество баллов за задачу: 100 баллов Задача 1. Простой Компьютер Ограничение по времен...»

«Российская академия сельскохозяйственных наук ГОСУДАРСТВЕННОЕ НАУЧНОЕ УЧРЕЖДЕНИЕ ВСЕРОССИЙСКИЙ ИНСТИТУТ АГРАРНЫХ ПРОБЛЕМ И ИНФОРМАТИКИ ИМЕНИ А.А. НИКОНОВА (ГНУ ВИАПИ РОССЕЛЬХОЗАКАДЕМИИ) УДК № госрегистрации Инв. № УТВЕРЖДАЮ Директор ВИАПИ им. А.А. Никонова С.О. Сип...»

«МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "НОВОСИБИРСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ" (НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ, НГУ) Факультет информационных технологий Ка...»

«Учреждение образования "Белорусский государственный университет информатики и радиоэлектроники" Методический материал в помощь кураторам (Рекомендовано отделом методической и воспитательной работы для внутреннего пользования) Тема: "Горе от ума" или "Трудно быть гением"...»

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ ПРИКАЗ " " 20_г. Москва № _ об утверждении тем выпускных квалификационных работ Утверд...»

«Автоматика. Информатика. Управление. Приборы УДК 621.396.23 DOI: 10.17277/vestnik.2015.01.pp.007-015 СИНТЕЗ ЭНЕРГОСБЕРЕГАЮЩЕГО УПРАВЛЕНИЯ Н. Г. Чернышов1, С. И. Дворецкий2 Кафедры: "Электроснабжение, электротехника и информационное обеспечение энергетических систем" (1); n-c-h@rambler.ru; "Техн...»

«Том 7, №5 (сентябрь октябрь 2015) Интернет-журнал "НАУКОВЕДЕНИЕ" publishing@naukovedenie.ru http://naukovedenie.ru Интернет-журнал "Науковедение" ISSN 2223-5167 http://naukovedenie.ru/ Том 7, №5 (2015) http://naukovedenie.ru/index.php?p=vol7-5 URL статьи: http://naukovedenie.ru/PDF/93TVN515.pdf DOI: 10.15862/93TVN515 (http://d...»

«Пояснительная записка Настоящая рабочая программа базового курса "Информатика и ИКТ" для 8 класса II ступени обучения средней общеобразовательной школы составлена на основе федерального компонента государственного образовательного стандарта...»

«417 Секция Информатика и прикладные исследования Оптимальный метод перераспределения общей памяти для двухприоритетной очереди, представленной в виде двух последовательных циклических FIFO-очередей Аксенова Е. А., Соколов А. В. (Петрозаводск,...»

«Аннотации к рабочим программам дисциплин   основной образовательной программы высшего образования  по направлению подготовки  02.03.02 ФУНДАМЕНТАЛЬНАЯ ИНФОРМАТИКА И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ с направленностью (профилем)   "Информатика и компьюте...»

«УДК 519.682.1 ОБ ОБЪЕКТАХ, ОПИСЫВАЕМЫХ АЛГОРИТМИЧЕСКИМ ЯЗЫКОМ © 2014 А. М. Фрумкин ст. науч. сотрудник каф. математического анализа и прикладной математики, канд. техн. наук, e-mail: frumkinam@mail.ru Курский государственный универси...»

«Министерство сельского хозяйства и продовольствия Республики Беларусь Информационно-вычислительное республиканское унитарное предприятие "ГИВЦ Минсельхозпрода" Типовой программный комплекс автоматизации учета и отчетност...»

«Механіко-технологічні системи та комплекси ISSN 2411-2798 (print) УДК 629.7.025.7 И. Б. КОВТОНЮК АЭРОДИНАМИЧЕСКИЕ ХАРАКТЕРИСТИКИ ТОНКОГО ПРОФИЛЯ С ИНТЕРЦЕПТОРОМ На основе метода дис...»

«Министерство образования Республики Беларусь Учреждение образования "Белорусский государственный университет информатики и радиоэлектроники" Кафедра: Радиоэлектронной техники ВВС и войск ПВО "Специальная подготовка" Теория для студентов дневной формы обучения...»

«УДК 004.312.44 МОДЕЛИРОВАНИЕ СИСТЕМЫ МОНИТОРИНГА ПУЛЬСА НА ОСНОВЕ ИК-ДАТЧИКА С ИСПОЛЬЗОВАНИЕМ UML Матюшкин Никита Викторович Пензенский государственный технологический университет Студент Резюме Пульс – это...»

«Государственное образовательное учреждение высшего профессионального образования Московской области "Международный университет природы, общества и человека "Дубна" (университет "Дубна") УТВЕРЖДАЮ проректор по учебной работе С.В. Моржухина "_"_...»

«1 Имитационное моделирование реальных биржевых торгов К.В. Воронцов к.ф.-м.н., н.с. ВЦ РАН, зам. директора FORECSYS www.forecsys.ru, e-mail: voron@ccas.ru (Москва) В результате сотрудничества Московской Межбанковской Валютной Биржи (М...»

«УЧЕНЫЕ ЗАПИСКИ №4, 2008 И. В. Соколова Информатизация общества как объект социологического исследования Информатизация общества – относительно новое явление для Соколова Ирина Викторовна, доктор социоломировой и отечественной социологической теории и практики, гическ...»

«Министерство образования Республики Беларусь Учреждение образования "Белорусский государственный университет информатики и радиоэлектроники" УТВЕРЖДАЮ Проректор по учебной и воспитательной работе Дик С.К. ""_2016 г. ПРОГРАММА Дополнительного вступительного экзамена в магистратуру по специальности 1-39 81 03 "...»

«Московский Государственный Университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики Кафедра системного программирования Курсовая работа Исследование и разработка методов нормализации слов...»

«Методика дистанционного обучения Термин "программирование" обычно связывают с составлением программ для компьютеров, хотя это понятие использовалось давно до появления вычислительных машин. "ПРОГРАММА ж. греч. краткий очерк, начертанье, перечень, изложенье, содержанье сочинения, предпол...»

«Центр сертифик ации Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики Магистерская программа "Математическое и п...»

«Министерство образования Республики Беларусь Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ ПРОГРАММА вступительного экзамена в магистратуру по специальнос...»

«Волошина Татьяна Геннадьевна, Мишанова Юлия Владимировна, Федорова Ирина Александровна ФОРМАЛЬНАЯ ОРГАНИЗАЦИЯ И СТРУКТУРНЫЕ ТИПЫ ПОЛИПРЕДИКАТИВНОГО ПРЕДЛОЖЕНИЯ С ПАРАТАКСИСОМ И ГИПОТАКСИСОМ В ДИАЛОГАХ КИНОСЦЕНАРИЕВ США Статья раскрывает особенности функционирования полипредикативных предложений с паратакси...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

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