- •Основные понятия и определения дисциплины.
- •История развития теории алгоритмов.
- •Роль алгоритмов в науке и технике.
- •Понятие алгоритма и алгоритмического процесса.
- •2. Формальное определение алгоритма
- •Алгоритмический процесс.
- •Основные вопросы теории алгоритмов.
- •Классификация алгоритмов.
- •Свойства алгоритмов.
- •Логика предикатов.
- •Интерпретация.
- •Истинность и выполнимость формул.
- •Нормальные алгоритмы Маркова.
- •Гипотеза Черча.
- •Машина Тьюринга.
- •Рекурсивные функции.
- •Алгоритмически неразрешенные проблемы.
- •Сложность алгоритмов.
- •Временная и вычислительная сложность.
- •Понятие p и np-задач.
- •Темпоральные логики. Нечеткая и модальные логики.
- •Примеры задач np-класса.
- •Логическое программирование.
- •Дедуктивные теории.
- •Свойства дедуктивных теорий. Противоречивость
- •Полнота
- •Независимость аксиом
- •Разрешимость
- •Формальные аксиоматические теории.
- •Свойство выводимости.
- •Логические матрицы.
- •Модели Крипке для логики высказываний.
- •Формальное определение
- •Основные понятия мЛиТа.
- •Логические функции.
- •Правила логики высказываний. Законы логики высказываний.
- •Основные понятия
- •Равносильность. Логическое следствие.
- •Кванторы.
- •Категорические высказывания. Высказывание Категорическое
- •Связанные и свободные переменные. Свободные и связанные переменные
- •Операции над кванторами
- •Общая значимость.
- •Логические функции.
- •Алгоритмы сортировки данных. Сортировка слиянием.
- •Алгоритмы сортировки данных. Сортировка «пузырьком».
- •Алгоритмы сортировки данных. Сортировка вставками.
- •Алгоритмы сортировки данных. Сортировка Шейкером.
- •Алгоритмы сортировки данных. Быстрая сортировка.
- •Алгоритмы сортировки данных. Сортировка подсчетом.
- •Моделирование алгоритмов программ с помощью блок-схем.
- •История развития математической логики.
- •Логика высказываний.
- •Булева алгебра и основные логические тождества.
- •Пропозициональные формулы и логические функции.
- •Аксиоматический метод исчисления высказываний.
Категорические высказывания. Высказывание Категорическое
а- высказывание, в котонром предикат утверждается или отрицается относительно субъекнта без ограничения к.-л. условиями и вполне определенно. В. к. обычно противопоставляются условным высказываниям и разделинтельным высказываниям. В традиционной логике В.к., как правило, отождествляются с простыми атрибутивными суждениями (см.: Суждение). Их структура выражается формулой: лS есть (не есть) Р
Связанные и свободные переменные. Свободные и связанные переменные
Связанное переименование, свободное переименование
Операции над кванторами
Правило отрицания кванторов — применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:
Общая значимость.
Логические функции.
Логическая функция – это функция, определенная на множестве истинностных значений (истина, ложи) и принимающая значение из того же множества.
Например:
F(А,В) = А В – логическая функция двух переменных
А и В, называющаяся «дизъюнкция»
Некоторая функция двух переменных будет полностью определена так:
F(0,0) = 0 F(0,1) = 1 F(1,0) = 1 F(1,1) = 1
Алгоритмы сортировки данных. Сортировка слиянием.
Это сортировка использует следующую подзадачу:
Есть 2 отсортированных массива, нужно сделать из них один общий тоже отсортированный.
Алгоритм работает по следующему принципу: разбить массив на 2 части, отсортировать каждую из них а потом слить обе части в одну отсортированную.
Program_Sliv_Sort
Var A,B: array [1…1000] of integer;
N: integer;
Procedure Sliv(p,q: integer): {процедура сливающая массивы}
Var r,i,j,k: integer;
Begin
r:= (p+q) div 2;
i:=p
j:=r+1
for k:=p to q do
if (i<=r) and ((j>q) or (a[i]<a[j])) then
begin
b[k]:=a[i];
i:=i+1;
end
else
begin
b[k]:=a[j]
j:=j+1;
end
for k:=p to q do
a[k]:=b[k];
end
procedure Sort (p,q:integer)
{p,q – индексы начала и конца сортируемой части массива}
Begin
If p<q then {массив из одного элемента тривиально упорядочен}
Begin
Sort (p,(1+q)div 2);
Sort ((p+q) div 2+1,q);
Sliv (p,q);
End;
End;
Begin
{определение размера массива (А - N) и его заполнение}
{запуск сортирующей процедуры}
Sort (1,N);
{вывод отсортированного массива}
End.
Алгоритмы сортировки данных. Сортировка «пузырьком».
Реализация данного алгоритма не требует дополнительной памяти алгоритм очень прост и состоит в следующем: берётся пара рядом стоящих элементов и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то мы меняем их местами. Эти действия продолжаем, пока есть такие пары. Когда таких пар не останется, то данные будут отсортированы. Для упрощения поиска таких пар данные просматриваются по порядку от начала до конца. Максимальный элемент как бы всплывает вверх отсюда и название алгоритма.
Program Bubble Sort
Var A: array [1…1000] of integer
N,I,j: integer
Begin
{определение размера массива A(N) и его заполнение}
………………………………………………………………………………………
{сортировка данных}
For i:=1 to n do
For j:=1 to n-i do
If A[j]>A[j+1] then
Begin {обмен элементов}
P:=A[j]
A[j]=A[j+1]
A[j+1]:=p
End
{вывод отсортированного массива}
End
Описание:
For i:=1 to n do - определяет количество проходов
For j:=1 to n-i do – сравнение пары элементов в том или ином проходе.