Понятие множества, отображения, функции, логической функции, булевой функции

1.Понятие множества, отображения, функции, логической функции, булевой функции.

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

Множества обозначаются прописными буквами латинского или готического алфавита: A, B, ...,M, K,... .

Если множество A состоит из элементов a, b,c,..., это обозначается с помощью фигурных скобок: A={a, b,c,...,} .

Множества, элементами которых являются числа называются числовыми:

N – множество всех натуральных чисел;

Zc (или Z+ или C+) – множество всех целых неотрицательных чисел;

Z (или C) – множество всех целых чисел;

Q – множество всех рациональных чисел;

R – множество всех действительных чисел;

R+ - множество всех действительных положительных чисел

По числу элементов, входящих в множество, множества делятся на три класса:

1. Если элементы множества можно сосчитать, то множество является КОНЕЧНЫМ

2. Если элементы множества сосчитать невозможно, то множество БЕСКОНЕЧНОЕ.

3.Множество, не содержащее ни одного элемента, называется ПУСТЫМ. Символически оно обозначается знаком Æ.

Способы задания множеств.

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

Множество можно задать, непосредственно перечислив все его элементы, причём, порядок следования элементов может быть произвольным. В этом случае названия всех элементов множества записываются в строчку, отделяются точкой с запятой и заключаются в фигурные скобки. Множество всех гласных букв русского алфавита: A={а; я; у; ю; э; е;о; ё; и; ы}.

Конечные и бесконечные множества могут быть заданы другим способом: указанием ХАРАКТЕРИСТИЧЕСКОГО СВОЙСТВА, т. е. такого свойства, которым обладает любой элемент данного множества и не обладает ни один элемент, не принадлежащий ему.

Отношения между множествами.

Наглядно отношения между множествами изображают при помощи особых чертежей, называемых КРУГАМИ ЭЙЛЕРА (или диаграммами Эйлера – Венна).Для этого множества, сколько бы они ни содержали элементов, представляют в виде кругов или любых других замкнутых кривых

Множество В является подмножеством множества А тогда и только тогда, когда каждый элемент множества В является элементом множества А.

Множества C и D называются равными тогда и только тогда, когда множество С является подмножеством множества D, и наоборот.

Операции над множествами:

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

1.Объединением двух множеств А и В называется множество С, которое состоит из элементов множеств А и В

2.Пересечением двух множеств А и В называется множество С, которое состоит из общих элементов множеств А и В

3.Разностью двух множеств А и В (А-В) , называется множество С, которое состоит из элементов множества А, которых нет в множестве В

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

Отображение (матем.) множества А в множество В, соответствие, в силу которого каждому элементу х множества А соответствует определённый элемент у = f (x) множества В, называют образом элемента х (элемент х называют прообразом элемента у).

Отображением множества E в множество F, или функцией, определенной на E со значениями в F, называется правило, или закон f, который каждому элементу ставит в соответствие определенный элемент.

Функция — математическое понятие, отражающее связь между элементами множеств

Логическая функция - это функция логических переменных, которая может принимать только два значения : 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения : 0 или 1.

Логический элемент - это устройство, реализующее ту или иную логическую функцию.

Y=f(X1,X2,X3,...,Xn) - логическая функция, она может быть задана таблицей, которая называется таблицей истинности.

Число строк в таблице - это число возможных наборов значений аргументов. Оно равно 2n, где n - число переменных. Число различных функций n переменных равно 2^2^n.

Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики) от n переменных — в дискретной математике отображение Bn → B, где B = {0,1} — булево множество. Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно».

Булевы свойства операций над множествами:

1. Идемпотентность (A и A) =A, (A или A)=A.

Термин идемпотентность означает свойство чего либо (объекта) которое проявляется в том, что повторное действие над объектом не изменяет его

2. Коммутативность (A и B) = (B и A), (A или B) = (B или A).

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

3. Ассоциативность A и (B и C) = (A и B) и C, A или (B или C)=(A или B) или C.

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

