Робоча навчальна програма кредитного модуля "Теорія інформації і кодування"

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ "КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ"

“ЗАТВЕРДЖУЮ” Декан факультету (директор інституту) (підпис) (ініціали, прізвище) " " 2012 р. (підпис) (ініціали, прізвище) " " 2012 р.

РОБОЧА НАВЧАЛЬНА ПРОГРАМА

КРЕДИТНОГО МОДУЛЯ

"Теорія інформації і кодування"

(назва та код кредитного модуля)

для напрямів підготовки (спеціальностей):

(шифр та назви напрямів, спеціальностей)

____________________

(форма навчання)

Програму рекомендовано кафедрою протокол № від “ “ 2012 р. Завідувач кафедри _____________ ______________ (підпис) (ініціали, прізвище)

Київ 2012

Робоча навчальна програма кредитного модуля з дисципліни

Теорія інформації і кодування

I. Загальні відомості

Метою і завданням навчальної дисципліни "Теорія інформації і кодування" є отримання базових теоретичних знань і практичних навичок з ефективного кодування і розпізнавання інформації, необхідних для подальшої дослідницької і прикладної роботи.

Предмет навчальної дисципліни "Теорія інформації і кодування" включає основні розділи з теорії інформації Шеннона, теорії статистичних рішень (байесівські та небаєсівські методи статистичних рішень та ємпіричний байесів метод), методи навчання та самонавчання у розпізнаванні образів. Знання та практичні навички, що будуть отримані в процесі вивчення курсу, дозволять значно розширити можливості студентів при засвоєнні подальших дисциплін із штучного інтелекту та виконанні дипломних проектів.

Вимоги до знань та вмінь, добутих протягом навчання.

Студент повинен знати: оптимізаційні методи ефективного кодування інформації, методи статистичного розпізнавання, що базуються на теорії статистичних рішень, методи навчання та самонавчання алгоритмів розпізнавання.

Студент повинен вміти: застосовувати набуті методи для ефективного кодування інформації, зокрема, зображень, для розв¢язку базових задач розпізнавання та проведення подальших наукових досліджень за фахом.

Місце в структурно-логічній схемі спеціальності. Нормативна навчальна дисципліна "Теорія інформації і кодування" є складовою циклу професійної підготовки фахівців освітньо-кваліфікаційного рівня “бакалавр”, базується на попередніх дисциплінах «Теорія ймовірностей і математична статистика», «Лінійна алгебра і лінійне програмування» і є базовою для вивчення дисципліни «Методи структурного розпізнавання» та інших дисціплін з штучного інтелекту.

Система контролю знань та умови складання іспиту. Навчальна дисципліна "Теорія інформації і кодування" оцінюється за модульно-рейтинговою системою. Вона складається з 3 модулів. Результати навчальної діяльності студентів оцінюються за 100 - бальною шкалою.

Модульний контроль полягає у трьох контрольних роботах з трьох розділів курсу, які виконуються у формі письмової підготовки відповіді на контрольне запитання і усній відповіді. Максимальна кількість балів за одну контрольну роботу складає 20 балів.

Підсумковий контроль проводиться у формі екзамену – 40 балів.

За результатами семестру студент отримує підсумкову оцінку за 100-бальною системою, яка розраховується як накопичення оцінок за кожен з модулів у семестрі та оцінки за екзамен. Максимальна підсумкова оцінка складає 100 = 3 * 20+40 балів.

	Змістовий модуль 1 (ЗМ1 )	Змістовий модуль 2 (ЗМ2 )	Змістовий модуль 3 (ЗМ3 )	Екзамен	Разом (підсумкова оцінка)
Максимальна оцінка в балах	20	20	20	40	100

Якщо студент з поважних обставин був відсутній на модульній контрольній роботі, він має право на 1 перескладання з можливістю отримання максимальної кількості балів. Термін перескладання визначається викладачем. Студент допускається до складання екзамену, якщо кількість набраних ним балів за семестр становить не менше 20 балів. Екзамен вважається не зданим, якщо сумарна кількість балів з дисципліни складає менше 60 балів. Підсумкова оцінка з дисципліни у балах (100–бальна шкала) переводиться у чотирибальну національну шкалу (див. роділ VI цієї програми).

