Седмичен изглед
-
Теми на лекцията от Сряда 22.02:
- Въведение
- Математически понятия:
- Моножества
- Целочислено деление и модолуване
- Степен, логаритъм
- Факториел
- Прости числа - проверка дали число е просто
- Рекурсия и итерация:
- Факториел
- Числа на Фибоначи
- Преобразуване между бройни системи
- Генериране на прости числа (решето на ераторстен)
- Факторизиране на числа
- Брой на нулите на които завършва факториел
- Най-голям общ делител, най-малко общо кратно
-
Организационни неща:
За да не се получава претъпкване на зали за упражнения, се въведе следното разпределение по (факултетния номер mod 4):- фн mod 4 = 0: четвъртък 18:00 зала 306
- фн mod 4 = 1: петък 18:00 зала 306
- фн mod 4 = 2: петък 18:00 зала 314
- фн mod 4 = 3: вторник 18:00 зала 020
Вторник (7ми март) няма да има упражнение защото така или иначе не можем да ви съберем. Следващите упражнения ще бъдат по лекциите от 1-ви и 8-ми март.
Предаден материал:- Кобминаторика
- Мотивация (защо са ни и къде да ги използваме)
- Какво можем да правим с комбинаторните конфигурации:
- Изброяване
- Генериране
- Кодиране
- Итериране
- Съпоставяне между множества комбинаторни конфигурации
- Пермутации
- Изброяване
- Генериране
- Кодиране
- Итериране
- Пермутации с повторение
- Вариации
- Вариации с повторение
- Комбинации
- Комбианции с повторение
- Асимптотични сложности
- Мотивация
- Нотацията O (голямо O)
- Нотацията Θ (тита)
-
Теми от лекцията на 8.03:
- Сложности
- Асимптотични сложности - нотациите O, o, Θ, омега малко, омега голямо.
- Сложности в най-лошия случай, в средния случай и амортизирани.
- Структури от данни:
- Абстрактни
- Списък, Стек, Опашка
- Статична реализация на списък, стек и опашка.
Теми за упражненията:- Комбинаторика
- Генериране на комбинации с рекурсия.
- Генериране на разбивания на число като сума с рекурсия.
- *Използване на next_permutation и prev_permutation от стандартната C++ библиотека.
- *Кодиране на вариации.
- Структури:
- Статична реализация на дек (с цикличен масив).
- Сложност на операциите при тази реализация.
- Сложности
-
Теми от лекцията на 15.03:
- Едносвързан списък
- статично и динамично заделяне на памет - разлики, особености и синтаксис
- динамична реализация
- Дървовидни структури:
- Коренови дървета, двоични дървета, рекурсивно обхождане
- Двоични дървета за търсене
- Балансирани и идеално балансирани дървета
- Дървета на Фибоначи
- Оценка на височината на балансирано дърво относно броя на елементите
- Преглед на AVL дървета, B-дървета и червено-черни дървета - сложност и приложения
- Списък
- Динамична реализация на едносвързан списък с указатели към началото и края на списъка (на лекции направихме реализация на списък с указател в началото);
- * Динамична реализация на двусвързан списък.
- Дървета
- Пресмятане на израз, зададен с двоично дърво;
- Динамична реализация на двоични дървета за търсене;
- Динамична реализация на коренови дървета (с произволен брой наследници) с използване на списък от наследници;
- * Статична реализация на двоични или коренови дървета.
- Едносвързан списък
-
Теми от лекцията на 22.03
Хеш таблици
- Хеш таблици vs. Масиви, Списъци и Дървета. Приложения на хеш-таблиците
Амортизирано константен достъп, вмъкване, изтриване. Големи масиви от данни, емпирична информация за ключовете.
- Хеш функции и колизии. Пригодност на хеш-функциите
Класически хеш-функции: остатък (прости размери), мултипликативно хеширане, извличане на цифри, сгъване, повдигане на средата на квадрат.
Хеширане на низове: адитивно хеширане.
- Управление на колизии
Отворено хеширане. Терминологична уговорка - това, което в [1] се нарича отворено хеширане, в [2], [3], [4] и др. се нарича затворено и обратно
линейно пробване, квадратично пробване, двойно хеширане.
Затворено хеширане
допълнетелна памет, списък на препълванията.
- Операции
Вмъкване, тъсене, изтриване, управление на редици от елементи, увеличаване на капацитета.
- Литература
- Наков, П., Добриков, П., Програмиране = ++Алгоритми, стр. 165-179
- Амерал, Л., Алгоритми и структури от данни в C++, стр 161-174
- wikipedia.org
- Шишков, П., колектив, Структури от данни, “Интеграл” Добрич, 1005, стр 314-329
Сортиране
- Сортиране vs. Търсене. Устойчивост и неустойчивост на сортиранията
- Сортиране чрез пермутации. Дърво на сравненията. Теорема за ускорението
- Мехурче. Оптимизации. Клатене
- Пряка селекция
- Сортиране чрез вмъкване (алгоритъм на картоиграча)
- Алгоритъм на Шел
Теми на упражненията
- Кеш за текстов файл със записи:
- Да се реализира като хеш таблица с фиксирана големина
- Да поддържа търсене по ключ (първата дума от реда)
- Справяне с колизиите става като се изхвърля стария запис от таблицата.
- При заявка която липсва в кеша се претърсва файла.
- Ако има време:
- Добавяне на стратегия за справяне с колизии
- Изхвърляне на least recentrly used при превишаване на капацитета (т.е. този който е достъпен най-късно за последен път). (става с двусвързан списък който минава през всички записи).
-
Теми от лекцията на 29.3
- Сортиране със сравнение
- Сортиране с вмъкване
- Сортиране по Шел
- Бързо сортиране по Хоор
- Метод на "зайците" и "костенурките"
- Сортиране с пряка елиминация (идея)
- Пирамидално сортиране
- Минимална времева сложност за универсални алгоритми за сортиране
- Устойчивост
- Сортиране на масив от индекси вместо на масив с данни
- Сортиране с трансформация
- Сортиране с множество, сортиране с индекси
- Сортиране с броене, сортиране със списък от индекси
- Побитово сортиране
- Метод на бройните системи
- Сортиране с пермутация
- Паралелни сортирания - преглед
- Търсене
- Последователно търсене, търсене в сортиран списък
- Търсене с преподреждане
- Квадратично търсене
- Двоично търсене
- Фибоначиево търсене
- Интерполационно търсене
- Реализация и експериметално сравнение на:
- сортиране по Шел със сортиране по метод на "зайци и костенурки"
- бързо и пирамидално сортиране
- побитово сортиране
- * метод на бройните системи
- * устойчиво сортиране с броене и списък от индекси
- Да се установи експериметално кой метод е най-добрия заместител на сортиране на малък брой елементи при бързото сортиране и колко е оптималния брой
- Реализация и експериментално сравнение на:
- последователно търсене и търсене с преподреждане
- квадратично и двоично търсене
- двоично и интерполационно търсене
- * двоично и Фибоначиево търсене
- Сортиране със сравнение
-
Графи. Обхождане на графи
1. Крайни релации. Примерни релации (=,<, is a, ...). Графи.
Дефиниции на граф (видове), съседи, степени, индуцирани подграфи, пътища - прости, цикли, .., клики, силно и слабо свързани компоненти (класове на еквивалентност в релацията на дъгите)
2. Представяния на граф
Матрица на съседство, Списък на съседите, Компоненти на свързаност
3. Прости операции с графи
Проверка за съседност, Намиране на списъка на наследниците
4. Обхождане в широчина. Обхождане в дълбочина.
Проверка за съществуване на път, намиране на един път (BFS - най-къс, DFS-някой, печатаме стековата рамка), връщане назад, намиране на всички пътища.
Интерсни четива:1. Граф на извикванията. http://en.wikipedia.org/wiki/Callgraph
2. Абстрактни семантични графи. http://en.wikipedia.org/wiki/Abstract_semantic_graph
3. Автоматична визуализация на графи http://en.wikipedia.org/wiki/Graphviz
4. Графи при интерпретация на компютърни програми. http://en.wikipedia.org/wiki/Combinator_graph_reduction
5. Силно-свързани компоненти. http://en.wikipedia.org/wiki/Strongly_connected_component
-
Екстремален път в граф. Цикли. Потоци. Транзитивност. Топологично сортиране.
1. Екстремален път в граф
- Алгоритъм на Форд-Белман.
- Алгоритъм на Флойд. Неравенство на триъгълника. Обобщен алгоритъм на Флойд.
- Алгоритъм на Дейкстра.
2. Потоци
- Максимален поток. Алгоритъм на Форд-Фулкерсон. Неефективност на алгоритъма при избиране на произволен подобряващ път.
- Минимален поток.
3. Цикли
- Фундаментално множество цикли. Минимален цикъл през връх.
- Хамилтонови цикли и задачата за търговския пътник.
- Ойлерови цикли.
4. Транзитивност
- Транзитивно затваряне на граф. Връзка с повдигането на матрицата на съседство на степен.
5. Топологично сортиране
- Топологично сортиране
- Пълно топологично сортиране
Теми за упражненията:
- Дейкстра (реализация с масив)
- Флойд
- *Фундаментално множество цикли
- *Ойлеров цикъл
- *Хамилтонов цикъл -
Теми на лекцията от 19.04
- Транзитивно затваряне
- Алгоритъм на Уоршал - преговор, Транзитивна редукция, контрол на компании, допълване ан ациксличен граф до слабо свързан
- Достижимост и свързаност
- Свързаност - силна и слаба (преговор), компоненти на силна и слаба свързаност
- Разделящи точки, двусвързаност
- k-свързаност
- Оптимални подмножества и центрове
- Минимално покриващо дърво - МПД свойство, алгоритъм на Прим, алгоритъм на Крускал
- Независими множества (клики и антиклики)
- Доминиращи множества
- База
- Център и радиус (външен, вътрешен, вътрешно-външен), p-център
- Двойкосъчетание, максимално двойкосъчетание
- Оцветяване и планарност
- Оцветяване и хроматично число - върхово и реброво
- Планарност на графи, теорема на Куратовски, теорема за четирите цвята
- Транзитивно затваряне и редукция, контрол на компании. Да се експериментира с размяна на реда на циклите
- Реализация на алгоритъм за намиране на силно свързани компоненти
- Реализация на алгоритъм за проверка за двусвързаност
- Реализация на алгоритмите на Прим и Крускал
- * Оптимизации на алгоритмите на Прим и Крускал
- * Реализация на максимално двойкосъчетание в двуделен граф
- * Някой от алгоритмите с пълно изчерпване по избор от следните: максимално независими множества, доминиращи множества, база, хроматично число, проверка за планарност.
-
16.04.2006. Търсене с връщане назад. NP
Пример: Да се провери дали дадено естествено число има делител.
1.5. NP NP NP задачи, които са поне толкова трудни, колкото всяка друга задача в NP. NP трудна, ако всяка проверяваща задача в NP NP задача е сводима към NP NP P. Една NP NP пълна, когато всяка друга NP NPNP
Забележка: Не всяка NP NP пълна: напр. stop NP-труден, но не е NP
1.5. Stop проблем. Разпознаване дали две различни програми смятат една и съща функция.
2. Търсене с връщане. Примери
Удовлетворимост на булева функция. Оцветяване на Граф. (*)Най-дълъг прост път в цикличен граф. Разходка на коня (не е NP
3.1.
3.2. (*)Ограничено Алфа-Бета отсичане.
[1] http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP
[2] http://en.wikipedia.org/wiki/Alpha-beta_pruning
-
-
Разделяй и владей
- Въведение
- Идея - за да решим задача с размер N, я разделяме на няколко по-малки независими. Например на 2 задачи с размер N/2. После има стъпка на обединяване отговорите на подзадачите.
- Приложения
- най-лесно се вижда за паралелни задачи. Разделяме задача на няколко подзадачи и всяка от поздачаите може да се изполнява независимо на отделна машина (или процесор).
- ако подзадачите са една и съща задача, може да се пресметнат само веднъж. например бързо повдигане на степен.
- получаване на нов по-добър алгоритъм.
- Класически задачи разделяй и владей
- Сортиране чрез сливане - ние избирам как да разделим
- Quick sort - случайно се избира как да се раздели
- Намиране на K-ти по големина елемент
- подобно на quick sort.
- избор на разделящ елемент - разделяне на 5торки и избор на техните медиани и т.н. до получаване на един елемент.
- Задача за намиране на най-близки точки
- Дадени са N точки в равнината. Търсят се двете точки, най-близо една до друга
- Равнината се разделя на две части от права.
- Решават се две двойно по-малки задачи.
- Провера дали най-малкото разстояние не е между точки от подзадачите
- Тривиална проверка на всяка точка от едната подзадача със всяка точка от другата подзадача води до подобрение с константа (N^2).
- Проверките могат да се ограничат до точки различаващи се по едната координата с по-малко от най-добрия отговор на подзадачите. При подходяща имплементация може да се направи O(N*log^2(N))
- Задача за бързо умножение на числа
- Числата се разделят на части.
- Всяка от частите си я представяме като цифра и умножаваме като две "двуцифрени" числа. Умножението на цифрите са подзадачите. Може да се направи с 3 подзадачи с размер N/2, ако по-дългото число за умножение е било с дължина N.
- Въведение
-
Теми от лекцията на 17.05:
Динамично оптимиране- Въведение
- Условия за прилагане
- Свеждане към под-задачи
- Зависимост между задачите
- Граф на задачите
- Рекурсивна реализация
- Итеративна реализация
- Редуциране на използваната памет
- Задача за раницата при многократно вземане на елемент
- Еднуаргументни задачи
- Възстановяване на оптималното решение
- Задача за раницата при еднократно вземане на елемент
- Допълнително параметризиране на задачите
- Запомняне в матрица
- Предимства и недостатъци на итеративните и рекурсивните реализации
- Редуциране на заетата памет за сметка на времето
- Обобщение
- Кеширане с map
- Най-дълга нарастваща подредица (само решението с O(N*N))
- Най-дълга обща подредица на две редици
- Най-дълъг общ отрез на два масива (отрез е като подниз, но не само за низове)
- *Edit distance на два низа (колко операции insert, delete и replace са необходими за да се достигне от един низ до другия).
Явно много често се получава така че студентите не успяват да разберат нещата в упражненията. За това моля и студентите и преподавателите да проявят малко инициатива за решаване на този проблем:- Студентите да питат повече конструктувни въпроси и да показват когато нещата не са им ясни.
- Преподавателите да следят по-често дали студентите разбират това което се говори, като задават подходящи въпроси.
- Въведение
-
Празници
-
Евристични и вероятностни алгоритми
Алчни алгоритми
- Египетски дроби
- Максимално съчетание на дейности
- Минимално оцветяване на граф и дърво
- Дробна задача за раницата
- Задача за магнитната лента
- Разходка на коня. Хеперкуб. Код на Грей
Търсене с налучкване
*Алгоритми Монте Карло и Лас Вегас
p- правилност на алгоритъм.
1. Проверка дали дадено число е просто
2. Числени алгоритми с приближение
Изчисляване на Pi. Изчисляване на определен интеграл от функция (Лице, заградено от крива).
Hill-climbing. Симулирано отгряване. Генетични алгоритми
Рекомбинация, мутация, естествен подбор. Техники: увеличено разнообразие на популацията, хипермутация, случайни имигранти, избор на елита.
Внимание! Някои от темите в тази секция не са засегнати в официалната литература по курса. Желателно е при подготовката си за изпита да прочетете, без да се задълбочавате много:
* Върхово покритие на граф
Забележка. Темите, означени със *, не са разказани на лекцията