О.Б. Лупанов - Элементы математической кибернетики (1161667), страница 10

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

Текст из файла (страница 10)

. , α̃ijsij . Образуем формальные дизъюнкции и перемножим их:^i,jα̃ij1 ∨ · · · ∨ α̃ijsij .Формально преобразуем полученное выражение в ДНФ“. При этом конъюнкции”будут соответствовать тестам, а минимальные конъюнкции — тупиковым тестам.55Приложение АНекоторые отношения (извлечение из [3])1. Отношениеf (x) a g(x)при x → a имеет место, если существуют такие положительные константы C1 > 1 и C2 6 1 и окрестность точки a, в которой (кроме, бытьможет, точки a) выполняетсяf (x) 6 C(x)g(x),где2.

Отношение C1 ,1,C(x) =C2 ,g(x) > 0,g(x) = 0,g(x) < 0.f (x) ≍ g(x)при x → a имеет место, если при x → a одновременно выполненыf (x) a g(x),g(x) a f (x).3. Отношениеf (x) . g(x)при x → a имеет место, если для любого ε > 0 существует такая окрестность точки a, в которой (кроме, быть может, точки a) выполняетсяf (x) 6 Cε (x)g(x),где 1 + ε,Cε (x) =1,1 − ε,56g(x) > 0,g(x) = 0,g(x) < 0.Приложение БПрограмма курса1. Дизъюнктивные нормальные формы (ДНФ). Допустимые и минимальные конъюнкции.

Тупиковые, минимальные и сокращенныеДНФ. Геометрическая интерпретация.2. Оценки сложности ДНФ (LD (n) и L′D (n)).3. Замкнутые ДНФ. Методы получения сокращенной ДНФ. Градиентный алгоритм.4. Критерий вхождения минимальной конъюнкции в ДНФ типасуммы тупиковых (ΣT ).5. Окрестность ранга r. Отсутствие критерия ранга r вхожденияминимальной конъюнкции в ДНФ типа суммы монотонных.6. Контактные схемы. Простейшие методы синтеза. Контактное дерево. Свойство разделительности.7. Реализации всех конъюнкций контактной схемы со сложностьюn2 (1 + o(1)).

Свойство ослабленной разделительности.8. Асимптотически наилучший метод синтеза контактных схем.9. Нижняя оценка функции LK (n). Асимптотика LK (n).10. Метод каскадов для контактных схем.11. Доказательство минимальности контактной схемы для линейнойфункции.12. Нижняя оценка вида Cn3/2 для сложности реализации линейнойфункции контактными схемами.13. Нижняя оценка вида n2 для сложности реализации линейнойфункции контактными схемами.14. Доказательство минимальности контактного дерева в классеразделительных схем.15.

Самокорректирующиеся контактные схемы. Корректировка одного замыкания/размыкания.16. Надежные контактные схемы из ненадежных элементов.17. Эквивалентные преобразования формул над {&, ∨, ¬, x, 0, 1}.5718. Эквивалентные преобразования контактных схем. Система правил γn . Производные правила (для цепей). Полнота γn для схем надпеременными {x1 , . . . , xn }.19. Отсутствие полной конечной системы правил преобразованияконтактных схем.20. Тесты.

Таблицы неисправностей. Тривиальные оценки длинытеста. Длина минимального теста для почти всех таблиц.21. Градиентный алгоритм построения тестов. Оценка длины.22. Диагностический тест. Доказательство соотношения D(n) = 2n .58Приложение ВНекоторые задачи, предлагавшиеся наэкзамене1. Найти число функций f (x1 , . .

. , xn ), на которых достигается оценка LD (f ) = n2n−1 (Ю. В. Таранников, 2003–2004 учебный год).59Литература[1] Алешин С. В. Распознавание динамических образов. Часть I. —М.: Изд–во МГУ, 1996.[2] Касами Т., Токура Н., Ивадари Ё., Инагаки Я. Теория кодирования. — М.: Мир, 1978.[3] Яблонский С. В. Введение в дискретную математику.

— М.: Высшая школа, 2001.⇔60.

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

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