ДМ 1 курс - 4 лекция - преобразование Мёбиуса, схемы из функциональных элементов

• Обсуждение теоремы и формулы преобразования Мебиуса.  

• Упоминание алгоритма построения полинома Жегалкина.  

• Введение в теорию, лежащую в основе этих методов.  

• Упоминание Мебиуса и его вклада в математику.  

• Объяснение односторонней поверхности Мебиуса.  

• Введение в полином Жегалкина и его доказательство существования.  

• Пример представления функции в виде полинома Жегалкина.  

• Запись полинома Жегалкина в общем виде.  

• Умножение на коэффициенты для обозначения выбора переменных.  

• Введение отношения доминирования для булевских векторов.  

• Переписывание формулы для вычисления значения функции.  

• Пример вычисления полинома Жегалкина для различных векторов.  

• Упрощение формулы для вычисления значений функции.  

• Рассматривается таблица истинности функции.  

• Подставляются все возможные наборы аргументов и вычисляются значения функции.  

• Таблица истинности функции представляет собой вектор в пространстве B^2^n.  

• Полином Жегалкина - это вектор коэффициентов, принадлежащих B^2.  

• Коэффициенты полинома Жегалкина соответствуют значениям функции при различных аргументах.  

• Полином Жегалкина и таблица истинности функции связаны через преобразование.  

• Преобразование вектора a в вектор f задается формулой.  

• Преобразование является линейным и может быть представлено как умножение матрицы на вектор.  

• Матрица преобразования не зависит от функции и одинакова для всех функций.  

• Пример матрицы преобразования для функции из четырех аргументов.  

• Матрица задает доминирование аргументов и преобразует вектор коэффициентов полинома Жегалкина.  

• Умножение матрицы на вектор коэффициентов дает таблицу истинности функции.  

• Обсуждение преобразования Жигалкина для получения таблицы истинности.  

• Упоминание о необходимости найти обратную матрицу для преобразования.  

• Доказательство существования обратной матрицы.  

• Доказательство, что матрица сама себе обратная.  

• Введение понятия преобразования Мебиуса.  

• Объяснение, что преобразование Мебиуса является инволюцией.  

• Объяснение умножения матрицы на вектор.  

• Пример с матрицей и вектором для получения элемента.  

• Упрощение формулы для получения результата.  

• Формулировка теоремы и подготовка к доказательству.  

• Преобразование правой части формулы.  

• Перебор возможных комбинаций для доказательства.  

• Перебор всех возможных комбинаций для доказательства.  

• Подсчет количества подходящих иксов.  

• Доказательство, что сумма коэффициентов равна единице.  

• Доказательство равенства вектора а матрице м.  

• Объяснение, что обратное преобразование является преобразованием Мебиуса.  

• Упоминание о матрице доминирования и её роли в преобразовании.  

• Аннотация Кнута используется для упрощения формул.  

• Пример: преобразование булевского утверждения в ноль или один.  

• Применение для построения таблицы коэффициентов многочлена Жигалкина.  

• Пример с таблицей истинности для стрелки Пирса.  

• Использование матрицы для получения коэффициентов многочлена Жигалкина.  

• Пример с доминирующими элементами и их проксованием.  

• Вопросы отсутствуют, переход к следующей теме.  

• Приветствие курсу архитектуры ЭВМ.  

• Обсуждение функциональных элементов и схем.  

• Обсуждение теоретических аспектов схем.  

• Изучение схем без циклов и их асимптотического поведения.  

• Введение в схемы из функциональных элементов и линейные программы.  

• Обзор способов представления булевых функций: таблицы истинности, формулы, схемы из функциональных элементов, линейные программы.  

• Проблемы с описанием функций короткими строками.  

• Естественные попытки человечества придумать короткие описания для функций.  

• Неизвестность конкретных семейств функций с нелинейными нижними границами.  

• Для случайной функции минимальная схема может иметь экспоненциальное число элементов.  

• Сложность доказательства нижних границ и методы их определения.  

• Обсуждение схем функциональных элементов.  

• Введение понятия ациклического ориентированного графа.  

• Объяснение, что такое граф и его элементы.  

• Определение ациклического ориентированного графа.  

• Отсутствие циклов в графе.  

• Пример циклического пути и его отсутствие в ациклическом графе.  

• Понятие топологической сортировки.  

• Определение и свойства топологической сортировки.  

• Отсутствие топологической сортировки в графах с циклами.  

