Algorithms for Data Science

obowiązkowe

Celem kursu jest nauka podstawowych algorytmów i struktur danych. Każdy temat będzie omawiany zarówno teoretycznie jak i aplikacyjnie (w popularnych językach programowania, takich jak C++ czy Python).

Ocena końcowa zależna jest od wyników uzyskanych w zadaniach programistycznych, kartkówkach i pisemnym egzaminie.

1. Wprowadzenie

-- Języki programowania, których będziemy używać

-- Jak samemu się uczyć algorytmiki

-- Przykładowy algorytm

-- Prawidłowość algorytmów: warunek stopu i niezmienniki pętli

2. Podstawowe definicje

-- Model obliczeniowy: maszyna RAM

-- Definicja problemu obliczeniowego

-- Złożoność algorytmiczna i notacja asymptotyczna

3. Analiza złożoności algorytmów

4. Metoda dziel i zwyciężaj

-- Twierdzenie o rekurencji uniwersalnej

5. Klasyczne algorytmy sortowania

-- Struktura danych: kopiec

6. Programowanie dynamiczne

7. Słowniki

-- Tablice i listy

-- Zrównoważone drzewa binarne

-- Tablice haszujące

8. Grafy

-- Definicje i zastosowania

-- Przeszukiwanie wstecz i w głąb

-- Minimalne drzewo rozpinające

-- Algorytm Dijkstry

-- Algorytm Floyda-Warshalla

-- Algorytm Kruskala

-- Struktury danych: stos, kolejka, kolejka priorytetowa

-- Struktura danych: find&union

9. Trudne problemy

-- Najważniejsze klasy złożoności: P, NP

-- Redukcje i NP-trudność

-- Przykłady problemów NP-trudnych

-- Rozwiązywanie trudnych problemów

Szacunkowy nakład pracy studenta:

Typ aktywności K (kontaktowe) S (samodzielne)

wykład (zajęcia) 22,5 0

ćwiczenia (zajęcia) 12 0

egzamin 2 0

konsultacje 2,5 0

przerabianie zadań z ćwiczeń 0 25

praca z materiałem do wykładu 0 20

przygotowanie do kolokwium 0 18

przygotowanie do egzaminu 0 18

rozwiązywanie zadań programistycznych 0 30

Razem 39 111 = 150

Polecana:

- Cormen T.H, Leiserson Ch.E, Rivest R.L, Stein C. Introduction to algorithms. The MIT Press.

- Banachowski L., Diks K., Rytter W. Algorytmy i struktury danych. WNT, 2011.

Dzięki kursowi, student:

– Zna podstawy teorii algorytmów i struktury danych

– Wie, jak zaprojektować własne algorytmy, dowieść ich poprawność i oszacować ich złożoność obliczeniową

– Rozumie istotność korzystania z właściwych struktur danych i wydajnych algorytmów w swojej pracy

– Jest w stanie zastosować wiedzę w praktyce, wybierając najbardziej odpowiednie struktury danych i metody algorytmiczne dla danych sytuacji, i używając ich we własnych projektach.

Ocena końcowa jest ważoną średnią ocen uzyskanych z egzaminu końcowego, zadań programistycznych oraz kartkówek. Żeby zaliczyć przedmiot (egzamin i ćwiczenia) należy uzyskać co najmniej połowę punktów z zadań programistycznych i kartkówek oraz połowę punktów z egzaminu.

Obecność na ćwiczeniach jest obowiązkowa przy czym dwie usprawiedliwione nieobecności są dozwolone.