32) Алгоритм и его свойства

Алгоритм- это точное предписание определяющее вычислительный процесс, от начальных данных к искомому результату. Свойства: 1) массовость, предполагается, что алгоритм может быть пригоден для решения всех задач данного типа. 2) результативность, алгоритм должен приводить к получению результата за конечное число шагов. 3) определенность, однозначность результата вычислительного процесса при заданных исходных данных. 4) Дискретность, описываемый алгоритмом процесс и сам процесс и сам алгоритм могут быть разбиты на элементарные этапы.

33) Схемы алгоритмов

Логическая схема алгоритмов- это выражение, состоящие из символов операторов, логических условий, следующих в определенном порядке, а также нумерованных стрелок, расставленных особым способом. Матричная схема алгоритмов – это квадратная матрица, элементы которой указывают условия передачи управления от i-го оператора строки к j-му оператору столбца. Граф-схема алгоритма - это ориентированный граф особого вида. Он содержит вершины 4 типов:1. операторные (прямоугольник) 2. условные (ромб), начальная вершина (овал) 4. конечная вершина (овал).вершины соединяются дугами.

Гост 19.701-90

-терминатор (начало, конец)

- поток данных

- соединитель

- решение

-процесс

- комментарий

34) Задачи теории алгоритмов

Задачи:1. алгебраически разрешимые: а) сложные б) простые

2. алгебраически не разрешимые

35) Логические исчисления: исчисление предикатов

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

Аксиомы исчисления предикатов: в качестве трех первых берутся, например, аксиомы исчисления высказываний:А1. А(ВА);

А2. (А(ВС))((АВ)(АС));

А3. ()((А)В).

Добавляются «собственные» аксиомы:

А4. x_i [A(x_i)  A(x_j)], где формула A(x_i) не содержит переменной x_j.

А5. [A(x_i)x_j A(x_j)], где формула A(x_i) не содержит переменной x_j.

Правила вывода:

1. Правило m.p: .

2. Правило связывания квантором общности:

,где формула В не содержит переменной x_i. Воспользуемся «метадовказательством»: соответствующее множество дизъюнктов невыполнимо (функция Сколема).

3. Правило связывания квантором существования:

где формула В не содержит переменной x_i..

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

36) Система натурального вывода

Система натурального вывода- это доказательство по Генцену. Правила вывода в этой формальной системы делятся на правила введения

1. введение конъюнкции: (В) ,Н-некоторое мн-во формул (гипотез) - метасимвол «влечет»

2. введение дизъюнкции: : (В) , ;

3. введение импликации: (В) ;

4введение инверсии: (В ) .

правила исключения логических операций:

5. исключение конъюнкции: (И) , ;

6.исключение дизъюнкции(И) 7.исключение импликации(И) ;

8.исключение инверсии(И ) .

Базисные правила:

Б1: Б2: