Рабочая программа дисциплины Теория помехоустойчивого кодирования Направление подготовки
| Вид материала | Рабочая программа |
- Рабочая программа дисциплины «Теория автоматов и формальных языков» Направление подготовки, 175.99kb.
- Рабочая программа дисциплины «Математическая логика и теория алгоритмов» Направление, 175.54kb.
- Рабочая программа учебной дисциплины «Теория телетрафика» Направление подготовки, 175.5kb.
- Рабочая программа дисциплины «Теория государства и права» пц. Б б. 1 Направление подготовки, 903.23kb.
- Рабочая программа дисциплины «теоретические основы теплотехники» Направление подготовки, 554.69kb.
- Рабочая программа дисциплины «Техническая термодинамитка» Направление подготовки, 804.99kb.
- Рабочая программа дисциплины Физика, ен. Ф. 03 направление подготовки, 491.56kb.
- Рабочая программа учебной дисциплины теория принятия решений Направление подготовки, 591.05kb.
- Рабочая программа дисциплины экономическая теория направление ооп, 340.57kb.
- Рабочая программа дисциплины «Компьютерная диагностика» Направление подготовки, 209.63kb.
Приложение 3
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Национальный исследовательский университет
Новосибирский государственный университет
Механико-математический факультет
УТВЕРЖДАЮ
_______________________
«_____»__________________201__ г.
Рабочая программа дисциплины
Теория помехоустойчивого кодирования
Направление подготовки
Error: Reference source not found
Профиль подготовки
Error: Reference source not found
Квалификация (степень) выпускника
Магистр
Форма обучения
Очная
Новосибирск 2010
Аннотация рабочей программы
Теория кодов, корректирующих ошибки представляет собой описание математическими средствами эффективных методов передачи, хранения и защиты информации по открытым каналам связи с шумами. Математические модели и методы теории кодирования широко применяются в информационных системах при решении насущных практических проблем для защиты информации от ошибок, котрые могут произойти при передаче данных по открытым каналам связи с помехами.
Теория помехоустойчивого кодирования сравнительно новая, но интенсивно и бурно развивающаяся, что диктуется, в первую очередь, практическими запросами передачи данных на большие расстояния по открытым каналам связи с шумами. Теория кодирования начала свое развитие с фундаментальных классических работ 1949 года Клода Шеннона.
Среди областей применения теории кодирования можно упомянуть такие существенные области, как связь с помощью копьютерных сетей, космическая связь, конфиденциальная передача данных (практическое приложение теории кодирования совместно с криптологией), телевидение. Эта наука — одна из важнейших научных направлений, бурно и интенсивно развиваемых в течение последних десятилетий. Без успехов в данных областях были бы невозможны современные системы связи и устройства хранения информации, во многом определяющие наблюдаемый сегодня прогресс в информационных системах и, вообще, в науке и технике. В настоящее время в нашей стране и за рубежом проводится интенсивный поиск новых эффективных методов математических моделей передачи данных.
Преподавание дисциплины предусматривает следующие формы организации учебного процесса: лекции, самостоятельная работа студента.
Программой дисциплины предусмотрены следующие виды контроля: текущий контроль успеваемости в форме контрольной работы, контроль в форме экзамена. Формы рубежного контроля определяются решениями Ученого совета, действующими в течение текущего учебного года.
Общая трудоемкость дисциплины составляет 161 зачетных единиц, 32 академических часа. Остальное время – контроль в форме контрольной и экзамена.
1. Цели освоения дисциплины
(Указываются цели освоения дисциплины (или модуля), соотнесенные с общими целями ООП ВПО).
Магистерская программа по специальности «Теория кодирования» предназначена для подготовки выпускников к научно-исследовательской работе в аспирантуре, а также для подготовки специалистов, способных решать разнообразные теоретические и практические задачи, возникающие при передаче и хранении информации.
2. Место дисциплины в структуре ООП бакалавриата
(Дается описание логической и содержательно-методической взаимосвязи с другими частями ООП (дисциплинами, модулями, практиками). Указываются требования к «входным» знаниям, умениям и готовностям обучающегося, необходимым при освоении данной дисциплины и приобретенным в результате освоения предшествующих дисциплин (модулей).)
Дисциплина «Error: Reference source not found» является частью математического цикла ООП по направлению подготовки «Error: Reference source not found», профиль «Error: Reference source not found».
Дисциплина «Error: Reference source not found» опирается на следующие дисциплины данной ООП:
- Дискретная математика
- Теория вероятностей
- Алгебра
- Математические методы защиты информации
Результаты освоения дисциплины «Error: Reference source not found» используются в следующих дисциплинах данной ООП:
- Дискретная математика
- Математические методы защиты информации
3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Error: Reference source not found»:
Выпускник магистратуры должен обладать следующими профессиональными компетенциями в соответствии с видами деятельности:
научно-исследовательская деятельность:
К1 уметь использовать методы передачи, хранения и защиты информации для исследования различных явлений и процессов, в том числе:
К1.1 знать методы теории кодирования для решения задач передачи информации по каналам связи с шумами
К1.2 знать криптографические методы защиты информации от несанкционированного доступа для передачи информации с использованием как криптосистем с секретными ключами, так и криптосистем с открытыми ключами.
К2 знать методы дискретной математики, в том числе:
К2.1 комбинаторные методы решения задач
К2.2 методы теории графов
К3.1 знать теорию вероятностей
К3.2 знать теорию чисел
К3.3 знать высшую алгебру и теорию полей Галуа
производственно-технологическая деятельность
К4 уметь применять современные методы теории кодирования и сжатия информации
К5 уметь применять криптографические методы защиты информации от несанкционированного доступа:
К5.2 владеть методами защиты информации, основанными на криптосистемах с открытыми ключами, основанных на методах теории кодирования, уметь создавать цифровые подписи
К6 владеть навыками построения основных методов защиты информации, в том числе
К6.2 владеть навыками кодирования и декодирования основных линейных кодов, в том числе циклических
4. Структура и содержание дисциплины
Общая трудоемкость дисциплины составляет ?? зачетные единицы, 36 часов.
| № п/п | Раздел дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам) | ||||
| Лекция | Лабор. работа | коллоквиум | Консультации работа | экзамен | |||||
| 1.1 | Модель канала связи, скорость кода, пропускная способность. Теорема Шеннона для двоичного симметричного канала связи с шумом (с доказательством | 2 | 1,2 | 4 | 0 | 33 | 8 | 20 | |
| 1.2 | Поле Галуа, его свойства. | | 3 | 2 | | | | | |
| 1.3 | Линейные коды. Кодирование и декодирование. Общие свойства линейных кодов. Теорема о связи проверочной и порождающей матриц. Теорема Глаголева. | | 4 | 2 | | | | | |
| 1.4 | Границы объема кода: граница Синглтона, граница Хэмминга, граница Варшамова-Гилберта. Оценки мощностей кодов, теоремы Джонсона. | | 5 | 2 | | | | | |
| 1.5 | Методы построения новых кодов из заданных. Комбинирование кодов. Теорема Плоткина. Каскадная конструкция. | | 6 | 2 | | | | | |
| 1.6 | Совершенные коды. Теорема о существовании совершенных кодов. Коды Хемминга над GF(q), способы задания, кодирование, декодирование, единственность. Группа автоморфизмов кода Хэмминга. Конструкции совершенных кодов: свитчинговые (коды Васильева, Моллара, конструкция  -компонент), каскадные (коды Зиновьева, Соловьевой, Фелпса). Оценки числа совершенных кодов. Общие свойства совершенных кодов, теоремы Шапиро и Злотника, группа автоморфизмов совершенных кодов. Связь совершенных кодов с блок схемами, конструкция Ассмуса и Маттсона. | | 7,8 | 4 | | | | | |
| 1.7 | Матрица Адамара. Коды Адамара. Связь кодов Адамара с кодами Хэмминга и блок-схемами. | | 9 | 2 | | | | | |
| 1.8 | Коды Рида-Маллера, группа автоморфизмов. Код Голея, его свойства. Код Нордстрома-Робинсона. | | 10 | 2 | | | | | |
| 1.9 | Двойственные коды. Весовой энумератор. Дискретное преобразование Фурье. Тождества Мак-Вильямс. | | 11 | 2 | | | | | |
| 1.10 | Циклические коды. Кольцо многочленов над полем Галуа. Определение циклического кода. Теорема о необходимом и достаточном условии существования циклического кода с порождающим многочленом g(x). Кодирование и декодирование циклических кодов. Примеры циклических кодов: коды Хэмминга, коды Боуза-Чоудхури- Хоквингема (БЧХ-коды), коды Рида-Соломона, коды Юсгесена, коды Гоппы. | | 12-16 | 10 | | | | | |
| | | | | | | | | | Экзамен |
| | | | | 32 | 0 | 33 | 8 | 20 | Итого 97 часов |
(Наиболее распространенные виды/формы организации учебного процесса: лекция/мастер-класс, лабораторная работа, практическая занятие, семинар/коллоквиум, самостоятельная работа студента, консультации/тьюторство, курсовое проектирование, производственная практика, научно-исследовательская работа, выпускная квалификационная работа).
5. Образовательные технологии
(Указываются образовательные технологии, используемые при реализации различных видов учебной работы. Наиболее распространенные виды/формы образовательных технологий: традиционные лекционно-семинарские системы обучения, информационные технологии (обучение в электронной образовательной среде), работа в команде, case-study (анализ реальных проблемных ситуаций и поиск решений), ролевая игра, проблемное изучение, контекстное изучение, обучение на основе опыта, индивидуальное обучение, междисциплинарное обучение, опережающая самостоятельная работа.
В соответствии с требованиями ФГОС ВПО по направлению подготовки реализация компетентностного подхода должна предусматривать широкое использование в учебном процессе активных и интерактивных форм проведения занятий (компьютерных симуляций, деловых и ролевых игр, разбор конкретных ситуаций, психологические и иные тренинги) в сочетании с внеаудиторной работой с целью формирования и развития профессиональных навыков обучающихся. В рамках учебных курсов должны быть предусмотрены встречи с представителями российских и зарубежных компаний, государственных и общественных организаций, мастер-классы экспертов и специалистов.
Удельный вес занятий, проводимых в интерактивных формах, определяется главной целью (миссией) программы, особенностью контингента обучающихся и содержанием конкретных дисциплин, и в целом в учебном процессе они должны составлять не менее 30% аудиторных занятий (определяется требованиями ФГОС с учетом специфики ООП). Занятия лекционного типа для соответствующих групп студентов не могут составлять более 50% аудиторных занятий (определяется соответствующим ФГОС)).
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины
Решение задач, написание рефератов по криптографии.
(Приводятся виды самостоятельной работы обучающегося, порядок их выполнения и контроля, дается учебно-методическое обеспечение (возможно в виде ссылок) самостоятельной работы по отдельным разделам дисциплины.
Указываются темы эссе, рефератов, курсовых работ и др. Приводятся контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины.)
7. Учебно-методическое и информационное обеспечение дисциплины
Программа курса
Кодирование в двоичном симметричном канале
- Модель канала связи, скорость кода, пропускная способность. Теорема Шеннона для двоичного симметричного канала связи с шумом (с доказательством). Вероятность ошибки декодирования. Стандартное расположение. Синдром.
- Поле Галуа, его свойства.
- Линейные коды. Кодирование и декодирование. Общие свойства линейных кодов. Теорема о связи проверочной и порождающей матриц. Теорема Глаголева.
- Границы объема кода: граница Синглтона, граница Хэмминга, граница Варшамова-Гилберта. Оценки мощностей кодов, теоремы Джонсона.
- Методы построения новых кодов из заданных. Комбинирование кодов. Теорема Плоткина. Каскадная конструкция.
- Совершенные коды. Теорема о существовании совершенных кодов. Коды Хемминга над GF(q), способы задания, кодирование, декодирование, единственность. Группа автоморфизмов кода Хэмминга. Конструкции совершенных кодов: свитчинговые (коды Васильева, Моллара, конструкция -компонент), каскадные (коды Зиновьева, Соловьевой, Фелпса). Оценки числа совершенных кодов. Общие свойства совершенных кодов, теоремы Шапиро и Злотника, группа автоморфизмов совершенных кодов. Связь совершенных кодов с блок схемами, конструкция Ассмуса и Маттсона.
- Матрица Адамара. Коды Адамара. Связь кодов Адамара с кодами Хэмминга и блок-схемами.
- Коды Рида-Маллера, группа автоморфизмов. Код Голея, его свойства. Код Нордстрома-Робинсона.
- Двойственные коды. Весовой энумератор. Дискретное преобразование Фурье. Тождества Мак-Вильямс.
- Циклические коды. Кольцо многочленов над полем Галуа. Определение циклического кода. Теорема о необходимом и достаточном условии существования циклического кода с порождающим многочленом g(x). Кодирование и декодирование циклических кодов. Примеры циклических кодов: коды Хэмминга, коды Боуза-Чоудхури- Хоквингема (БЧХ-коды), коды Рида-Соломона, коды Юсгесена, коды Гоппы.
а) основная литература:
- Ф.И.Соловьева, Введение в теорию кодирования, учебное пособие для студентов ММФ и ФИТ НГУ., Изд. НГУ, 2006г., 123 с., под грифом УМО.
- Мак-Вильямс Ф. Дж. А.., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. Пер. с англ. – М.: Связь, 1979. – 744 с.
- Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. – М.: Наука. 1980. – 399 с.
- Сидельников В.М., Теория кодирования, Физматлит, 2008, 324 с.
- Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. Пер. с англ. – М.: Мир. 1976. – 594 с.
б) дополнительная литература:
- Шеннон Л.А. Работы по теории информации и кибернетике. М.: ИЛ. 1963.
- Конвей Дж.Н., Слоэн Н.Дж.А. Упаковки шаров, решетки и группы. Пер. с англ. – М.: Мир. 1990. –I, II т.
- Solov'eva F.I., On perfect codes and related topics, Lecture Notes, Pohang University of Science and Technology (POSTECH), Republik of Korea, 2004, 80 pp.
в) программное обеспечение и Интернет-ресурсы:
8. Материально-техническое обеспечение дисциплины
- Ноутбук, медиа-проектор, экран.
- Программное обеспечение для демонстрации слайд-презентаций.
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению «Error: Reference source not found» и профилю подготовки «Error: Reference source not found».
Автор: Соловьева Фаина Ивановна
д.ф.-м.н., профессор ММФ НГУ
в.н.с. ИМ СО РАН
Рецензент (ы)
Программа одобрена на заседании
(Наименование уполномоченного органа вуза (УМК, НМС, Ученый совет)
от ___________ года, протокол № ________