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

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

Направление подготовки (специальность): 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


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

Ноден П., Китте К. Алгебраическая алгоритмика. – М.: Мир, 1999. – 720с.

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

3. Ван дер Варден Б.Л. Алгебра. – М.: Наука, 1976.

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