Algorytmy i struktury danych

Wyniki egzaminu

Uaktualniłem wyniki 5 lipca. 7 i 9 lipca mam konsultacje w godzinach 7:30 - 8:30.

W arkuszu są również wyniki z ćwiczeń i laboratoriów.

• • w części zadaniowej w pierwszym terminie 3 punkty uznawałem za 100%

  • w drugim terminie 100% to 4 zadania czyli 4 punkty, ale zaliczenie w praktyce jest od 1.5+epsilon punkta

  • w części testowej obniżyłem próg do 50%

  • każdy może poprawiać część zadaniową, ale liczy się druga próba, nie max

  • część testową poprawiają osoby poniżej progu

  • w arkuszu konieczność poprawiania jest na czerwono

UWAGI dodane w przeddzień egzaminu poprawkowego

• • część zadaniową wszyscy dostają o 9:00

  • osoby poprawiające część testową, dostają ją wraz z częścią zadaniową

  • nie wypuszczam nikogo przed godziną 10:00

  • nie wpuszczam nikogo po wyjściu pierwszej osoby

Zasady zaliczania

• Zaliczenie ćwiczeń (kwestie nieustalone tu ustala prowadzący ćwiczenia):

  • 1. na koniec semestru, prowadzący ćwiczenia przekazuje prowadzącemu wykład punktację w zakresie 0 - 100%

    2. zadania ukazują się co tydzień, w piątki po wykładzie

    3. na ćwiczeniach mogą (powinny) się odbywać kartkówki z materiału z wszystkich poprzednich ćwiczeń

• Zaliczenie laboratorium (kwestie nieustalone tu ustala prowadzący laboratorium):

• • 1. na koniec semestru, prowadzący laboratorium przekazuje prowadzącemu wykład punktację w zakresie 0 - 100%

    2. zadania ukazują się w piątki po wykładzie, przewidziane są cztery większe programy

    3. zadania należy oprogramować w języku C (nie C++ ani żadnym innym wariancie obiektowym)

    4. nieoficjalnym ułatwieniem jest serwer fragles, na którym będą się ukazywać zadania i na którym można wstępnie przetestować swoje rozwiązania; będą się tam również ukazywać zadania pomocnicze - zachęcamy do ich oprogramowania (przykład: zadania kopiec i union-find jako pomoc do zadania MST)

• Zaliczenie egzaminu

• • 1. termin egzaminu: 20 czerwca 9:00 - 12:00, C1.205

    2. termin egzaminu poprawkowego: 1 lipca 9:00 - 12:00, A1.329

    3. egzamin składa się z dwóch części:

       1. 50 minut test z wiedzy

       2. 1h:50min zadań takich jak na ćwiczeniach

• Progi do zaliczenia:

• • 1. ćwiczenia na przynajmniej 50%

    2. laboratorium na przynajmniej 50%

    3. egzamin - próg części testowej: 70%, próg części zadaniowej: 50%

• Składniki oceny końcowej:

• • 1. 25%: punkty z ćwiczeń

    2. 25%: punkty z laboratorium

    3. 10%: punkty z testowej części egzaminu

    4. 40%: punkty z zadaniowej części egzaminu

• Skala ocen:

• • • 10% - 50%: ndst

    • 50% - 60%: dst

    • 60% - 70%: dst+

    • 70% - 80%: db

    • 80% - 90%: db+

    • 90% - 100%: bdb

Ocena celująca

Warunkiem wstępnym jest zasłużenie na ocenę bardzo dobrą. W trakcie semestru będą się pojawiać zadania: niektóre do zaprogramowania, niektóre do przemyślenia.

• 1. Należy oprogramować zadanie Największy prostokąt, a także przemyśleć uogólnienie, w którym szukamy trójkąta o jak największym polu i podstawie na poziomie ziemi.

Zagadnienia omówione na wykładzie:

• 1. Stabilne skojarzenie w grafie dwudzielnym

  2. Złożoność obliczeniowa, kopiec

  3. Algorytmy grafowe: BFS, DFS, spójne składowe, silnie spójne składowe

  4. Algorytmy zachłanne

  5. Dziel i rządź

  6. Programowanie dynamiczne

  7. Drzewa zbalansowane - czerwono-czarne i AVL

  8. Skip-listy, Quicksort, wybór k-tego elementu

  9. Sortowanie w czasie liniowym: kubełkowe, przez zliczanie; tablise hashujące

  10. Teoria liczb: sito Eratostenesa, algorytm Euklidesa, testowanie pierwszości

  11. Analiza zamortyzowana

  12. Algorytmy tekstowe

  13. Geometria obliczeniowa

  14. Algorytmy on-line

  15. Algorytmy aproksymacyjne

Zadania na ćwiczenia:

1. Lista 1

2. Lista 2

3. Lista 3

4. Lista 4

5. Lista 5

6. Lista 6

7. Lista 7

8. Lista 8

9. Lista 9

10. Lista 10

11. Lista 11

Zadania na laboratorium:

• 1. Zadanie 1

  2. Należy rozwiązać na dwa sposoby (algorytm Kruskala, algorytm Prima) i użyć poprawnie struktur kopca oraz zbiorów rozłącznych. W zadaniach na nieoficjalnym serwerze fragles.im.pwr.wroc.pl, zadanie nazywa się "Minimalne drzewo rozpinające".

  3. Wydawanie reszty przy ograniczonej i nieograniczonej liczbie monet danego typu. Zadania mon1 i mon2 na serwerze fragles.

  4. Oprogramuj drzewo zbalansowane: AVL lub czerwono-czarne. Zadanie na fraglesie: Lepsze drzewo.

  5. Proste zadania z list ćwiczeniowych: Cykle w grafie skierowanym, Szeregowanie zadań, Znaczne inwersje, Najdłuższy podciąg rosnący

A propos plagiatów

Jak Państwo zauważyliście, plagiaty i bardzo duże podobieństwa kodów potrafimy wykrywać, ale tym razem nie będziemy wyciągać konsekwencji.

Literatura

• 1. "Algorithm Design", Jon Kleinberg, Eva Tardos

Literatura uzupełniająca

• 1. "Algorithms", Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani (wydane również przez PWN)

  2. "Introduction to Algorithms", Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (wydane również przez WNT i PWN)