ЗМЕНШЕННЯ ОБЧИСЛЮВАЛЬНОЇ СКЛАДНОСТІ АЛГОРИТМУ ВИЗНАЧЕННЯ ДОСКОНАЛИХ ЧИСЕЛ ТА ВИВЧЕННЯ ЦЬОГО ПОНЯТТЯ У СЕРЕДНІЙ ШКОЛІ
DOI:
https://doi.org/10.32782/3041-2021/2024-2-9Ключові слова:
досконалі числа, асимптотична обчислювальна складність, оптимізація алгоритмівАнотація
В статті обґрунтована доцільність вивчення поняття асимптотичної обчислювальної складності на уроках інформатики в середній школі, починаючи з теми «Вкладені цикли». Доведено парність досконалих чисел та показано, що квадрати натуральних чисел не можуть бути досконалими числами. Встановлено, що для визначення досконалості числа N його нетривіальні дільники варто шукати на інтервалі від двох до квадратного кореня з N-1 та додавати до суми не лише знайдений дільник, а й отриману частку. Це дало змогу прискорити обчислення та не перевіряти відмінності частки від дільника. Наведені в статті вдосконалення алгоритму пошуку досконалих чисел на заданому інтервалі дають змогу зменшити його асимптотичну обчислювальну складність з O(N2) до складність з O(N2) до O(N N ). ВВ процесі виведення теорем про парність та властивості досконалих чисел використано дедуктивний метод. Оцінку складності алгоритмів визначення досконалих чисел на заданому інтервалі проведено методами теорії алгоритмів. В роботі описано реалізації розроблених алгоритмів мовою програмування C#. Правильність теоретичних викладок та коректність наведених фрагментів програм підтверджена експериментально за допомогою віддаленого незалежного обчислювального середовища на сайті https://www.e-olymp. com. В дослідженні показано, що кардинальне зменшення обчислювальної складності алгоритму можливо насамперед за рахунок зменшення асимптотичної обчислювальної складності. Поняття асимптотичної обчислювальної складності в контексті часу виконання доцільно формувати в учнів на уроках інформатики не тільки спеціалізованих, а й загальноосвітніх шкіл, починаючи з 7 класу, в процесі вивчення вкладених циклів, наприклад, за допомогою задачі визначення досконалих чисел на заданому інтервалі. Це формуватиме в учнів навики написання не лише правильних, а й ефективних програм.
Посилання
Обчислювальна складність. URL: https://znaimo.com.ua/Обчислювальна_складність#link0 (дата звернення: 21.12.2020).
Програма курсу «Інформатика». 5 – 9 класи загальноосвітніх навчальних закладів. URL: https://mon.gov.ua/storage/app/media/zagalna%20serednya/programy-5-9-klas/onovlennya-12-2017/programa-informatika-5-9-traven-2015.pdf (дата звернення: 21.12.2020).
Програма курсу «Інформатика». 8–9 класи загальноосвітніх навчальних закладів з поглибленим вивченням інформатики. URL: https://mon.gov.ua/storage/app/media/zagalna%20serednya/programy-5-9-klas/informatika.pdf (дата звернення: 21.12.2020).
Шинкаренко В. І. Особливості практичного застосування показників обчислювальної складності алгоритмів. Проблеми програмування. 2008. № 2-3. С. 57-63.
Оцінка складності алгоритмів, або Що таке О(log n). URL: https://echo.lviv.ua/dev/53 (дата звернення: 21.12.2020).
Руденко В. Д., Речич Н. В., Потієнко В. О. Інформатика для загальноосвітніх навчальних закладів з поглибленим вивченням інформатики : підруч. для 9 кл. загальноосвіт. навч. закл. Харків : Вид-во «Ранок». 2017. 240 с.
Захарова О. Вивчаємо математику: Досконалі числа. 2014. URL: http://matematikav6.blogspot.com/2014/09/blog-post_66.html (дата звернення: 21.12.2020).
Perfect number. URL: https://en.wikipedia.org/wiki/Perfect_number (дата звернення: 21.12.2020).
Great Internet Mersenne Prime Search. URL: https://www.mersenne.org/ (дата звернення: 21.12.2020).
Теорія чисел – математичні основи розв’язування олімпіадних задач. URL: https://www.e-olymp.com/uk/blogs/posts/53 (дата звернення: 21.12.2020).
Креневич А. П., Обвінцев О. В. С у задачах і прикладах : навчальний посібник із дисципліни «Інформатика та програмування». Київ: Видавничо-поліграфічний центр «Київський університет», 2011. 208 с.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms, Third Edition. Cambridge: MIT Press, 2009. 1320 p.