4. Правило поглощения A и (A или B)=A, A или (A и B) = A.

одна переменная поглощает другие

5. Дистрибутивность - свойство согласованности двух бинарных операций, определённых на одном и том же множестве. Две бинарные операции + и × удовлетворяют свойству дистрибутивности, если для любых трех элементов x y z :

6. Инволюция не (не(A))=A.

Преобразование, которое является обратным самому себе.

7. Свойство констант (A и U) = A, (A или U) = U, (A и пустое множество) = пустое множество, (А или пустое множество) = A.

8. Закон исключённого третьего и закон противоречия (A или не(A)) = U, (A и не(A)) = пустое множество.

9. Не (А и В) = (не (А) или не (В)), не (А и В) = (не (А) или не (В)).

Каждую функцию алгебры логики можно записать в виде формулы или представить таблицей истинности. Таблица истинности для n переменных содержит 2n строк. Следовательно, каждая функция алгебры логики принимает 2n значений, состоящих из 0 или 1. Общее же число наборов значений, состоящих из 0 и 1, длины 2n равно 22n. В частности, число различных функций от одной переменной равно четырем.

х	f1(x)	f2(x)	f3(x)	F4(x)
0	1	1	0	0
1	1	0	1	0

Из этой таблицы следует, что две функции являются константами f1(x) = 1 и – f2(x) = x, а остальные f3(x) = Ø x и f4(x) = 0.

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

2.Булева алгебра. Функции многих переменных.

БУЛЕВА АЛГЕБРА, область математики, содержащая правила обращения с множествами, а также с логическими утверждениями типа «и», «или».

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

Функции двух переменных z = f(x, y).

Две из них f0 = 0 и f15 = 1 являются константами.

функциями одной переменной.

- конъюнкция (функция И)

-дизъюнкция (функция или)

-импликация (следование)

-сложение по модулю 2

-эквивалентность или подобие

-штрих Шеффера

-стрелка Пирса

3.Высказывания. Исчисление высказываний. Логические связки и операции. 4.Законы логики. Основные эквивалентности.

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

Здесь два объекта интерпретируются как истина (будем обозначать как true) и ложь (будем обозначать как false). Далее мы будем называть символы true и false булевыми величинами, а переменные, которые их обозначают - булевыми переменными.

Обычно элементарные высказывания обозначают строчными буквами латинского алфавита a, b, c, x, y …, которые также являются логическими переменными.

Из элементарных высказываний можно составить более сложные с помощью логических связок Ø, Ù, Ú, ®, º, называемых соответственно отрицание, логическое и (конъюнкция), логическое или (дизъюнкция), логическое следствие (импликация), эквивалентность и круглых скобок (, ). Семантику логических связок можно представить с помощью таблицы истинности. В левой части этой таблицы перечисляются все возможные комбинации значений логических переменных.

Виды высказываний

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

Логическая связка — это любая логическая операция над высказыванием. Например, употребляемые в обычной речи слова и словосочетания «не», «и», «или», «если… , то», «тогда и только тогда» являются логическими связками.

Основные операции над логическими высказываниями

Отрицание логического высказывания — логическое высказывание, принимающее значение «истинно», если исходное высказывание ложно, и наоборот.

Конъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны.

Дизъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда хотя бы одно из них истинно.

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

Равносильность (эквивалентность) двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны или ложны.

Логика высказываний (или пропозициональная логика от англ. propositional logic) — это формальная теория, основным объектом которой служит понятие логического высказывания.

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

1. Закон двойного отрицания:

А = .

2. Переместительный (коммутативный) закон:

— для логического сложения:

A V B = B V A

— для логического умножения:

A&B = B&A.

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

3. Сочетательный (ассоциативный) закон:

— для логического сложения:

(A Ú B) Ú C = A Ú (BÚ C);

— для логического умножения:

(A&B)&C = A&(B&C).

