Схема на раздела

◄28 март - 3 април
►11 април - 17 април

  • КН, групи 5 и 6 - Продължение  на BFS, Минимални пътища в графи - алгоритъм на Dijkstra

    Задачи, които решихме:

    1) 2015 (летен) Контролно 2:

    Още една редица - Задачата се решава с BFS (макар и малко странно да изглежда отначало). Първоначално слагаме в опашката само числото А. След това на всеки ход вземаме един елемент от опашката, прилагаме върху него двете операции, описани в условието, и новополучените два елемента ги слагаме в опашката, ако още не са били слагани в нея. В момента, в който от опашката извадим число равно на B, отговорът на задачата е броят нива + 1, които сме обходили с BFS-то.

    2) 2015 Домашно 5:

    Пешо - Задачата се решава с директно прилагане на Dijkstra. Пускаме Dijkstra от всяка болница и гледаме всеки път каква е сумата от всички dist[i], за които i не е болница. От всички суми, минималната е нашият отговор.

    Задачи за упражнение:

    1) 2015 Домашно 5:

    Cheating

    2) 2015 (летен) Контролно 2: 

    Пътища

    3) Домашно Дейкстра:

    Екскурзия

    4) 2014 Домашно Dijkstra:

    Превъртял

    • Dijkstra Файл
    • КН 1-2 група

      Разгредаме начините за представяне на граф в паметта:

      • матрица на съседство
      • списък на съседите
      • списък на ребрата

      За всяко от тях видяхме каква е сложността за проверка дали има ребро между два върха и обхождане на всички съседи между на връх:

      _

      		има ли ребро (u,v) обхождане на съседите на връх u памет
      матрица на съседствоO(1) O(N) N*N
      списък на съседите O(logD) O(D) N*D
      списък на ребрата
      		 O(logE) O(max(logE, D)) E

      където N е броят на върховете, D е най-голямата степен на ребро и E и броят на ребрата.

      Разгледахме алгоритмите BFS, DFS и Dijsktra и решихме няколко задачи от http://judge.openfmi.net:9280/practice/open_contest?contest_id=39

      • Школа
      • Диаметър

       

◄28 март - 3 април
►11 април - 17 април