- •Множества. Операции над множествами.
- •Законы алгебры множеств.
- •Мощность множества. Теорема о числе подмножеств конечного множества.
- •Бинарные отношения и их типы
- •Отношение эквивалентности. Теорема о разбиении множества на классы.
- •Перестановки и сочетания
- •Формулы о подсчете числа подстановок из сочетаний с повторениями и без повторений.
- •Высказывания. Операции над высказываниями.
- •Булевы функции
- •12. Законы равносильности. Доказать законы Де Моргана.
- •13. Формулы алгебры логики, их классификация и примеры.
- •14. Алгоритмы определения типа формулы.
- •15. Двойственные формулы. Принцип двойственности.
- •20. Сднф и алгоритмы ее построения.
- •21. Скнф и алгоритмы ее построения.
- •22. Теорема о разложении.
- •23. Контактные схемы.
- •24. Логические схемы.
- •26.Область истенности булевой фун-ции. Покрытие обл. Заданной в днф.
- •27.Метод Блейка,Нельсона, графический метод.
- •28. Минимальная днф. Метод инпликантных матриц.
- •29.Сокращенная днф. Теорема о связи сднф и мднф.
- •30. Тупиковая днф. Теорема о связи тднф и мднф
- •31.Алгоритмпостроения тупиковой днф
- •41. Квантор общности. Теорема о применении квантора общности для предиката определенном на конечном множестве.
- •42. Квантор существования. Теорема о применении квантора существования для предиката определенного на конечном множестве.
- •43. Законы алгебры логики предикатов.
- •44. Тождественно истинные предикаты, примеры. Теорема о тождественно истинных предикатах.
- •45. Тождественно ложные предикаты и теорема о тождественно ложных предикатах.
- •46. Понятие следствия и равносильности предикатов, примеры.
- •47. Формулы алгебры логики предикатов и их классификация.
- •48. Законы Де Моргана для алгебры логики предикатов.
- •49. Закон пронесения квантора общности через конъюнкцию.
- •50. Закон пронесения квантора существования через дизъюнкцию.
- •51.Закон пронесения квантора общности и существования через импликацию.
- •53. Детерминированные функции и графическое изображение (примеры).
- •54. Ограничено-детерминированные функции.
- •55. Диаграммы Мура.
- •56. Канонические уравнения ограничено-детерминированных функций.
- •57. Машины Тьюринга.
- •58. Простейшие функции. Теорема о простейших функциях.
- •59. Операция примитивной рекурсии. Примитивно-рекурсивные функции. Примеры.
- •60. Операция минимизации. Рекурсивные функции.
- •61. Тезисы Тьюринга и Черча. Теорема о связи между рекурсивными функциями и функциями вычислимыми по Тьюрингу (без доказательства).
- •62. Графы. Способы задания графов.
- •63. Формула Эйлера.
- •64. Графы к3,3 и к5,5. Теорема.
- •65. Плоские графы. Теорема о плоских графах (без доказательства).
- •66. Эйлеровые графы. Теорема о Эйлеровых графах. Гамильтоновы графы.
- •67. Деревья. Теорема о деревьях (без доказательства).
- •68. Предмет теории кодирования, алфавитное кодирование.
- •69. Префиксный код. Теорема о префиксном коде.
- •70. Разделимый код. Теорема Маркова (без доказательства).
67. Деревья. Теорема о деревьях (без доказательства).
Дерево - это связный граф без циклов.
Теорема: в графе типа дерева с n вершинами n-1 ребер.
68. Предмет теории кодирования, алфавитное кодирование.
Кодирование – это преобразования информации в формулу удобную для передачи по определенному каналу связи. Декодирование – восстановление принятого сообщения из-за кодированного вида в вид доступный для потребителя.
В общем случае задачу кодирования можно представить следующим образом: Пусть заданы два алфавита А и В, состоящие из конечного числа символов:
А={a1,a2,…,an} и B={b1,b2,…,bn}. Элементы алфавита называются буквами. Упорядоченный набор в алфавите А назовем словом a=a1,a2,…,ai,…,an, где i принадлежит [1;n]. n называется длиной слова и обозначается | a |. Пустое слово обозначается /\. |/\|=0. Для слова a а1 является началом, а аn – окончанием. Множество всех непустых слов алфавита А обозначим А*: A*={ a, | a |>0}. Множество А называют алфавитом сообщений, а множество В — кодирующим алфавитом. Множество слов, составленных в алфавите В, обозначим В*. Обозначим через F отображение слов алфавита А в алфавит В. Тогда слово B=F(a) назовем кодом слова a. Кодированием называют универсальный способ отображения информации при ее хранении, передаче и обработке в виде системы соответствий между элементами сообщений и сигналами, при помощи которых эти элементы можно зафиксировать. Таким образом, код — правило однозначного преобразования (т.е. функция) сообщения из одной символической формы представления (исходного алфавита А) в другую (объектный алфавит В), обычно без каких-либо потерь информации. Процесс преобразования F: А*→В* слов исходного алфавита А в алфавит В называется кодированием информации. Процесс обратного преобразования называется декодированием.
69. Префиксный код. Теорема о префиксном коде.
Пре́фиксный код в теории кодирования — код со словом переменной длины, имеющий такое свойство (выполнение условия Фано): если в код входит слово a, то для любой непустой строки b слова ab в коде не существует. Хотя префиксный код состоит из слов разной длины, эти слова можно записывать без разделительного символа.
Например, код, состоящий из слов 0, 10 и 11, является префиксным, и сообщение 01001101110 можно разбить на слова единственным образом: 0 10 0 11 0 11 10
Код, состоящий из слов 0, 10, 11 и 100, префиксным не является, и то же сообщение можно трактовать несколькими способами: 0 10 0 11 0 11 10 0 100 11 0 11 10
Теорема: Если |B| = q и натуральные числа l1, l2, …, lr удовлетворяют неравенству:
то существует префиксный код B1, B2, …, Br (в алфавите B) такой, что
длина(Bi) = li (i = 1, 2, …, r).
70. Разделимый код. Теорема Маркова (без доказательства).
Кодирование A* → B* называется взаимно однозначным (декодируемым,
разделимым), если для любых слов и
Теорема: Пусть : ai → Bi (i = 1, 2, …, r) — некоторое кодирование.
Пусть W — максимальное число кодовых слов, которые «помещаются» подряд внутри кодового слова. Пусть li — длина слова Bi и . Тогда если кодирование не взаимно однозначно, то существуют два различных слова a' A*, a'' A*,