Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

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 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
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 2023/2024 - sem. letni" (w trakcie)

Okres: 2024-02-19 - 2024-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 120 miejsc więcej informacji
Wykład, 60 godzin, 120 miejsc więcej informacji
Koordynatorzy: Andrzej Zalewski
Prowadzący grup: Klara Borowa, Krzysztof Chabko, Waldemar Grabski, Szymon Kijas, Piotr Maciąg, Stanisław Pawlak, Łukasz Skonieczny, Marcin Szlenk, Andrzej Zalewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2023/2024 - sem. zimowy" (zakończony)

Okres: 2023-10-01 - 2024-02-18
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 57 miejsc więcej informacji
Wykład, 60 godzin, 57 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Krzysztof Chabko, Waldemar Grabski, Krzysztof Gracki, 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 2022/2023 - sem. letni" (zakończony)

Okres: 2023-02-20 - 2023-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 120 miejsc więcej informacji
Wykład, 60 godzin, 120 miejsc więcej informacji
Koordynatorzy: Andrzej Zalewski
Prowadzący grup: Krzysztof Chabko, Waldemar Grabski, Wiktor Kuśmirek, Stanisław Pawlak, Marcin Szlenk, Andrzej Zalewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2022/2023 - sem. zimowy" (zakończony)

Okres: 2022-10-01 - 2023-02-19
Wybrany podział planu:
Przejdź do planu
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 2021/2022 - sem. letni" (zakończony)

Okres: 2022-02-23 - 2022-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 120 miejsc więcej informacji
Wykład, 60 godzin, 120 miejsc więcej informacji
Koordynatorzy: Andrzej Zalewski
Prowadzący grup: Krzysztof Chabko, Waldemar Grabski, Wiktor Kuśmirek, Łukasz Neumann, Marcin Szlenk, Andrzej Zalewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2021/2022 - sem. zimowy" (zakończony)

Okres: 2021-10-01 - 2022-02-22
Wybrany podział planu:
Przejdź do planu
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 2020/2021 - sem. letni" (zakończony)

Okres: 2021-02-20 - 2021-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 130 miejsc więcej informacji
Wykład, 60 godzin, 130 miejsc więcej informacji
Koordynatorzy: Andrzej Ratkowski, Andrzej Zalewski
Prowadzący grup: Klara Borowa, Krzysztof Chabko, Waldemar Grabski, Wiktor Kuśmirek, Łukasz Neumann, Andrzej Ratkowski, Andrzej Zalewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

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

Okres: 2020-10-01 - 2021-02-19
Wybrany podział planu:
Przejdź do planu
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:
Przejdź do planu
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.
pl. Politechniki 1, 00-661 Warszawa tel: (22) 234 7211 https://pw.edu.pl kontakt deklaracja dostępności USOSweb 7.0.0.0-7 (2024-03-18)