Перейти до змісту

ЛР15. Порівняння пошуків і проєктування тестів

Коротко про роботу

Є два сценарії: багато запитів до вже впорядкованих даних та один запит до невпорядкованої послідовності. Варіант визначає STUDENT_X.

Відкрити робочий зошит Як виконувати лабораторні

1. Умова

Є два сценарії: багато запитів до вже впорядкованих даних та один запит до невпорядкованої послідовності.

Усі обчислення виконуйте з даними свого STUDENT_X. Значення варіанта друкує перша комірка зошита.

2. Що треба знати

Робота виконується після Л1–Л7. Потрібні поняття:

  1. лінійний і двійковий пошук
  2. значення n
  3. підрахунок операцій
  4. проєктування тестів

Межа матеріалу

Використовуйте поняття, вивчені до Л1–Л7. Не включайте в одноразовий пошук у невпорядкованих даних окрему сортировку: її прямо виключає умова цієї задачі.

3. Варіант, вхідні дані та результат

У зошиті заповніть STUDENT_NAME, STUDENT_GROUP і STUDENT_X від 1 до 30.

Вхідні дані

Поле Зміст
sorted_values впорядкований набір даних для повторних запитів
unsorted_values невпорядкований набір даних для одного запиту
target_sorted ціль у першому сценарії
target_unsorted ціль у другому сценарії

Поля результату

Поле Зміст
choice_sorted binary або linear для впорядкованих даних
choice_unsorted вибір для одноразового пошуку в невпорядкованих даних
linear_comparisons порівняння у другому сценарії
binary_iterations ітерації у першому сценарії

Назви полів результату не змінюйте.

4. Терміни і правила

Терміни

  • метрика роботи — однакова величина для порівняння алгоритмів, тут кількість перевірок/ітерацій.
  • передумова алгоритму — властивість входу, без якої алгоритм не гарантує правильний результат.

Правила

  1. Для sorted_values дані вже впорядковані та передбачають багато пошукових запитів.
  2. Для unsorted_values передбачений один пошуковий запит; попереднє сортування у цьому сценарії заборонене умовою.
  3. linear_comparisons рахує порівняння з target_unsorted до першого збігу.
  4. binary_iterations рахує перевірені середини під час пошуку target_sorted.

5. Завдання

Завдання 1

Виберіть пошук для впорядкованих і невпорядкованих даних. Запишіть назви у choice_sorted і choice_unsorted та коротко поясніть вибір.

Завдання 2

Порахуйте linear_comparisons для unsorted_values і binary_iterations для sorted_values.

Завдання 3

Перевірте лінійний пошук на відсутньому значенні, а двійковий — на останньому елементі. Виведіть результати обох тестів.

6. Перевірка і здача

  1. Запустіть самоперевірку та виправте помилки.
  2. Перезапустіть ядро і виконайте роботу ще раз від початку.
  3. Збережіть .ipynb і PDF з кодом та результатами.

Назва PDF: LR15_Прізвище_Група_VNN.pdf.