- •Основные понятия и определения дисциплины.
- •История развития теории алгоритмов.
- •Роль алгоритмов в науке и технике.
- •Понятие алгоритма и алгоритмического процесса.
- •2. Формальное определение алгоритма
- •Алгоритмический процесс.
- •Основные вопросы теории алгоритмов.
- •Классификация алгоритмов.
- •Свойства алгоритмов.
- •Логика предикатов.
- •Интерпретация.
- •Истинность и выполнимость формул.
- •Нормальные алгоритмы Маркова.
- •Гипотеза Черча.
- •Машина Тьюринга.
- •Рекурсивные функции.
- •Алгоритмически неразрешенные проблемы.
- •Сложность алгоритмов.
- •Временная и вычислительная сложность.
- •Понятие p и np-задач.
- •Темпоральные логики. Нечеткая и модальные логики.
- •Примеры задач np-класса.
- •Логическое программирование.
- •Дедуктивные теории.
- •Свойства дедуктивных теорий. Противоречивость
- •Полнота
- •Независимость аксиом
- •Разрешимость
- •Формальные аксиоматические теории.
- •Свойство выводимости.
- •Логические матрицы.
- •Модели Крипке для логики высказываний.
- •Формальное определение
- •Основные понятия мЛиТа.
- •Логические функции.
- •Правила логики высказываний. Законы логики высказываний.
- •Основные понятия
- •Равносильность. Логическое следствие.
- •Кванторы.
- •Категорические высказывания. Высказывание Категорическое
- •Связанные и свободные переменные. Свободные и связанные переменные
- •Операции над кванторами
- •Общая значимость.
- •Логические функции.
- •Алгоритмы сортировки данных. Сортировка слиянием.
- •Алгоритмы сортировки данных. Сортировка «пузырьком».
- •Алгоритмы сортировки данных. Сортировка вставками.
- •Алгоритмы сортировки данных. Сортировка Шейкером.
- •Алгоритмы сортировки данных. Быстрая сортировка.
- •Алгоритмы сортировки данных. Сортировка подсчетом.
- •Моделирование алгоритмов программ с помощью блок-схем.
- •История развития математической логики.
- •Логика высказываний.
- •Булева алгебра и основные логические тождества.
- •Пропозициональные формулы и логические функции.
- •Аксиоматический метод исчисления высказываний.
Алгоритмы сортировки данных. Сортировка вставками.
Создаётся новый массив в который последовательно вставляются элементы из исходного массива, таким образом чтобы новый массив был упорядоченным. Вставка происходит следующим образом: в конце нового массива выделяется свободная ячейка далее анализируется элемент, стоящий перед пустой ячейкой и если этот элемент больше вставляемого, то подвигаем элемент в свободную ячейку (при этом на том месте, где он стоял, образуется пустая ячейка) и сравниваем следующий элемент. Дальше мы получаем ситуацию, когда элемент, стоящий перед пустой ячейкой меньше вставляемого или пустая ячейка стоит в начале массива. Помещаем вставляемый элемент в пустую ячейку дальше по очереди вставляем все элементы исходного массива очевидно, что если до вставки элемента массив был упорядочен, то после вставки перед вставленным элементом расположены все элементы меньшие его, а после – большие. Т.к. порядок элементов в новом массиве не меняется, то сформированный массив будет упорядоченным после каждой вставки.
Program Insertion
Var A,B: array [1…1000] of integer
N, I, j: integer
Begin
{определение размера массива A(N) и его заполнения}
……………………………………………………………………………………………………
{сортировка данных}
For i:=1 to N do
Begin
J:=1
While (j>1) and (B[j-1] > A[i]) do
Begin
B[J]:=B[j-1]
J:=j-1
End
B[j]:=A[i];
End;
{Вывод массива B}
End
Описание:
Integer – натуральные числа
Алгоритмы сортировки данных. Сортировка Шейкером.
Особенности: работает в 2 раза чем пузырёк.
Когда данные сортируются не в оперативной памяти, а на жёстком диске, то количество перемещений элементов существенно влияет на время работы. Этот алгоритм уменьшает количество таких перемещений действуя следующим образом: за 1 проход из всех элементов выбирается минимальный и максимальный потом минимальный элемент помещается в начало массива, а максимальный соответственно в конец. Далее алгоритм выполняется для остальных данных. Таким образом за каждый проход 2 элемента помещаются на свои места, следовательно понадобится n/2 – проходов
n – количество элементов
Program Shaker Sort
Var A: array [1…1000] of integer;
N,i,j: integer;
Min, max: integer
Begin
{Определение размера массива (A – N и его заполнение)}
……………………………………………………………………………………….
{сортировка данных}
For i:=1 to n do
Begin
If A[i]>A[i+1] then
Begin
Min:=i+1;
Max:=I;
End
Else
Begin
Min:=i;
Max:=i+1;
For j:=i+2 to n-i+1 do
If A[j]>A[max] then
Max:=j
Else
If A[j]< A[min] then
Min:=I;
{обмен элементов}
P:=A[i];
A[i]:=A[min];
A[min]:=P;
If max:=I then
Max:=min
P:=A[N-i+1];
A[max]:=P;
End;
{вывод отсортированного массива А}
End
Алгоритмы сортировки данных. Быстрая сортировка.
Program Quick Sort
Var A:Array[1…1000] of integer;
N,T: integer,
Procedure Sort (p,q: integer);
{p,q – индексы начала и конца сортируемой части массива}
Var i,j,k integer,
Begin
If p<q then {массив из одного элемента trab – 110…}
Begin
r:=A[p];
i:=p-1
j:=q+1
Reperat
j:=j-1
un[i] A[j]<=r,
if i<j then
begin
T:=A[i];
A[i]:=A[j];
A[j]:=T;
End,
End;
Sort (p,i),
Sort (j+1,q);
End,
End
Begin
{определение размера массива}
…………………..
Как и в сортировке слиянием массив разбивается на 2 части с условием что все элементы первой части меньше любого элемента второй потом каждая часть сортируется отдельно разбиение на части достигается упорядочиванием относительно некоторого элемента массива