4. Распределительный (дистрибутивный) закон:

— для логического сложения:

(A Ú B)&C = (A&C) Ú (B&C);

— для логического умножения:

(A&B) Ú C = (A Ú C)&(B Ú C).

5. Закон общей инверсии (законы де Моргана):

— для логического сложения

=& ;

— для логического умножения:

= Ú

6. Закон идемпотентности

— для логического сложения:

A Ú A = A;

— для логического умножения:

A&A = A.

7. Законы исключения констант:

— для логического сложения:

A Ú 1 = 1, A Ú 0 = A;

— для логического умножения:

A&1 = A, A&0 = 0.

8. Закон противоречия:

A& = 0.

9. Закон исключения третьего:

A Ú = 1.

10. Закон поглощения:

— для логического сложения:

A Ú (A&B) = A;

— для логического умножения:

A&(A Ú B) = A.

11. Закон исключения (склеивания):

— для логического сложения:

(A&B) Ú ( &B) = B;

— для логического умножения:

(A Ú B)&( Ú B) = B.

12. Закон контрапозиции (правило перевертывания):

(A Û B) = (BÛ A).

┐(А→В) = А&┐В

┐А&(АÚВ)= ┐А&В

АÚ┐А&В=АÚВ

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

В алгебре логики определено отношение эквивалентности (=), которое удовлетворяет следующим свойствам:

Х = Х - рефлексивность;

если X = Y, то Y = X - симметричность;

если X = Y, Y = Z, то X = Z - транзитивность.

Из отношения эквивалентности следует принцип подстановки: если X = Y, то в любой формуле, содержащей X, вместо X можно подставить Y и будет получена эквивалентная формула.

Эквивалентности:

X + 0 = X

X + 1 = 1

X + X = X

X + = 1

X 0 = 0

X 0 = X

X X = X

X = 0

5.Основная теорема булевой алгебры. СКНФ, СДНФ, ДНФ, КНФ

Любая двоичная функция может быть представлена как суперпози-ция только трех функций: И, ИЛИ и НЕ.

Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание.

Определение 1: Конъюнкцией(или логическое умножение) двух булевых переменных называется следующая функция.

Определение 2: Дизъюнкцией(логическое сложение) двух булевых переменных называется следующая функция.

Дизъюнктивная нормальная форма(ДНФ)

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

Алгоритм построения СДНФ:

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

Очевидно, для любой булевой функции , кроме константы 0, существует единственная СДНФ (с точностью до порядка литералов и конъюнкций). Поэтому данная форма представления булевой функции является канонической.

Конъюнктивная нормальная форма(КНФ)

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

Алгоритм построения СКНФ:

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

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

6.Проблема полноты. Функционально полные, неполные, избыточные системы функций.

7.Алгебра Жегалкина. Теорема о представлении функции единственным многочленом Жегалкина

8.Классы функций. Теорема о полноте.

Система функций {f1…fn} называется полной, если любую булеву функцию можно представить в виде суперпозиции функций из этой системы (т. е. можно представить формулой, куда входят только функции из этой системы).

Теорема:

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

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

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

специальная алгебра где

В алгебре Жегалкина выполняются следующие соотношения:

1. x y = y x;

2. x ( y z ) = x y x z;

3. x x = 0;

4. x = 1;

5. x 0 = x.

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

Теорема.

Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.

x y = x y (x & y)

~x = x 1

Применив эти формулы, мы всякую булеву функцию выразим через операции & и.

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

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

булевы функции, сохраняющие константу 0;

булевы функции, сохраняющие константу 1;

самодвойственные булевы функции;

линейные булевы функции;

монотонные булевы функции;

К булевым функциям сохраняющим константу 0, относят такие булеы функции f(x1,...,xn), для которых справедливо соотношение f(0,...,0)=0

К булевым функциям сохраняющим константу 1, относят такие булеы функции f(x1,...,xn), для которых справедливо соотношение f(1,...,1)=1.

