Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych
Koordynator przedmiotu:
Rajmund Kożuszek
Status przedmiotu:
Fakultatywny ograniczonego wyboru
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne - podstawowe
Kod przedmiotu:
AISDI
Semestr nominalny:
1 / rok ak. 2021/2022
Liczba punktów ECTS:
6
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. liczba godzin kontaktowych – 94 godz., w tym  obecność na wykładach: 60 godz.,  obecność na zajęciach laboratoryjnych: 30 godz.,  udział w konsultacjach związanych z realizacją przedmiotu: 4 godz. 2. praca własna studenta – 76 godz., w tym  analiza literatury i materiałów wykładowych związana z przygotowaniem do kolejnych wykładów, wykonanie wskazanych zadań przykładowych: 20 godz.  wykonanie ćwiczeń przygotowawczych do laboratorium: 30 godz.  wykonanie zadania projektowego: 16 godz.  przygotowanie do egzaminu: 10 godz. Łączny nakład pracy studenta wynosi 170 godz., co odpowiada 6 pkt. ECTS.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
3.5 pkt. ECTS, co odpowiada 94 godz. kontaktowym.
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
3 pkt. ECTS, co odpowiada 60 + 16 = 76 godz. realizacji ćwiczeń
Formy zajęć i ich wymiar w semestrze:
  • Wykład60h
  • Ćwiczenia0h
  • Laboratorium30h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Matematyka konkretna 1 (MAKO1), Podstawy programowania i informatyki (PIPR)
