- •1.1.1. Поняття множини
- •1.1.2. Елементи множини
- •1.1.3. Рівність множин
- •1.1.4. Задання та запис множин
- •1.1.5. Підмножини. Універсальна множина.
- •1.1.6. Операції над множинами та їхні властивості
- •Доведемо обернене включення:.
- •1.1.7. Потужність множин
- •Література
- •1.2.2. Декартовий (прямий) добуток множин
- •1.2.3. Бінарні відношення
- •1.2.4. Переріз відношення. Фактор-множина
- •1.2.5. Способи задання відношень
- •Література
- •Тема 1.3. Властивості відношень
- •1.3.1. Теоретико-множинні операції над відношеннями
- •1.3.2. Композиція відношень
- •1.3.3. Обернені відношення
- •1.3.4. Рефлексивні, симетричні і транзитивні відношення
- •1.3.5. Відношення еквівалентності
- •1.3.6. Відношення порядку
- •1.3.7. Відображення і функції
- •Література
- •Розділ 2. Теорія графів
- •Тема 2.1. Основні елементи теорії графів
- •2.1.1. Поняття графа
- •2.1.2. Ізоморфізм графів. Підграф. Суграф. Частковий граф
- •2.1.3. Числові характеристики графа
- •2.1.4. Маршрути незамкнені (ланцюги, шляхи) і замкнені (цикли, контури). Повнота. Зв’язність. Сильна зв’язність
- •2.1.5. Способи задання графа
- •Література
- •Тема 2.2. Операції над графами
- •2.2.1. Поняття графа
- •Тема 2.3. Дерева і цикли у графах
- •2.3.1. Компоненти зв’язності
- •Розглянемо незв’язний неорієнтований граф .
- •Отже, наведений на прикладі граф має три компоненти зв’язності.
- •2.3.2. Ранг та цикломатичне число графа
- •Якщо граф – вироджений, тобто має лише вершини, а ребра – відсутні, то і. За теоремою 2.3.2 додавання нового ребра збільшує або, або. Отже, числатаможуть лише зростати.
- •2.3.3. Дерева і ліси
- •Література
- •Тема 2.4. Розфарбування графа
- •2.4.1. Задача про чотири фарби. Правильне розфарбування графа
- •2.5.2. Визначення хроматичного числа. Хроматичний поліном
- •Література
- •Розділ 3. Загальна алгебра
- •Тема 3.1. Групи
- •3.1.1. Поняття алгебраїчної операції
- •3.1.2. Означення і приклади груп
- •Література
- •Тема 3.3. Поля
- •3.3.1. Означення поля. Приклади полів
- •3.3.2. Властивості полів
- •Література
- •Розділ 4.
- •Тема 4.1 булева алгебра
- •4.1.1 Визначення булевої функції
- •4.1.2. Формули логіки булевих функцій
- •4.1.3. Рівносильні перетворення формул
- •Основні правил булевих формул.
- •Правило рівносильних перетворень
- •4.1.4. Двоїстість. Принцип двоїстості.
- •4.1.5. Булева алгебра (алгебра логіки). Повні системи булевих функцій
- •Література
- •Тема 4.2. Нормальні форми
- •4.2.2 Розкладання булевої функції по змінним
- •Література
- •Тема 4.3. Мінімізація формул булевих функцій у класі диз'юнктивних нормальних форм
- •4.3.1. Застосування алгебри булевих функцій до релейно-контактних схем
- •Контрольні питання до теми 4
- •Література
- •Розділ 5.Комбінаторний аналіз
- •Тема 5.1. Основні поняття комбінаторного аналізу
- •5.1.1. Основні правила комбінаторики
- •Розв’язання
- •5.1.2. Розміщення. Розміщення з повтореннями
- •Розв’язання
- •Розв’язання
- •5.1.3. Перестановки. Перестановки з повтореннями
- •Розв’язання
- •Розв’язання
- •5.1.4. Комбінації. Комбінації з повтореннями
- •Розв’язання
- •Розв’язання
- •Розв’язання
- •5.1.6. Біном Ньютона. Трикутник Паскаля. Властивості біноміальних коефіцієнтів
- •Література
- •Розділ 6.Теорія інформації та кодування
- •Тема 6.1. Теоретичні положення
- •1.2. Приклади розв’язання задач
- •6.3. Задачі
- •Література
- •7. Ефективне кодування
- •7.1. Теоретичні положення
- •7.2. Приклади розв’язання задач
- •Задача 7.2.2
- •Задача 7.2.5
- •1010000011001010011001001011110.
- •0001011011011101100110101100001011011.
- •7.3. Задачі
- •Література
0001011011011101100110101100001011011.
Кодова послідовність має 37 двійкових символів. Відзначимо, що при кодуванні символів джерела рівномірним двійковим кодом ( мінімальна довжина такого коду в даному випадку становить 2 ) довжина кодової послідовності буде дорівнювати 60.
7.3. Задачі
7.3.1. Значення ймовірностей pi , з якими дискретне джерело інформації генерує символи алфавіту, для різних варіантів наведені у таблиці 7.3.1. Побудувати нерівномірні ефективні коди за методиками Шеннона-Фано та Хаффмена для кодування символів джерела. Порівняти ефективність кодів.
Таблиця 7.3.1
№ варіанта |
p1 |
p2 |
p3 |
p4 |
p5 |
p6 |
p7 |
p8 |
p9 |
1 |
0,31 |
0,08 |
0,05 |
0,14 |
0,02 |
0,20 |
0,08 |
0,07 |
0,05 |
2 |
0,11 |
0,16 |
0,03 |
0,26 |
0,04 |
0,05 |
0,03 |
0,02 |
0,30 |
3 |
0,55 |
0,07 |
0,04 |
0,04 |
0,15 |
0,07 |
0,05 |
0,03 |
0 |
4 |
0,08 |
0,05 |
0,11 |
0,07 |
0,33 |
0,24 |
0,04 |
0,04 |
0,04 |
5 |
0,22 |
0,18 |
0,04 |
0,06 |
0,03 |
0,04 |
0,06 |
0,29 |
0,08 |
6 |
0,07 |
0,41 |
0,13 |
0,09 |
0,06 |
0,11 |
0,05 |
0,04 |
0,04 |
7 |
0,35 |
0,15 |
0,06 |
0,02 |
0,03 |
0,08 |
0,02 |
0,07 |
0,22 |
8 |
0,18 |
0,05 |
0,27 |
0,29 |
0,02 |
0,03 |
0,05 |
0,11 |
0 |
9 |
0,12 |
0,03 |
0,05 |
0,40 |
0,12 |
0,08 |
0,05 |
0,04 |
0,11 |
10 |
0,52 |
0,12 |
0,05 |
0,18 |
0,04 |
0,03 |
0,06 |
0 |
0 |
11 |
0,26 |
0,14 |
0,05 |
0,10 |
0,07 |
0,11 |
0,02 |
0,20 |
0,05 |
12 |
0,04 |
0,33 |
0,17 |
0,06 |
0,02 |
0,12 |
0,05 |
0,16 |
0,05 |
13 |
0,28 |
0,03 |
0,04 |
0,15 |
0,05 |
0,04 |
0,07 |
0,34 |
0 |
14 |
0,07 |
0,15 |
0,06 |
0,39 |
0,05 |
0,14 |
0,08 |
0,03 |
0,03 |
15 |
0,45 |
0,15 |
0,03 |
0,07 |
0,08 |
0,02 |
0,06 |
0,09 |
0,05 |
16 |
0,09 |
0,44 |
0,18 |
0,09 |
0,03 |
0,05 |
0,02 |
0,02 |
0,08 |
17 |
0,06 |
0,05 |
0,15 |
0,04 |
0,14 |
0,08 |
0,03 |
0,20 |
0,25 |
18 |
0,22 |
0,05 |
0,16 |
0,05 |
0,05 |
0,03 |
0,02 |
0,34 |
0,08 |
19 |
0,33 |
0,24 |
0,05 |
0,08 |
0,06 |
0,12 |
0,05 |
0,07 |
0 |
20 |
0,08 |
0,22 |
0,15 |
0,05 |
0,08 |
0,05 |
0,06 |
0,24 |
0,07 |
7.3.2. Алфавіт немарковського дискретного джерела інформації складається з чотирьох символів: {A,B,C,D}.Чисельні значення ймовірностей виникнення символів для різних варіантів наведені у таблиці 7.3.2. Побудувати нерівномірні ефективні коди за методикою Шеннона-Фано або Хаффмена ( за Вашим бажанням ) для кодування поодиноких символів джерела та слів довжиною у два символи. Оцінити та порівняти ефективність отриманих кодів. Побудованими кодами закодувати фрагмент тексту довжиною у 30 символів, що був вироблений джерелом. Фрагменти текстів для різних варіантів наведені у таблиці 7.3.3.
Таблиця 7.3.2
№ варіанта |
p(A) |
p(B) |
p(C) |
p(D) |
№ варіанта |
p(A) |
p(B) |
p(C) |
p(D) |
1 |
0,15 |
0,63 |
0,05 |
0,17 |
11 |
0,16 |
0,43 |
0,07 |
0,34 |
2 |
0,33 |
0,10 |
0,12 |
0,45 |
12 |
0,05 |
0,33 |
0,32 |
0,30 |
3 |
0,25 |
0,07 |
0,53 |
0,15 |
13 |
0,27 |
0,15 |
0,45 |
0,13 |
4 |
0,08 |
0,35 |
0,11 |
0,46 |
14 |
0,24 |
0,04 |
0,64 |
0,08 |
5 |
0,32 |
0,38 |
0,24 |
0,06 |
15 |
0,14 |
0,16 |
0,29 |
0,41 |
6 |
0,27 |
0,51 |
0,13 |
0,09 |
16 |
0,51 |
0,05 |
0,34 |
0,10 |
7 |
0,65 |
0,15 |
0,06 |
0,14 |
17 |
0,28 |
0,22 |
0,07 |
0,43 |
8 |
0,18 |
0,05 |
0,27 |
0,50 |
18 |
0,12 |
0,35 |
0,11 |
0,42 |
9 |
0,12 |
0,53 |
0,25 |
0,10 |
19 |
0,08 |
0,45 |
0,24 |
0,23 |
10 |
0,42 |
0,22 |
0,18 |
0,18 |
20 |
0,25 |
0,15 |
0,51 |
0,09 |
Таблиця 7.3.3
№ варіанта |
Фрагмент тексту |
1 |
BBDBDABDBACBBDBDBBBABDBBABBBBD |
2 |
AADABDDCABAADDADDBACDDDDDCADBA |
3 |
CCCCCABCDACBDCCCCCDCAACCADCDDC |
4 |
ABDBDDDCDDBDDDDDBDBDCBDCDBCBDB |
5 |
BCBABBBAACCBCCAAACABBBBABADAAA |
6 |
CBBABACAABCBCCABDABCBBBABBDBBB |
7 |
ACBABAAAADDAADBAADAADBAAAAAADA |
8 |
CDDCDDDDCCCDDDDDCCCCDCDCBCBCDA |
9 |
BDBBDAABBBBCBDCBBBBBBBACCCBCBC |
10 |
CACBADBAAAABABABBABCAACCADACBA |
11 |
BBDBADABCBBBBADADABADBACBBABCA |
12 |
DBDBCBABCDBDCBDCCCBCBBDBBCBDCC |
13 |
BACCBCCCCCADBAAABABABACDCBCACC |
14 |
CCCACBCACCAACACDCCCCCACACACAAC |
15 |
DDDACDDCDCCCCBDCCDBBCDBADCAABD |
16 |
AAADAAAAAADAACBCACACCACCAACBAC |
17 |
DDAACBCABDAAABCDAADDADDDCBABDB |
18 |
ABBDDDBBDBCDBDDBBDDDBDADBDDDDD |
19 |
CADDDDCDBBDBADCBDADBBABCBCDBAB |
20 |
CBCACCADCCCCDCCACCDDDABCCACBAD |
2.3.3. Алфавіт марковського дискретного джерела інформації, що має глибину пам’яті h = 1, складається з трьох символів: {A,B,C}. Чисельні значення умовних ймовірностей виникнення символів для різних варіантів наведені у другому стовпці таблиці 7.3.4. Побудувати нерівномірні ефективні коди за методикою Шеннона-Фано або Хаффмена для кодування поодиноких символів джерела та слів довжиною у два символи. Розробити марковський алгоритм для кодування символів джерела. Оцінити і порівняти ефективність отриманих кодів та марковського алгоритму. Побудованими кодами закодувати фрагмент тексту довжиною у 30 символів, що був вироблений джерелом. Фрагменти текстів для різних варіантів наведені у третьому стовпці таблиці 7.3.4.
Таблиця 7.3.4
№ варіанта |
Фрагмент тексту | |
1 |
ACBBABCBBABCCBA
| |
2 |
BCACCCABCCCAACA
| |
3 |
CCAACCBBCCACCAC CCCBCCCCCBCBCCC | |
4 |
ACBCACAAAACCACA ACABCCABCACACAA | |
5 |
AABCBAAABBABAAA AAAABBBAAABCBBC | |
6 |
ABABABACCCCCCAB ABAAAACCCABBACC | |
7 |
ACBBBBCBACBACAC ACBACBBACACBACB | |
8 |
ACBCBAABAABACAA AAAAABAAACAACBC | |
9 |
CBCBCCACAAABBCA ABBCBCAAAACABCB | |
10 |
BABBCACBBACCACC BCABBCCBBBBCACC | |
11 |
BCCCCBCCCABCBCB CACCCBCCCCCCCCB | |
12 |
BCABCABCCABABCC CABABCABCBACAAB | |
13 |
CCACAACCABCCCAB CAAABCACCBABABA | |
14 |
CABAAAABCAAACAB CBAAACAAAACACCA | |
15 |
BACBAAABCBACBCB CBCBAABCBBCBAAB | |
16 |
CABBBBACBCBBBBA BBBABBBABBBABBB | |
17 |
CACACCCCCBBCCAC CCCCCCCACCBACAA | |
18 |
CCBACBACCBBAACB AACBABAABCBACBA | |
19 |
ACAACCACACCBACA CCBCABACAAACAAC | |
20 |
BCBCBCACBCCBBBB BABBBBBBBBCBBBB |