Algorithms for Data Science 2400-DS1AL
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
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
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.
Kryteria oceniania
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.
Literatura
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.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: