- Розібратись в загальному і структурою даних "дерево" — де використовується, чому так називається.
- Розібрати всі запропоновані варіанти — виконувати потрібно тільки одне (за варіантом), але теоретичні питання будуть стосуватись всіх завдань.
- Уважно розібратись з алгоритмічної складністю роботи з деревами (а точніше — звідки там так часто береться логарифм)
Написати програму-інтерпретатор математичних виразів, що підтримує змінні та (в більш складному варіанті) оператори розгалуження. Можете взяти за основу вашу або чиюсь попередню лабораторну роботу із Shunting Yard.
В цій роботі замість того, щоб одразу обчислювати значення кожної операції, необхідно спочатку побудувати абстрактне синтаксичне дерево виразу. Далі обчислення виразу зводиться до обходу дерева в глибину і обчислення значення вузлів дерева або прийняття рішення про зміну порядку обходу дерева. Як приклад, можна навести умовний оператор: обчислюється лише одна з гілок вершини цього оператора, а інша пропускається.
Значення змінних під час обходу дерева найкраще зберігати в хеш-таблиці. Ніякі типи даних, крім чисел із плаваючою комою, впроваджувати не обов'язково.
AST використовують щоразу при компіляції програм написаних практично всіма мовами програмування. Наприклад, наступному фрагментові коду (приклад з вікіпедії)
while b ≠ 0
if a > b
a := a − b
else
b := b − a
return a
може відповідати таке дерево:
На вхід програмі подається текстовий файл з кодом, наприклад:
abc = 1;
q = 3;
2+abc*q;
Програма має вивести результат обчислення останнього виразу на екран:
result = 5.0
Синтаксис вашої мови можете вибрати будь-який. Програма має підтримувати змінні з іменем довжиною в будь-яку кількість символів, наприклад "a", "abc", "getthereveryfastindeed".
Складніший варіант (+1 бал): додати оператор if. Щоб не додавати булеві типи даних, можна вважати за true будь-яке відмінне від 0 число з плаваючою комою. Синтаксис оператора довільний (з дужками, без дужок, з endif, з блоками { }, або відступами, як у python), але це має бути не тернарний оператор. Наприклад,
a = if b then 1 else 2 або a = b ? 1 : 2 рівнозначні вирази. Перший варіант синтаксис python, другий - С. Обидва вирази є тернарними операторами, а не умовними.
Приклад правильного умовного оператора:
if D then
x1 = (b + sD) / (2 * a)
x2 = (b - sD) / (2 * a)
else
x = b / (2 * a)
Написати програму, що за вказаними координатами та радіусом виводить список всіх установи, що знаходять всередині кола/квадрата із центром у заданих координатах та заданим радіусом.
Майже будь-якій програмі (застосунку, сервісу) сьогодні доводиться мати справу з даними. Сервіси зберігають інформацію про своїх користувачів (ім'я\логін), їх дії (замовлення, особисті кабінети), купу аналітичних даних (що клікнув користувач, як довго знаходився на певній сторінці, як часто заходить у сервіс). Цих даних накопичується так багато, що обробляти та аналізувати їх вручну стає дуже важко. Виникла ціла галузь комп'ютерних наук - Data Science, термін Bid Data та багато чого іншого цікавого, з чим ви ще обов'язково познайомитесь далі.
В цій же роботі вам пропонується більш просте завдання — написати структуру для ефективної обробки певних даних. Очевидно, що якщо зберігати дані (скажімо, інформацію про користувачів) невпорядковано, то навіть при порівняно невеликій базі в мільйон записів кожна операція — спроба щось знайти буде потребувати повного перебору абсолютно всіх записів, що буде займати багато ресурсів — як процесорних, так і часових.
Будь-яка сучасна база даних підтримує індексування — створення допоміжної структури даних, що дозволяє набагато швидше виконувати певні дії над даними. Наприклад, якщо побудувати навіть найпростіше бінарне дерево пошуку, то запит "знайти користувача віком 32 роки" буде виконуватись вже за логарифмічний час. Префіксне дерево в свою чергу дозволить виконувати подібні запити на полях що є рядками (наприклад, ім'я). Сьогодні в базах даних дуже часто біля одного набору даних знаходиться декілька індексів,що дозволяють робити ефективні запити на різних полях.
Індекси можна будувати не тільки над рядками та числами, але й над більш цікавими даними - наприклад над географічними точками. Для цього є навіть окрема назва — Spatial index. Найчастіше, такий індекс реалізовується за допомогою спеціальних дерев, що називаються R-Tree
Вам дається файл наступного формату (csv) лінк
Широта; Довгота; Тип; Підтип; Назва; Адреса;
Ці дані взяті з відкритих джерел — із Open Street Map. Для вашої зручності дані були попередньо оброблені у такий зручний формат із оригінального формату .osm. Ваше завдання - написати програму, що буде приймати на вході географічну точку (широта, довгота), ціле число N, та тип/підтип шуканого об'єкта. Програма має вивести на екран всі установи, що потрапляють у квадрат довжиною N кілометрів із центром в заданій точці. Очевидний варіант — перебирати всі точки та перевіряти, чи потрапляє вона в потрібний сектор. Але це дуже неефективно, і суть завдання полягає саме у роботі зі структурою даних.
> rtree.exe --db=data.csv --lat=30.212, --long=35.872 --size=20
We found next entities in the sector:
1.
2...
Більше складне завдання (+1 бал): вводити не довжину сторони квадрату, а радіус кола
Також пам'ятайте, що координати певної точки на планеті - це широта та довгота, при чому відстань у один градус між двома точками на екваторі набагато більше, ніж відстань у один градус близько до полюсів. Це треба враховувати і коректно рахувати відстані. Для кращого розуміння потрібно почитати про Проекцію Меркатора та пограти у відому гру від Гугла, що показує як ця проекція викривлює справжні масштаби
- Простою мовою про R-дерева
- Цікавий вид R-дерев - дерево Гільберта