Algorytmy i struktury danych

Zakłada się, że uczestnik niniejszego kursu posiada następującą wiedzę i umiejętności (zdobyte na przedmiocie Podstawy algorytmiki programowania (1000-I1PAiP) i przedmiotach matematycznych na 1 roku):

• zna podstawowe techniki programistyczne (obsługa wejścia/wyjścia, pętle, instrukcje warunkowe, funkcje, przekazywanie parametrów, tablice, struktury) potrafi ich sprawnie używać w wybranym języku programowania (zalecane C++ lub Python);
  


• posiada elementarną wiedzę matematyczną: rozumie zapis symboliczny, zna podstawy logiki, kombinatoryki i arytmetyki (indukcja, ciągi liczbowe) oraz zna pojęcie funkcji i związane z nim notacje;
  


• umie czytać ze zrozumieniem algorytmy w postaci pseudokodu oraz pisać programy na ich podstawie.
  

przedmiot obligatoryjny

30 godz. – wykład; 30 godz. – ćwiczenia

50 godz. – praca własna: bieżące przygotowanie do zajęć, praca z literaturą

35 godz. – praca własna: przygotowanie do egzaminu

3 godz. – egzamin

RAZEM: 148 godz.

6 pkt. ECTS

(W1) ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie programowania, algorytmów oraz ich poprawności i złożoności (por. K_W02 );

(W2) zna najważniejsze struktury danych i wykonywane na nich operacje oraz ich wpływ na złożoność obliczeniową algorytmów i zarządzanie pamięcią (por. K_W05, również K_W07);

(W3) zna podstawowe metody projektowania, analizowania i programowania algorytmów (projektowanie strukturalne, rekurencja, metoda dziel i zwyciężaj, metoda zachłanna, programowanie dynamiczne, złożoność obliczeniowa), por. K_W04;

(W4) zna podstawowe klasyczne algorytmy i ich zastosowania: algorytmy wyszukiwania i porządkowania, algorytmy optymalizacyjne, algorytmy grafowe (por. K_W02 i K_W04).

(U1) potrafi zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania obliczeniowych problemów informatycznych, analizuje je pod kątem możliwości ich algorytmicznego rozwiązania z jak najlepszą złożonością obliczeniową (por. K_U01);

(U2) projektuje, analizuje pod kątem poprawności i złożoności obliczeniowej oraz programuje algorytmy; wykorzystuje podstawowe techniki algorytmiczne i umie dopasować struktury danych i metody projektowania algorytmów odpowiednie do danego problemu (por. K_U07);

(U3) implementuje podstawowe klasyczne algorytmy, uzasadnia ich poprawność, określa ich złożoność obliczeniową oraz umie dostosować je do rozwiązania konkretnych, specyficznych problemów (por. K_U07);

(U4) potrafi pisać, uruchamiać i testować programy w wybranym środowisku programistycznym (por. K_U05);

(U5) potrafi pracować indywidualnie nad projektem programistycznym, w tym także potrafi zarządzać swoim czasem oraz podejmować zobowiązania i dotrzymywać terminów (por. K_U03).

(K1) myśli twórczo w celu udoskonalenia istniejących bądź stworzenia nowych rozwiązań (w zakresie problemów algorytmicznych, por. K_K02);

(K2) jest gotów do pokonywania trudności stojących na drodze do realizacji założonego celu i systematycznej pracy nad projektem programistycznym; jest nastawiony na jak najlepsze i terminowe wykonanie zadania (por. K_K04);

(K3) jest gotów do krytycznej oceny swojej wiedzy i dalszego jej doskonalenia z wykorzystaniem różnych źródeł informacji (por. K_K03).

- pokaz

- wykład informacyjny (konwencjonalny)
- wykład problemowy

- ćwiczeniowa
- doświadczeń
- klasyczna metoda problemowa
- laboratoryjna
- projektu
- referatu

- metody rozwijające refleksyjne myślenie
- metody służące prezentacji treści

Jest to podstawowy kurs algorytmiki, obejmujący najważniejsze metody projektowania i analizy algorytmów oraz wykorzystywane w nich struktury danych. Szczególny nacisk kładzie się na uzasadnianie poprawności i szacowanie złożoności obliczeniowej algorytmów. Dokładnie omawiane są przykłady algorytmów rozwiązujących konkretne problemy, w tym: zasady ich działania, niezbędne elementarne narzędzia matematyczne, uzasadnienia poprawności oraz metody efektywnej implementacji.

