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

Algorytmy i Struktury Danych 2

Informacje ogólne

Kod przedmiotu: WMI.TCS.ASD2.OL Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Algorytmy i Struktury Danych 2
Jednostka: Instytut Informatyki Analitycznej
Grupy:
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: polski

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

Okres: 2021-02-24 - 2021-06-14
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: (brak danych)
Strona przedmiotu: http://satori.tcs.uj.edu.pl
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ocena wliczana do średniej:

tak

Efekty kształcenia:

E1: zna standardowe algorytmy i struktury danych stosowane w rozwiązaniach problemów algorytmicznych w geometrii obliczeniowej, przetwarzaniu tekstów, zagadnieniach teorioliczbowych

E2: rozumie znaczenie pojęcia obliczeniowej trudności, zna definicję klasy NP i problemu NP-zupełnego, identyfikuje przykładowe problemy NP-zupełne, zna wybrane algorytmy aproksymacyjne

E3: zna podstawowe koncepcje algorytmiczne występujące w obliczeniach równoległych, podaje przykłady ich zastosowań

E4: potrafi modelować problemy przedstawione w języku naturalnym posługując sie językiem matematyki i zaawansowanymi koncepcjami algorytmicznymi

E5: potrafi zaproponować rozwiązanie dla typowego problemu algorytmicznego w omawianych dziedzinach oraz ustnie i pisemnie przedstawić jego rozwiązanie

E6: projektuje i implementuje algorytmy wykorzystując podstawowe i wybrane zaawansowane techniki algorytmiczne

E7: ma pogłebioną umiejętność testowania swojego programu, szukania w nim błędów i optymalizowania go

Prerekwizyt:

Algorytmy i Struktury Danych 1 WMI.TCS.ASD1.OL
Matematyka Dyskretna WMI.TCS.MD.OL

Wymagania wstępne:

Algorytmy i struktury danych 1

Matematyka dyskretna

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.


Student otrzymuje ocenę końcową z modułu na podstawie punktów przyznawanych na ćwiczeniach oraz punktów uzyskanych podczas egzaminu ustnego.

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, E3, E4, E6, E7)

Samodzielne rozwiązywanie zadań tablicowych (E1, E2, E3, E4, E5)

Dyskusja podczas zajęć (E4, E5, E6)

Egzamin ustny

Dokładne kryteria oceny ustala wykładowca.

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:

6 ECTS.


Udział w wykładach - 30 godz.

Udział w zajęciach laboratoryjnych – 30 godz.

Samodzielna implementacja zadań programistycznych – 60 godz.

Samodzielne rozwiązywanie zadań tablicowych– 30 godz.

Przygotowanie do kolokwiów i egzaminu – 30 godz.

Łączny nakład pracy studenta: 180 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:

Algorytmika tekstów: wyszukiwanie wzorca, struktury danych dla wyszukiwania. Geometria obliczeniowa: techniki, struktury danych, przykłady zastosowań. Wybrane algorytmy liczbowe. NP-zupełność. Podstawy równoległości.

Pełny opis:

1. Wyszukiwanie wzorca w tekście: prefikso-sufiksy, metoda KMP, automat Aho-Corasic, algorytm Karpa-Rabina.

2. Tablice sufiksowe: konstrukcja metodą Karpa-Millera-Rosenberga, tablica wspólnych prefiksów i optymalny algorytm wyszukiwania, drzewa sufiksowe i ich związek z tablicami sufiksowymi.

3. Podstawowe techniki geometrii obliczeniowej: wyznacznik wektorów, zamiatanie, zastosowania w algorytmach wypukłej otoczki i znajdowania przecięć odcinków.

4. Dalsze algorytmy geometryczne: przynależność punktu do wielokąta, reprezentacja podziału płaszczyzny, lokalizacja punktu na płaszczyźnie metodą warstw, kd-drzewa i wyszukiwanie po zakresie.

5. Programowanie liniowe, metoda sympleks, dualność.

6. Problemy liczbowe: algorytm Euklidesa, arytmetyka modularna, logarytm dyskretny, algorytm RSA.

7. Liczby pierwsze, test probabilistyczny.

8. Szybkie przekształcenie Fouriera.

9. Trudność obliczeniowa: klasa NP, problemy NP-zupełne, przykłady dowodów NP-zupełności, algorytmy aproksymacyjne.

10. Podstawy obliczeń współbieżnych: przykłady algorytmów równoległych i ich złożoność, algorytmy wielowątkowe.

Literatura:

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 III, PWN, 2012.

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.