Седмичен изглед
-
Конспект за практикума по ДАА
1. Автоматични рефери и състезателно програмиране.
2. Сортиране за време Θ(n2) — метод на мехурчето,
сортиране чрез пряк избор, сортиране чрез вмъкване.
Сортиране чрез броене.3. Сортиране за време Θ(n log n) — бързо сортиране,
пирамидално сортиране, сортиране чрез сливане.4. Двоично търсене.
5. Непретеглени графи. Основни алгоритмични схеми:
обхождане в дълбочина и обхождане в ширина.
Топологично сортиране.6. Претеглени графи. Алгоритми на Дейкстра,
на Флойд—Уоршал и на Белман—Форд.7. Минимално покриващо дърво. Алгоритми за построяване:
алгоритъм на Прим—Ярник и алгоритъм на Крускал.8. Динамично програмиране.
Курсове от минали години:
— 2012 / 2013 уч. г., зимен семестър;
— 2016 / 2017 уч. г., летен семестър;
— 2017 / 2018 уч. г., зимен семестър;
— 2017 / 2018 уч. г., летен семестър.Схема за оценяване на практикума по ДАА
През семестъра се дават N домашни (между 5 и 10 вкл.), носещи общо 50 точки, т.е. всяко домашно носи по 50 / N точки.
Има две контролни с по три задачи и едно контролно с четири задачи. Това прави общо десет задачи, всяка от които носи по 25 точки, така че максимумът е 250 точки.
Контролните и домашните носят общо 300 точки.
Ще можете да съберете дори повече от 300 точки с помощта на специалните домашни и бонуса за решени задачи.
През семестъра ще има две специални домашни, като всяка тяхна задача ще носи по най-много 20 точки при пълно решение. Тези задачи ще бъдат по-трудни и евентуално ще съдържат учебен материал, който не е взет на упражнения, т.е. ще трябва евентуално да положите повече усилия, за да ги решите.Ще има и бонус точки за петимата студенти, решили най-много задачи в "Арената" през семестъра.
Точки на задача се получават пропорционално на броя тестове, на които вашата програма изкарва верен резултат, т.е. не е задължително да решите една задача напълно, за да изкарате точки от нея. Няма да бъдете наказвани за изпратени грешни програми и ще се взима най-доброто ваше решение, а не последното.
Контролните ще бъдат по толкова астрономични часа, колкото е броят на задачите. Срокът за всяко домашно ще бъде не по-кратък от две седмици.
Скала за оценките:
[90т., 104т.] - 3.00 [105т., 119т.] - 3.50 [120т., 134т.] - 4.00 [135т., 149т.] - 4.50 [150т., 164т.] - 5.00 [165т., 179т.] - 5.50 [180т., ∞ ) - 6.00
-
- https://judge.openfmi.net/practice/get_problem_description?contest_id=32&problem_id
=99
- https://judge.openfmi.net/practice/get_problem_description?contest_id=32&problem_id
=100
- https://judge.openfmi.net/practice/get_problem_description?contest_id=8&problem_id=22 — тази задача няма да може да се реши с някое от бавните сортирания. Ще я решим за 100 точки с някое от бързите сортирания. Задачата е добра от гледна точка на това, че можете на практика да видите кой алгоритъм от кой е по-бърз и кой колко точки ще ви донесе.
- http://informatika.bg/problems/DAA.2011.Trosver/Trosver.pdf — понеже няма къде да си тествате решението на тази задача, можете да пратите решението си като решение на следващата задача, която е същата, но с малко по-различно условие, ограничения и вход: http://acm.timus.ru/problem.aspx?space=1&num=1290
- https://judge.openfmi.net/practice/get_problem_description?contest_id=3&problem_id=11
- https://judge.openfmi.net/practice/get_problem_description?contest_id=32&problem_id
=99
-
Задачи за бързи сортировки:
1) https://judge.openfmi.net/practice/open_contest?contest_id=33
· Drinking Game — приложение на HeapSort. Можете да решите задачата за 100 точки и с използването на приоритетна опашка.· PermSwap — намиране на броя на инверсиите в масив — приложение на MergeSort.
· Бързо сортиране — задачата се решава с използването на някой от бързите алгоритми (ако прецените, можете да се опитате да я решите и с бавните алгоритми за сортиране, за да видите колко по-бавни са те при голям вход).
2) https://judge.openfmi.net/practice/open_contest?contest_id=83 — задача, подобна на задачата за шоколадите от предния път. Разликата е, че тук трябва да използвате някое от бързите сортирания.
3) https://judge.openfmi.net/practice/open_contest?contest_id=72 — График (*).
4) https://judge.openfmi.net/practice/get_problem_description?contest_id=40&problem_id=124
5) https://judge.openfmi.net/practice/get_problem_description?contest_id=98&problem_id=314
6) https://judge.openfmi.net/practice/open_contest?contest_id=85 — Evil (за упражнение вкъщи).
-
Задачи за двоично и троично търсене:
1) Намерете ∛n с точност до третия знак след десетичната запетая, където n се въвежда от клавиатурата.
2) https://judge.openfmi.net/practice/open_contest?contest_id=77 — E.Sysadmin.
3) https://judge.openfmi.net/practice/open_contest?contest_id=85 — Sequence.
4) https://judge.openfmi.net/practice/open_contest?contest_id=37 — всички задачи.
5) https://judge.openfmi.net/practice/open_contest?contest_id=84 — Elliot.
6) https://judge.openfmi.net/practice/open_contest?contest_id=10 — Алкохолици.
7) https://judge.openfmi.net/practice/open_contest?contest_id=3 — Exam.
8) https://judge.openfmi.net/practice/open_contest?contest_id=98 — Ферма.
Материали за троично търсене:
- https://www.hackerearth.com/practice/algorithms/searching/ternary-search/tutorial/
- https://en.wikipedia.org/wiki/Unimodality#Unimodal_function
- https://en.wikipedia.org/wiki/Ternary_search
- https://www.hackerearth.com/practice/algorithms/searching/ternary-search/tutorial/
-
Обхождане в дълбочина: Школа.
Топологично сортиране: Meteorite.
Обхождане в ширина: Ябълки, Game.
Задачи:
-
(авторово решение на задачата "Школа" —
примерна реализация на търсене в дълбочина)
-
-
Алгоритъм на Дейкстра:
Пътуване, Cheating (може и с BFS),
Sober, Атака, Денивелация,
Lovers, Екскурзия (иска досещане).Още задачи:
- Състезание № 82 — Пътища.
- Състезание № 76 — всичко.
- Състезание № 60 — Превъртял.
- Състезание № 102 — Railways.
- Състезание № 82 — Пътища.
-
Графи:
http://judge.openfmi.net/practice/open_contest?contest_id=79 – Реконструкция
http://judge.openfmi.net/practice/open_contest?contest_id=88 – Хипертелепорт
http://judge.openfmi.net/practice/open_contest?contest_id=86 – Поддръжка
ДП:
http://judge.openfmi.net/practice/open_contest?contest_id=62 – Первази
ДАА - контролно 2 (есен 2012): Паркетиране
2012 Упражнение - Динамични: Всички задачи
2011 ДАА - Контролно 2 - Разправия (Известна още като "Братска подялба")
2015 ДАА Тренировка 2 - D.Fuel
-
-
-
-
-
-
-
-
-