Контрольно – измерительные материалы МаЛТА 2011
Контрольно – измерительные материалы ДМ 2011
1. Основные понятия теории множеств. Антиномия Рассела.
2. Операции над множествами.
3. Соответствия отображения и функции.
4. Отношения и их свойства. Применение отношений в базах данных.
5. Цифровое задание множеств. Конституенты I, Æ.
6. Операции на множествах, понятие алгебры.
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. Задача о нахождении кратчайшего пути в графах с ребрами произвольной длины.
37. Задача коммивояжёра. Дерево обхода.
38. Анализ графа Марковской сети.
39. Понятие о дискретной оптимизации. Полный перебор.
40. Метод ветвей и границ на примере поиска отказов.
41. Нахождение максимального потока в транспортной сети.
42. Транспортная задача.
43.Генетические алгоритмы.
44. Парето-оптимизация.
45. Программные продукты для решения задач дискретной математики.
46.Головоломка о вечеринках. Теорема Рамсея.
47. Задача о свадьбах. Теорема Холла.
48.Множества внешней и внутренней устойчивости графа. Метод Магу.
49. Конечные автоматы. Автоматы Мили и Мура. Вероятностные автоматы.
50.Автоматные базисы и проблема полноты. Базис Жегалкина.
51.Минимизация переключательных функций автомата в базисе «сумма по модулю два, НЕ». Понятие о системной минимизации переключательных функций автомата.
52.Булева производная.
53.Синтез логических автоматов.
56.Эксперименты с автоматами. Анализ автоматов.
57.Построение контрольного и диагностического теста. Дерево контроля. Дерево диагностирования.
58.Эквивалентность в автоматах. Прямое произведение автоматов.
59.Минимизация автоматов.
60.Понятие формальной грамматики.
61.Автоматные языки. Применение грамматик для построения языков высокого уровня.
62.Коллективы автоматов. Нейросетевые автоматы.
63. Понятие о кодировании. Помехоустойчивое кодирование. Понятие о криптографии.
64. Кодирование по Хэммингу.
65. Кодирование с использованием математического аппарата умножения и деления полиномов.
66. Сигнатурный анализ.
67. Понятие о теории игр.
Экзамен 2011
- Построить ТПВ синхронного автомата-распознавателя 0021 в алфавите {0,1,3,2}
- Построить ПТП автомата управления счётчиком количества рабочих в цехе
- Получить разбиения p0, p1 для заданной ТПВ автомата Мура
| № y(t) | Функции переходов и выходов | |||
| j y(t+1) | z(t) | |||
| а | b | а | b | |
- Получить T,w для порогового элемента И
- Получить T,w для порогового элемента ИЛИ
- Построить граф переходов и ТПВ счётчика с коэффициентом счёта 3
- Получить массив констант для программной реализации автомата-распознавателя 0132 методом ПЛА.
- Построить матрицу Хэмминга для n=4
- Получить уравнения кодирования Хэмминга для n=2
- Получить уравнения декодирования Хэмминга для n=2
- Закодировать с помощью циклического кодирования (порождающий полином G(X3) = X3 + X +1 ) информационную посылку, десятичный номер которой соответствует сумме номера студента по списку и числа 10.Продемонстрировать декодирование при передаче информации а) без ошибки; б) с однократной ошибкой; в) с многократной ошибкой; г) с ошибкой, кратной порождающему полиному.
- Получить контрольный тест автомата
- Получить диагностический тест автомата
- Получить тест методом булевых производных
- Минимизировать ПФ в базисе {Å, И, НЕ}:f(х1х2х3)= Å 0,1,5,6
- Выполнить системную минимизацию: f1(авс)=0,1,4;f2(авс)=1,5,7.
- Получить сигнатуру для схемы (G(X3) = X3 + X +1 )
- Представить логический преобразователь автомата в базисе Жегалкина
- Представить логический преобразователь автомата в базисе И-НЕ
- Представить логический преобразователь автомата в базисе ИЛИ-НЕ
Контрольно – измерительные материалы МаЛТА 2011
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. Нормальные алгорифмы Маркова.
37. Универсальная абстрактная машина и проблема самоприменимости в теории алгоритмов.
38. Сложность алгоритмов.
39. Задачи теории алгоритмов.
40. Современные модальные логики.
41. Классификация функций К-значной логики
42. Функциональная полнота многозначных ПФ.
43. Понятие о нечеткой логике.
44. Понятие о логическом программировании на языке Пролог.
45. Арифметизация булевых функций.
46. Псевдобулевы функции.
47. Представление булевой функции рядом Фурье.
48. Матрица Адамара. Спектральные коэффициенты БФ и ПБФ.
49. Реляционная алгебра.
50. Реляционное исчисление.
Задачи к экзамену.
1. Формализовать высказывание. Получить СДНФ, СКНФ, ДНФ, КНФ, ПЖ.
Представить высказывание в виде суперпозиции только следующих операций 1) «Штрих Шеффера», 3) «Стрелка Пирса», 3)»Импликация» и «Отрицание», 4) «Импликация» и «Константа нуля»(«0»). Получить разложение Шеннона.
2.Доказать или опровергнуть общезначимость формулы, используя законы алгебры логики и формулы равносильных преобразований, а также путем построения дерева доказательства.
3.Проверить аргумент методом резолюций. Получить все следствия из данных посылок.
4.Формализовать умозаключение по заданному модусу в логике предикатов. Доказать или опровергнуть умозаключение по заданному модусу методом резолюций с использованием двух моделей.
5.Выполнить арифметизацию БФ, ПБФ
6. Получить ряд Фурье для БФ, ПБФ.
7. Получить функции автомата по ГСА
8.Определить свойства БФ.
9.Получить вероятность безотказной работы по структурной схеме надёжности логико-вероятностным методом.
10.Получить цепочку формального языка по ее номеру, получить номер цепочки в заданном алфавите.
11. Проверить правильность умозаключения Аристотелевской силлогистики с помощью кругов Эйлера.
12. Получить машину Тьюринга для вычисления переключательной функции.
13. Получить машину Тьюринга для распознавания последовательности.
14. Получить машину Поста для вычисления переключательной функции.
15.Написать программу на языке ПРОЛОГ для определения отношения родства.