Algorytmy i struktury danych 1 3.4.KRK.12SX.ASD1
A. Problematyka wykładu
Podstawowe pojęcia: algorytm, zadanie, problem i jego specyfikacja. Algorytm jako sposób rozwiązania problemu. Pseudo-język. Problem sortowania metodą porównań. Sortowanie przez wstawianie.
Podstawy analizy algorytmów – poprawność i złożoność.
Techniki projektowania algorytmów: metoda „dziel i zwyciężaj”. Sortowanie przez scalanie. Twierdzenie o rekurencji uniwersalnej.
Sortowanie przez kopcowanie. Dolne szacowanie złożoności czasowej dla problemu sortowania. Problem wyboru. Sortowanie szybkie.
Zbiory dynamiczne. Abstrakcyjne struktury danych i ich implementacje: stosy, kolejki, listy, słowniki, kolejki priorytetowe. Abstrakcyjne struktury danych i ich implementacje: drzewa binarnych poszukiwań. Wyszukiwanie w drzewach binarnych.
Grafy, reprezentacje komputerowe grafów. Programowanie dynamiczne – problem najkrótszych ścieżek. Podstawowe algorytmy grafowe, przeszukiwanie wszerz i w głąb.
Techniki projektowania algorytmów: algorytmy zachłanne, przeszukiwanie z nawrotami.
Informacja o problemach obliczeniowo trudnych, problem stopu.
B. Problematyka laboratorium
Sortowanie przez wstawianie, sortowanie przez scalanie, sortowanie przez kopcowanie, sortowanie szybkie - analiza teoretyczna i empiryczna. Inne algorytmy sortujące przy pomocy porównań. Stosy, kolejki, listy, kolejki priorytetowe. Drzewa binar-nych poszukiwań. Reprezentacja wielotablicowa struktur ze wskaźnikami. Reprezentacje komputerowe grafów. Problem najkrótszych ścieżek. Domknięcie przechodnie grafu. Przeszukiwanie wszerz i w głąb. Kody Huffmana. Problem konika szachowego.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
W cyklu 2022/23-Z: | W cyklu 2023/24-L: |
Efekty kształcenia
Wiedza
W01 Zna pojęcia: algorytm, zadanie, problem i jego specyfikacja, pseudokod, poprawność i złożoność algorytmu.
W02 Zna problem sortowania oraz standardowe algorytmy sortujące przy pomocy porównań. Zna twierdzenie o rekurencji uniwersalnej oraz dolne szacowanie złożoności czasowej dla problemu sortowania.
W03 Zna techniki projektowania algorytmów: dziel i zwyciężaj, programowanie dynamiczne, algorytmy zachłanne, przeszukiwanie z nawrotami,.
W04 Zna abstrakcyjne struktury danych: listy, drzewa, grafy, słowniki, drzewa poszukiwań binarnych, haszowanie, stosy, kolejki, kolejki priorytetowe. Zna podstawowe problemy i algorytmy na drzewach oraz grafowe.
Umiejętności
U01 Przeprowadza analizę złożoności algorytmu oraz rozumie praktyczne znaczenie tego pojęcia.
U02 Konstruuje oraz implementuje algorytmy z wykorzystaniem podstawowych technik: dziel i zwyciężaj, programowanie dynamiczne, algorytmy zachłanne, przeszukiwanie z nawrotami.
U03 Stosuje wybrane struktury danych do rozwiązania określonego problemu informatycznego. Implementuje struktury dynamiczne w wybranym języku programowania.
U04 Implementuje podstawowe algorytmy grafowe do rozwiązania problemów pokrewnych.
Kompetencje społeczne (postawy)
K01 Intuicyjnie rozumie znaczenie analizy algorytmów i dostrzega sens rozwijania swoich kompetencji w tym zakresie. Potrafi zadawać pytania zmierzające do pokonania trudności napotykanych przy rozwiązywaniu problemu.
K02 Znając ograniczenia w stosowaniu metod informatyki, rozumie potrzebę popularnego przedstawiania laikom trudniejszych zagadnień oraz przedstawienia swojej opinii w tym zakresie..
K03 Korzysta z literatury książkowej i zasobów internetowych szukając wskazówek do rozwiązania problemu.
Kryteria oceniania
Metody dydaktyczne
Wykład / wykład problemowy / wykład z prezentacją multimedialną.
Ćwiczenia laboratoryjne: samodzielne opracowanie projektów ilustrujących prezentowany materiał.
A. Sposób zaliczenia
• zaliczenie z oceną (laboratorium)
• zaliczenie z oceną (wykład)
B. Formy zaliczenia
• (W) zaliczenie z oceną: ustalenie oceny zaliczeniowej na podstawie frekwencji, ocen cząstkowych otrzymywanych w trakcie trwania semestru za wykonanie prac zaliczenio-wych. możliwość podniesienia oceny: prezentacja wybranego algorytmu/struktury da-nych, analiza algorytmu oraz omówienie ewentualnej implementacji;
• (L) zaliczenie z oceną: ustalenie oceny zaliczeniowej na podstawie ocen cząstkowych otrzymywanych w trakcie trwania semestru za wykonanie prac zaliczeniowych
C. Podstawowe kryteria
• (W) obecność na zajęciach; pozytywna ocena z zaliczenia laboratorium,
• (L) uzyskanie pozytywnej oceny końcowej.
Literatura
A. Literatura wymagana
A.1. wykorzystywana podczas zajęć
A.2. studiowana samodzielnie przez studenta
1. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wprowadzenie do algorytmów, WNT, Warszawa 2005 (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Wprowadzenie do algorytmów.)
2. Lech Banachowski, Krzysztof Diks, Wojciech Rytter, Algorytmy i struktury danych, WNT, Warszawa 2006..
3. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983 (Projektowanie i analiza algorytmów, Algorytmy i struktury danych, Helion, 2003).
B. Literatura uzupełniająca
1. Niklaus Wirth, Algorytmy+struktury danych=programy, WNT, Warszawa 2001.
2. inne podręczniki dostępne on-line poprzez Bibliotekę Główną UO („ibuk”)
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: