Шпаргалка по "Программированию и компьютерам"

 Нахождение  минимального пути в  графах

• Алгоритм поиска в ширину

 Алгоритм  применим для ненагруженных графов и работает за время O(N²), где N – количество вершин в графе. Воспользуемся этим алгоритмом для нахождения длин минимальных путей из v_s во все остальные вершины графа:

 Шаг 1. Каждой вершине v_i поставим в соответствие метку L_i – длину минимального пути от v_s до v_i. Изначально L_i = ¥ для i¹s, L_s = 0. Заносим в очередь вершину v_s. Переходим к шагу 2;

 Шаг 2. Извлекаем очередную вершину  v_i из очереди [если осуществляется поиск минимального пути из v_s в v_i, то алгоритм может завершить работу сейчас]. Всем смежным с ней вершинам v_j, метки которых L_j = ¥, присвоим метки L_j=L_i+1. Занесём эти вершины в очередь. Переходим к шагу 3;

 Шаг 3. Если очередь пуста, то алгоритм заканчивает  работу, иначе переходим к шагу 2.

 Теперь  по полученным значениям L_i восстановим один из минимальных путей из v_s в v_d:

 Шаг 1. Если L_d = ¥, то пути из v_s в v_d не существует, и алгоритм заканчивает работу, иначе переходим к шагу 2.

 Шаг 2. Текущей вершиной v_c объявляем v_d. Переходим к шагу 3;

 Шаг 3. Занесём v_c в стек. Если v_c = v_s, то переходим к шагу 5, иначе переходим к шагу 4;

 Шаг 4. Текущей вершиной v_c объявляем одну из вершин v_j, метки которыхL_j=L_c-1. Переходим в шагу 3;

 Шаг 5. Последовательно извлекаем из стека все находящиеся в нём  вершины – полученная последовательность и является одним из минимальных  путей из v_s в v_d.

• Алгоритм Дейкстры

 Алгоритм  применим для нагруженных графов, дуги которых неотрицательны, и работает за время O(N²), где N – количество вершин в графе. Воспользуемся этим алгоритмом для нахождения длин минимальных путей из v_s во все остальные вершины графа:

 Шаг 1. Каждой вершине v_i поставим в соответствие следующие метки:

 1) L_i – длину минимального пути от v_s до v_i;

 2) Q_i – вершину, из которой v_i получила свою метку L_i;

 3) C_i – признак постоянности метки L_i (если С_i = 0, то метка L_i является временной, иначе постоянной.

 Изначально  L_i = ¥, C_i = 0 для i¹s. L_s = 0, C_s = 1. Q_i = 0 для всех i. Переходим к шагу 2;

 Шаг 2. Текущей вершиной v_c объявляем одну из вершин v_j, метки которых L_j являются минимальными и временными (C_i = 0). Если такой вершины не найдено, то алгоритм заканчивает работу, иначе переходим к шагу 3;

 Шаг 3. Присваиваем v_c постоянную метку C_c = 1. Всем вершинам v_j, смежным с v_c, метки которых L_j > L_c + len(v_c, v_j) присваиваем метки L_j = L_c + len(v_c, v_j) и Q_j = v_c. Переходим к шагу 2.

 Теперь  по полученным значениям L_i и Q_i восстановим один из минимальных путей из v_s в v_d:

 Шаг 1. Если L_d = ¥, то пути из v_s в v_d не существует, и алгоритм заканчивает работу, иначе переходим к шагу 2.

 Шаг 2. Текущей вершиной v_c объявляем v_d. Переходим к шагу 3;

 Шаг 3. Занесём v_c в стек. Если v_c = v_s, то переходим к шагу 5, иначе переходим к шагу 4;

 Шаг 4. Текущей вершиной v_c объявляем вершину v_j = Q_c. Переходим в шагу 3;

 Шаг 5. Последовательно извлекаем из стека все находящиеся в нём  вершины – полученная последовательность и является одним из минимальных  путей из v_s в v_d. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 4. Алгебра логики. Понятие  логической функции.  Примеры логических  функций одной  и двух переменных. Формулы алгебры  логики. Равносильность  формул.

 Алгебра логики

 Алгебра логики – алгебра, образованная множеством B = {0, 1} и всеми логическими операциями, определёнными на этом множестве.

 Понятие логической функции

 Логическая  функция – функция f (x₁,…,x_n), принимающая значения из B, когда её аргументы пробегают B. Список переменных функции – упорядоченный набор (x₁, …, x_n).

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

 Функцией  от 1-го арг наз-ся функ f(x) заданная на мн-ве из 2-х элемнтов и принимающая  значения в том же 2-х элементном множестве

• Функции одной переменной

 j₁ – константа 0;

 j₂ – тождественная функция;

 j₃ – отрицание;

 j₄ – константа 1.

 Фун-ия g(x,y) заданная на мн-ве {0,1}x{0,1}={0,1}2 и принимающая  значения в 2-х эле-ом мн-ве т.о. сапостовляет любой упорядоченной паре составленной из 0 и 1  либо 0 либо1

• Функции двух переменных

 Их 16, вот некоторые из них:

 j₂ – конъюнкция ( & );

 j₇ – сложение по модулю 2 ( Å );

 j₈ – дизъюнкция ( Ú );

 j₉ – стрелка Пирса ( ¯ );

 j₁₀ – эквиваленция ( « );

 j₁₄ – импликация ( ® );

 j₁₅ – штрих Шеффера ( | ).

 Формулы алгебры логики

 Алфавит алгебры логики содержит логические переменные, логические связки и скобки. Формула – слово в языке, порождённом КС грамматикой со следующими правилами:

 I ® x_i, I ® (ØI), I ® ( I & I ), I ® ( I Ú I ), I ® ( I ® I ), I ® ( I ¯ I ), I ® ( I | I ), I ® ( I « I ), I ® ( I Å I ).

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

 Пример: x₁ & x₂ ® x₃ Ú x₁.

 Равносильность  формул

 Определение

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

 Равносильность  – отношение эквивалентности  между формулами.

 Основные  равносильности

 1) Коммутативность:  A & B º B & A; A Ú B º B Ú A;

 2) Ассоциативность: (A & B) & С º A & (B & С); (A Ú B) Ú С º A Ú (B Ú С);

 3) Дистрибутивность: A & (B Ú С) º (A & B) Ú (A & С); A Ú (B & С) º (A Ú B) & (A Ú С);

 4) Закон идемпотенции: A & A º A; A Ú A º A;

 5) Законы де Моргана: Ø (A & B) º ØA Ú ØB; Ø (A Ú B) º ØA & ØB;

 6) Законы поглощения: A & (A Ú B) º A; A Ú (A & B) º A;

 7) Законы расщепления: A º (A Ú B) & (A Ú ØB); A º (A & B) Ú (A & ØB);

 8) Свойство  нуля: A & 0 º 0; A Ú 0 º A;