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

Analiza Algorytmów

Informacje ogólne

Kod przedmiotu: WMI.TCS.AA1.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: Analiza Algorytmów
Jednostka: Instytut Informatyki Analitycznej
Grupy:
Punkty ECTS i inne: 6.00 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ęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Maciej Ślusarek
Prowadzący grup: Maciej Ślusarek
Strona przedmiotu: http://forum.tcs.uj.edu.pl
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Efekty kształcenia:

E1: zna podstawowe metody analizy probabilistycznej algorytmów i potrafi je zastosować w wybranych obszarach algorytmiki

E2: zna metodę analizy amortyzowanej i umie ją wykorzystać do analizy ciągu operacji na strukturze danych

E3: zna wybrane zaawansowane algorytmy i struktury danych dla problemów związanych z porządkowaniem i wyszukiwaniem i potrafi wykonać analizę ich złożoności

E4: wykorzystuje analizę algorytmów do oceniania możliwości efektywnego rozwiązania zadanego problemu i do szacowania skuteczności danego rozwiązania
Wymagania wstępne:

Algorytmy i struktury danych 2,

Matematyka dyskretna,

Metody probabilistyczne informatyki (Rachunek prawdopodobieństwa)
Forma i warunki zaliczenia:

Student otrzymuje ocenę końcowa z ćwiczeń na podstawie punktów przyznawanych za rozwiązywanie zadań domowych oraz punktów uzyskanych na kolokwiach.


Student otrzymuje ocenę końcową z modułu na podstawie punktów przyznawanych na ćwiczeniach (z waga 50%) oraz punktów uzyskanych podczas egzaminu ustnego (z wagą 50%).
Metody sprawdzania i kryteria oceny efektów kształcenia uzyskanych przez studentów:

Kolokwia (E1, E2, E3, E4)

Egzamin (E1, E2, E3, E4)

Samodzielne rozwiązywanie zadań domowych (E1, E2 E3, E4)
Metody dydaktyczne:

1. Wykład.

2. Ćwiczenia.
Bilans punktów ECTS:

6 ECTS


Udział w wykładach - 30 godz.

Udział w ćwiczeniach – 30 godz..

Samodzielne rozwiązywanie zadań domowych – 60 godz.

Przygotowanie do kolokwiów i egzaminu oraz obecność na egzaminie – 40 godz.

Łączny nakład pracy studenta: 160 godzin , co odpowiada 6 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 3
Skrócony opis:

Zaawansowane metody analizy algorytmów na wybranych przykładach algorytmów sortowania i wyszukiwania.
Pełny opis:

1. Równania rekurencyjne w analizie algorytmów. Twierdzenie o rekurencji uniwersalnej, warianty.

2. Elementy rachunku prawdopodobieństwa: zmienne losowe wskaźnikowe, problem sekretarki, generowanie losowych permutacji.

3. Technika funkcji tworzących w analizie przypadku średniego. Przykład: wartość oczekiwana i wariancja quicksortu.

4. Analiza amortyzowana. Przykład: drzewa rozchylane (splay), problem statycznego słownika.

5. Dolne oszacowania na złożoność sortowania, algorytmy bliskie temu oszacowaniu: sortowanie turniejowe, algorytm Forda-Johnsona i problem minimalnej liczby porównań.

6. Statystyki pozycyjne, algorytm Hadiana-Sobela, wybrane dolne oszacowania.

7. Problem Find-Union, analiza, przykłady zastosowań.

8. Wyszukiwanie interpolacyjne, metoda kwadratowa i jej złożoność.

9. Analiza probabilistyczna drzewowych realizacji słownika - drzewa poszukiwań binarnych i kopcodrzewa.

10. Haszowanie: analiza haszowania otwartego, uniwersalne rodziny funkcji haszujących, haszowanie doskonałe.

11. Kolejki priorytetowe i kopce złączalne: kopce Fibonacciego, kolejki van Emde Boas'a, zastosowanie w algorytmach grafowych.
Literatura:

Moduł ma charakter autorski, obowiązuje przede wszystkim materiał wyłożony, literatura ma charakter pomocniczy. Do odpowiednich zagadnień literatura podawana jest na bieżąco w trakcie wykładu.

1. T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, C. Stein, Wprowadzenie do algorytmów, wydanie II, WNT, 2003.

2. L.Banachowski, A.Kreczmar, W.Rytter, Analiza algorytmów i struktur danych, WNT, 1987

3. L.Banachowski, K.Diks, W.Rytter, Algorytmy i struktury danych, WNT, 2001

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 usosweb12a