Направление подготовки: 010200 Математика и компьютерные науки - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Направление подготовки: 010200 Математика и компьютерные науки 1 52.92kb.
Программа дисциплины интегральные преобразования и операционное исчисление 1 30.41kb.
Программа для студентов направления 010200. 62 Математика и компьютерные... 1 272.46kb.
О специальности Обучаясь по направлению подготовки «Математика и... 1 54.83kb.
1. общая характеристика специальности 010200 прикладная математика... 2 476.21kb.
Вопросы по философским проблемам и истории математики для магистрантов... 1 41.05kb.
Рабочая программа дисциплины математика направление подготовки: 270800. 4 593.84kb.
Рабочая программа дисциплины Социология науки Направление подготовки... 1 179.38kb.
Использование информационных технологий для совершенствования учебного... 1 21.13kb.
Программа дисциплины функциональный анализ 1 37.14kb.
Программа дисциплины нис для направления 010100. 62 «Математика»... 1 186.36kb.
Электронная цифровая подпись. Понятие, виды и практика их применения 1 206.85kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Направление подготовки: 010200 Математика и компьютерные науки - страница №1/1

Наименование дисциплины: Методы аутентификации

Направление подготовки: 010200 Математика и компьютерные науки


Профильная направленность: Математика и компьютерные науки

Квалификация (степень) выпускника: магистр

Форма обучения: очная

Автор: к.ф.–м.н., доцент, доцент кафедры алгебры и математической логики С. И. Яблокова.


1. Целями освоения дисциплины (модуля) «Методы аутентификации» являются:

обеспечение подготовки в одной из важных областей криптографии и ее приложений, а также в области обработки больших объемов данных на ЭВМ; овладение основными быстрыми методами поиска и сортировки, приемами хеширования и протоколами аутентификации.

2. Дисциплина «Методы аутентификации» входит в цикл вариативных профессиональных дисциплин по профилю подготовки «Алгебра, теория чисел, математическая логика и приложения». Для ее успешного изучения необходимы знания, умения и навыки, приобретенные в ходе изучения таких базовых и специальных курсов, как «Теория чисел», «Теория графов», «Криптография», «Криптографические протоколы», а также курсы, связанные с изучением основ программирования. Эта дисциплина закладывает знание основных приемов эффективной обработки информации на ЭВМ, а также знание основных протоколов, обеспечивающих безопасность передачи информации.

3. В результате освоения дисциплины обучающийся должен:
Знать:

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


Уметь:

использовать быстрые алгоритмы поиска и сортировки, а также основные протоколы аутентификации.


Владеть:

основными методами работы с большими объемами информации и с конфиденциальной информацией при использовании современных компьютерных технологий.



    4. Общая трудоемкость дисциплины составляет 2 зачетные единицы, 72 часа.

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


п/п

Раздел дисциплины

1

Сортировка вставками: простые вставки, оценка числа сравнений. Бинарные и двухпутевые вставки. Метод Шелла. Сложность алгоритма.

2

Обменная сортировка: метод пузырька, оценка числа сравнений. Обменная сортировка со слиянием: алгоритм, его геометрическая интерпретация.

Быстрая сортировка (сортировка Хоара). Оценка числа сравнений.



3

Сортировка с помощью выбора. Квадратичный выбор. Выбор из дерева.

Пирамидальная сортировка. Оценка в худшем случае.



4

Сортировка слиянием. Двухпутевое слияние, простое двухпутевое слияние.

Распределяющая сортировка: лексикографический порядок ключей, сравнение двух алгоритмов по их эффективности. Цифровая распределяющая сортировка



5

Последовательный поиск; быстрый последовательный поиск. Среднее время поиска. Распределение частот по закону Зипфа, среднее время поиска. Самоорганизующаяся таблица и оценка среднего числа сравнений.

6

Поиск посредством сравнения ключей. Бинарный поиск. Теорема о числе сравнений. Внутренний и внешний путь в дереве, длины этих путей, их связь.

7

Полностью сбалансированное бинарное дерево. Леммы и теорема о минимальной длине внешних путей. Среднее число сравнений при бинарном поиске. Однородный бинарный поиск. Модификация Шера.

8

Фибоначчиев поиск. Фибоначчиево дерево, алгоритм поиска.

9

Бинарные деревья поиска. Симметричный порядок обхода. Оптимальные деревья поиска. Алгоритм построения таких деревьев.

10

Почти оптимальные деревья бинарного поиска. Два подхода. Математическое ожидание взвешенной длины пути случайного, оптимального, сбалансированного и монотонного деревьев.

11

Бинарные деревья, сбалансированные по высоте. Оценка крайних случаев времени поиска. Вставка новых узлов: вращение и двойное вращение. Удаление узлов.

Цифровой поиск (поиск по бору).



12

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

13

Фибоначчиево хеширование. Хеширование, основанное на теории кодирования.

Разрешение коллизий методом цепочек, методом открытой адресации, методом открытой адресации с двойным хешированием.



14

Основные задачи криптографии. Криптографические протоколы. Задача аутентификации, код аутентификации, протоколы идентификации.

Фиксированные пароли и атаки на них. Сильная идентификация: симметричные и асимметричные алгоритмы шифрования.



15

Односторонние (однонаправленные) функции. Доказательства с нулевым разглашением. Протокол аутентификации Фиата - Шамира как протокол с нулевым разглашением. Протокол аутентификации Шнорра.

16

Криптографические хеш-функции. Ключевые функции хеширования. Бесключевые хеш-функции. Устойчивость к коллизиям. Примеры хеш-функций.

17

Цифровая подпись, назначение цифровой подписи. Цифровая подпись на основе шифросистем с открытыми ключами. Цифровая подпись Фиата – Шамира. Цифровая подпись Эль – Гамаля.

18

Цифровая подпись Шнорра.

Одноразовые подписи. Схема Диффи – Лампорта.


6. Учебно-методическое и информационное обеспечение дисциплины:


а) основная литература:

  1. Кнут Д. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. – М.: Мир, 1978. – 846с.

  2. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 478с.

  3. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2001. – 480с.

4. Ященко В.В.(ред.) Введение в криптографию. – Санкт-Петербург: МЦНМО, 2001. –

288с.


5. Ростовцев А., Маховенко Е. Введение в криптографию с открытым ключом. – Санкт-

Петербург: НПО «Мир и Семья», 2001. – 336с.

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

-- М.: Мир,1979. – 535с.

7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. – М.: МЦНМО,

2001. – 960с.


б) дополнительная литература:
1. Берлекэмп Э. Алгебраическая теория кодирования. – М.: Мир, 1971