Algorytmy i Struktury Danych 1
Informacje ogólne
Kod przedmiotu: | WMI.TCS.ASD1.OL |
Kod Erasmus / ISCED: |
(brak danych)
/
(0613) Tworzenie i analiza oprogramowania i aplikacji
|
Nazwa przedmiotu: | Algorytmy i Struktury Danych 1 |
Jednostka: | Instytut Informatyki Analitycznej |
Grupy: | |
Punkty ECTS i inne: |
5.00
LUB
6.00
(w zależności od programu)
|
Język prowadzenia: | polski |
Zajęcia w cyklu "Semestr zimowy 2023/2024" (zakończony)
Okres: | 2023-10-01 - 2024-01-28 |
Przejdź do planu
PN WT LAB
LAB
LAB
ŚR WYK
CZ PT |
Typ zajęć: |
Laboratorium, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Maciej Ślusarek | |
Prowadzący grup: | Andrzej Pezarski, Krzysztof Potępa, Maciej Ślusarek | |
Strona przedmiotu: | http://satori.tcs.uj.edu.pl | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Przedmiot - Zaliczenie lub ocena | |
Efekty kształcenia: | E1: zna zaawansowane struktury danych oparte o drzewa wyszukiwań binarnych: drzewa AVL, drzewa czerwono-czarne, B-drzewa, kopcodrzewa, drzewa rozchylane, i metody ich realizacji programistycznej E2: ma pogłębioną wiedzę o technikach konstrukcji algorytmów, w szczególności o programowaniu dynamicznym i metodzie zachłannej E3: zna podstawowe jak i wybrane zaawansowane algorytmy dla wielu problemów grafowych E4: potrafi modelować problemy przedstawione w języku naturalnym posługując sie językiem matematyki i koncepcjami algorytmicznymi E5: potrafi zaproponować rozwiązanie dla nietrudnego problemu algorytmicznego oraz ustnie i pisemnie przedstawić jego rozwiązanie E6: projektuje i implementuje algorytmy wykorzystując podstawowe i wybrane zaawansowane techniki algorytmiczne E7: potrafi testować swój program, szukać w nim błędów i optymalizować go |
|
Wymagania wstępne: | Metody Programowania |
|
Forma i warunki zaliczenia: | Student otrzymuje ocenę końcowa z ćwiczeń na podstawie punktów przyznawanych za systematycznie oddawane programy zaliczeniowe, rozwiązywania zadań tablicowych oraz punktów uzyskanych na kolokwiach. Warunkiem koniecznym otrzymania zaliczenia ćwiczeń jest oddanie wszystkich obowiązkowych zadań programistycznych. Oceną końcową z modułu jest ocena końcowa z ćwiczeń. |
|
Metody sprawdzania i kryteria oceny efektów kształcenia uzyskanych przez studentów: | Kolokwia (E1, E2, E3, E4, E5, E6) Samodzielnie implementowane zadania programistyczne (E1, E2, E5, E6, E7) Samodzielne rozwiązywanie zadań tablicowych (E1, E2, E3, E4, E5) Dyskusja podczas zajęć (E4, E5, E6) |
|
Metody dydaktyczne: | 1. Wykład ilustrowany prezentacją komputerową. 2. Ćwiczenia w laboratorium komputerowym, połączone z dyskusją przy tablicy. 3. Samodzielne implementacja zadań programistycznych i automatyczne testowanie ich na serwerze zadaniowym |
|
Bilans punktów ECTS: | 5 ECTS. Udział w wykładach - 30 godz. Udział w zajęciach laboratoryjnych – 30 godz. Samodzielna implementacja zadań programistycznych – 50 godz. Samodzielne rozwiązywanie zadań tablicowych– 30 godz. Przygotowanie do kolokwiów – 10 godz. Łączny nakład pracy studenta: 150 godzin , co odpowiada 5 punktom ECTS |
|
Wymiar, zasady i forma odbywania praktyk: | nie dotyczy |
|
Sylabus przedmiotu dla studentów rozpoczynających studia od roku akademickiego 19/20 lub później: | Informatyka analityczna, studia stacjonarne pierwszego stopnia, rok 2 |
|
Skrócony opis: |
Projektowanie, analiza i implementacja drzewiastych struktur danych i algorytmów grafowych. Techniki konstrukcji efektywnych algorytmów. |
|
Pełny opis: |
Treści modułu kształcenia 1. Programowanie dynamiczne: DAG podzadań, odtwarzanie rozwiązania, problem wielkości pamięci. Przykłady: problem komiwojażera, problem plecakowy, najdłuższy wspólny podciąg i algorytm Hirschberga, pakowanie z ustaloną listą rozmiarów. 2. Algorytmy zachłanne - wybrane przykłady: szeregowanie z minimalizacją opóźnień, optymalne buforowanie w pamięci podręcznej. 3. Drzewa zrównoważone: drzewa AVL, drzewa czerwono-czarne, B-drzewa. 4. Inne mechanizmy równoważenia drzew: probabilistyczny (kopcodrzewa), amortyzowany (drzewa rozchylane). 5. Problemy spójności w grafach, silnie spójne składowe, dwuspójne składowe. 6. Najkrótsze ścieżki w grafach, algorymy: Bellmana/Forda, Dijkstry, Warshalla/Floyda, Johnsona. 7. Minimalne drzewa rozpinające, algorytmy: Jarnika/Prima, Boruvki/Sollina, Kruskala; problem sumowania zbiorów rozłącznych. 8. Przepływy w sieciach, algorytmy: Forda/Fulkersona, Edmondsa/Karpa, "push-relabel" 9. Skojarzenia w grafach dwudzielnych: algorytm oparty na przepływach oraz algorytm Hopcrofta/Karpa. |
|
Literatura: |
Moduł ma charakter autorski, obowiązuje przede wszystkim materiał wyłożony, literatura ma charakter pomocniczy. 1. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, wydanie II, WNT, 2003. 2. L.Banachowski, K.Diks, W.Rytter, Algorytmy i struktury danych, WNT, 2001 3. D. Knuth, Sztuka programowania, tom 1 i 3, WNT, 2002 4. A.V.Aho, J.E.Hopcroft, J.D.Ullman, Projektowanie i analiza algorytmów, PWN 1985, Helion 2003. |
Właścicielem praw autorskich jest Uniwersytet Jagielloński w Krakowie.