Politechnika Warszawska - Centralny System Uwierzytelniania
Nie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 103D-INxxx-ISP-AISDI Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy i struktury danych
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Podstawy informatyki )-Informatyka-inż.-EITI
( Przedmioty podstawowe )-Informatyka w multimediach-mgr.-EITI
( Przedmioty podstawowe )-Inteligentne systemy-mgr.-EITI
( Przedmioty podstawowe )-Sztuczna inteligencja-mgr.-EITI
( Przedmioty techniczne )---EITI
Punkty ECTS i inne: 6.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

AISDI

Numer wersji:

4

Skrócony opis:

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.

Pełny opis:

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ść wykładu

  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ń.



Zakres laboratorium

  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.
Literatura:

  1. Cormen T, Leiserson Ch, Rivest R: Wprowadzenie do algorytmów, Warszawa, 2018.
  2. Robert Sedgewick, Kevin Wayne (2012) - Algorithms.
  3. Skiena S, The Algorithm Design Manual, 2nd Edition, Springer, 2010.
  4. Dasgupta S, Papadimitriou C, Vazirani U, Algorytmy, PWN, Warszawa 2010.
  5. Bentley J, Perełki programowania, Wydanie II, 2012.
Metody i kryteria oceniania:

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.

Zajęcia w cyklu "rok akademicki 2020/2021 - sem. zimowy" (w trakcie)

Okres: 2020-10-01 - 2021-02-12
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 36 miejsc więcej informacji
Wykład, 60 godzin, 36 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Krzysztof Chabko, Wiktor Kuśmirek, Łukasz Skonieczny, Marcin Szlenk
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. letni" (zakończony)

Okres: 2020-02-22 - 2020-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 130 miejsc więcej informacji
Wykład, 60 godzin, 130 miejsc więcej informacji
Koordynatorzy: Andrzej Zalewski
Prowadzący grup: Krzysztof Chabko, Wiktor Kuśmirek, Piotr Maciąg, Andrzej Ratkowski, Marcin Szlenk
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.