Вопросы к экзамену. 1. Что называется объединением, пересечением множеств?

1. Что называется объединением, пересечением множеств?

2. Что называется разностью, симметрической разностью, дополнением множества?

3. Как проиллюстрировать диаграммой Эйлера-Венна одно из тождеств теории множеств?

4. Что такое однозначное (многозначное) отображение?

5. *Что такое инъективное, сюръективное, биективное отображение?

6. Что такое мощность конечного множества и как это связано с биекцией?

7. Что такое декартово произведение множеств и что вы знаете о его мощности?

8. *Что вы знаете о мощности множества двоичных наборов?

9. Какова мощность множества всех подмножеств данного множества?

10. Что такое отношение на множестве (с примерами)?

11. Что такое рефлексивное, симметричное, транзитивное отношение?

12. *Что такое отношение эквивалентности и каково его основное свойство?

13. *Что такое отношение нестрогого порядка?

14. *Что такое отношение строгого порядка?

15. Что такое вполне упорядоченное множество, цепь?

16. Каковы основные элементы канала связи?

17. В чем задача кодера и декодера?

18. В чем суть основополагающего вывода Шеннона?

19. *Что такое алфавит, буква, слово?

20. *Что такое код?

21. Что такое двоичный (n,k)-код?

22. Что такое скорость (n,k)-кода и к чему она стремится при эффективном кодировании?

23. *Что такое расстояние Хемминга и как оно связано с исправлением единичных ошибок?

24. *Каков алгоритм кодера (7,4)-кода Хемминга?

_____________________

Символом * отмечены вопросы, обязательные для студентов, получивших по теории четыре балла и выше; остальные студенты готовят к экзамену все вопросы.

25. *Каков алгоритм декодера (7,4)-кода Хемминга?

26. Что вы знаете о существовании других кодов Хемминга?

27. Как связано расстояние Хемминга с исправлением нескольких ошибок?

28. Что такое конечное поле GF(q) и каковы в нем операции?

29. В чем идея РМ-кодов, РС-кодов, БЧХ-кодов?

30. В чем идея каскадных кодов?

31. Что называется орграфом, графом, вершиной, дугой, ребром?

32. Что такое путь, цепь, контур, цикл?

33. Что такое связный граф, компонента связности?

34. Что такое мультиграф, взвешенный (нагруженный) граф?

35. В чем состоят три задачи о кратчайшем пути в графе?

36. *Каков алгоритм решения задачи 2?

37. *Каков алгоритм решения задачи 3?

38. Что такое эйлерова цепь (цикл) и задача Эйлера?

39. *У каких графов существует эйлерова цепь (цикл)?

40. Что такое плоский и планарный граф?

41. *В чем состоит формула Эйлера и для каких объектов она верна?

42. *Как выглядят непланарные графы № 1 и №2, типов 1 и 2?

43. В чем состоит теорема Куратовского-Понтрягина?

44. Что такое толщина графа и какое неравенство для нее вы знаете?

45. В чем состоит теорема Уитни?

46. *Что такое матрица смежности орграфа и каким свойством обладает матрица смежности неориентированного графа?

47. Что показывают элементы степеней матрицы смежности?

48. *Что называется деревом, ордеревом, бинарным ордеревом?

49. *Как строится код Харари?

50. Что такое матрица инцидентности?

51. *Как строится код Прюфера?

52. Что называется уровнем вершины ордерева, глубиной ордерева, висячей вершиной ордерева и дерева?

53. Как строится префиксный код бинарного ордерева?

54. Какие три способа обхода бинарного ордерева вы знаете?

55. Как связаны число вершин бинарного ордерева и его глубина?

56. Что такое дерево поиска и как вести поиск в нем?

57. Что такое идеально сбалансированное, сбалансированное ордерево?

58. Что называется атомом, списком и как связаны деревья со списками?

59. *В чем состоит задача о раскраске вершин графа и каков алгоритм ее решения?

60. *В чем состоит задача о раскраске ребер графа и что вы знаете о хроматическом индексе?

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

Дата добавления: 2014-11-20