Uniwersytet Jagielloński w Krakowie - Centralny System Uwierzytelniania
Strona główna

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 Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
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) 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.
zobacz reguły punktacji
Język prowadzenia: polski

Zajęcia w cyklu "Semestr zimowy 2023/2024" (zakończony)

Okres: 2023-10-01 - 2024-01-28
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Jagielloński w Krakowie.
ul. Gołębia 24, 31-007 Kraków https://www.uj.edu.pl kontakt deklaracja dostępności mapa serwisu USOSweb 7.0.4.0 usosweb12c