• Pojęcie algorytmu i jego złożoności obliczeniowej.
  • Problem a algorytm. Specyfikacja problemu.
  • Funkcja kosztu i pełna funkcja kosztu.
  • Koszt zamortyzowany.
  • Złożoność asymptotyczna, notacje "O", "Ω", "Θ". Własności i przykłady.
  • Metody wyznaczania funkcji kosztu algorytmów rekurencyjnych.
• Elementarne struktury danych: tablica, stos, kolejka, lista, wektor.
• Przegląd wybranych algorytmów sortowania.
• Metody projektowania algorytmów.
  • Metoda przyrostowa.
  • Dziel i zwyciężaj.
  • Metoda zachłanna.
  • Programowanie dynamiczne.
  • Przykłady zastosowań, m.in.: sortowanie przez scalanie, problem bankomatu, problem plecakowy, optymalny wybór zajęć, optymalne nawiasowanie ciągu mnożeń macierzy.
• Dowodzenie poprawności algorytmu.
  • Częściowa poprawność: systemy formalne Hilberta i Hoare'a, niezmiennik pętli.
  • Całkowita poprawność: własność stopu, zbieżnik pętli.
• Drzewiaste struktury danych.
  • Drzewa poszukiwań binarnych (BST).
  • Wzmianka o drzewach czerwono-czarnych.
  • Kopiec binarny.
  • Złożoność operacji.
  • Zastosowania, m.in.: wyszukiwanie, analiza wyrażeń, implementacja kolejki priorytetowej, sortowanie (heapsort).
• Elementy teorii grafów, reprezentacja grafów w komputerze.
• Algorytmy grafowe i ich zastosowania.
  • Przeglądanie grafów w głąb (DFS) i wszerz (BFS). Testowanie spójności i najkrótsze drogi.
  • Najkrótsze drogi w grafach z wagami - algorytmy Dijkstry i Bellmana-Forda.
  • Minimalne drzewo rozpinające (MST), przekroje.
  • Struktura danych zbiorów rozłącznych, analiza heurystyczna implementacji.
  • Algorytmy Kruskala i Prima znajdowania MST.
• *Wprowadzenie do algorytmów aproksymacyjnych i teorii NP-zupełności. Problem komiwojażera.

W trakcie ćwiczeń w laboratoriach studenci analizują i implementują zarówno poznane na wykładzie, jak i zaprojektowane przez siebie algorytmy.

Literatura podstawowa:

• T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT PWN, 2018.
• L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 2018.
• M.M. Sysło, Algorytmy, Helion, 2016.
• D. Harel, Rzecz o istocie informatyki. Algorytmika, WNT, 1992.
• J. Tomasiewicz, Zaprzyjaźnij się z algorytmami, Przewodnik dla początkujących i średnio zaawansowanych, PWN, 2016.

Literatura uzupełniająca:

• M.M. Syslo, N. Deo, J.S. Kowalik, Algorytmy optymalizacji dyskretnej z programami w języku Pascal, WN PWN, 1997.
• M.M. Sysło, Piramidy, szyszki i inne konstrukcje programistyczne, Helion, 2015.
• A.V. Aho, J.E. Hopcroft, J.D. Ullman, Algorytmy i struktury danych, Helion, 2003.
• R.J. Wilson, Wprowadzenie do teorii grafów, PWN 2016.
• P. Stańczyk, Algorytmika praktyczna. Nie tylko dla mistrzów, PWN, 2009.
• P. Mikołajczyk, Wprowadzenie do STL, UMCS, Lublin 2012.

Na zaliczenie przedmiotu składa się :

• Zaliczenie laboratorium na podstawie oceny z kolokwium (W1-W4, U1-U3, K1) oraz z implementacji algorytmów (U3-U5) i ich prezentacji (K1-K3).
• Zaliczenie egzaminu pisemnego z wykładu (W1-W4, U1-U3, K1).

Warunkiem koniecznym jest uzyskanie pozytywnej oceny dla każdego z powyższych elementów. Warunkiem dopuszczenia do egzaminu jest zaliczenie laboratoriów. Bardziej szczegółowe zasady zaliczenia mogą znajdować się w informacjach dla zajęć w konkretnym cyklu i będą podane przez prowadzących laboratoria i wykład.