Limit liczby studentów:
150
Cel przedmiotu:
Celem przedmiotu jest przedstawienie najważniejszych struktur danych i algorytmów oraz pokazanie sposobów ich implementacji we współczesnych językach programowania. Wyjaśnione zostaną zagadnienia dotyczące oceny złożoności czasowej i pamięciowej algorytmów. Treść przedmiotu pozwoli studentom na dobór właściwej struktury danych i algorytmu do rozwiązywanego problemu programistycznego, a następnie stworzenie ich poprawnej implementacji. W ramach przedmiotu omówione zostaną również zagadnienia dotyczące definiowania języków formalnych. Przedstawione zostaną podstawowe klasy gramatyk formalnych oraz odpowiadające im rodzaje automatów. Wybrane wykłady będą prowadzone w formie dyskusji.
Treści kształcenia:
WYKŁADY: 1. Wprowadzenie (4 godz.) Informacje o przedmiocie. Regulamin przedmiotu. Liniowe struktury danych: tablica, lista jedno i dwukierunkowa (powtórzenie). Złożoność obliczeniowa - wprowadzenie. 2. Algorytmy sortowania (8 godz.) Sortowanie przez wybieranie i przez wstawianie (powtórzenie). Sortowanie Shella, sortowanie szybkie, sortowanie przez scalanie, sortowanie przez kopcowanie. Dolne ograniczenie dla problemu sortowania. Sortowanie kubełkowe. 3. Wyszukiwanie i funkcja mieszająca (4 godz.) Wyszukiwanie liniowe, binarne, interpolacyjne, z podziałem Fibonacciego. Tworzenie funkcji skrótu, tablica mieszająca, filtr Blooma, algorytm MinHash. 4. Drzewa (6 godz.) Drzewa BST, drzewa AVL, B-drzewa, drzewa splay, drzewa czerwono-czarne. 5. Algorytmy tekstowe (4 godz.) Wyszukiwanie wzorca, algorytm Rabina-Karpa, algorytm Knutha-Morrisa-Pratta, drzewa suffiksowe, indeks odwrócony. 6. Algorytmy równoległe (4 godz.) Podstawowe problemy i metody zrównoleglania algorytmów, równoległe strumienie, równoległe “Dziel i rządź”, metoda map-reduce. 7. Grafy i algorytmy grafowe (14 godz.) Rodzaje grafów, reprezentacja grafów, przeszukiwanie wszerz i w głąb, sortowanie topologiczne, składowe spójne, najkrótsze ścieżki (alg. A*, Dijkstry, Bellmana-Forda, Floyda-Warshalla), minimalne drzewa rozpinające (alg. Kruskala, Prima), redukcja i domknięcie przechodnie, sieci przepływowe (alg. Forda-Fulkersona, Edmondsa-Karpa), skojarzenia (alg. Hopcrofta-Karpa, Edmondsa), cykl Eulera i cykl Hamiltona, klika, pokrycie wierzchołkowe, kolorowanie, izomorfizm. 8. Lingwistyka (6 godz.) Słowo, język, operacje na słowach i językach, składnia, semantyka, gramatyka, automat, klasyfikacja Chomskiego, języki regularne i automaty skończone: gramatyki regularne, analiza i synteza automatów, grafy przejść, determinizm i niedeterminizm, wyrażenia regularne, języki bezkontekstowe i automaty ze stosem. 9. Złożoność obliczeniowa (6 godz.) Problem obliczeniowy, model obliczeniowy, złożoność obliczeniowa (rodzaje złożoności), asymptotyka, notacja dużego O, Omegi, Thety oraz małego o, omegi, hierarchia klas złożoności (wynikająca z asymptotyki), inne klasy złożoności, P, NP, NP-Hard, NP-Complete (problem P=NP), coNP, PP, BPP, RP, coRP, ZPP, NC, BQP, przykład: problem SAT, maszyna Turinga, twierdzenie Cooka-Levina, hipoteza Churcha-Turinga, komputer kwantowy. 10. Przegląd metod konstruowania algorytmów (4 godz.) Algorytmy zachłanne, brutalne, aproksymacyjne, metoda dziel i rządź, programowanie dynamiczne, problemy spełniania ograniczeń. LABORATORIA: 1. Organizacja laboratoriów. Zapoznanie się z narzędziami. Pisanie testów jednostkowych. Usuwanie błędów krytycznych aplikacji. Wyszukiwanie wycieków pamięci. Profilowanie aplikacji. 2. Implementacja słownika opartego o drzewo binarne. Implementacja słownika opartego o funkcję mieszającą. Porównanie efektywności czasowej obu rozwiązań. 3. Odbiór zadania z pkt. 2. 4. Zadanie grafowe. Implementacja zadanego algorytmu grafowego. 5. Odbiór zadania z pkt. 4. Omówienie zadania projektowego: implementacja aplikacji wymagającej od studentów dobrania i/lub opracowania kilku odpowiednich struktur danych i algorytmów spośród prezentowanych na wykładzie. 6. Praca nad zadaniem projektowym. Ocena przyjętych założeń. Konsultacje. 7. Odebranie zadania projektowego.
Metody oceny:
Realizacja przedmiotu obejmuje następujące formy zajęć:  wykład prowadzony w wymiarze 4 godz. tygodniowo; w wybranych zagadnieniach przewidziana jest aktywizacja studentów na wykładzie (wybrane wykłady prowadzone w formie dyskusji),  zajęcia laboratoryjne w wymiarze 4 godz. co dwa tygodnie; w ramach tych zajęć student, korzystając z oprogramowania i sprzętu komputerowego, będąc pod opieką prowadzącego zajęcia, będzie realizował wskazane zadania dotyczące implementacji algorytmów. Wybór tematów projektów i rozwiązań przeprowadzany będzie przy użyciu metody burzy mózgów. Sprawdzanie założonych efektów kształcenia realizowane jest przez:  ocenę wiedzy i umiejętności związanych z realizacją zadań laboratoryjnych – ocena z wybranych ćwiczeń laboratoryjnych;  ocenę wiedzy wykazanej na egzaminie.
Egzamin:
tak
Literatura:
• Cormen T, Leiserson Ch, Rivest R: Wprowadzenie do algorytmów, Warszawa, 2018 • Robert Sedgewick, Kevin Wayne (2012) - Algorithms • Skiena S, The Algorithm Design Manual, 2nd Edition, Springer, 2010 • Dasgupta S, Papadimitriou C, Vazirani U, Algorytmy, PWN, Warszawa 2010 • Bentley J, Perełki programowania. Wydanie II, 2012
Witryna www przedmiotu:
https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103D-INxxx-ISP-AISDI
Uwagi:
(-)

Efekty uczenia się