- •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.Машины Тьюринга. Примеры. Функции, вычислимые по Тьюрингу.
69.Реализация автоматов схемами.
Функциональным элементом называется устройство, имеющее n упорядоченных отрезков вверху, которые называются входами, и один отрезок внизу, называемый выходом функционального элемента.
Функциональный элемент изображается так:
На входы функционального элемента могут подаваться сигналы двух типов, причём при подаче набора сигналов на входы элемента задержки, на выходе мгновенно возникает сигнал одного из этих типов, причём каждый набор входных сигналов однозначно определяет значение выходного сигнала.
Элементом задержки называется конечный автомат, имеющий два внутренних состояния, входной и выходной алфавиты которого имеют по два символа и совпадают, и который осуществляет задержку входного сигнала на один такт времени.
Элемент задержки изображается так:
Верхний отросток называется входом, а нижний — выходом элемента задержки.
Полюсами называется упорядоченный набор кружков, помеченных символами различных переменных. Схема из функциональных элементов и элементов задержки определяется
индуктивно:
а) совокупность полюсов (кружков, помеченных символами переменных) есть схема; все полюсы являются её вершинами',
б) результат присоединения к вершинам схемы всех входов некоторого элемента (функционального элемента или элемента задержки) есть схема; вершинами новой схемы являются все вершины исходной схемы и выход присоединённого элемента,
а полюсами — все полюсы исходной схемы;
в) результат присоединения выхода задержки к некоторому полюсу xi есть схема; её вершинами являются все вершины исходной схемы, за исключением х-, а полюсами — все полюсы исходной схемы, кроме xi. Операция, соответствующая пункту в), называется введением обратной связи.
70. Ограниченно детерминированные функции. Информационные деревья.
Если А- какой-либо алфавит, то пусть A* обозначает множество всех слов, а A0 - множество всех слов или множество всех сверхслов в алфавите А. Функция f, отображающая A0 в B0 , где Аи В- произвольные конечные алфавиты, наз. детерминированной функцией, если выполняются следующие два условия:
1) для любого α из A0 длина f(α) равна длине а
2)если-α слово длины l где α1 = αα’ , α2 = αα’’, α’, α’’Є A0 , то значения f(α1) и f(α2) имеют одинаковые начала длины l.
Если детерминированная функция f определена на множестве всех сверхслов в алфавите А, то в силу условий 1) и 2) она однозначно распространяется на множество A*: для произвольного слова α длины l значение f(a) совпадает с началом длины l значения f(αβ) , где β- произвольное сверхслово в алфавите А. Таким образом, всякая детерминированная функция f удовлетворяет условию:
3) для любого слова α из A* и любого β из A0 справедливо равенство f(αβ) = f(α)fα(β), где f α - некоторая детерминированная функция на множестве A0 , однозначно определяемая словом α.
Функция fa , наз. остаточной функцией для f. Из условия 3) следует, что всякая детерминированная функция f определяет на множестве A* отношение эквивалентности R: αRβ тогда и только тогда, когда fα=fβ . Ранг этого отношения, или, что то же, максимальное число попарно различных остаточных функций, наз. весом детерминированной функции f.
Если вес детерминированной функции конечен, то она наз. ограниченно-детерминированной функцией. Это понятие распространяется и на функции от т-переменных, где m≥2 если наборы из т-слов одинаковой длины (или сверхслов) в алфавитах A1, … , Am соответственно рассматривать как слова (сверхслова) в алфавите A1× … × Am , являющемся декартовым произведением алфавитов A1, … , Am . Таким же образом можно рассматривать О.-детерминированной функции с несколькими выходами, т. е. значениями которых являются наборы из к-слов или сверхслов соответственно в алфавитах B1, … , Bk Класс всех О.-детерминированной функции совпадает с классом функций, вычислимых конечными автоматами. Поэтому для задания О.-детерминированной функции могут быть использованы те же средства, что и для задания конечных автоматов, например, каноническое уравнения (см. Автомат конечный, Автоматов способы задания). Отсюда следует, в частности, что класс О.-детерминированной фунции с совпадающими алфавитами A1= … =Am = B замкнут относительно суперпозиций. Минимальный (по числу состояний) автомат U(A, S, B, φ, ψ, s1 ) вычисляющий О.-детерминированной функции f веса т, содержит п-состояний и может быть построен следующим образом. Пусть α1, …,αn - произвольные представители всех классов эквивалентности отношения R. Каждому классу R(αi), i=1, … , n , ставится в соответствие некоторое состояние si автомата U. Функция переходов j и функция выходов ψ определяются следующими условиями: если aЄA и 1≤ i ≤n, то φ(si, a)=sj , где состояние sj соответствует классу R(αi a); ψ(si, a)=fαi(a). В качестве начального берется состояние, соответствующее классу R(е), где е - пустое слово.