Вопросы к экзамену по дискретной математике. 1 курс ФРТ. Весна 2012.

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. Алгоритм генерации k – элементных подмножеств конечного множества.

30. Алгоритм перечисления всех подмножеств конечного множества.

31. Перечисление элементов декартова произведения множеств.

32. Перечисление перестановок в лексикографическом порядке.

33. Определения порядкового номера перестановки.

34. Восстановление перестановки по ее порядковому номеру.

35. Логические переменные (высказывания) и операции над ними.

36. Булевы функции, их свойства и представления.

37. Булева алгебра и ее свойства.

38. Дизъюнктивная нормальная форма булевой функции и алгоритмы приведения формулы для булевой функции к совершенной дизъюнктивной нормальной форме (СДНФ).

39. Конъюнктивная нормальная форма булевой функции и алгоритмы приведения формулы для булевой функции к совершенной конъюнктивной нормальной форме (СДНФ).

40. Булева алгебра и алгебра множеств.

41. Алгоритмы минимизации булевых форм.

42. Двойственность булевых функций и принцип двойственности.

43. Представление булевой функции многочленом Жегалкина и способы его построения.

44. Класс функций, сохраняющих нуль и его свойства.

45. Класс функций, сохраняющих единицу и его свойства.

46. Класс линейных функций и его свойства.

47. Класс монотонных функций и его свойства.

48. Класс самодвойственных функций и его свойства.

49. Теорема Поста.

Сосновский Н.Н.