Булевы функции f1(x1,...,xn) и f2(x1,...,xn) называются двойственными друг другу, если выполняется соотношение

f1(x1,...,xn)=/(f2(/x1,...,/xn))

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

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

Это - такая логическая функция, которую можно выразить через , 0 и 1.

Булева функция f(x1,...,xn) называется монотонной, если для любых двух наборов Y = <y1,y2,...,yn> и B = <b1,b2,...,bn> таких, что Y >= B имеет место неравенство f(y1,...,yn)>=f(b1,...,bn).

Это - такая логическая функция, которую можно выразить через & и.

Теорема Поста:

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

9.Предикаты, связь исчисления высказываний и исчисления предикатов. Кванторы. Связанные и свободные переменные.

10.Эквивалентные соотношения в исчислении предикатов.

Предика́т (лат. praedicatum — заявленное, упомянутое, сказанное) — любое математическое высказывание о некоторой функции, в котором есть, по меньшей мере, одна переменная.

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

Логические операции:

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

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

Отрицанием предиката А(х) называется новый предикат, который принимает значение «истина» при всех значениях х Т, при которых предикат А(х) принимает значение «ложь», и принимает значение «ложь», если А(х) принимает значение «истина»

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

Кванторные операции

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

Квантор всеобщности — это условие, которое верно для всех обозначенных элементов, в отличие от квантора существования, где условие верно только для каких-то отдельных из указанных чисел.

обозначение -

Квантор существования — это предикат свойства или отношения для, по крайней мере, одного элемента области определения. (Квантор существования отличается от квантора всеобщности, который утверждает, что свойство или отношение выполняется для всех элементов области.)

обозначение -

Связь кванторов с операциями алгебры высказываний

Если , то

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

1. Аксиома двойного отрицания:

2. Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции):

3. Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов):

4. Аксиомы одинаковых операндов:

5. Аксиомы поглощения (множителем — множителя-суммы или слагаемым — слагаемого-произведения):

6. Аксиомы распределения операции (дизъюнкции относительно конъюнкции и наоборот):

7. Аксиомы де Моргана (перенесения бинарной операции на операнды):

8. Аксиомы нейтральности (взаимноинверсных множителей или слагаемых):

9. Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем,

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

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

-Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,

-свободные переменные формулы F являются свободными переменными формулы F,

-переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),

-все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.

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

Связанная переменная - переменная v связана в формуле F, если F содержит вхождение Kv, где K — квантор.

В логике (алгебре) предикатов справедливы все эквивалентные соотношения логики (алгебры) высказываний, а также собственные эквивалентные соотношения:

11.Логический вывод и метод резолюций. Примеры.

12.Дизъюнкты Хорна, фразы и резолюции. Примеры.

13.Правила унификаций в методе резолюций.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример: вывод решения в логической модели на основе метода резолюций.

Даны утверждения:

«Сократ – человек»;

«Человек – это живое существо»;

«Все живые существа смертны».

Требуется методом резолюций доказать утверждение «Сократ смертен».

Решение:

Шаг 1. Преобразуем высказывания в дизъюнктивную форму:

Шаг 2. Запишем отрицание целевого выражения (требуемого вывода), т. е. «Сократ бессмертен»:

Шаг 3. Cоставим конъюнкцию всех дизъюнктов (т. е. построим КНФ), включив в нее отрицание целевого выражения:

Шаг 4. В цикле проведем операцию поиска резольвент над каждой парой дизъюнктов:

Получение пустого дизъюнкта означает, что высказывание «Сократ бессмертен» ложно, значит истинно высказывание «Сократ смертен».

Дизъюнктом Хорна называется такой дизъюнкт, у которого k = 0 или k = 1. При k = n = 0 получается пустой дизъюнкт, обозначаемый символом Л.

Фразы Хорна (Horn clause) представляют собой подмножество фраз, содержащих только один позитивный литерал. В общем виде фраза Хорна представляется выражением

