- •2.Высказывания.Операции над высказываниями.
- •3. Тождественно истинные и тождественно ложные высказывания. Равносильные высказывания.
- •4.Суперпозиция функций. Бинарные отношения. Свойства бинарных отношений
- •5.Отношение порядка. Отношение эквивалентн. Бинарные опер.
- •6. Алгебры. Алгебра Кантора и булева алгебра. Изоморфизм. Операции над двоичными числами.
- •7. Булевы функции. Мощность множества булевых функций от переменных.
- •8. Элементарные булевы функции.
- •9. Формулы. Основные эквивалентности формул.
- •Порядок действий в формулах алгебры логики
- •10. Принцип двойственности. Двойственные булевы функции.
- •11.Теорема о разложении
- •12. Совершенные дизъюнктивные нормальные формы.
- •25. Перестановки с повторениями
- •26. Полиномиальная теорема. Принцип Дирихле.
- •27.Рекуррентные соотношения и производящие функции.
- •28. Принцип включения и исключения:
- •30. Схемы правильных рассуждений. Аксиоматические теории
- •32. Минимальные , кратчайшие и тупиковые днф.
- •33. Сокращённые днф. Построение сокращённых днф булевых функций методом Блейка.Пример.
- •34. Построение сокращённых днф булевых функций методом Квайна.Пример.
- •35.Построение Сокращенных днф геометрическим методом. Пример.
- •36. Построение минимальных днф с помощью карт Карно.
- •37. Метод Нельсона. (Построение сокращенной днф с помощью кнф).
- •38.Построение всех тупиковых днф. Алгоритм минимизации функций в классе нормальных форм.
- •39. Понятие о функциях k-значной логики. Их особенности.
- •40.Графы. Изоморфизм графов.
- •41.Способы задания графов.
- •42. Действия над графами.
- •43. Ориентированные и неориентированные графы.
- •44.Маршруты. Пути. Цепи. Связные графы.
- •45. Геометрическая реализации графа. Теорема о реализации конечного графа в трёхмерном пространстве.
- •46.Эйлеровы циклы. Задача о кенигсбергских мостах. Теорема Эйлера.
- •47.Обобщенная теорема об эйлеровых цепях.
- •48. Гамильтоновы графы. Задача о коммивояжере.
- •49. Взвешенный граф. Граф-дерево.
- •50. Цикломатическое число. Остов графа. Базис циклов.
- •51. Двудольные графы.
- •52. Планарные графы. Критерий планарности.
- •53. Теорема Куратовского-Понтрягина. Граф Петерсена.
- •54.Двухполюсные сети. Параллельно-последовательные сети. Поток в сети.
- •55.Теорема Форда-Фалкерсона о максимальном потоке. Расчет максимального потока в сети.
- •56.Общие принципы помехоустойчивого кодирования. Примеры.
- •57.Типы ошибок. Сжатие информации.
- •58.Код Хэмминга.
- •59.Троичный код Хэмминга. Пример.
- •60.Алфавитное кодирование.
- •61. Алгоритм Фано.Пример
- •62. Алгоритм кодирования Хаффмена.Пример
- •63. Формальные грамматики. Основные понятия.
- •64. Классификация языков по Хомскому
- •65. Типы языков. Вывод цепочек. Дерево вывода
- •66.Конечные автоматы. Автоматы Мили и Мура. Канонические уравнения
- •67.Таблица состояний, диаграмма состояний автомата.
- •68.Дешифратор.
- •69.Реализация автоматов схемами.
- •70. Ограниченно детерминированные функции. Информационные деревья.
- •71. Понятие алгоритма. Основные свойства алгоритмов. Вычислимость.
- •72. Рекурсивные функции. Операторы суперпозиции и примитивной рекурсии.
- •73. Примитивно рекурсивные предикаты. Свойства.
- •74. Классы рекурсивных функций. (п.Р., о.Р., ч.Р.). Тезис Черча.
- •75. Машины Тьюринга. Принципы работы. Протокол работы.
- •76.Машины Тьюринга. Примеры. Функции, вычислимые по Тьюрингу.
58.Код Хэмминга.
Зафиксируем число n, вычислим l такое, что 2l-2≤n≤2l, т.е. l=[]=1. Для произвольного слова Х=х1х2…хnвычислим H(x)=x1el(1)…xnel(n)- вектор полученный в результате сложения векторов el(i), является двоичными кодами номеров единичных символов слова х.
Теорема(Код Хэмминга): Hn состоящий из всех слов Х=х1х2…хn, таких, что Hn(х)=(0,0,..,0) является кодом с исправлением одного замещения. |Hn|- число элементов кода |Hn|=2n-1, причём компоненты или позиции соответствующие 20,21,22,…,2l-1 наз. проверочными позициями. Позиции отличные от проверочных называются информационными.
Суть метода Хэмминга в том, что кодируемое слово длины n дополняется l проверочными разрядами, которые определяются образом высчитывания при кодировании. В итоге передаёт слово, длины m+l, где проверочные символы стоят на 20,21,22,…,2l-1месте.
59.Троичный код Хэмминга. Пример.
Расширенный код Хэмминга(EHml) получен из двоичного кода Хэмминга добавлением бита проверенного на чётность, минимальное расстояние в таком коде увеличивается до 4, т.е. полученный код исправляющий одну ошибку и обнаруживающий 2 ошибки. Код Хэмминга может быть распространён на любое конечное поле Fq. Выберем произвольно l и построим проверочную матрицу для линейного кода Fq с избыточностью b исправляемую одну ошибку, добавлением каждый новый столбик будем проверять, что он ЛНЗ от ранее выбранного столбца.
1.Выберем q0=1 столбцов, когда столбец выбран, удаляем из дальнейшего рассмотрения не только этот столбец, но и все его q-1 кратных столбцов. Получим, что . Построен таким образом минимальный кодHml(p) имея избыточность если существует проверочная матрица семейства столбцов.
Теорема: Код Хэмминга избыточности 1 над полем Fq является линейным:является совершенным кодом исправляющим ошибку.
Док-во: Длина кода n=, т.к. код имеет избыточностьl, то его размерность n-l, значит граница Хэмминга определяется условиями qn-l(1+(q-1)n)≤qn, qn-l(1+(q-1))=qn-lql=qn≤qn код является совершенным.
Задача: Рассмотри троичный [13,10] код Хэмминга
Декодировать (2,2,2,2,2,2,1,1,1,1,1,1,1) Х=(11001), |Х|=5, l=[]+1=4 и ещё построить таблицу и найти проверочные элементы.
60.Алфавитное кодирование.
Постройка кода, когда кодируется каждая буква алфавита А={а1,а2,…} называется алфавитным кодированием.
Пусть α=α1α2 некоторое слово, тогда α1 называется префиксом(началом слова), а α2-постфиксом(конец слова). Алфавитное кодирование задаётся схемой: δ=(α1→β1,…,αn→βn) где αi, βi. Множество слов V={βi |βi}, i=1,n называется множеством элементарных кодов.
Алфавитное кодирование можно использовать для любого множества сообщений S. F:A*→B* ,если F(α)=(βi1,…,βik), где α=(αi1,…,αik).
Пример: А={0,1,2,3,4,5,6,7,8,9} B={0,1}
δ1={0→0, 1→1, 2→10, 3→11, 4→100, 5→101, 6→110, 7→111, 8→1000, 9→1001}.
Пример: А={0,1,2,3,4,5,6,7,8,9} B={0,1}
δ2={0→0000, 1→0001, 2→0010, 3→0011, 4→0100, 5→0101, 6→0110, 7→0111, 8→1000, 9→1001}.
Схемы δ1и δ2 являются однозначными, но δ1не является взаимно-однозначным соответствием, а кодирование по схеме δ2 является взаимно-однозначным. Схема алфавитного кодирования δ называется разделимой, если любое слово, составленное из элементов кодов единственным образом, разбивается на эти элементарные коды. Алфавитное кодирование с разделимой схемой допускает декодирование.
Теорема: Префиксная схема является разделимой. Для того чтобы схема алфавитного кодирования была разделимой необходимо, чтобы длина элементарных кодов удовлетворяла неравенству Макмиллана: , гдеki=|βi|.