разписание

1. Увод в предметната област на курса, 
   свързване с други избираеми и задължителни курсове,
   ревю на темите, които ще разгледаме.

2. Увод в алгоритмите.

- НОД (алгоритъм на Евклид с деление)
- просто число
- простите числа по-малки от N (решето на Ератостен)
- прости числа в интервала [a,b]
- комбинаторика : генериране на пермутации/вариации
-- пресмятане на  
   (n)
   ( ) = ? 	
   (k)		
   чрез триъгълник на Паскал
- разбиване на естествено число на всички възможни суми

3. Увод в структурите от данни. Динамичен масив.

- сложност на операциите.
- нотацията голямо О. (подробна теоритична постановка се разглежда в рамките на курса ДАА')
- бързина на растежа на някои от познатите функции.
- темплейтни класове контейнери
- реализация на динамичен масив (vector)
- итератор
- сложност на операциите + търсене

4. Свързан списък.

- разновидности - едно/двусвързан, цикличен
- реализация + итератор
- сравнение с динамичния масив

5. Стек / Опашка.

- представяне като адаптори върху динамичен масив или свързан списък
- приложения
- стек + статична/последователна реализация
- стек динамична реализация
- опашка динамична + статична/последователна реализация
- дек, приоритетна опашка - обща идея

6. Сортиране / търсене.

- концепции при сортировките 
	(стабилност, сравнения, размени, адаптивност към полусортирани данни)
	
- реализация на простите сортировки със сравнения:
	Метод на мехурчето, пряка селекция, сортиране чрез вмъкване

- алгоритми за търсене:
	последователно търсене, търсене със стъпка, двойчно търсене


7. Сортиране /част втора/.

- сложни сортировки + техните реализации:
	"бързо" сортиране, сортиране чрез сливане, "пирамидално" сортиране

- сортировки приложими върху свързан списък + реализация
	
- сортировки без сравнения + техните реализации :
	сортиране чрез броене на честотите, сортиране в "кофи", сортиране по "разряди"
	
- кои сортировки можем да използваме като "частични"

* след като сме научили "пирамидалното" сортиране, можем да имплментираме
  двоична приамида и приоритетна опашка.
* идеята за паралелна реализация на сортировките. 

8. Дървета (в темите за дървета и графи ще са ни полезни теоритичните познания от ДС').

- обща концепция, рекурсивни дефиниции, приложения

- двоично дърво за претърсване + имплементация:
	включване, изключване, търсене, обхождане,
	намиране на дълбочина, намиране броя на листата 
	
- дървета с прозволен брой разклонения

*9. Дървета /част втора/.

- префиксни дървета

- *балансирани/идеално балансирани дървета:
-- дефиниции, примери : 
	
	- Дърво на Фибоначи, пирамида за heap sort
	
	- 2-3-4 дървета - идея
	
	- червено - черно дърво - приложения +
	  имплементация на ляво - водещо червено - черно дърво 
		
	- AVL дърво - идея
	
	- "Бе" дървета обща идея, приложения
	
10. Хеш функции, хеш таблици.

- концепция + сложност на операциите

- хешираща функция, класически примери :
	остатък по модул размера на масива,
	сума ASCII кодовете + размера на стринга
	
- справяне с колизии :
	затворено - чрез линейна стъпка,
				чрез квадратична стъпка,
				чрез двойно хеширане
				
	отворено - чрез списък на препълванията

- примерни реализации

- известни хеширащи функции използвани в практиката:
   CRC, MD, SHA

11. Графи.

- представяне в паметта:
   списък от ребрата, матрица на съседство(на тегловност),
   списъци на съседите
   
- разлики, приложения

- търсене на път в граф:
	имплементация на "търсене в ширина" (BFS)/"търсене в дълбочина"(DFS) в "лабиринт",     
	имплементация на BFS/DFS обобщено 		

12. Графи /част втора/.
	
- алгоритми за построяване на МПД (минимално покриващо дърво):
	Прим и Крускал + имплементации  

13. Графи /част трета/.

-алгоритми за разстояния в граф:
	-- в нетегловен граф: BFS
	-- в тегловен граф:
	
		Дийкстра -> най-къс път от върха s до всички останали 
				/без отрицателни тежести/
				
		Флойд - Варшал -> най - къс път между всяка двойка върхове     
		
		Белман - Форд -> най-къс път от върха s до всички останали
						/по-бавен от Дийкстра, но може и отрицателни тегла/   
		
*14. Класове алгоритми и примери.

- "Търсене с връщане":
  -- задачата за разходката на коня
  -- задачата за разполагане на 8 дами на шахматна дъска
  -- метод на разклоненията и границите ( връзка с ИО')

- "Разделяй и владей": 
  -- вече сме разгледали - сортиращите схеми ("бързо сортиране", "сортиране чрез сливане")
  -- бързо повдигане на степен
  -- задачата за Ханойските кули

- "Динамичното оптимиране":
  -- вече сме разгледали - Прим, Крускал, Дийкстра
  -- задачата за братската подялба
  -- оптимизационни задачи от ИО'

  
- "Евристични и алчни алгоритми":
  -- вече сме разгледали - Прим и Крускал (алчни алгоритми)
  -- търсене с налучкване
  -- програма за лекции  
  -- модификации на идеите зад BFS & DSF:
     (разглеждат се подробно в курса по ИИ')
	 Depth bound search, Iterative deepening [основа на останалите]
     Best first search, Beam search, Hill climbing search, A* [чрез евристики]
				   
- "Шифриране"
			   
- "Компресиране": 
  -- кодиране по Хъфман (материал от лекциите по СДП')

15. Обобщение. Въпроси. Обсъждане темите за проекти. Насоки за добрите практики.


###################################--------------ОБЩА ИНФОРМАЦИЯ--------------###################################

Числата от 1 до 15 би трябвало да коренспондират с поредната седмица от началото на семестъра,
но са възможни динамични промени в програмата.

Темите са свързани с представяне на различни класове алгоритми и
изискват допълнително четене и писане на примерни задачи извън рамките на практикума.

По време на целия курс се разглежа и използването на STL стандартините контейнери/алгоритми.
Повечето примери са имплементирани, използвайки C++ до C++14, но
някои от примерите са написани на чисто C, за да могат студентите да свикват и с него.

Всички абривиатури отбелязани с ' са съкращения на наименованията на някои предмети, водени във ФМИ' :
ИО'  - Изследване на операциите /запознава слушащите курса с основните линейно-оптимизациони задачи/
ДС'  - Дискретни структури /цели опознаване на основните похвати за общуване на математически език / 
ЕАИ' - Езици автомати и изчислимост /показва теорията зад автоматите, регулярните изрази и дефинира решимост по Тюринг/
ДАА' - Дизайн и анализ на алгоритми /практическата част на всичко научено от ДС'/
ИИ'  - Изкуствен интелект /из темите : евристични и генетични алгоритми, невронни мрежи /
ФМИ' - Факултет по математика и информатика към СУ'
СУ'  - Софийски университет "Климент Охридски"

#ако не е дефинирано ВАЖНО
#дефинираме ВАЖНО като !!!

Всички теми отбелязани с * са допълнения към основния курс,
изцяло по усмотрение на преподавателите - Иван Филипов, Николай Бабулков и Василена Пейчева.

С теоритичната им част ще можете да се запознаете в рамките на някои
от курсовете - ДАА', ДС', ЕАИ', ИО', ИИ'.

#край на ако // отнасящо се за дефиницията на ВАЖНО !!!