Вопросы/задания: Вопросы
Описание
Характеристики вопросов/заданий
Список файлов
- Вопросы.txt 2,9 Kb
- Прочти меня!!!.txt 136 b
ДИСКРЕТНАЯ МАТЕМАТИКА (1 курс, 2 семестр, 1 поток)
1. Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
2. Теорема о разложении ф.а.л. по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
3. Полные системы. Примеры полных систем /с доказательством полноты/.
4. Теорема Жегалкина о представимости ф.а.л. полиномом.
5. Понятие замкнутого класса. Замкнутость классов.
6. Двойственность. Класс самодвойственных функций, его замкнутость.
7. Класс монотонных функций, его замкнутость.
8. Лемма о несамодвойственной функции.
9. Лемма о немонотонной функции.
10. Лемма о нелинейной функции.
11. Теорема Поста о полноте системы функций алгебры логики.
12. Теорема о максимальном числе функций в базисе в алгебре логики.
13. Теорема о предполных классах.
14. *k - значные функции. Теорема о существовании конечной полной системы в множестве к-значных функций.
15. Основные понятия теории графов. Изоморфизм графов. Связность.
16. Деревья. Свойства деревьев.
17. Корневые деревья. Верхняя оценка их числа.
18. Геометрическая реализация графов. Теорема о реализации графов в трёхмерном пространстве.
19. Планарные /плоские/ графы. Формула Эйлера.
20. Доказательство непланарности графов К5 и К3,3 Теорема Понтрягина - Куратовского /доказательство в одну сторону/.
21. Теорема о раскраске планарных графов в 5 цветов.
22. Схемы из функциональных элементов. Реализация функций алгебры схемами.
23. Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
24. Метод Карацубы.
25. Дешифратор. Асимптотика сложности дешифратора. Верхняя оценка сложности реализации произвольной ф. а. л.
26. Мультиплексор. Верхняя оценка сложности мультиплексора.
27. Шифратор. Верхняя оценка сложности шифратора.
28. Алфавитное кодирование. Схемы кодирования, обладающие свойством префикса. Неприводимые коды и их свойства.
Теорема Маркова о взаимной однозначности алфавитного кодирования.
29. Неравенство Макмиллана.
30. Существование кода со свойством префикса в классе кодов с заданными длинами элементарных кодов.
31. Коды с минимальной избыточностью /оптималъные коды/.
Алгоритм построения кода с минимальной избыточностью. ОТМЕНЕН
32. Теорема редукции.
33. Коды с исправлением r ошибок. Оценка функции мr(n)
34. Саморректирующиеся коды. Оценка функции м1(n) Коды Хемминга.
35. Понятие ограниченно-детерминированной функции. Конечные автоматы и автоматные пункции. Представление конечного автомата диаграммой Мура. Автомат единичной задержки.
36. Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
37. Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
38. Теорема Мура. Теорема об отличности состояний 2 автоматов.
39. Машины Тьюринга. Вычислимые функции. Примеры вычислимых функций.
40. Алгоритмическая неразрешимость проблемы самоприменимости машины Тьюринга.
Файл скачан с сайта StudIzba.com
При копировании или цитировании материалов на других сайтах обязательно используйте ссылку на источник
Начать зарабатывать