Основы дискретной математики

Дисциплина Информационные системы

Заказчик	123456sh ☆ 0 ✍ 3 ♥ 0
Вид работы	Практика
ВУЗ	Волгоградский институт бизнеса
Срок	04.02.2016
Вариант	Не указан
Бюджет	Не определен ₽

Тема №4. Теория кодирования
Упражнение 1. Каков код букв W и w в ASCII?
Упражнение 2. Какое из соотношений несет в себе больше информации  или  ? 
Упражнение  3.  Найти  энтропию  дискретной  случайной  величины  ,  заданной 
распределением
Упражнение  4.  Дискретные случайные величины  ,  -  зависимы и распределены также 
как и соответствующие дискретные случайные величины из предыдущей задачи. Найти  , 
если совместное распределение вероятностей  и  описывается законом 
Упражнение  5.  Дискретные  случайные  величины  и  определяются  подбрасыванием 
двух  идеальных  тетраэдров,  грани  которых  помечены  числами  от  1  до  4.  дискретная  случайная 
величина  равна  сумме  чисел,  выпавших  при  подбрасывании  этих  тетраэдров,  т.е. 
. Вычислить  ,  и  . 
Упражнение  6.  Подсчитать сколько информации об  содержится в дискретной случайной величине  ,  а  также  .  Дискретные  случайные  величины  и  берутся  из предыдущего упражнения. 
Упражнение  7.  Дискретная  случайная  величина  (д.с.в.)  равна  количеству  "гербов", 
выпавших на двух идеальных монетках.  Найти энтропию  . Придумать минимальный код для  , 
вычислить его среднюю длину и обосновать его минимальность. 
Упражнение  8.  Про  д.с.в.  известно,  что  ее  значениями  являются  буквы  кириллицы. 
Произведен  ряд  последовательных  измерений  ,  результат  которых  -  "ТЕОРИЯИНФОРМАЦИИ". 
Составить на основании этого результата приблизительный закон распределения вероятностей этой д.с.в. и оценить минимальную среднюю длину кодов для  Упражнение  9.  Закодировать  сообщения  "AABCDAACCCCDBB",  "КИБЕРНЕТИКИ"  и  "СИНЯЯ 
СИНЕВА СИНИ", вычислить длины в битах полученных кодов, используя алгоритмы LZW.

Тема №5. Основы дискретной математики
В шахматном турнире по круговой системе участвуют семь студентов. Известно, что Ваня сыграл шесть 
партий, Толя – пять, Леша и Дима –по три, Семен и Илья – по две, Женя - одну. С кем сыграл Леша?
2.  Покажите, что следующие объекты можно рассматривать как графы:
∙  вершины и ребра многогранника;
∙  план лабиринта;
∙  дружеские отношения в группе студентов;
∙  генеалогическое дерево;
∙  теннисный турнир;
∙  страны на карте.
3.  На  рисунке  изображены  молекулы  этилена  и  бензола;  через  С  и  Н  обозначены  атомы  углерода  и водорода соответственно. Можно ли считать эти диаграммы графами? Если да, то что будет являться необходимым условием, для того чтобы граф представлял собой молекулу какого-либо углеводорода?
4. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими? 
5.  Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими? 
6.  В  некоторой  стране  19  регионов.  Может  ли  оказаться  так,  что  у  каждого  региона  1,  5  или  9  соседних регионов?
7.  В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
В розыгрыше первенства по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?
9.  Нарисуйте полный граф с n вершинами, если:
а) n = 2  б) n = 3  в) n = 5
10.  Спортивные  соревнования  проводятся  по  круговой  системе.  Это  означает,  что  каждая  пара  игроков 
встречается  между  собой  ровно  один  раз.  В  соревновании  с  двенадцатью  участниками  провели  все встречи. Сколько было сыграно встреч? 
11.  В некотором государстве система авиалиний устроена так, что любой город соединен авиалиниями не 
более чем с тремя другими и из любого города в любой другой можно перелететь, сделав не боле одной пересадки. Какое наибольшее число городов может быть в этом государстве?
12.  Какие из предложенных графов являются регулярными?