|
Перейти к полному списку специальных курсов кафедры
Программа экзамена по спецкурсу "Дискретный анализ и интеллектуальные системы"
Функциональные системы
1. Теорема
о критериальности системы предполных классов в конечно-порожденной ФС.
2. Теорема
о критериальности системы предполных классов в  .
3.
Алгоритм построения всех  -множеств в .
4. Лемма
о  в .
5. Лемма
о  в .
6. Лемма
о  при  в .
7. Теорема
Кузнецова о критериалности класса множеств сохранения -множеств в .
8. Теорема
о совпадении множества предполных классов с множеством максимальных элементов
частичного порядка классов сохранения -множеств в .
9. Алгоритм
построения частичного порядка классов сохранения -множеств.
10. Алгоритм
распознавания полноты конечных систем в .
11. Предполные
классы в  и их -множества.
12. Существование
счетных замкнутых классов в  без предполных классов.
13. Существование
замкнутых классов в с не менее, чем счетным множеством, предполных классов.
14. Теорема Розенберга о классификации минимальных
замкнутых классов, содержащих тождественную функцию.
15. Предполнота классов сохранения множеств констант в .
16. Предполнота классов сохранения эквивалентности в .
17. Предполнота класса самодвойственных функций в .
18. Предполнота класса монотонных функций в .
19. Предполнота класса линейных функций в .
20. Критериальность предполных классов Яблонского.
Минимизация булевых функций
21. Минимизация булевских функций. Функция Шеннона
сложности ДНФ для б.ф.
22. Геометрическая модель минимизации б.ф. Теорема о
простых импликантах б.ф.
23. Алгоритм Блейка. Теорема о сильных расширениях СокДНФ.
24. Теорема о МДНФ монотонной б.ф.
25. Тупиковая ДНФ. Алгоритм построения ТДНФ.
26. Теорема о ДНФ типа  .
27. Регулярная грань. Теорема о ДНФ типа  .
Кодирование
28. Алфавитное
кодирование. Префиксные коды. Однозначность декодирования префиксных кодов.
29. Обращение
схемы кодирования. Однозначность обратной префиксной схемы кодирования.
30. Длина
схемы кодирования. Нетривиальное разложение. Критерий однозначности
декодирования (Теорема Маркова).
31. Граф
арифметической схемы кодирования. Алгоритм распознавания неоднозначности
декодирования.
32. Теорема
Макмиллана об однозначной схеме кодирования (неравенство Макмиллана).
33. Теорема
Макмиллана о существовании префиксной схемы кодирования.
34. Код
с минимальной избыточностью (код Хаффмена). Оптималное кодирование.
35. Кодовое
дерево Хаффмена. Его свойства. Алгоритм построения кода Хаффмена.
36. Код
Хемминга. Информационные и проверочные биты. Минимальное расстояние между
кодовыми словами.
Наверх
| 
