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

Analiza Algorytmów

Informacje ogólne

Kod przedmiotu: WMI.TCS.AA1.OL Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Analiza Algorytmów
Jednostka: Instytut Informatyki Analitycznej
Grupy:
Punkty ECTS i inne: 6.00
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ęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Maciej Ślusarek
Prowadzący grup: Bartłomiej Bosek, 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:

informatyka analityczna

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.