- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Полиномиальный алгоритм проверки простоты числа презентация
Содержание
- 1. Полиномиальный алгоритм проверки простоты числа
- 2. План семинара Постановка задачи Идея алгоритма
- 3. Постановка задачи Дано натуральное число n. Необходимо
- 4. План семинара Постановка задачи Идея алгоритма
- 5. Основная идея алгоритма Лемма 1.1.
- 6. План семинара Постановка задачи Идея алгоритма
- 7. Алгоритм Agrawal
- 8. План семинара Постановка задачи Идея алгоритма
- 9. Время работы алгоритма Лемма 2.1. Лемма 2.2.
- 10. Время работы алгоритма Лемма 2.3.
- 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
План семинара Постановка задачи Идея алгоритма Полиномиальный алгоритм Оценка времени работы алгоритма Доказательство корректности алгоритма
Слайд 2План семинара
Постановка задачи
Идея алгоритма
Полиномиальный алгоритм
Оценка времени работы алгоритма
Доказательство корректности
алгоритма
Слайд 3Постановка задачи
Дано натуральное число n. Необходимо проверить является ли оно простым
за полиномиальное время от длины числа n в бинарной форме.
Слайд 4План семинара
Постановка задачи
Идея алгоритма
Полиномиальный алгоритм
Оценка времени работы алгоритма
Доказательство корректности
алгоритма
Слайд 6План семинара
Постановка задачи
Идея алгоритма
Полиномиальный алгоритм
Оценка времени работы алгоритма
Доказательство корректности алгоритма
Слайд 8План семинара
Постановка задачи
Идея алгоритма
Полиномиальный алгоритм
Оценка времени работы алгоритма
Доказательство корректности
алгоритма
Слайд 10Время работы алгоритма
Лемма 2.3.
Доказательство:
Шаг 1:
Шаг 2-3:
Шаг 4:
Шаг 5:
Так как каждая
проверка равенства требует
умножений полиномов степени с
коэффициентами размером .
умножений полиномов степени с
коэффициентами размером .
Слайд 12План семинара
Постановка задачи
Идея алгоритма
Полиномиальный алгоритм
Оценка времени работы алгоритма
Доказательство корректности алгоритма
Слайд 18Если не запомните ничего другого
Существует полиномиальный алгоритм проверки простоты числа
Идея алгоритма:
Доказано,
что алгоритм работает корректно и за время
Слайд 19Источники
M.Agrawal, N.Kayal, N.Saxena «PRIMES is in P»
А.Черемушкин «Лекции по арифметическим алгоритмам
в криптографии»
П.Ноден, К.Китте «Алгебраическая алгоритмика»
Т.Кормен, Ч.Лейзерсон, Р.Ривест «Алгоритмы: построение и анализ»
П.Ноден, К.Китте «Алгебраическая алгоритмика»
Т.Кормен, Ч.Лейзерсон, Р.Ривест «Алгоритмы: построение и анализ»
