Вопросы к экзамену. 1. Алфавиты и формальные языки

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. Примеры простейших линейных автоматов Мура.