II. Розподіл навчального часу

Для засвоєння кредитного модулю передбачається такий розподіл навчального часу:

Семестр/код кредитного модуля	Всього годин	Розподіл годин за видами занять	Кількість МКР	Вид індивідуального завдання	Семестрова атестація
Лекції	Практичні заняття	СРС
Всього	У тому числі на виконання індивідуального завдання
7	144	36	36	72	36	3	Програма	Екз.

Індивідуальні завдання полягають у написанні програми для розвязку тієї чи іншої конкретної задачі кодування і обробки зображень.

III. Мета та завдання кредитного модуля

Мета та завдання кредитного модуля викладені у розд. I даної робочої програми.

IV. Тематичний план

Назви розділів, тем	Розподіл за семестрами та видами занять
Всього	Лекції	Практичні заняття (контрольні роботи)	СРС
Розділ 1. Основи теорії інформації, загальні методи компресії інформації, методи компресії зображень	30	10	10	10
ЛЕКЦІЇ Лекція 1.1. Кодувальник, дерево кодування, насичені і ненасичені кодувальники, якість кодувальника. Ентропія, як нижня границя математичного сподівання довжини коду. Лема Шеннона і пряма лема про довжини кодів.	2	2
Лекція 1.2. Обернена лема продовжини кодів. Існування кодувальника з середньою довжиною коду, яка мало відрізняється від ентропії повідомлення.	2	2
Лекція 1.3. Кодувальник Шеннона-Фано. Побудова оптимальних кодувальників. Дерево Хаффмена.	2	2
Лекція 1.4. Формальні властивості ентропії, як характеристики невизначеності випадкового повідомлення. Основна теорема Шеннона про швидкість передачі повідомлень через канал без перешкод.	2	2
Лекція 1.5. Принципи арифме-тичного кодування та особливості його програмування.	2	2
ПРАКТИЧНІ ЗАНЯТТЯ Практичне заняття 1.1. Локально-визначене кодування зображень. Побудова оптимального локально-визначеного кодувальника.	2		2
Практичне заняття 1.2. Реалізація кодування Шеннона-Фано.	2		2
Практичне заняття 1.3. Динамічне кодування Хаффмена.	2		2
Практичні заняття 1.4 і 1.5. Формулювання завдань для індивідуального виконання.	4		4
Контрольна робота № 1	10			10
Розділ 2. Статистична теорія розпізнавання	36	12	12	12
ЛЕКЦІЇ Лекція 2.1. Байесівські задачі розпіз-навання.	2	2
Лекція 2.2. Теорія двоїстості у небайесів-ських задачах розпізнавання.	2	2
Лекція 2.3. Задачі Неймана-Пірсона, мі-німаксна задача і задача Вальда, як базові задачі небайесівської теорії рішень.	2	2
Лекція 2.4. Стратегії розвязку базових небайесівських задач.	2	2
Лекція 2.5. Емпіричний байесівський підхід Роббінса.	2	2
Лекція 2.6. Задачі Роббінса і алгоритм їх розвязку.	2	2
ПРАКТИЧНІ ЗАНЯТТЯ Практичне заняття 2.1. Мінімізація байесівського ризику для різноманітних штрафних функцій.	2		2
Практичне заняття 2.2. Узагальнені задачі Неймана-Пірсона.	2		2
Практичне заняття 2.3. Небайесівські задачі складених статистичних рішень.	2		2
Практичні заняття 2.4-2.6. Розгляд завдань для індивідуального виконання.	6		6
Контрольна робота № 2	12			12
Розділ 3. Методи навчання і самонавчання у розпізнаванні образів	42	14	14	14
ЛЕКЦІЇ Лекція 3.1. Базові статистичні моделі обєктів, що розпізнаються.	2	2
Лекція 3.2. Навчання і самонавчання як найвірогідніше оцінювання невідомих параметрів статистичної моделі обєктів.	2	2
Лекція 3.3. Формулювання задачі самонавчання і алгоритм її розвязку.	2	2
Лекція 3.4. Монотонний характер алгоритму самонавчання.	2	2
Лекція 3.5. Автоматичне налагодження стратегії розпізнавання. Алгоритми Козинця та доведення їх збіжності.	2	2
Лекція 3.6. Персептрон і теорема Новікова.	2	2
Лекція 3.7. Принципи безпомилкового налагодження стратегій розпізнавання.	2	2
ПРАКТИЧНІ ЗАНЯТТЯ
Практичне заняття 3.1. Найвірогідніше оцінювання параметрів базових статистич-них моделей.	2		2
Практичне заняття 3.2. Алгоритми само-навчання для базових статистичних моделей.	2		2
Практичне заняття 3.3. Модифікація алгоритмів Козинця і персептрона на випадок, коли кількість прихованих станів обєкту більше двох.	2		2
Практичне заняття 3.4. Принципи викривлення-спрямлення ознакових просторів. Налагодження квадратичних, сферичних та еліпсоїдальних дискримінантних функцій.	2		2
Практичні заняття 3.5-3.7. Розгляд завдань для індивідуального виконання.	6		6
Контрольна робота № 3	14			14
Виконання індивідуальних завдань.	36			36
ВСЬОГО	144	36	36	72