р :- q1,...,qn. Такая фраза интерпретируется следующим образом:

"Для всех значений переменных в фразе p истинно, если истинны q1 и... и qn",

т. е. пара символов ":-" читается как "если", а запятые читаются как "и".

14. Язык Пролог. Решения задач.

Пролог–программа предназначена для решения отдельной задачи. В связи с этим Пролог считается декларативным языком программирования.( построенный: - на описании данных; и - на описании искомого результата).

Пролог может быть использован в различных приложениях, относящихся к искусственному интеллекту :

– общение с ЭВМ на естественном языке;

– символьные вычисления;

– написание компиляторов;

– базы данных;

-  экспертные системы и т. д

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

– константы;

– переменные;

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

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

Переменные служат для обозначения объектов, значения которых меняются в ходе выполнения программы. Имена переменных начинаются с заглавных букв или знака «_». Область действия переменной – предложение. Одноименные переменные в разных предложениях могут иметь разные значения.

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

Функтор различается двумя параметрами (именем и числом параметров):

– point(X, Y, Z) и point(X, Y) – разные предикаты

– point/3 - это означается, что у предиката point 3 аргумента,

– point/2 - это означается, что у предиката point 2 аргумента.

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

1. При записи фактов надо соблюдать следующие правила:

-Имена всех отношений и объектов с маленькой буквы.

-Сначала записывается имя отношения, затем в круглых скобках через запятую объекты.

-В конце ставится точка.

Введем отношение - родиparent) между объектами.

parent (tom, bob).

Это факт, определяющий, что Том является родителем Боба.

Вопрос в обычном прологе начинается с?-

? - parent (bob, pat).

Yes

?-parent (Y, juli), parent (X, Y).

X=bob

Y=pat

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

child(Y, X) :- parent (X, Y).

eсли условие parent (X, Y). выполняется, то логическим следствием из него будет утверждение child(Y, X).

15. Понятие алгоритма, его свойства, примеры алгоритмически нерешаемых задач.

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

Свойства алгоритмов:

1.  Поочередное выполнение команд алгоритма за конечное число шагов приводит к решению задачи, к достижению цели. Разделение выполнения решения задачи на отдельные операции (выполняемые исполнителем по определенным командам) – важное свойство алгоритмов, называемое дискретностью.

2.  Каждый алгоритм строится в расчете на некоторого исполнителя. Для того чтобы исполнитель мог решить задачу по заданному алгоритму, необходимо, чтобы он  был в состоянии понять и выполнить каждое действие, предписываемое командами алгоритма. Такое свойство алгоритмов называется определенностью (или точностью)алгоритма. (Например, в алгоритме указано, что надо взять 3—4 стакана муки. Какие стаканы, что значит 3—4, какой муки?)

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

4.  Универсальность. Алгоритм должен быть составлен так, чтобы им мог воспользоваться любой исполнитель для решения анало­гичной задачи. (Например, правила сложения и умножения чисел годятся для любых чисел, а не для каких-то конкретных.)

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

Дискретность (от лат. discretus — разделенный, прерывистый) – это разбиение алгоритма на ряд отдельных законченных действий (шагов).

Детерминированность (от лат. determinate — определенность, точность) - любое действие алгоритма должно быть строго и недвусмысленно опре­делено в каждом случае.

Конечность - каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения.

Массовость - один и тот же алгоритм можно использовать с разными исходными данными. Результативность - в алгоритме не было ошибок. 

Существует 4 вида алгоритмов: линейный, циклический, разветвляющийся, вспомогательный. 
Линейный (последовательный) алгоритм — описание действий, которые выполняются однократно в заданном порядке. 
Линейный алгоритм применяется при вычислении арифметического выражения, если в нем используются только действия сложения и вычитания. 
Циклический алгоритм — описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие. Перечень повторяющихся действий называется телом цикла. 
Условие — выражение, находящееся между словом «если» и словом «то» и принимающее значение «истина» или «ложь». 
Разветвляющийся алгоритм — алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий. 

