- •1. Дм функции алгебра логики, реализация функций формулами, канонические формы
- •2. Дм полнота и замкнутость систем функций. Теорема о функциональной полноте
- •3. Дм проблемы построения минимальных днф
- •4. Дм Схемы из функциональных элементов в базисе {и, или, не}. Задача построения схем из функциональных элементов и подходы к её решению. Примеры.
- •6. Дм графы, способы задания, геометрическая реализация
- •7. Дм теория кодирования, алфавитное кодирование, проблема однозначности кодирования, префиксные коды
- •8. Дм коды с минимальной избыточностью (коды Хафмана)
6. Дм графы, способы задания, геометрическая реализация
примеры задач на графы
Графом G наз-ся пара объектов V и E (G=V,E). V={a1, a2, …} мн‑во вершин, E={(ai, aj)}- мн-во ребер. Каждое ребро может быть либо упорядоченно, либо нет; в зависимости от этого граф ориентированный или неориентир-ый.
Пусть m=|V| - число вершин, n=|E| - число ребер. Если m и n конечны, то граф конечный.
Пр1: V={1,2,3,4}, E={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}
Путь из ai в aj:
Путь из вершины в саму себя, не содержащий дважды одно и тоже ребро, наз‑ся циклом. Если цикл состоит из одного ребра, то его называют петлей.
Граф, не сод-ий циклов, наз-ся ациклическим.
Граф наз-ся связным, если между любыми его вершинами существует путь.
Г
Т
[Т] каждый конечный граф G м.б. реализован в трехмерном евклидовом пространстве.
Граф, который м.б. реализован в 2-мерном пр-ве - плоский (планарный).
П р2: не планарный граф:
Два графа наз-ся изоморфными, если они имеют одинаковое кол‑во вершин и ребер и сущ-ет взаимнооднозначное соответствие между вершинами и ребрами этих графов, при котором соотв. ребра соед-ся с соотв. верш-ми.
Дерево – любой связный ациклический граф.
Деревом графа наз-ся любой связный ациклический подграф. Если дерево графа содержит все его вершины, то оно наз-ся остов.
Маршрут из 0 в k = 0l11l2…lkk, где li=(i-1i). Если все ребра маршрута различны, то это цепь.
Эйлеровой цепью в графе наз-ся замкнутая цепь, сод-ая все ребра.
Г
Т
граф явл-ся эйлеровым т.тогда, когда степень каждой вершины четная.
Гамельтоновым циклом наз-ся простой цикл, содержащий все вершины.
Алгоритм построения остовного дерева минимальной стоимости: ребра в графе упорядочиваем по возрастанию. последовательно выбираем ребра (из упорядоченной последовательности) до тех пор, пока выбранные ребра не дадут дерева. Очередное ребро выбираем только в том случае, если при его добавлении не возникает цикла.
Задачи на графы: задача комивояжера (нахождение минимального гамильтонова цикла на графе с N вершинами), транспортная задача
7. Дм теория кодирования, алфавитное кодирование, проблема однозначности кодирования, префиксные коды
сообщение[кодер]код сообщ.[канал связи]код сообщ.[декодер]сообщ. на выходе
Проблемы: однозначность кодирования, оптимизация кодирования, обнаружение и исправление ошибок
П усть a={a1,a2,…,an}-исх. алф., A= , l(A) – длина слова, S(A)-мн‑во всех слов в алф. A, S(A)S(A)-мн‑во всех возм-х сообщ. на входе; b={b1,b2,…,bq}-алфавит, В- слово в нем.
Пусть задано отобр. F: AS(A) BS(B). Слово B – код сообщения A. Процесс перехода от A к B – кодирование. Отобр. F- некоторый алгоритм.
Алфавитное кодирование: задается схема кодирования , которая каждому символу алфавита a ставит в соответствие слово B из алфавита b:
: |
a1 – B1 |
Слова B1…Br нас-ся элементарными кодами. Могут иметь произвольную конечную длину |
a2 – B2 |
||
… |
||
ar – Br |
Рассмотри проблему однозначности кодирования:
Будем считать, чт S(a)=S(a). Пусть S(B)S(B) – образ мн-ва S(A) при кодировании. Если отображение S(A)S(B) взаимнооднозначно, то проблема декодирования решается однозначно.
Пр1: |
: |
a1 – b1 |
-однозначна |
a2 – b1b2 |
Пусть слово B=BB. Тогда B - префикс, B - суффикс.
С
Т
если схема кодирования обл-ет св-вом префикса, то кодирование будет взаимнооднозначным.
Пр2: |
: |
a1 – b1b2 |
-обдадает св-вом префикса однозначна |
a2 – b1b1 |
|||
a3 – b3 |
Т еорема Маркова:
l(B)-длина слова B, li=l(Bi), -длина схемы кодирования
П
Т
Э
Т
Алфавитное кодирование со схемой явл-ся неодн‑м т.тогда, когда граф Г() содержит ориентированный цикл, проходящий через вершину .