Вариант 2
Показать, что ├ А→АА.
Применить операцию к f по xi, результирующую функцию представить в аналитической форме, где f(x1,x2)=Sg(x1
2x2),
i=1.Найти вес о.-д.ф.
y(t)=
1(t-1)q2(t-1)
q1(t)=q1(t-1)→x(t)
q2(t)=
2(t-1)
q1(0)=q2(0)=1
Является ли код С однозначно декодируемым, где
С={20,01202,22,2001,2012010,10201121,1112}. Найти неприводимое слово.
Построить f(x,y)=R(g,h), применяя операцию Пр к g(x) и h(x,y,z) по переменной y, записать f(x,y) в аналитической форме, где g(x)=1, h(x,y,z)=x y.
Вариант 3
Показать, что ├ АА→А.
Применить операцию к f по переменной xi. Результирующую функцию представить в аналитической форме, где f(x1,x2)=
(x1,x2),
i=2.Найти вес о.-д.ф.
y(t)=
q1(t-1)
2(t-1)+
1(t-1)q2(t-1)
q1(t)=
1(t-1)q2(t-1)
q2(t)=
2(t-1)
q1(0)=0, q2(0)=1
Является ли код С однозначно декодируемым, где С={001,021,102,201,001121,01012101}. Найти неприводимое слово.
Построить f(x,y)=R(g,h), применяя операцию Пр к g(x) и h(x,y,z) по переменной y, записать f(x,y) в аналитической форме, где g(x)=3х, h(x,y,z)=3уz.
Вариант 4
Показать, что ├ (А→В) → (А→А).
Применить операцию m к f(x)=
– .
Результирующую функцию записать в
аналитической форме,
Найти вес о.-д.ф.
y(t)=
+
1(t-1)+q2(t-1)
q1(t)=q2(t-1)→q1(t-1)
q2(t)=q1(t-1)
q1(0)=q2(0)=0
Является ли код С однозначно декодируемым, где С={0,01,0010001001}. Найти неприводимое слово.
Применяя операцию Пр к g(x) и h(x,y,z) по y, построить f(x,y)=R(g,h), записав её в аналитической форме, где g(x)=x, h(x,y,z)=x+у.
Вопросы экзамена
1 Семестр
ФАЛ, табличное представление, перечень всех элементарных ФАЛ.
Основные тождества ФАЛ.
Правила поглощения, склеивания и обобщенного склеивания.
Существенные и фиктивные переменные ФАЛ.
Понятие формулы. Реализация ФАЛ формулами.
Равенство ФАЛ, эквивалентность формул.
Определение операции суперпозиции над ФАЛ, пример.
Разложение ФАЛ по к переменным, где к<n.
СДНФ, СКНФ (k=n).
10. Полнота системы ФАЛ (2 теоремы).
11. Примеры полных систем (не менее 6 с доказательством полноты).
12. Единственность представления ФАЛ полиномами Жегалкина.
Методы построения полинома Жегалкина.
Замыкание, свойства операции замыкания (с доказательством), замкнутые классы.
Класс Т0 , его свойства.
Класс Т1, его свойства.
Класс L, леммы о нелинейных функциях.
Принцип двойственности.
Класс S, его свойства.
Лемма о несамодвойственной функции.
Класс М, его свойства.
Лемма о немонотонной функции.
Теорема о полноте в Р2 .
Возможность выделения из любой полной системы в Р2 полной подсистемы, состоящей из не более чем 4-х функций.
Предполные классы в Р2 .
Базисы, примеры базисов (обязательно для всех предполных классов, для каждого не менее 2-х базисов).
Представление о результатах Поста.
Правило суммы, произведения в комбинаторике (примеры).
Число r-перестановок без повторения, доказательство, пример.
Число r-перестановок с повторением, доказательство, пример.
Число r-сочетаний без повторения, доказательство, пример.
Число r-сочетаний с повторением, доказательство, пример.
Биномиальные коэффициенты и их свойства
Биномиальная теорема, доказательство, применение.
Полиномиальная теорема, доказательство, применение.
Формула включения и исключения, примеры (число функций от данного числа существенных переменных).
Формула решета, применение.
Производящие функции и их свойства, применение.
Определение схемы из функциональных элементов (СФЭ).
Реализация любой ФАЛ некоторой СФЭ, теорема.
Сложность СФЭ, функция Шеннона, основная задача синтеза.
Метод синтеза, основанный на моделировании СДНФ ФАЛ.
Метод синтеза, основанный на совместной реализации всевозможных конъюнкций длины n.
Метод Шеннона.
Специальное представление ФАЛ в асимптотически наилучшем методе синтеза.
Асимптотически наилучший метод синтеза. Метод Лупанова.
Графы. Основные понятия и определения.
Способы представления графов. Пример.
Графы, все виды графов. Примеры.
Некоторые соотношения в графе.
Перечисление графов (3 задачи).
Равенство графов. Изоморфность графов. Примеры.
Оценка числа неизоморфных графов (с p вершинами и q ребрами отдельно).
Укладка графов. Укладка графов в трехмерном пространстве.
Плоскость, планарность графов.
Формула Эйлера для плоских графов.
Следствия, вытекающие из формулы Эйлера для плоских графов.
Непланарность графов К5 и К3,3.
Операция подразделения ребра. Гомеоморфность графов. Примеры.
Теорема Понтрягина-Куратовского.
Критерий Понтрягина-Куратовского планарности графов. Пример.
Деревья и их свойства (с доказательством).
Деревья и операции над ними, примеры.
Оценка числа неизоморфных корневых деревьев с q-ребрами.