Drukuj sylabusAlgorytmy 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
|
| Język prowadzenia: | polski |
Zajęcia w cyklu "Semestr letni 2023/2024" (w trakcie)
| Okres: | 2024-02-26 - 2024-06-16 |
 
PN WT ŚR WYK
LAB
LAB
LAB
CZ PT |
| Typ zajęć: |
Laboratorium, 30 godzin
Wykład, 30 godzin
|
|
| Koordynatorzy: | Maciej Ślusarek | |
| Prowadzący grup: | Marcin Briański, Andrzej Pezarski, Maciej Ślusarek | |
| 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 |
|
| 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 lub później: | Informatyka analityczna, studia stacjonarne pierwszego stopnia, rok 2 |
|
| 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. |
|
Właścicielem praw autorskich jest Uniwersytet Jagielloński w Krakowie.
