Скачать 0.91 Mb.
|
Глава 4. Задача сортировки реверсалами
генных последовательностей
Глава 5. Задача восстановления вершин графа
группах
СИНТЕЗ И СЛОЖНОСТЬ ДИСКРЕТНЫХ УПРАВЛЯЮЩИХ СИСТЕМ Введение. Понятие управляющей системы (УС), примеры: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, ветвящиеся программы. Проблемы оценок сложности управляющих систем. Связь с проблемой P NP Дизъюнктивные нормальные формы. Совершенные, минимальные, кратчайшие, сокращенные, тупиковые ДНФ. Соотношение между различными типами ДНФ Контактные схемы. Простейшие методы синтеза контактных схем. Метод Шеннона синтеза контактных схем. Метода Лупанова синтеза контактных схем Схемы из функциональных элементов. Метод Лупанова синтеза схем из функциональных элементов. Функция Шеннона сложности вычисления булевых функций схемами из функциональных элементов Теорема Яблонского о невозможности элиминации перебора при построении последовательности самых сложных функций Эффективные нижние оценки сложности. Сложность линейной функции в классе контактных схем. Метод Нечипорука получения нижних оценок сложности контактных схем, формул, ветвящихся программ Метод Субботовской. Пример Андреева Метод Храпченко получения нижних оценок сложности параллельно-последовательных контактных схем для линейной функции. Нижние оценки сложности вычисления булевых функций ветвящимися программами ЭЛЕМЕНТЫ ТЕОРИИ ДИСКРЕТНЫХ СТРУКТУР Формулы обращения. Формула включений и исключений. Частично упорядоченные множества, их функции Мебиуса и теорема об обращении Мебиуса. Производящие функции. Возвратные последовательности и рекуррентные соотношения. Решение линейных рекуррентных соотношений. Теорема Рамсея и ее частный случай для графов. Одно приложение теремы Рамсея. Теорема Ван-дер-Вардена. Конечные геометрии. Структура конечной плоскости. Конечные плоскости и их связь с другими комбинаторными конфигурациями: латинские квадраты. Блок-схемы и их связь с конечными плоскостями. Булевы функции, формулы. Реализации булевых функций. Дискретные устройства без памяти – схемы из функциональных элементов. Дискретные устройства с конечной памятью – конечные автоматы. Представление событий в автоматах. Существование событий, не представимых в конечных автоматах. Регулярные события. Источники. Детерминированные источники. Теоремы синтеза и анализа автоматов. Схемы отношений и дистанционно регулярные графы. Алгебра Боуза-Меснера. Дуальность в схемах отношений. Подмножества в схемах отношений. Схемы Хэмминга и Джонсона. Метрические и P(Q)-полиномиальные схемы. КОДЫ И СХЕМЫ Предметы теории кодирования, теории блок-схем (designs). Модель канала связи с шумами, определение кода (теоретические и геометрическое). Задание кода. Пример кода Хэмминга длины 7. Кодовое расстояние, линейные коды. Теорема о связи проверочной и порождающей матриц. Граница Хэмминга, код Хэмминга, его кодирование и декодирование. Границы Синглтона, Варшамова-Гилберта. Методы построения кодов, теорема Плоткина. Совершенные коды. Конструкция Васильева. Построение кодов общей проверкой на четность. Нижняя оценка числа совершенных кодов. Совершенные и совершенные расширенные коды длины 15 и 16, их классификация. Системы троек Штейнера порядка n (STS(n)), определение, спектр существования. Теорема о необходимом и достаточном условии существования STS(n), примеры STS(n) для малых n, эквивалентные STS(n). Конструкция произведения. Конструкция Ассмуса и Маттсона, ее связь с конструкцией Васильева. Теорема о совокупности кодовых слов веса 3 в совершенном коде (веса 4 в совершенном расширенном коде). Определение блок-схемы, теорема о параметрах блок-схемы. Неравенство Фишера. Свитчинги в блок-схемах и кодах. Свитчинговость конструкций Васильева, Ассмуса-Маттсона. Представление кода Хэмминга через объединение линейных компонент, -компоненты. Системы четверок Штейнера порядка n (SQS(n)), определение, спектр существования, примеры. Конструкции Ханани и Алиева. Cвитчинговая конструкция SQS(n). Полиномы Кравчука. Введение в полностью регулярные коды. Теорема Ллойда. Теорема Зиновьева, Леонтьева и Тиетвайнена. ГРАФЫ И АЛГОРИТМЫ
СОВЕРШЕННЫЕ СТРУКТУРЫ
ДИСКРЕТНЫЙ АНАЛИЗ Научно-исследовательский семинар ТЕОРИЯ ГРАФОВ Научно-исследовательский семинар ТЕОРИЯ КОДИРОВАНИЯ Научно-исследовательский семинар ФАКТОРНЫЕ ЯЗЫКИ Научно-исследовательский семинар КОМБИНАТОРИКА И СИМВОЛЬНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ Научно-исследовательский семинар |
Российской федерации приказ Российской Федерации об охране здоровья граждан от 22 июля 1993 г. N 5487-1 (Ведомости Съезда народных депутатов Российской Федерации... | Без гражданства в российской федерации Российской Федерации, на свободное передвижение, выбор места пребывания и жительства в пределах Российской Федерации и других прав... | ||
Доклад Правительства Российской Федерации Президенту Российской Федерации... «О мерах по реализации Указа Президента Российской Федерации от 28 июня 2007 г. №825 «Об оценке эффективности деятельности органов... | Национальный стандарт российской федерации Цели и принципы стандартизации в Российской Федерации установлены Федеральным законом от 27 декабря 2002 г. N 184-фз "О техническом... | ||
Национальный стандарт российской федерации Цели и принципы стандартизации в российской Федерации установлены Федеральным законом от 27 декабря 2002 г. №184-фз «О техническом... | Министерство экономического развития российской федерации Указом Президента Российской Федерации от 01. 02. 2005 n 112 "О конкурсе на замещение вакантной должности государственной гражданской... | ||
Комплексная программа 5-11 классы Под общей редакцией А. Т. Смирнова Конституции Российской Федерации и федеральных законов Российской Федерации в области безопасности жизнедеятельности, Стратегии национальной... | Национальный стандарт российской федерации автомобили скорой медицинской помощи Цели и принципы стандартизации в Российской Федерации установлены Федеральным законом от 27 декабря 2002 г. N 184-фз "О техническом... | ||
Комментарий к уголовно-процессуальному кодексу российской федерации Смирнов А. В., доктор юридических наук, профессор, советник Конституционного Суда Российской Федерации, действительный государственный... | Министерство здравоохранения российской федерации главный государственный санитарный врач Российской Федерации, 1999, n 14, ст. 1650) и "Положения о государственном санитарно-эпидемиологическом нормировании", утвержденного... | ||
Министерство здравоохранения российской федерации главный государственный санитарный врач Российской Федерации, 1999, n 14, ст. 1650) и "Положения о государственном санитарно-эпидемиологическом нормировании", утвержденного... | Министерство здравоохранения российской федерации главный государственный санитарный врач Российской Федерации, 1999, n 14, ст. 1650) и "Положения о государственном санитарно-эпидемиологическом нормировании", утвержденного... | ||
Утверждаю Президент Российской Федерации В. Путин стратегия развития... Российской Федерации в Арктике на период до 2020 года и дальнейшую перспективу, утвержденных Президентом Российской Федерации 18... | Министерство связи и массовых коммуникаций российской федерации Российской Федерации от 1 февраля 2005 г n 112 "О конкурсе на замещение вакантной должности государственной гражданской службы Российской... | ||
Национальный стандарт российской федерации гост р 53423- 2009 Цели и принципы стандартизации в Российской Федерации установлены Федеральным законом от 27 декабря 2002 г. №184-фз «О техническом... | Об утверждении порядка Основ законодательства Российской Федерации об охране здоровья граждан от 22 июля 1993 г. N 5487-1 (Ведомости Съезда народных депутатов... |