Способы задания алгоритма:

ñ  словесный, (недостаток–многословность, возможна неоднозначность–«он встретил ее на поле с цветами»),

ñ  табличный (физика, химия и т. д.),

ñ  графический (блок-схемы).

Примеры алгоритмически нерешаемых задач.

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

Неразрешимость

Если принять за единицу измерения радиус круга и обозначить x длину стороны искомого квадрата, то задача сводится к решению уравнения: x2 = π, откуда: . Как известно, с помощью циркуля и линейки можно выполнить все 4 арифметических действия и извлечение квадратного корня; отсюда следует, что квадратура круга возможна в том и только в том случае, если с помощью конечного числа таких действий можно построить отрезок длины π. Таким образом, неразрешимость этой задачи следует из неалгебраичности (трансцендентности) числа π, которая была доказана в 1882 году Линдеманом.

Однако эту неразрешимость следует понимать, как неразрешимость при использовании только циркуля и линейки. Задача о квадратуре круга становится разрешимой, если, кроме циркуля и линейки, использовать другие средства (например, квадратрису). Простейший механический способ предложил Леонардо да Винчи.[1] Изготовим круговой цилиндр с радиусом основания R и высотой , намажем его чернилами и прокатим по плоскости. За один полный оборот цилиндр отпечатает на плоскости прямоугольник площадью πR2.

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

3.Удвоение куба — классическая античная задача на построение циркулем и линейкой ребра куба, объём которого вдвое больше объёма заданного куба.

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

16. Сложность Алгоритма. Тезис Черча.

Основы оценок сложности алгоритмов

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

Нахождение точной зависимости  для конкретной программы -- задача достаточно сложная. По этой причине обычно ограничиваются асимптотическими оценками этой функции, то есть описанием ее примерного поведения при больших значениях параметра . Иногда для асимптотических оценок используют традиционное отношение  (читается <<О большое>>) между двумя функциями , определение которого можно найти в любом учебнике по математическому анализу, хотя чаще применяют отношение эквивалентности  (читается <<тэта большое>>). Его формальное определение есть, например, в книге [#!korman!#], хотя нам пока достаточно будет понимания данного вопроса в общих чертах.

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

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

Не менее интересен и пример вычисления -го числа Фибоначчи. В процессе ее исследования фактически уже было выяснено, что ее сложность является экспоненциальной и равна. Подобные программы практически не применимы на практике. В этом очень легко убедиться, попробовав вычислить с ее помощью 40-е число Фибоначчи. 

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

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

1	Факториальная	N!	Алгоритмы комбинаторики (сочетания, перестановки и т. д.)
2	Экспоненциальная	KN	Алгоритмы перебора (brute force)
3	Полиномиальная	NK	Алгоритмы простой сортировки (buble sort)
4	Линейный логарифм	N * log(N)	Алгоритмы быстрой сортировки (heap sort)
5	Линейная	K * N	Перебор элементов массива
6	Логарифмическая	K * log(N)	Бинарный поиск
7	Константная	К	Обращение к элементу массива по индексу

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

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

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

Тезис Чёрча — Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает эквивалентность между строго формализованным понятием частично вычислимой функции и неформальным понятием вычислимости.

Позднее были сформулированы другие практические варианты утверждения:

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

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

17. Понятие рекурсии.

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

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

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

Рекурсия. Различные формы рекурсии.

Основная идея рекурсивного определения заключается в том, что функцию

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

к ранее определенным функциям или к самой определяемой функции, но с более

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

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

Рекурсивная процедура, во-первых содержит всегда по крайней мере одну

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

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

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

Прерванный процесс каким-нибудь образом запоминается. Он будет ждать и

начнет исполняться лишь после окончания нового процесса. В свою очередь,

новый процесс может приостановиться, ожидать и т. д.

Будем говорить о рекурсии по значению и рекурсии по аргументам. В

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

Во втором - в качестве результата функции возвращается значение некоторой

другой функции и рекурсивный вызов участвует в вычислении аргументов этой

функции. Аргументом рекурсивного вызова может быть вновь рекурсивный вызов

и таких вызовов может быть много.

Рассмотрим следующие формы рекурсии:

простая рекурсия;

параллельная рекурсия;

взаимная рекурсия.

Рекурсия называется простой, если вызов функции встречается в

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

программировании соответствует обыкновенный цикл.

Рекурсию называют параллельной, если она встречается одновременно в

нескольких аргументах функции.

Рассмотрим использование параллельной рекурсии на примере

преобразования списочной структуры в одноуровневый список:

Рекурсия является взаимной между двумя и более функциями, если они

вызывают друг друга.

18. Язык Лисп. Решение задач

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

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

Идеология Лиспа крайне проста: данные и программы представляются в нем в одной и той же форме. Благодаря такой униикации представления данные могут интерпретироваться как програм-

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

Основные положения программирования на Лиспе.

Лисп ориентирован на обработку нечисловых задач. Он основан на алгебре

списочных структур, лямбда-исчислении и теории рекурсий.

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

заключенное в скобки, введенное вне редактора считается функцией и

выполняется сразу после нажатия «ENTER».

Чтобы предотвратить вычисление значения выражения, нужно перед этим

выражением поставить апостроф «’». Апостроф перед выражением - это на самом

деле сокращение лисповской функции QUOTE.

В Лиспе формы представления программы и обрабатываемых ею данных одинаковы.

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

Типы данных не связаны с именами объектов данных, а сопровождают сами

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

различные объекты.

Основные типы данных языка - атомы и списки.

Атомы - это символы и числа.

Список - упорядоченная последовательность, элементами которой

являются атомы либо списки. Списки заключаются в круглые скобки, элементы

списка разделяются пробелами. Несколько пробелов между символами

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

остаток, т. е. список без первого элемента, называется «хвостом. Список в

котором нет ни одного элемента, называется пустым и обозначается «()» либо

NIL.

Функция CAR предназначена для извлечения первого элемента списка, который возвращается в качестве ее результата. Например,

(car '(

вернет 1

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

(cdr '(

(

CONS, наоборот, производит слияние двух аргументов, формируя из них список, который возвращается в качестве результата. Функция принимает ровно 2 (!) аргумента, первый из которых используется в качестве CAR-части списка, а второй - в качестве его CDR-части. Это очень важно - первый аргумент рассматривается функцией cons именно как элемент вновь формируемого списка

Предикат ATOM проверяет, является ли аргумент атомом. Аргу-

ментом может быть любое S-выражение. Значение предиката равно T,

если значение аргумента - атом, и NIL, когда значение аргумента -

не атом.

Предикат EQ проверяет тождественность двух символов. Предикат

EQ принимает значение T, если символы идентичны, и значение NIL во

всех других случаях, включая случаи, когда аргументами являются не

символы.

19. Элементы теории формальных грамматик

Описание языковых построений исследуется в теории формальных грамматик и языков. Базовым понятием этой теории является понятие алфавита.

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

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

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

Примеры

Пусть задан алфавит { а, b, с, 1, 2 }. Тогда цепочками в этом алфавите являются следующие слова: ааааааа, 12bbbb, a2b, 1 , 0, где 0 - пустая цепочка в этом алфавите.

Конкатенацией (композицией) цепочек х и у называют новую цепочку z==ху, получаемую приписыванием символов цепочки у к концу цепочки х.

Цепочку (слово) у называют подцепочкой (подсловом) цепочки z, если справедливо одно из следующих соотношений:

z=xy, z=yx, z=xyt, где х и t - какие-либо цепочки.

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

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

При этом все слова языка, составленные из символов алфавита, называют терминальными символами языка.

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

Правила порождения предложений некоторого языка называют его грамматикой.

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

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

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

Если обозначить множество терминальных символов через Т, а множество нетерминальных символов через U, то будет справедливо следующее утверждение: V = Т È U. Здесь “È” - знак объединения множеств.

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

Итак, языком L называется следующая система множеств:

L = < Т, U, G(S) >, где G(S) - грамматика языка с начальным символом S.

G = < VT, VN, P, S >
G — грамматика
VT — алфавит терминальных символов (то из чего состоит язык, слова)
VN — алфавит не терминальных символов
P — продукция (все возможные цепочки языка)
S — начальный символ

VN = { S, N } N может «превращаться» в SN или N N → SN → SS → 42
N — некий терминальный символ

Сортировки-

Процесс упорядочивания информации и называют «сортировкой».

1. Поиск наименьшего элемента массива.

Ищет наименьший элемент в массиве простым перебором. Если заменить знак "<" на ">", то можно искать наибольший элемент. 

Пусть нам дан массив из N чисел

3, 6, 1, 2, 9, 5.

На первом шаге мы находим наименьшее число — 1 — и должны переместить его на первое место.( просто меняем местами два элемента массива)

1 | 6, 3, 2, 9, 5.

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

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

На втором шаге мы находим минимальное число в правой части — среди элементов массива

1, 2 | 3, 6, 9, 5.

2. Сортировка массива по возрастанию.

Это наиболее естественный алгоритм упорядочивания. Допустим, что элементы a1,...,ai-1 уже упорядочены, тогда среди оставшихся (ai,...,an) находим минимальный элемент и меняем его местами с i-тым элементом. И т. д. пока массив не будет полностью упорядочен.

3. Сортировка массива по возрастанию (метод пузырька).

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

Последовательно просматриваем числа a1,...,an находим наименьшее i такое, что a i > ai+1. Поменять ai и ai+1 местами, возобновить просмотр с элемента ai+1 и т. д. Тем самым наибольшее число передвиниться на последнее место. Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра в котором участвовали только первый и второй элементы.

Сортировка перемешиванием (улучшение сортировки пузырьком)

Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.

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

Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.

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

Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

5.  Сортировка массива по возрастанию (метод простых вставок).

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

Последовательно просматриваем a2,...,an и каждый новый элемент ai вставляем на подходящее место в уже упорядоченную совокупность a1,...,ai-1. Это место опред-ся последовательным сравнением ai с упорядоченными элементами a1,...,ai-1.

5. Сортировка массива по возрастанию (метод бинарных вставок).

Этот алгоритм представляет из себя оптимизированную версию предыдущего, отличие заключается в том, что при поиске место, на которое надо вставить элемент ai в уже упорядоченную совокупность a1,...,ai-1, определяется алгоритмом деления пополам (отсюда и название алгоритма "бинарные вставки" здесь понимаем как "вставка делением пополам"). 

6.Сортировка массива методом Шелла(улучшение сортировки вставками).

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d . После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

7. Сортировка массива по возрастанию
(метод Уильяма Флойда, бинарных деревьев).

Алгоритм основан на представлении массива в виде бинарного дерева, обладающего особыми свойствами. В памяти компьютера все элементы массива расположены последовательно, структура же дерева определяется следующим образом: будем считать, что i элемент массива ("предок") имеет два элемента потомка с номерами 2i и 2i+1. Дерево имеет нормальную форму, если любой элемент предок больше своих потомков.
 Для понимания алгоритма рассмотрите приведенную блок-схему. Из свойств алгоритма стоит заметить, что он дает стабильно хорошую скорость упорядочивания (порядка n log(n)), вне зависимости от того с каким массивом работает, и поэтому используется в случаях когда необходимо гарантировано упорядочить массив за короткое время.

8. Быстрая сортировка

Краткое описание алгоритма

-выбрать элемент, называемый опорным.

-сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.

-повторить рекурсивно для «меньших» и «больших».