AiSD-2015

Ważne

Egzamin: 18.06.2015 11:00-14:00 w C-13 sala 1.31

Egzamin poprawkowy: 01.07.2015 11:00-14:00 w C-13 sala 1.31

Osoby o następujących numerach indeksów są zwolnione z egzaminu z oceną celującą, bo uzyskały przynajmniej 150% normy na ćwiczeniach i (prawie) 100% na laboratoriach. Proszę się upewnić dwa razy:

1. 013208786

2. 013208815

3. 013208727

4. 013211584

5. 013208800

6. 012204389

7. 013208749

8. 013208761

9. 013208745

10. 013208752

11. 013208808

Uwaga

Wykład w dniu 5 czerwca nie odbędzie się i zostanie odrobiony 19 czerwca w godzinach 9:15 - 11:00 w sali D1.312B.

Serwer testowy

Zadania laboratoryjne można (ale nie trzeba) testować na serwerze z testami.

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)

• Zaliczenie egzaminu

• • 1. termin egzaminu: wkrótce

    2. termin egzaminu poprawkowego: wkrótce

    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

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 BST, zbalansowane - AVL i czerwono-czarne

  8. Skip-listy, quick-sort

  9. Wybór k-tego elementu - losowy i deterministyczny, sortowania liniowe - przez zliczanie, kubełkowe, radix-sort, tablice hashujące

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

  11. Algorytmy aproksymacyjne

  12. Algorytmy online

Lista zagadnień na egzamin (ma pomóc, ale nie gwarantuję, że jest pełna):

Złożoność - co oznaczają dolne i górne ograniczenia, złożoność pamięciowa, złożoność obliczeniowa, analiza najgorszego przypadku, dolne ograniczenie na sortowanie w modelu z porównaniami i w modelu sortowania na liczbach, sortowanie przez wstawianie, sortowanie przez wybór, sortowanie przez scalanie, sortowanie kopcowe, sortowanie bąbelkowe, sortowanie szybkie, co to jest sortowanie stabilne, rozwiązywanie podstawowych równań rekurencyjnych (znanych z przykładów analizy dziel i zwyciężaj), działania na kopcu, budowa kopca z tablicy, przechodzenie grafu wszerz, przechodzenie grafu w głąb, spójne składowe, silnie spójne składowe, drzewa, drzewa zbalansowane i operacje rotacji, działania modulo liczba pierwsza, ciąg Fibonacciego, wrzucanie kul do pojemników i wpływ na hashowanie.

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

    1. Dodatkowe zadania z list dra Marcina Kika (tutaj link), jeśli skończą się zadania na poprzednich listach: 2a.31, 2b.2, 2b.13, 2b.18, 3a.12, 4a.5, 6.7, 6.17, 7.6

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.

  3. Wydawanie reszty przy ograniczonej i nieograniczonej liczbie monet danego typu. Ściślejsze wersje: mon1 i mon2.

1. Oprogramuj drzewo zbalansowane: AVL lub czerwono-czarne. Zadanie lepsze drzewo.

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

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)

EGZAMIN - wyniki

Wstępne wyniki w arkuszu poniżej. Zaraz tu dopiszę zmiany zasad (wyłącznie na Państwa korzyść). Jeszcze może przemnożę punkty innych sprawdzających.

• 1. Próg zaliczenia testu zmieniony na 50%.

  2. Próg zaliczenia egzaminu zmieniony na 1 pkt. Procenty są liczone od 2 punktów.

  3. W kolumnie "Zdane" jest wartość logiczna - czy przekroczone są wszystkie progi z ćwiczeń, laboratorium, testu i egzaminu.

  4. W kolumnie "Pkt ocen. autom." jest obliczona wartość 25% ćw + 25% lab + 10% testu + 40% egzaminu

  5. W kolumnie "Ocena" jest proponowana ocena (wszystko powyżej 5.0 to cel), zgodnie z wzorem z początku semestru, ale jest zaokrąglanie zamiast podłogi (przy obcinaniu do pełnych dziesiątków procent).

  6. Na poprawce można pisać sam test lub samą część zadaniową lub obie części.

Jeszcze złagodziłem - 0.3 zamiast 0.1 za poprawne ograniczenie dolne na sortowanie bez dowodu i próg zmniejszony do 0.8. Więcej nie zmniejszę.

UWAGA: dodałem 0.2 punkta tym osobom, które w drugim zadaniu tworzyły dodatkową listę i na koniec podstawiały ją pod listę A. Dodałem tym, których zadanie poza tym było poprawne lub prawie poprawne.

Na razie są surowe dane z poprawy. Progi: 10 pkt dla testu i 2 pkt dla części zadaniowej.

Jeśli ktoś poprawiał tylko test, punkty i ocena są liczone zgodnie z poprzednimi progami i wzorem.

Jeśli ktoś poprawiał egzamin, progiem jest 2 punkty, a maksimum to 4 punkty i ocena liczona jest z wzorem podanym na początku semestru i wciąż widniejącym na stronie.