- •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.Машины Тьюринга. Примеры. Функции, вычислимые по Тьюрингу.
71. Понятие алгоритма. Основные свойства алгоритмов. Вычислимость.
Под алгоритмом понимается способ преобразования представления информации.
Основные особенности алгоритма:
Определенность. Алгоритм разбивается на отдельные шаги (этапы), каждый из которых должен быть простым и локальным.
Ввод. Алгоритм имеет некоторое (быть может, равное нулю) число входных данных, т.е. величин, заданных ему до начала работы.
Вывод. Алгоритм имеет одну или несколько выходных величин, т. е. величин, имеющих вполне определенное отношение к входным данным.
Детерминированность. После выполнение очередного шага алгоритма однозначно определено, что делать на следующем шаге.
Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, её вычисляющий, то есть такой алгоритм A, что
• если f(n) определено для некоторого натурального n, то алгоритм A останавливается на входе n и печатает f(n);
• если f(n) не определено, то алгоритм A не останавливается на входе n.
Несколько замечаний по поводу этого определения:
1. Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое под множество натурального ряда). Например, нигде не определённая функция вычислима (в качестве A надо взять программу, которая всегда зацикливается).
2. Можно было бы изменить определение, сказав так: «если f(n) не определено, то либо алгоритм A не останавливается, либо останавливается, но ничего не печатает». На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).
3. Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0, 1}), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, «конструктивные объекты». Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.
72. Рекурсивные функции. Операторы суперпозиции и примитивной рекурсии.
Исходными функциями являются:
1) z(х) = 0 — нуль функция;
2) N(x) = х + 1 — функция следования:
3) Ik(x1,...,xn) = Xk k=1…n. —селекторная функция, (функция выбора аргумента, проектирующая функция)
Из исходных функций образуются все остальные функции при помощи операций, которые наз. Функциональными операторами.
Целочисленные компоненты вводятся как суперпозиции функций z(x) и N(x): N(z(x))=0+1=1 N(N(z(x)))=2
Функцию g(x)=x+z можно записать как:
N(N(I1(x))) = (x+1)+1=x+2
Говорят, что функция n получается применением операции суперпозиции S, функция f,g1,…,gn при этом записывается так:
h= S( f,g1,…,gn) если h(x1,...,xn)= f(g1( x1,...,xn),…, gn( x1,...,xn))
Говорят, что функция f зависящие от h+1 переменной получаются применением оператора примитивной рекурсии R к функция g(xn) и h(xn+1) если f=R(g,h):
1)f(x1,...,xn,0) = g(x1,...,xn)
2) f(x1,...,xn,k+1)=h(x1,...,xn,k,f(x1,...,xn,k)) k=N {0}
В данном случае рекурсия ведется по последней переменной и выражает уже известный способ математической индукции.
Функция f называется примитивно-рекурсивной если она может быть получена из исходных функций применением конечного числа операторов суперпозиции и примитивной рекурсии.