Вопросы по ОК с5 2005

ПРОГРАММА курса
«Основы кибернетики»
(2 поток, осень 2005)

1. Инвариантные классы (ИК). Примеры и свойства. Существование ИК характеристики 0, 1/2, 1.
2. Оценки сложности функции Шеннона в классе СФЭ для ИК. Сложные множества. Правильные алгоритмы. Теорема С. В. Яблонского о неустранимости перебора.
3. Эквивалентные преобразования (постановка задачи). Существование конечной полной системы тождеств (КПСТ) для формул алгебры логики.
4. Функция Линдона. Основные тождества А_1,2,3, В_m, С_m. Полнота системы Т_w.
5. Свойство Сⁿ. Лемма о сохранении свойства Сⁿ. Теорема Линдона.
6. Существование КПСТ для СФЭ.
7. Тождества в КС. Доказательство тождеств I—VII. Лемма о звездах.
8. Теорема Мурского о полноте системы Tw.
9. Индекс схемы. Невыводимость тождества Cn+i из тождеств 1-5, 6т. Теорема о несуществовании КПСТ для КС.
10. Полиномиальная сводимость языков. Классы Р и NP. Язык 2-выполнимость. NP-полные языки.
11. Теорема Ст. Кука.
12. Некоторые полные языки: 3-выполнимость, (0,1)-целочисленное программирование,
13. NP-трудность задач: Клика, Вершинное покрытие, Покрытие множеств.
14. NP-трудность задачи Раскраска.
15. Моделирование машин Тьюринга схемами. Теорема Сэвиджа о моделировании тыоринговых вычислений.
16. Самокоррекция КС. Тривиальная самокоррекция. Примеры нетривиальной самокоррекции КС.
17. Асимптотика функции Шеннона для КС. корректирующих одно замыкание (или один обрыв) контакта.
18. Тесты. Алгоритм построения всех тупиковых тестов. Нижние оценки длины тестов для таблиц. Верхняя оценка длины теста для почти всех таблиц.
19. Оценки длины теста для КС, реализующей счетчик четности.
20. Синтез СФЭ из ненадежных элементов. Оценка вероятности

неправильною срабатывания СФЭ. Невозможность построения сколь угодно надежных схем. Пример нарастания ненадежности. Пример изменения выразительной способности СФЭ. Критерий возможности сколь угодно надежной реализации булевых функций.

1. Повышение надежности с помощью функции голосования. Однородные деревья. Число внутренних вершин однородного дерева с q висячими вершинами. Лемма о поддеревьях.
2. Верхняя оценка сложности реализации произвольной булевой функции (БФ) схемами в базисе {H,V,&, # Теорема о сколь угодно надежной реализации произвольной БФ схемой в базисе {H,V,&, -} с надежным элементом Н.

ЛИТЕРАТУРА

1. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. Изд-во МГУ, 1984.
2. Лупанов О. Б. О синтезе некоторых классов управляющих систем. — в кн. Пробл. Киберн., вып. 10, с. 85-100.
3. Яблонский СВ. Об алгоритмической сложности синтеза минимальных контактных схем. — в кн. Проблемы кибернетики, вып.2, М.: Наука, — 1959, с.75-122.
4. Эквивалентные преобразования управляющих систем. — Изд-во МГУ — 1986 — сост. Яблонский СВ., 40 с.
5. Кибернетический сборник, вып. 12 (нов. серия), М: МИР, — 1975 — с.5-31.
6. Гэри М., Джонсон Д., Вычислительные машины и трудно решаемые задачи. — М.: Мир, 1982.
7. Нигматуллин Р. Г., Сложность булевых функций. — М.: Наука — 1991. 208 с.
8. Надежность управляющих систем. — Изд-во МГУ — 1991 — сост. Яблонский СВ.,
9. Сапоженко А. А., Некоторые вопросы сложности алгоритмов М. МГУ, ВМиК, 2001, 48 с.