• Доказательство теоремы о топологической сортировке.  

• Использование леммы о существовании вершины без ребер.  

• Индуктивное доказательство теоремы.  

• Удаление вершины без ребер и доказательство теоремы.  

• Завершение экскурса и возвращение к схемам функциональных элементов.  

• Схема функциональных элементов - это ориентированный граф с пронумерованными входящими ребрами.  

• Вершины делятся на три типа: входные, внутренние и выходные.  

• Входные вершины соответствуют входным переменным, внутренние - функциям, выходные - выходным переменным.  

• Входные вершины не имеют входящих ребер и соответствуют входным переменным.  

• Внутренние вершины помечены функциями и имеют входящую степень, равную арности функции.  

• Выходные вершины имеют только входящие ребра и соответствуют выходным переменным.  

• Схема вычисляет функцию, сопоставляя каждой вершине значение по топологической сортировке.  

• Входные вершины получают значения соответствующих аргументов.  

• Внутренние вершины вычисляют функции от значений в вершинах, из которых ведут ребра.  

• Выходные вершины получают значения от вершин, из которых ведут их единственные ребра.  

• Функцию можно представить формулой, используя множество функций, используемых в функциональных элементах.  

• Формула строится путем сопоставления каждой вершине формулы, соединяющей предыдущие вершины.  

• Формула и схема могут быть преобразованы друг в друга, что позволяет использовать оба представления для задания функции.  

• Схемы позволяют перестраивать целые куски схемы, добавляя или удаляя ребра.  

• Формулы компактнее, но схемы позволяют лучше контролировать структуру функции.  

• Преобразование формулы в схему и наоборот требует дополнительных шагов, но возможно.  

• Обсуждение перерисовки схемы горизонтально.  

• Выходные вершины не влияют на вычисления.  

• Каждая вершина вычисляет свою функцию, но одна из них объявляется главной.  

• Добавление новых элементов в схему.  

• Использование функциональных элементов для вычисления.  

• Пример с формулой для XOR.  

• Подстановка формулы для XOR.  

• Увеличение длины формулы при добавлении новых переменных.  

• Теорема Субботинской о невозможности линейной формулы для XOR.  

• Теорема утверждает, что не существует формулы линейной длины для XOR.  

• Изменение базиса может привести к радикальным изменениям.  

• Пример с добавлением в базис XOR.  

• Схемы более четко описывают сложность функций.  

• Пример с добавлением XOR в базис.  

• Изменение базиса приводит к радикальным изменениям в формулах.  

• Теорема утверждает, что функцию можно представить формулой в базисе тогда и только тогда, когда её можно представить схемой.  

• Пример с топологической сортировкой и деревом разбора.  

• Базисы для формул и схем совпадают.  

• Определение размера схемы.  

• Минимальное количество функциональных элементов в схеме.  

• Входы и выходы обычно не считаются.  

• Понятие глубины схемы.  

• Пример двух схем для XOR.  

• Использование специальных обозначений для функциональных элементов.  

• Рассматриваются две схемы с одинаковым размером, но разным алгоритмом вычисления.  

• Первая схема позволяет вычислить значение за два такта, вторая - за три.  

• Логика подсказывает, что первая схема лучше.  

• Глубина схемы определяется рекурсивно: глубина входов равна нулю.  

• Для каждой вершины берется максимум глубин вершин, из которых идут ребра, и прибавляется один.  

• Глубина всей схемы равна максимуму глубин всех вершин.  

• Глубина и размер схемы зависят от базиса.  

• Пример: в базисе "и или не" схемы увеличиваются в пять раз.  

• Теорема утверждает, что изменение базиса влияет только на константу.  

• Для любой функции и базиса существует константа, которая не зависит от функции.  

• Доказательство теоремы: выражение функции в базисе "б-один" увеличивает количество элементов не более чем в константу.  

• Оптимальная схема в базисе "б-один" не может быть хуже оптимальной схемы в базисе "б-два".  

• Рассматривается асимптотическое поведение размера схемы при увеличении количества аргументов.  

• Размер схемы зависит от количества аргументов, но не от конкретного базиса.  

• Пример: для функции "ксор" от n аргументов требуется n-1 элементов.  

• Размер схемы с точностью до константы определен однозначно для любой функции.  

• Для семейства функций сложность определяется константой, не зависящей от базиса.  

• Лекция завершается обсуждением этих выводов.