Що таке складність алгоритму?

Уяви, що тобі треба знайти певний вірш у збірці Тараса Шевченка «Кобзар». Те, як швидко ти його знайдеш, залежить не лише від твоєї швидкості, а й від того, який метод (алгоритм) ти обереш.

Складність алгоритму — це міра того, скільки ресурсів (часу або пам'яті) витрачає комп'ютер на виконання програми залежно від обсягу вхідних даних (кількості слів, чисел тощо).

Зазвичай ми говоримо про часову складність:

1. Лінійна складність: Ти перевіряєш кожну сторінку по черзі з першої до останньої. Якщо в книжці 100 сторінок — ти зробиш до 100 кроків. Якщо 1000 — до 1000 кроків.

2. Стала складність: Ти точно знаєш номер сторінки й одразу відкриваєш її. Незалежно від того, наскільки товста книга, ти робиш лише 1 дію.

📝 Практичне завдання «Пошук „Заповіту“»

Контекст:

У нас є список назв творів Тараса Шевченка, відсортований за алфавітом. Нам потрібно знайти, чи є у списку твір «Заповіт».

Твій список:

1. Гайдамаки

2. Гамалія

3. Заповіт

4. Катерина

5. Наймичка

Завдання:

1. Порахуй, скільки кроків (порівнянь) зробить алгоритм, який перевіряє кожну назву по черзі (лінійний пошук), щоб знайти «Заповіт».

2. Уяви, що список виріс до 100 творів, і «Заповіт» опинився в самому кінці. Скільки кроків знадобиться тоді?

✅ Розв’язок завдання

1. Для короткого списку:

   • Крок 1: Це «Гайдамаки»? Ні.

   • Крок 2: Це «Гамалія»? Ні.

   • Крок 3: Це «Заповіт»? Так!

   • Відповідь: Алгоритм зробив 3 кроки.

2. Для списку зі 100 творів:

   • Якщо ми шукаємо «Заповіт» лінійним пошуком і він останній, нам доведеться порівняти його з усіма попередніми назвами.

   • Відповідь: Алгоритм зробить 100 кроків.

Висновок: Лінійна складність означає, що кількість роботи росте прямо пропорційно кількості даних. У програмуванні це позначають як O(n).

Задача: «Найвищі вершини Карпат»

Умова: У тебе є список назв п'яти найвищих вершин Українських Карпат та їхня висота у метрах. Дані:

1. Говерла — 2061 м

2. Бребенескул — 2035 м

3. Піп Іван Чорногірський — 2021 м

4. Петрос — 2020 м

5. Гутин Томнатик — 2016 м

Завдання:

1. Напиши програму на Python, яка зберігає ці дані у вигляді списку.

2. Впорядкуй список за висотою (від найменшої до найбільшої).

3. Додай можливість пошуку висоти вершини за її назвою, яку вводить користувач.

Інвентаризація в магазині електроніки

Умова: У тебе є список цін на 8 різних моделей смартфонів. Ціни занесені в масив.

Тобі потрібно:

1. Створити масив із цінами (можна задати вручну або випадково).

2. Відсортувати цей список за спаданням (від найдорожчого до найдешевшого), щоб виставити преміальні моделі на вітрину першими.

3. Пошук за бюджетом: Користувач вводить суму, яку він готовий витратити. Програма має знайти, чи є в списку смартфон, який коштує рівно стільки (лінійний пошук).

4. Фільтрація: Вивести всі ціни, які менші за 15 000 грн (бюджетні варіанти).

Задача: «Рейтинг геймерів»

Уявіть, що ти розробляєш систему для кіберспортивного турніру. У тебе є список балів, які набрали 10 учасників у грі. Бали записані у масив (список) у довільному порядку.

Завдання: Напиши програму, яка впорядкує ці бали від найменшого до найбільшого, щоб визначити місце кожного гравця.

https://products.aspose.ai/words/uk/crosswordmaker/

Завдання на тему «Алгоритми впорядкування масиву» (9 клас) для виконання у Google Colab на мові Python.

Завдання 1: Метод «бульбашки» (Bubble Sort)

Умова: Дано список оцінок учня: [8, 11, 7, 9, 10, 6]. Напиши програму, яка впорядкує цей список за зростанням (від найменшої до найбільшої) за допомогою алгоритму бульбашки.

Завдання 2: Сортування вибором (Selection Sort)

Умова: Маємо список температур за тиждень: [12, 15, 10, 14, 13, 11, 9]. Впорядкуй їх за спаданням (від найтеплішої до найхолоднішої), використовуючи метод вибору.

Завдання 3: Використання вбудованих інструментів Python

Умова: Створи список імен друзів у довільному порядку. Використовуючи вбудований метод Python, відсортуй їх за алфавітом. Додай до списку нове ім'я та відсортуй ще раз.

Як перевірити в Google Colab:

1. Перейди на colab.research.google.com.

2. Натисни «New Notebook» (Новий блокнот).

3. Скопіюй код кожного завдання в окрему клітинку (Code cell).

4. Натисни кнопку Play зліва від клітинки, щоб побачити результат.

Практичне завдання: "Аналіз температури за лютий"

Умова: Ти — метеоролог-початківець. У тебе є дані про температуру повітря вдень протягом одного тижня (7 днів). Тобі потрібно написати програму на Python, яка:

1. Знаходить найвищу температуру тижня (максимум).

2. Знаходить найнижчу температуру тижня (мінімум).

3. Виводить ці значення на екран.

💡 Як працює алгоритм (логіка)

Уяви, що перед тобою лежить ряд карток із числами сорочкою вгору.

1. Ми беремо першу картку і кажемо: «Припустимо, це і є наше найбільше число».

2. Відкриваємо наступну. Якщо число на ній більше за наше «найбільше», ми забуваємо старе і запам’ятовуємо нове.

3. Повторюємо це до кінця ряду.

✅ Розв’язок завдання

Ось код, який можна скопіювати та вставити прямо у Google Colab:

Python

🚀 Як перевірити в Google Colab:

1. Перейди на colab.research.google.com.

2. Натисни "New Notebook" (Новий блокнот).

3. Скопіюй код вище у порожню чарунку (cell).

4. Натисни кнопку Play (трикутник) зліва від коду або натисни Ctrl + Enter.

Варіант 1. «Цифровий слід: Що про мене знає Google?» (Практичне)

Мета: Дослідити, яку інформацію збирають корпорації та як її обмежити.

• Завдання: 1. Скористатися сервісом Google Takeout (або розділом "Мої дії") та проаналізувати свою історію геолокації за останній місяць.

  2. Подивитися, які рекламні інтереси приписав учню алгоритм (Ads Settings).

  3. Скласти «карту ризиків»: що може дізнатися про тебе зловмисник, маючи доступ до цих даних.

• Результат: Чек-лист «Як почистити свій цифровий слід».

Варіант 2. «Штучний інтелект vs Реальність: Детектор фейків» (Трендове)

Мета: Навчитися розрізняти згенерований контент від справжнього.

• Завдання: 1. Використати нейромережі для створення реалістичного фейку про якийсь закон фізики 

  2. Провести експеримент: показати зображення іншим учням/вчителям і перевірити, чи повірять вони.

  3. Розробити алгоритм «5 ознак Deepfake», на які варто звертати увагу.

• Результат: Презентація з прикладами «ідеальної брехні» та методами її викриття.

Варіант 3. «Анатомія фішингу: Як нас ловлять на гачок» (Соціальне)

Мета: Дослідити психологічні прийоми маніпуляції в мережі.

• Завдання: 1. Знайти (або змоделювати) приклади фішингових повідомлень у Telegram чи Instagram (наприклад, про "виплати допомоги" або "голосування у конкурсі").

  2. Проаналізувати, на які «тригери» тиснуть шахраї: терміновість, страх, жадоба чи цікавість.

  3. Створити інтерактивну гру-квіз (наприклад, на Wordwall чи Kahoot) «Шахрай чи Друг?».

• Результат: Короткий відеоролик (TikTok/Reels) з розбором реальної схеми шахрайства.

Варіант 4. «Мій пароль — фортеця чи картковий будинок?» (Технічне)

Мета: Наочно продемонструвати швидкість зламу простих паролів.

• Завдання: 1. Використати онлайн-сервіси (наприклад, How Secure Is My Password) для перевірки різних комбінацій.

  2. Провести опитування серед однокласників (анонімно!): як часто вони змінюють паролі та чи використовують 2FA (двофакторну автентифікацію).

  3. Дослідити, як працюють менеджери паролів.

• Результат: Порівняльна таблиця: скільки часу потрібно на брутфорс (злам) пароля з 6 та 12 символів.

Покроковий план виконання для учнів:

Уяви, що тобі потрібно записати оцінки 30 учнів класу. Можна створити 30 окремих змінних (a1, a2, a3...), але це незручно. Набагато простіше використати масив.

Масив — це іменована група однотипних елементів, що зберігаються в пам'яті комп'ютера один за одним.

Як це працює (на простих прикладах):

• Масив як потяг: Кожен вагон — це окремий елемент. У вагоні лежить якесь значення (число, текст), а на самому вагоні написаний його номер.

• Масив як готель: Назва готелю — це назва масиву. Номери кімнат — це індекси, а люди, що там живуть — це значення.

Основні характеристики:

1. Ім’я: У всього масиву одна спільна назва (наприклад, marks або names).

2. Індекс (номер): Це порядковий номер елемента в масиві. Важливо: у більшості мов програмування (Python, C++, Java) нумерація починається з 0, а не з 1.

3. Значення: Те, що саме зберігається в конкретній «комірці» масиву.

Зміна значень елементів масиву — це база програмування. Це як перекладати речі в коробках або змінювати цінники в магазині. Оскільки ти просив на «ти», давай розберемо три прості, але реальні задачі, які допоможуть закріпити цю тему.

Ми будемо використовувати мову Python, бо вона найпопулярніша у 9 класі, але логіка однакова для всіх мов.

Задача 1. Акція в магазині (Зменшення значень)

Умова: Маємо масив цін на товари. Сьогодні чорна п'ятниця, і на всі товари діє знижка 50%. Потрібно оновити ціни в масиві.

Код:

Python

prices = [100, 250, 40, 500, 120]

# Проходимо по кожному індексу масиву
for i in range(len(prices)):
 prices[i] = prices[i] / 2 # Змінюємо значення: ділимо на 2

print("Нові ціни зі знижкою:", prices)

Задача 2. Калібрування датчика (Збільшення значень)

Умова: Термометр показує температуру в кімнаті, але він збився і показує на 2 градуси менше, ніж є насправді. Потрібно додати 2 до кожного вимірювання в масиві.

Код:

Python

temps = [18, 19, 21, 17, 20]

for i in range(len(temps)):
 temps[i] = temps[i] + 2 # Збільшуємо кожен елемент на 2

print("Коректні показники температури:", temps)

Задача 3. Обнулення помилок (Заміна за умовою)

Умова: В масиві зберігаються результати тестів. Якщо значення від’ємне (це помилка системи), його треба замінити на 0.

Код:

Python

results = [85, -5, 92, -10, 78]

for i in range(len(results)):
 if results[i] < 0:
 results[i] = 0 # Замінюємо тільки ті значення, що менше нуля

print("Очищені результати:", results)

Що важливо запам'ятати:

1. Індекс (i) — це «адреса» елемента в масиві. Щоб змінити значення, ми звертаємось до нього саме через індекс: масив[i] = нове_значення.

2. Цикл for — ідеальний інструмент для перебору всіх елементів масиву по черзі.

3. Умова if — дозволяє змінювати не всі елементи, а тільки ті, що нам потрібні.

Алгоритми опрацювання елементів одновимірного масиву

1. Основна ідея

Для розв'язання обох задач нам потрібно переглянути кожен елемент масиву. Це робиться за допомогою циклу (зазвичай for). В середині циклу ми перевіряємо умову (за допомогою if).

Ключові змінні:

• Для суми: створюємо змінну (наприклад, S), якій спочатку присвоюємо 0.

• Для кількості: створюємо змінну-лічильник (наприклад, K), якій також спочатку присвоюємо 0.

2. Алгоритм знаходження суми

Ми «пробігаємо» масивом і, якщо елемент нам підходить, додаємо його значення до загальної скарбнички.

Логіка (псевдокод):

1. Надати S = 0.

2. Для кожного елемента A[i] у масиві:

   • Якщо A[i] задовольняє умову (наприклад, A[i] > 0):

     • Збільшити S на значення елемента: S = S + A[i].

3. Вивести S.

3. Алгоритм знаходження кількості

Тут нас не цікавить, наскільки велике число в елементі. Нам важливо лише те, що він "існує" і підходить під умову. Кожен такий елемент додає до лічильника одиницю.

Логіка (псевдокод):

1. Надати K = 0.

2. Для кожного елемента A[i] у масиві:

   • Якщо A[i] задовольняє умову:

     • Збільшити K на одиницю: K = K + 1.

3. Вивести K.

4. Практичне завдання (Python)

Умова: Маємо список оцінок учня за семестр: [8, 12, 5, 10, 11, 4, 9]. Потрібно знайти:

1. Суму оцінок, які вищі за 9 балів.

2. Кількість таких оцінок.

Розв'язок:

Python

# Наш масив (список)
grades = [8, 12, 5, 10, 11, 4, 9]

# Початкові значення
total_sum = 0
count = 0

# Цикл для перебору елементів
for x in grades:
 if x > 9: # Умова: оцінка вища за 9
 total_sum += x # Додаємо саме число до суми
 count += 1 # Додаємо 1 до лічильника

# Вивід результатів
print("Сума оцінок (>9):", total_sum)
print("Кількість оцінок (>9):", count)

Результат роботи програми:

Сума оцінок (>9): 33 (це 12 + 10 + 11) Кількість оцінок (>9): 3

Що важливо пам'ятати:

• Обнулення: Якщо ти забудеш на початку присвоїти змінним 0, програма може видати помилку або додати результат до старого значення, що залишилося в пам'яті.

• Умова: Умова в if може бути будь-якою: парні числа (x % 2 == 0), від'ємні (x < 0) або числа в діапазоні.