IV.2. Лекції –36 год.

Розділ 1. Основи теорії інформації, загальні методи компресії інформації, методи компресії зображень. -10 год.

1.1. Кодувальник, дерево кодування, насичені і ненасичені кодувальники, якість кодувальника. Ентропія, як нижня границя математичного сподівання довжини коду. Лема Шеннона і пряма лема про довжини кодів. -2 год.

1.2. Обернена лема про довжини кодів. Існування кодувальника з середньою довжиною коду, яка мало відрізняється від ентропії повідомлення.- 2 год.

1.3. Кодувальник Шеннона-Фано. Побудова оптимальних кодувальників. Дерево Хаффмена. - 2 год.

1.4. Формальні властивості ентропії, як характеристики невизначеності випадкового повідомлення. Основна теорема Шеннона про швидкість передачі повідомлень через канал без перешкод. - 2 год.

1.5. Принципи арифметичного кодування та його програмування. - 2 год.

Розділ 2. Статистична теорія розпізнавання – 12 год.

2.1. Байесівські задачі розпізнавання. -2 год.

2.2. Теорія двоїстості у небайесівських задачах розпізнавання. -2 год.

2.3. Задачі Неймана-Пірсона, мінімаксна задача і задача Вальда, як базові задачі небайесівської теорії рішень. -2 год.

2.4. Стратегії розвязку базових небайесівських задач. -2 год.

2.5. Емпіричний байесівський підхід Роббінса. -2 год.

2.6. Задачі Роббінса і алгоритм їх розвязку. -2 год.

Розділ 3. Методи навчання і самонавчання у розпізнаванні – 14 год.

3.1. Базові статистичні моделі обєктів, що розпізнаються. -2 год.

3.2. Навчання і самонавчання як найвірогідніше оцінювання невідомих параметрів статистичної моделі обєктів. -2 год.

3.3. Формулювання задачі самонавчання і алгоритм її розвязку. -2 год.

3.4. Монотонний характер алгоритму самонавчання. -2 год.

3.5. Автоматичне налагодження стратегії розпізнавання. Алгоритми Козинця та доведення їх збіжності. -2 год.

3.6. Персептрон і теорема Новікова. -2 год.

3.7. Принципи безпомилкового налагодження стратегій розпізнавання. -2 год.

IV.3. Практичні заняття – 36 год.

Розділ 1. Основи теорії інформації, загальні методи компресії інформації, методи компресії зображень. -10 год.

1.1. Локально-визначене кодування зображень. Побудова оптимального локально-визначеного кодувальника. – 2 год.

1.2. Реалізація кодування Шеннона-Фано. – 2 год.

1.3. Динамічне кодування Хаффмена. – 2 год.

1.4. Формулювання завдань для індивідуального виконання. – 4 год.

Розділ 2. Статистична теорія розпізнавання – 12 год.

2.1. Мінімізація байєсівського ризику для різноманітних штрафних функцій. – 2 год.

2.2. Узагальнені задачі Неймана-Пірсона. – 2 год.

