С.А. Ложкин, В.В. Жуков - Построение базы данных оптимальных или близких к оптимальным КС и AIG (1132849)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Построение базы данных оптимальных илиблизких к оптимальным контактных схем иAnd Inverter Graph’овВведениеГлобальная задачаДля всех функций от 5 переменных построить оптимальные посложности схемы.ВведениеГлобальная задачаДля всех функций от 5 переменных построить оптимальные посложности схемы.Сейчас существует база для контактных схем и And Inverted Graph’ов.ВведениеГлобальная задачаДля всех функций от 5 переменных построить оптимальные посложности схемы.Сейчас существует база для контактных схем и And Inverted Graph’ов.Не все схемы в ней являются оптимальными.ВведениеВсе 232 функций разбиваются на 1, 228, 156 классов эквивалентности.ВведениеВсе 232 функций разбиваются на 1, 228, 156 классов эквивалентности.Каждый класс включает в себя функции, получаемые друг из друга перестановкой и инвертированием переменных.ВведениеРаспределение сложностей контактных схемВведениеУтверждение 1Верно следующее равенство:LКС (5) = 19ВведениеУтверждение 1Верно следующее равенство:LКС (5) = 19Верхнюю оценку доказывает построенная база схем.Нижняя оценка доказана Сусовым в 1981 году.ВведениеРаспределение сложностей AIGВведениеУтверждение 2Верно следующее равенство:LAIG (5) ≤ 17ВведениеУтверждение 2Верно следующее равенство:LAIG (5) ≤ 17Верхнюю оценку доказывает построенная база схем.Нижняя оценка не доказывалась.Открытые проблемыВ базе осталось 9 контактных схем сложности 19.Являются ли они оптимальными?Возможно, можно построить схемы меньшей сложности для некоторых из этих функций.Открытые проблемыВ базе осталось 9 контактных схем сложности 19.Являются ли они оптимальными?Возможно, можно построить схемы меньшей сложности для некоторых из этих функций.Задача 1Попытаться улучшить одну или несколько из 9 схем сложности19.Открытые проблемыТакже можно улучшать не только самые сложные схемы, но исхемы меньшей сложности.Открытые проблемыТакже можно улучшать не только самые сложные схемы, но исхемы меньшей сложности.Задача 2Предложить алгоритм синтеза контактных схем для функций отмалого числа переменных.Улучшить с помощью него базу КС.Оценивание решения будет основываться на сложности улучшенных схем и их количестве.Открытые проблемыЗадача 3Попытаться улучшить несколько из 55 AIG сложности 17.Задача 4Предложить алгоритм синтеза AIG для функций от малого числапеременных.Улучшить с помощью него базу AIG.Открытые проблемыКак было сказано выше, не существует никакой нетривиальнойоценки функции Шеннона для And Inverter Graph’ов от 5 переменных.Задача 5Вывести нижнюю оценку функции Шеннона LAIG (5).Отправка решенийДля внесения своего вклада в базу схем нужно:I Зарегистироваться в системе Spoon Enginehttp://mks2.cs.msu.ruОтправка решенийДля внесения своего вклада в базу схем нужно:I Зарегистироваться в системе Spoon Enginehttp://mks2.cs.msu.ruI Дождаться получения прав на отправку схем (ускорить этоможно, написав на vk.com/zhvv1 или zhvv117@gmail.com)Отправка решенийДля внесения своего вклада в базу схем нужно:I Зарегистироваться в системе Spoon Enginehttp://mks2.cs.msu.ruI Дождаться получения прав на отправку схем (ускорить этоможно, написав на vk.com/zhvv1 или zhvv117@gmail.com)I Залить свои решенияОтправка решенийДля внесения своего вклада в базу схем нужно:I Зарегистироваться в системе Spoon Enginehttp://mks2.cs.msu.ruI Дождаться получения прав на отправку схем (ускорить этоможно, написав на vk.com/zhvv1 или zhvv117@gmail.com)I Залить свои решенияI PROFIT!Что было сделано1.

Полный перебор КС с малым число контактовЧто было сделано1. Полный перебор КС с малым число контактов2. Полный перебор AIG не осуществлялсяЧто было сделано1. Полный перебор КС с малым число контактов2. Полный перебор AIG не осуществлялся3. Метод каскадов и его модификации для КС (LКС (5) ≤ 24)Что было сделано1.2.3.4.Полный перебор КС с малым число контактовПолный перебор AIG не осуществлялсяМетод каскадов и его модификации для КС (LКС (5) ≤ 24)Построение КС по тупиковым ДНФ (LКС (5) ≤ 22)Что было сделано1.2.3.4.5.Полный перебор КС с малым число контактовПолный перебор AIG не осуществлялсяМетод каскадов и его модификации для КС (LКС (5) ≤ 24)Построение КС по тупиковым ДНФ (LКС (5) ≤ 22)Мутации существующих в базе схем(LКС (5) ≤ 19, LAIG (5) ≤ 17).

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций