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

Презентация:



Advertisements
Похожие презентации
1 3 o 5 Оценка эффективности инвестиций 6 Определение затрат.
Advertisements

1 Комбинаторные алгоритмы Локальный поиск. 2 Простейшая задача o размещениях Дано: Полный граф G = (F D, E), стоимости вершин f: F Q + и ребер c: E Q.
Найди недостающее слагаемое
1 ЧТО МОЖНО ДЕЛАТЬ? ЧЕГО ДЕЛАТЬ НЕЛЬЗЯ? ЧТО ЛЮДИ ОБЯЗАНЫ ДЕЛАТЬ? ЧЕГО ОНИ ДЕЛАТЬ НЕ ОБЯЗАНЫ? 3 КАКИЕ У ЧЕЛОВЕКА ЕСТЬ ПРАВА? КАКИЕ У ЧЕЛОВЕКА ЕСТЬ ОБЯЗАННОСТИ?
Умножение и деление на 2. 2х1= 2х2= 2х3= 2х4= 2х5= 2х6= 2х7= 2х8= 2х9=
NP-полнота Теорема Кука. Полиномиальная сводимость Пусть Π 1 =(X 1,Y 1 ) и Π 2 =(X 2,Y 2 ) задачи распознавания. Будем говорить, что Π 1 полиномиально.
Учитель начальных классов Акиншина Н.Н Зарядка для глаз.
Список вопросов к семинарам по проекту в 8 а классе 1.Что такое мышление? 2.Зачем человеку мыслить? 3.Чем отличается мыслить и думать? 4.Нужно ли ы школе.
РОССИЯ 2010 Региональная программа модернизации здравоохранения на 2011, 2012 годы.
Алгоритм Эдмондса Лекция 11. Идея алгоритма Эдмондса Пусть есть некоторое паросочетание M, построим M-чередующийся лес F. Начинаем с множества S вершин.
Параллельность в пространстве Параллельность прямых Параллельность прямой и плоскости Параллельность плоскостей Прямые не пересекаются и лежат в одной.
Никто не забыт, и ничто не забыто.
ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Асимптотический анализ Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных.
Н Как можно назвать эти фигуры одним словом? Какая из фигур лишняя и почему?
Учебный курс Основы вычислительной математики Лекция 1 доктор физико-математических наук, профессор Лобанов Алексей Иванович.
Устный счет. НАЗОВИТЕ ЧИСЛО, СОСТОЯЩЕЕ ИЗ 1 ДЕСЯТКА. НАЗОВИТЕ ЧИСЛО, СОСТОЯЩЕЕ ИЗ 1 ДЕСЯТКА И 5 ЕДИНИЦ. НАЗОВИТЕ ЧИСЛО, КОТОРОЕ НА 1 ЕДИНИЦУ БОЛЬШЕ, ЧЕМ.
Математический диктант 17,9 Вычислите: 1 вариант 2 вариант – 8,3 + (–11,5) – (– 1,9) 1.1. – 6,1 + (–12,4) – (– 2,8) 15, – – – 13 3.
Подобные треугольники
И = 7-6= 10-0=
Как «устроены» числа.. 10 десять 1 десяток 1 десяток и = 11 Одиннадцать.
Транксрипт:

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

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: Так как каждая проверка равенства требует умножений полиномов степени с коэффициентами размером.

1 Время работы алгоритма Лемма 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» А.Черемушкин «Лекции по арифметическим алгоритмам в криптографии» П.Ноден, К.Китте «Алгебраическая алгоритмика» Т.Кормен, Ч.Лейзерсон, Р.Ривест «Алгоритмы: построение и анализ»