Алгоритми пошуку простих чисел

1 2 3 4

Ім'я файлу: Курсова.docx
Розширення: docx
Розмір: 268кб.
Дата: 26.04.2023
скачати

МІНІСТЕРСТВО ОСВІТИ, НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
ДОНБАСЬКА ДЕРЖАВНА МАШИНОБУДІВНА АКАДЕМІЯ
КАФЕДРА

КОМП'ЮТЕРНИХ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
курсова робота
з дисципліни

«Теорія алгоритмів»
ТЕМА: «Алгоритми пошуку простих чисел»
Варіант: 1

Виконав:

студент групи КН 18-1

Білинський В.Д. ______________

(підпис)

Керівник:

Сташкевич І.І. ________________

(підпис)

Дата захисту роботи	Оцінка	Підписи викладачів

м. Краматорськ 2019 р.

АНОТАЦІЯ
Курсова робота з дисципліни «Теорія алгоритмів» на тему: «Алгоритми пошуку простих чисел» студента групи КН 18-1 (Білинського Валерія Дмитровича), містить 34 сторінки машино друкувального тексту, 9 рисунків, 1 таблицю, 9 формул.

У роботі було визначено сутність простого числа, означено принципи його пошуку за допомогою ряду певних алгоритмів.

Було розглянуто принципи дії наївного перебору, оптимізованого перебору подільників, перебору із запам'ятовуванням знайдених простих чисел, решета Ератосфена, його оптимізації, решета Аткіна, решета Сундарама, чисел Мерсена, теста Люка-Лемера, теореми Ферма, теста Мілера-Рабіна, Тест Baillie-PSW.

Після аналізу складності алгоритмів, їх швидкості та доцільності використання під конкретні ситуації було обрано решето Ератосфена у якості алгоритму, який використано для складання функціональної програми.

Після розробки та випробувань програму із використанням решета Ератосфена можна рекомендувати для пошуку простих чисел на заданому проміжку.

Курсова робота виконана за напрямком «Комп’ютерні науки», дисципліна «Теорія алгоритмів», та може бути пропонована студентам для самостійного вивчення питань з пошуку простих чисел.

З М І С Т

Вступ………………………………………………………………….	4
1 АЛГОРИТМИ ПОШУКУ ПРОСТИХ ЧИСЕЛ…………………...	5
1.1 Просте число і його властивості………………………………...	5
1.2 Алгоритми пошуку і розпізнавання простих чисел…………....	7
1.2.1 Наївний перебір………………………………………………...	7
1.2.2 Оптимізований перебір дільників……………………………..	7
1.2.3 Перебір із запам’ятовуванням знайдених простих чисел…...	8
1.2.4 Решето Ератосфена…………………………………………….	9
1.2.5 Модифікації решета Ератосфена……………………………...	15
1.2.6 Решето Аткіна…………………………………………………..	19
1.2.7 Решето Сундарама……………………………………………...	21
1.2.8 Числа Мерсена і тест Люка-Лемера…………………………..	22
1.2.9 Теорема Ферма…………………………………………………	22
1.2.10 Тест Мілера-Рабіна…………………………………………...	23
1.2.11 Тест Ballie-PSW……………………………………………….	24
1.3 Висновки і обрання методу за яким буде складена програма...	25
2 РОЗРОБКА ПРОГРАМИ………………………………...………...	26
2.1 сучасні вимоги до програмних продуктів………………………	26
2.2 Обґрунтування вибору засобів реалізації………………………	26
2.3 Структура програмного продукту………………………………	26
2.4 Зовнішній вигляд програми та опис її функціонування……….	27
3 КЕРІВНИЦТВО КОРИСТУВАЧА………………………………..	32
3.1 Запуск програми………………………………………………….	32
3.2 Робота з програмою……………………………………………...	32
Висновок……………………………………………………………...	33
Джерела……………………………………………………………….	34

Вим

Лист

№ докум.

Підпис

Дата

Розроб.

Білинський В.Д.

Перевір.

Сташкевич І.І.

Т. контр.

КН-18-1

Н. контр.

Зат.

1 2 3 4

скачати

© Усі права захищені
написати до нас