Алгебраическая алгоритмика

Наименование дисциплины: Алгебраическая алгоритмика

Направление подготовки (специальность): 090301 Компьютерная безопасность

Специализация: Математические методы защиты информации

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

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

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

1. Целями освоения дисциплины "Алгебраическая алгоритмика" являются:

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

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

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

Знать:

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

Уметь:

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

Владеть:

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

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

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

№	Раздел дисциплины
1	Кольцо. Кольцо ℤи кольцо многочленов над полем. Целостное кольцо. Теория делимости в целостных кольцах. Обратимый элемент кольца, ассоциированные элементы кольца. Группа обратимых элементов кольца. Наибольший общий делитель (НОД) элементов кольца. Свойства НОД.
	2	Отношения делимости в ℤ и в Теоремы о евклидовом делении. Алгоритм Евклида в кольцах в ℤ и Теоремы о представлении НОД в ℤ и в
	3	Сложность алгоритма Евклида. Теоремы Ламе и Лазара.
	4	Расширенный алгоритм Евклида в ℤ и в Вычисление коэффициентов Безу. Оценки коэффициентов Безу. Приложение к решению линейных диофантовых уравнений.
	5	Алгоритм Евклида и цепные дроби. Свойства цепных дробей. Теорема единственности, Теорема о представлении рациональных чисел цепными дробями. Периодические цепные дроби.
	6	Евклидовы кольца и делимость. Основная теорема арифметики для евклидовых колец. Следствия для колец ℤ и Факториальное кольцо. Неприводимые и простые элементы кольца. Кольцо
	7	Теоремы о простых числах. Решето Эратосфена. Неприводимые многочлены. Разложение на множители над ℂ, ℝ, ℚ и ℤ. Теорема Гаусса. Примитивные многочлены. Рациональные корни многочленов с целыми коэффициентами. Критерий Эйзенштейна.
	8	Сравнения и их свойства. Классы вычетов по данному модулю. Кольцо вычетов по модулю m. Факторкольцо Поля ℤ/ (n) и
	9	Функция Эйлера и ее основные свойства. Малая теорема Ферма. Теорема Эйлера. Дихотомический алгоритм. Псевдопростые числа по данному основанию. Числа Кармайкла. Теорема Вильсона. Тесты простоты. Детерминистические тесты и тесты псевдопростоты.
	10	Многомодульная арифметика. Представление со смешанными основаниями. Выбор модулей для двоичного компьютера.
11	Линейные рекуррентные последовательности максимального периода. Периодические и почти периодические последовательности. Одношаговые генераторы. Декартово произведение генераторов. Необходимые и достаточные условия того, что линейный генератор сравнений является генератором максимального периода.
12	Мультипликативная группа кольца . Циклические группы. Примитивный корень по модулю m. Порядок элемента группы. Цикличность группы при простом p. Лемма Гаусса. Теорема Гаусса (необходимое и достаточное условие цикличности группы .
13	Решения линейного сравнения с одним неизвестным. Китайская теорема об остатках для чисел. Китайские теоремы об остатках для систем сравнений. Китайская теорема об остатках для многочленов.
14	Интерполяция над полем. Формула Лагранжа. Интерполяция с помощью китайской теоремы об остатках.
15	Неприводимые многочлены с коэффициентами из . Число неприводимых многочленов степени n в Критерий неприводимости многочлена над . «Решето Эратосфена» для многочленов над .
16	Конечное поле. Свойства его элементов. Основные теоремы. Факторкольцо Характеристика поля. Мультипликативная группа конечного поля. Примитивный элемент поля. Нахождение примитивного элемента в конечном поле. Поле разложения многочлена. Минимальный многочлен алгебраического над полем элемента. Правило возведения в степень p в поле с характеристикой p. Корни неприводимого многочлена в Существование конечного поля из элементов. Неприводимые многочлены в конечном поле. Разложение многочлена на неприводимые в конечном поле. Построение полей Галуа
17	Линейная и циклическая свертки, их связь. Запись через многочлены. Алгоритм Винограда построения быстрых алгоритмов вычисления коротких сверток.
18	Дискретное преобразование Фурье. Теорема о свертке. БПФ – алгоритм Кули – Тьюки. Алгоритмы Кули – Тьюки по основанию два с прореживанием по времени и по частоте.
17	Алгоритм Рейдера сведения ДПФ к циклической свертке для преобразований простой длины. Алгоритм Рейдера в случае, когда длина преобразования есть степень простого числа. Алгоритм Рейдера в случае, когда длина преобразования есть степень двойки.
19	Малый БПФ-алгоритм Винограда для случаев: 1) длина преобразования есть простое число; 2) длина преобразования есть степень простого числа; 3)длина преобразования есть степень двойки.

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

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

1.блокова алгебраической алгоритмики. Часть 1: учебное пособие. – Ярославль: ЯрГУ, 2008. – 127с.

2.Яблокова алгебраической алгоритмики. Часть 2: учебное пособие. – Яро -

славль: ЯрГУ, 2009. – 120с.

3.Яблокова, С. И., Введение в быстрые алгоритмы цифровой обработки сигналов : учеб. пособие для вузов / ; Яросл. гос. ун-т, Ярославль, ЯрГУ, 2009, 136c

б) дополнительная литература:

1.  Алгебраическая алгоритмика. – М.: Мир, 1999. – 720с.

2.  Основы компьютерной алгебры с приложениями. – М.: Мир, 1994. – 554с.

3. Ван дер Варден . – М.: Наука, 1976.

4. Алгебраическая теория кодирования. – М.: Мир, 1971.