|
|
 |
> К списку экзаменов
- Размещения, сочетания, перестановки и формулы для подсчета числа их элементов.
- Число элементов сочетаний с повторением.
- Бином Ньютона.
- Булевы функции. Табличный способ задания булевых функций. Элементарные булевы функции.
- Существенные и фиктивные переменные. Равенство булевых функций.
- Формулы. Реализации булевых функций формулами.
- Эквивалентные формулы. Эквивалентные преобразования формул.
- Двойственные функции. Принцип двойственности.
- Теорема о разложении булевых функций по переменным.
- Совершенная ДНФ. Совершенная КНФ. Полином Жегалкина.
- ДНФ. Проблема минимизации ДНФ.
- Тупиковая ДНФ. Алгоритм упрощения ДНФ.
- Постановка задачи минимизации булевых функций в геометрической форме. N-мерный единичный куб.
- Сокращенная ДНФ. Теорема о покрытии.
- Теорема связи между сокращенной и минимальной ДНФ.
- Построение сокращенной ДНФ.
- Алгоритм построения тупиковой ДНФ.
- Определение полной системы булевых функций. Теорема о сведении полноты одной системы к другой.
- Замкнутые классы и их свойства. Теорема о полноте.
- Теоремы Поста.
- Графы. Ориентированные и неориентированные графы. Путь. Цепь. Цикл.
- Связные графы.
- Полные графы. Изоморфные графы.
- Оценка числа графов.
- Геометрическая реализация графа.
- Сети, деревья.
- Двухполюсные сети. Операция подстановки сетей.
- Сильносвязные сети. Граничные вершины. Отростки.
- Тривиальная сеть. Классы сетей. P-сеть, S-сеть, H-сеть.
- Определение P-, S-, H-разложимых сетей. Лемма о единственности типа разложений.
- Определение логической сети.
- Схемы из функциональных элементов. Проводимость схемы.
- Синтез сумматора.
- Функция Шеннона. Теорема о нижней оценке функций Шеннона.
- Теорема о верхней оценке функций Шеннона.
- Детерминированные функции. Определение.
- Задание детерминированных функций с помощью деревьев. Вес дерева.
- Алфавитное кодирование. Постановка задачи распознавания взаимооднозначности алфавитного кодирования.
- Префиксная схема. Теорема о префиксной схеме.
- Построение графа по префиксной схеме.
- Неравенство Макмиллана (теорема).
- Равномерное кодирование.
- Коды с минимальной избыточностью. Средняя длина. Лемма о кодах с минимальной избыточностью.
- Коды Хемминга. Построение кодов.
- Описание машины Тьюринга.
- Операции над машинами Тьюринга.
- Операции суперпозиции, примитивной рекурсии, минимизации.
- Теорема о вычислимости частично-рекурсивной функции.
|
