Минобрнауки томский государственный университет факультет информатики утверждаю




Скачать 55.94 Kb.
НазваниеМинобрнауки томский государственный университет факультет информатики утверждаю
Дата19.01.2013
Размер55.94 Kb.
ТипЗадача
МИНОБРНАУКИ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ИНФОРМАТИКИ


УТВЕРЖДАЮ

Декан факультета

С.П. Сущенко

« » 2010 г.


ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЕ

(ОПД.В.01)

РАБОЧАЯ ПРОГРАММА

трудоемкость дисциплины 4 зачетные единицы


НАПРАВЛЕНИЕ 010400 – ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ


Томск

2010


УТВЕРЖДЕНО

кафедрой теоретических основ информатики.

Протокол №05/10 от 01.09.2010

Зав. кафедрой, профессор

Ю.Л. Костюк


СОСТАВИТЕЛЬ

д.т.н., зав. кафедрой теоретических основ информатики

Ю.Л. Костюк



I.Организационно-методический раздел


Цель курса – формирование основ знаний по теории информации, принципам кодирования, изучение важнейших алгоритмов в этой области.

Задача учебного курса. Студент должен знать основные понятия теории информации, принципы разработки эффективных алгоритмов кодирования и обработки информации, методы исследования этих алгоритмов.

Дисциплины-предшественники: основы дискретной математики, математическая логика и теория алгоритмов, теория конечных графов и ее приложения, алгебра и геометрия, основы программирования, алгоритмы и анализ сложности.

Требования к уровню освоения дисциплины. Успешно освоившим дисциплину считается студент, обладающий знанием теории информации, владеющий принципами разработки эффективных алгоритмов кодирования и обработки информации, методами исследования этих алгоритмов.

II.Содержание дисциплины

II.1.Лекционный курс


1. Коды, информация, энтропия

Канал связи и сообщение. Информация дискретного сообщения. Энтропия. Кодирование. Избыточность. Кодирование Хаффмана. Методы сжатия сообщений.

2. Помехоустойчивое кодирование

Коды проверки на четность. Кодовое расстояние, его влияние на свойства кода. Линейные коды, их свойства. Простой и расширенный код Хемминга. Полиномиальная арифметика. Циклические коды, их свойства.

3. Случайные числа

Случайная и псевдослучайная последовательность. Линейные конгруэнтные последовательности, их свойства. Дважды случайный датчик. Статистические тесты. Генерирование случайных чисел для произвольных распределений.

4. Алгоритмы над сверхдлинными числами

Двоичное представление сверхдлинных целых чисел. Сложение, вычитание и умножение чисел в двоичном виде и в виде машинных слов. Русский крестьянский метод деления двоичных чисел. Деление "в столбик" для чисел в виде машинных слов. Ускоренный алгоритм умножения, основанный на методе «разделяй и властвуй». Наибольший общий делитель (алгоритм Евклида) для сверхдлинных чисел. Обобщенный алгоритм Евклида, вычисление обратных по модулю чисел. Рекурсивный алгоритм умножения по методу "разделяй и властвуй". Модульная арифметика. Китайская теорема об остатках. Алгоритм Гарнера восстановления чисел по остаткам. Разложение чисел на множители.

II.2.Лабораторные работы


Лабораторные работы выполняются по ИНДИВИДУАЛЬНЫМ ЗАДАНИЯМ:

1. Построение кода Хаффмана для символов конкретного текста.

2. Кодирование и декодирование текста заданным неравномерным кодом.

3. Построение кода со сжатием повторяющихся символов. Кодирование и декодирование для этого кода.

4. Линейный случайный датчик и его исследование.

5. Дважды случайный датчик.

6. Датчик для битовых последовательностей.

7. Шифрование и дешифрование случайной последовательностью.

8. Шифрование и дешифрование методом подстановки.

9. Шифрование и дешифрование методом перестановки.

10. Шифрование и дешифрование методом возведения в степень по модулю.

11. Кодирование и декодирование линейным корректирующим кодом.

12. Кодирование и декодирование кодом Хемминга.

13. Кодирование и декодирование циклическим кодом.

14. Деление длинных чисел "в столбик".

15. Быстрое возведение в степень длинных чисел.

16. Быстрое возведение в степень длинных чисел по модулю.

17. Быстрое умножение длинных чисел рекурсивным разрезанием пополам.

18. Обобщенный алгоритм Евклида для коротких чисел.

19. Проверка делимости сверхдлинного числа на короткие простые числа.

Распределение часов курса по темам и видам работ


№№ пп

Наименование тем

Всего часов

Аудиторные занятия (час),

в том числе

Самостоятельная

работа










лекции

семинары

лабораторные занятия




1

Коды, информация, энтропия

13

10







3

2

Помехоустойчивое кодирование

11

8







3

3

Случайные числа

13

10







3

4

Алгоритмы над сверхдлинными числами

11

8







3

5

Лабораторные работы

36

0




36




ИТОГО




84

36




36

12



III.Учебно-методическое обеспечение курса

III.1.Основная литература


1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир,1979.

2. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.

3. Галлагер Р. Теория информации и надежная связь. – М.: Советское радио, 1974.

4. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. – М.: Мир, 1977.

Похожие:

Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – закрепление теоретических знаний по теоретическим и математическим основам информатики, навыков создания и анализа программных...
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Требования к уровню освоения дисциплины – владение методами математического анализа
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – изучение методов объектно-ориентированного анализа и проектирования
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – изучение методов объектно-ориентированного анализа и проектирования
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – изучение математических основ и алгоритмов представления и обработки изображений
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – изучение теории формальных языков, автоматов и методов построения трансляторов
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – ознакомить студентов с основными задачами компьютерной графики и методами их решения
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Задача учебного курса – ознакомление с основными понятиями и методами неклассических логик с ориентацией на их использование в практической...
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Задача учебного курса – ознакомление с основными понятиями и методами неклассических логик с ориентацией на их использование в практической...
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Задача учебного курса – ознакомление с основными понятиями и методами математической логики и теории алгоритмов с ориентацией на...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница