Вопросы и задачи к экзаменационным билетам по курсу "Дискретная математика"

ВОПРОСЫ К БИЛЕТАМ ПО КУРСУ ДИСКРЕТНОЙ МАТЕМАТИКИ

2012 – 2013 уч.год, 2-й курс, весенний семестр.

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. Процедура кодирования по Хеммингу  для  длины исходного кода 8.

26. Понятие шифрования. Причины  необходимости шифрования.

27. Основные способы борьбы с несанкционированным доступом  к  сообщению.

28. Шифрование  по ключу. Виды ключей. Что такое дешифрование ?

29. Примеры  симметричного  шифрования. Гамма шифра.

30. Основная  идея  шифрования  с  открытым ключом.

31. Стандартный  алгоритм  несимметричного  шифрования (алгоритм RSA).

32. Функция Эйлера. Формулировка теоремы Эйлера. Малая теорема Ферма.

33. Связь между физическими и экранными координатами.

34. Эрмитова интерполяция кубическими сплайнами дефекта два.

35. Параметризация дуги. Параметризация по длине дуги.

36. Алгоритмы поиска интервала, которому принадлежит заданная точка. 

37. Графическое изображение линий, заданных поточечно.

38. Параллельное проектирование, как элемент трехмерной графики.

39. Группа поворотов на плоскости.

40. Матричное представление оператора поворота в трехмерном пространстве.

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

42. Алгоритм определения принадлежности точки замкнутой области с кусочно-линейной границей.

43. Выпуклая линейная оболочка. «Обход Грэхэма».

44. Полугруппы. Примеры.

45. Определение группы. Примеры.

46. Классы вычетов.

47. Поле. Примеры полей. Поле комплексных чисел.

48. Матрицы Паули и их свойства.

49. Сложение и умножение кватернионов. Длина кватерниона.

ЗАДАЧИ К БИЛЕТАМ ПО КУРСУ ДИСКРЕТНОЙ МАТЕМАТИКИ

2012 – 2013 уч.год, 2-й курс, весенний семестр.

1. Для каждого символа  из  верхней строки  приведены  частоты, с какими они встречаются в тексте; частоты  выписаны  в нижней строке.

Составить коды  символов по  Фано.

2.Для каждого символа  из  верхней строки  приведены  частоты, с какими они встречаются в тексте; частоты  выписаны  в нижней строке.

Составить коды  символов по  Фано.

3. Для каждого символа  из  верхней строки  приведены  частоты, с какими они встречаются в тексте; частоты 

выписаны  в нижней строке.

Составить коды  символов по  Фано.

     - - - - - - - - - - - - - - - - - - - - -  - - - - - - - - - - - - - - - - - - - - -  - - - - - - - - - - - - - - - - - - - - -

4. Найти  все  числа, находящиеся  на  кодовом расстоянии, равном 1, - от числа  72 (предварительно найти код этого числа по Хеммингу).

5. Для чисел  121  и 233  после  составления кодов  по Хеммингу  найти  кодовое расстояние  между  ними.

6. Перевести  числа  А и В  в  двоичную систему  счисления;  в  двоичной системе счисления  вычислить А+В ;