АЛГОРИТМИ І СКЛАДНІСТЬ. 2 СЕМЕСТР. ЗАДАЧІ
Для візуалізації графу зв'язків використовувати (https://www.graphviz.org/)
Приклади використання
https://tushavin.ru/graphviz/
http://lib.custis.ru/Graphviz
http://www.webgraphviz.com
1. Ідеальне хешування. (2 бали)
2. Дерево порядкової статистики (реалізація на основі червоно-чорного дерева). (2 бали).
3. Реалізуйте розширюване дерево (splay tree). (2 бали)
4. Оптимальне бінарне дерево пошуку (динамічне програмування). (2 бали)
5. Реалізація персистентної множини на основі червоно-чорного дерева. Час роботи вставки і
видалення в найгіршому випадку і об‘єм необхідної пам’яті мають бути О(log n). (Можна
реалізувати на простому бінарному дереві пошуку – тоді мінус бал). (3 бали)
6. Реалізація В+ -дерева. (3 бали)
7. Реалізація біноміальної піраміди. (3 бали)
8. Реалізація піраміди Фібоначчі. (3 бали)
9. Алгоритм Джонсона для розріджених графів (включає алгоритми Беллмана-Форда і
Дейкстри). В алгоритмі Дейкстри використайте піраміду Фібоначчі (у випадку реалізації
звичайної черги з пріоритетами – мінус бал). (5 балів)
Варіант 1
Предметна область Карта світу
Об'єкти Країни, Міста
Примітка Карта світу містить множину
країн для кожної країни
визначено множина міст.
Варіант 2
Предметна область Бібліотека
Об'єкти Автори, Книги
Примітка Книги в бібліотеці
згруповані по авторам. У
кожного учасника є
множина книг.
варіант 3
Предметна область Відділ кадрів
Об'єкти Підрозділи, Співробітники
Примітка Є множина
підрозділів підприємства. В
кожному підрозділі працює
множина співробітників.
варіант 4
Предметна область Навчальний відділ
Об'єкти Групи, Студенти
Примітка Є множина навчальних
груп. Кожна група включає в
себе множину студентів.
варіант 5
Предметна область Автосалон
Об'єкти Виробники автомобілів,
марки
Примітка Марки автомобілів
згруповані по
виробникам. У кожного
виробника є
множина марок.
варіант 6
Предметна область Агентство новин
Об'єкти Категорії новин, Новини
Примітка Новини згруповані по
категоріям. У кожній категорії
є множина новин.
варіант 7
Предметна область Продуктовий магазин
Об'єкти Категорія продукту, Продукт
Примітка Продукти в магазині
згруповані за категоріями для кожної категорії
визначено множина
продуктів.
варіант 8
Предметна область Футбол
Об'єкти Команди, Гравці
Примітка Є множина футбольних
команд для кожної команди
визначено множина гравців.
варіант 9
Предметна область Музичний магазин
Об'єкти Виконавці, Альбоми
Примітка У музичному магазині альбоми
згруповані по виконавцям для кожного виконавця задано
множина альбомів.
варіант 10
Предметна область Аеропорт
Об'єкти Авіакомпанії, Рейси
Примітка Є множина
авіакомпаній для кожної
авіакомпанії визначені її
рейси.
варіант 11
Предметна область Файлова система
Об'єкти Папки, Файли
Примітка Є множина папок для
кожної папки визначено
множину файлів.
варіант 12
Предметна область Розклад занять
Об'єкти Дні тижня, Заняття
Примітка Є множина днів для
кожного дня визначено множина
занять.
варіант 13
Предметна область Нотатки
Об'єкти Календарні дні, Заходи
Примітка Є множина днів для
кожного дня визначено множина
заходів.
варіант 14
Предметна область відеомагазинів
Об'єкти Жанри, Фільми
Примітка Є множина жаров для
кожного жанру визначено
множина фільмів.
варіант 15
Предметна область Залізниця
Об'єкти Дороги, Станції
Примітка Є множина залізних
доріг. У відомстві кожної
дороги знаходиться множина
станцій.
варіант 16
Предметна область Склад
Об'єкти Секції, Товари
Примітка Товари на складі згруповані
по секціях для кожної секції
задано множина товарів.
варіант 17
Предметна область Кафедра університету
Об'єкти Викладачі, Дисципліни
Примітка На кафедрі є множина
викладачів для кожного
викладача задано множина
дисциплін.
варіант 18
Предметна область Програмне забезпечення
Об'єкти Виробники, Програмні
продукти
Примітка Програмні продукти
згруповані по
виробникам для кожного
виробника задано множина
продуктів.
варіант 19
Предметна область Геометрія
Об'єкти Багатокутники, Вершини
Примітка Є множина
багатокутників кожен
багатокутник складається з
довільного числа вершин.
варіант 20
Предметна область Схема метро
Об'єкти Лінії, Станції
Примітка Є множина ліній
метрополітену кожна лінія
складається з послідовності
станцій.
Додаткові матеріали:
https://drive.google.com/drive/folders/0B1dkotQCgQPvSW5vODdNcGpzeGs
http://www.mkurnosov.net/teaching/index.php/DSA/fall2015
http://dsabook.mkurnosov.net/
https://habrahabr.ru/post/128017/