Uniwersytet Jagielloński w Krakowie - Punkt LogowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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)
zobacz reguły punktacji
Język prowadzenia: polski

Zajęcia w cyklu "Semestr zimowy 2020/2021" (jeszcze nie rozpoczęty)

Okres: 2020-10-01 - 2021-01-28

Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Maciej Ślusarek
Prowadzący grup: Piotr Micek, 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 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:

informatyka analityczna

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.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Jagielloński w Krakowie.