2.3. Небайєсівські задачі складених статистичних рішень. – 2 год.

2.4. Розгляд завдань для індивідуального виконання. – 6 год.

Розділ 3. Методи навчання і самонавчання у розпізнаваннігод.

3.1. Найвірогідніше оцінювання параметрів базових статистичних моделей. – 2 год.

3.2. Алгоритми самонавчання для базових статистичних моделей. – 2 год.

3.3. Модифікація алгоритмів Козинця і персептрона на випадок, коли кількість прихованих станів обєкту більше двох. – 2 год.

3.4. Принципи викривлення-спрямлення ознакових просторів. Налагодження квадратичних, сферичних та еліпсоїдальних дискримінантних функцій. – 2 год.

3.5. Розгляд завдань для індивідуального виконання. – 6 год.

IV.4. Індивідуальні завдання

В усіх поданих далі завданнях йдеться про створення і тестування програми, що вирішує ту чи іншу задачу кодування зображень і їх оброблення у стисненому вигляді.

1. Динамічне кодування зображення в процесі одноразового перегляду (сканування).

2. Побудова оптимального локально-визначеного кодувальника.

3. Кодування на основі 4-дерев.

4. Кодування символів і біграм за Хаффменом. Виконати динамічну модифікацію кодування за Хаффменом.

5. Кодування Шенона-Фано.

6. Арифметичне кодування. Алгоритм кодування.

7. Арифметичне кодування. Алгоритм декодування.

8. Розпізнавання двовимірних гаусівських моделей у випадку двох прихованих станів.

9. Алгоритмами перцептрона та Козинця. Лінійне розділення множин.

10. Алгоритмами перцептрона та Козинця. Розділення множин за допомогою кола.

11. Алгоритмами перцептрона та Козинця. Розділення множин за допомогою квадратичної функції.

12. Визначити суму цифр за їх зображеннями.

13. Самонавчання.

V. Контрольні питання з дисципліни

Контрольні питання призначені для самоконтролю студентами ступені оволодіння навчального матеріалу, а також для поточної, семестрової (екзамен) перевірки якості набутих знань.

ЗАПИТАННЯ ДО КОНТРОЛЬНОЇ РОБОТИ № 1

1. Необхідні й достатні умови оборотності кодування зображень. Пошук оптимального кодувальника зображень.

2. Нерівність Шеннона.

3. Довести, що довжини кодів подій задовольняють умові .

4. Довести, що якщо числа задовольняють умові , то існують кодів з довжинами .

5. Довести, що математичне сподівання довжини коду не менше ентропії події, що кодується.

6. Довести, що існує кодувальник подій, для якого математичне сподівання довжини коду менше, ніж ентропія плюс 1.

7. Довести, що . Довести, що . Нехай - випадкова величина з ймовірностями . Нехай - випадкова величина з ймовірностями . При яких ймовірностях ентропія пари максимальна?

8. Нехай - випадкова величина з ентропією . Нехай - достатньо довга послідовність її реалізацій. Довести, що цю послідовність можна запам’ятати в пам’яті з об’ємом , де - довільне додатнє число.

9. Кодування Шеннона-Фано та алгоритм його побудови. Приклади його неоптимальності та оптимальності.

10. Кодування Хаффмена та доведення його оптимальності.

11. Арифметичне кодування.

ЗАПИТАННЯ ДО КОНТРОЛЬНОЇ РОБОТИ № 2

1. Байесівська задача статистичних рішень. Загальний вигляд стратегії для випадку, коли прихований стан приймає тільки два значення.

2. Байесівська стратегія, що мінімізує ймовірність хибного розпізнавання.

Байесівська стратегія при можливій відмові від розпізнавання.

3. Побудувати стратегію вирішення байесівської задачі з функцією штрафів

,

обчислювальна складність якої не залежить від і лінійно залежить від . Навести двовимірне узагальнення обчислювальної процедури.

4. Побудувати стратегію вирішення байесівської задачі з функцією штрафів

,

обчислювальна складність якої пропорційна не , а .

5. Побудувати стратегію вирішення байесівської задачі з функцією штрафів

,

обчислювальна складність якої пропорційна не , а .

6. Нехай - множина зображень, - множина цифр, , - послідовність зображень, , - прихована послідовність цифр на цих зображеннях. Відомо, що імовірність пари дорівнює , де - імовірність, задана для кожного зображення і кожної цифри .

Побудувати обчислювально ефективну стратегію, яка за заданою послідовністю приймає рішення про суму .

7. Задача Неймана-Пірсона.

8. Мінімаксна задача розпізнавання.

9. Задача Вальда.

10. Узагальнена задача Неймана-Пірсона для випадку двох небезпечних станів.

11. Узагальнена задача Неймана-Пірсона для двох нормальних станів.

12. Узагальнена задача Неймана-Пірсона для двох небезпечних і двох нормальних станів.

13. Складена задача статистичних рішень.

ЗАПИТАННЯ ДО КОНТРОЛЬНОЇ РОБОТИ № 3

1. Емпіричний байесів підхід Г. Роббінса до статистичних рішень.

2. Роббінса і алгоритм її розвязку. Монотонний характер алгоритму розвязку задачі Г. Роббінса.

3. Властивість нерухомих точок алгоритму розвязку задачі Г. Роббінса.

4. Найвірогідніша оцінка параметрів моделі з незалежними ознаками.

5. Найвірогідніша оцінка параметрів гаусової моделі (одновимірний випадок).

6. Найвірогідніша оцінка параметрів псевдогаусової моделі.

7. Задача самонавчання і алгоритм її розвязку. Монотонний характер алгоритму самонавчання.

8. Алгоритм самонавчання для моделі з незалежними ознаками.

9. Алгоритм самонавчання для гаусової моделі (одновимірний випадок).

10. Алгоритм самонавчання для псевдогаусової моделі.

11. Алгоритм Козинця і доведення його збіжності.

12. Алгоритм персептрона і теорема Новікова.

13. Модифікація алгоритмів Козинця і персептрона для випадку, коли кількість прихованих станів більше 2.

14. Алгоритм побудови сфери, що розділяє дві множини.

15. Алгоритм побудови еліпса, що розділяє дві множини.

16. Алгоритм побудови квадратичної дискримінантної функції.

17. Побудова гіперплощини, що розділяє дві скінчені множини точок разом зі сферами заданого радіусу, що їх оточують.

18. Навчання на основі врахування всієї множини стратегій, що не суперечать емпіричним даним.

Запитання, що виносяться на екзамен, складаються із контрольних запитань до залікових модулей 1, 2, 3.

VI. Поточне і семестрове оцінювання.

Успішність студента оцінюється на основі:

- виконання індивідуального завдання;

- двох контрольних робіт;

- складання екзамену.

Кожна контрольна робота оцінюється в балах. Максимальна оцінка за контрольну роботу – 20 балів. Максимальна оцінка за екзамен – 60 балів.

Підсумкова оцінка за курс в цілому складається з суми оцінок з трьох контрольних робіт і оцінки на екзамені.

Студент допускається до складання екзамену, якщо:

- він виконав індивідуальне завдання;

- одержав сумарну оцінку за виконання контрольних робіт, не меншу, ніж 20 балів.

Екзамен вважається успішно складеним, якщо за нього отримано оцінку, не меншу, ніж 20 балів у 60-бальній шкалі.

Підсумкова оцінка за курс в цілому переводиться у ECTS та традиційні оцінки згідно таблиці:

Підсумкова оцінка	Оцінка ECTS	Традиційна оцінка
95...100	А Відмінно	Відмінно
85...94	В Дуже добре	Добре
75...84	С Добре
65...74	D Задовільно	Задовільно
60...64	Е Достатньо
Підсумкова оцінка < 60	Fx Погано	Незадовільно
Сумарна оцінка за контрольні роботи < 20 або індивідуальне завдання не виконано	F Дуже погано	не допущено

VII. Навчально-методичні матеріали.

М. Шлезингер, В. Главач. Десять лекций по статистическому и структурному распознаванию. – К.: Наук. думка, 20 с. , . Вероятность и информация.- М.: Наука, 1973, 511 с. . Математические средства обработки изображений. – К.: Наук. думка, 1989. - 198 с.

Программу склав ст. викл.,