Презентация на тему Полиномиальный алгоритм проверки простоты числа

Презентация на тему Полиномиальный алгоритм проверки простоты числа, предмет презентации: Разное. Этот материал содержит 19 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

Полиномиальный алгоритм проверки простоты числа

Комалёва Ольга


Слайд 2
Текст слайда:

План семинара

Постановка задачи

Идея алгоритма

Полиномиальный алгоритм

Оценка времени работы алгоритма

Доказательство корректности алгоритма


Слайд 3
Текст слайда:

Постановка задачи

Дано натуральное число n. Необходимо проверить является ли оно простым за полиномиальное время от длины числа n в бинарной форме.



Слайд 4
Текст слайда:

План семинара

Постановка задачи

Идея алгоритма

Полиномиальный алгоритм

Оценка времени работы алгоритма

Доказательство корректности алгоритма


Слайд 5
Текст слайда:

Основная идея алгоритма

Лемма 1.1.






Слайд 6
Текст слайда:

План семинара

Постановка задачи

Идея алгоритма

Полиномиальный алгоритм

Оценка времени работы алгоритма

Доказательство корректности алгоритма


Слайд 7
Текст слайда:

Алгоритм Agrawal


Слайд 8
Текст слайда:

План семинара

Постановка задачи

Идея алгоритма

Полиномиальный алгоритм

Оценка времени работы алгоритма

Доказательство корректности алгоритма


Слайд 9
Текст слайда:

Время работы алгоритма

Лемма 2.1.


Лемма 2.2.




Слайд 10
Текст слайда:

Время работы алгоритма

Лемма 2.3.



Доказательство:
Шаг 1:
Шаг 2-3:
Шаг 4:
Шаг 5:
Так как каждая проверка равенства требует
умножений полиномов степени с
коэффициентами размером .


Слайд 11
Текст слайда:

Время работы алгоритма

Лемма 3.2.(Фоуври)




Лемма 3.3.


Слайд 12
Текст слайда:

План семинара

Постановка задачи

Идея алгоритма

Полиномиальный алгоритм

Оценка времени работы алгоритма

Доказательство корректности алгоритма


Слайд 13
Текст слайда:

Алгоритм Agrawal


Слайд 14
Текст слайда:

Обозначения


Слайд 15
Текст слайда:

Доказательство корректности

Теорема 3.1.

Лемма 3.2.


Слайд 16
Текст слайда:

Доказательство корректности

Определение 3.3.



Лемма 3.4.


Слайд 17
Текст слайда:

Доказательство корректности

Лемма 3.5.(Hendric Lenstra Jr.)


Лемма 3.6.


Лемма 3.7.


Слайд 18
Текст слайда:

Если не запомните ничего другого

Существует полиномиальный алгоритм проверки простоты числа

Идея алгоритма:


Доказано, что алгоритм работает корректно и за время


Слайд 19
Текст слайда:

Источники

M.Agrawal, N.Kayal, N.Saxena «PRIMES is in P»
А.Черемушкин «Лекции по арифметическим алгоритмам в криптографии»
П.Ноден, К.Китте «Алгебраическая алгоритмика»
Т.Кормен, Ч.Лейзерсон, Р.Ривест «Алгоритмы: построение и анализ»


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

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


Для правообладателей

Яндекс.Метрика