Strona główna

Sylabus modułu kształcenia na studiach wyższych Nazwa Wydziału


Pobieranie 35.92 Kb.
Data18.06.2016
Rozmiar35.92 Kb.


Sylabus modułu kształcenia na studiach wyższych


Nazwa Wydziału

Wydział Matematyki i Informatyki

Nazwa jednostki prowadzącej moduł

Zespół Katedr i Zakładów Informatyki Matematycznej

Nazwa modułu kształcenia

Algorytmy i struktury danych

Kod modułu

WMI.TCS.ASD1.OL, WMI.TCS.ASD2.OL,

Język kształcenia

polski

Efekty kształcenia dla modułu kształcenia

Lp.

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

zna podstawowe i wybrane zaawansowane techniki geometrii obliczeniowej

E5

zna podstawowe algorytmy numeryczne

E6

zna techniki wyszukiwania wzorca w tekście oraz struktury danych stosowane w tym problemie

E7

Zna podstawowe klasy złożoności i ich inkluzje

E8

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

E9

potrafi zaproponować rozwiązanie dla nietrudnego problemu algorytmicznego oraz ustnie i pisemnie przedstawić jego rozwiązanie

E10

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

E11

potrafi testować swój program, szukać w nim błędów i optymalizować go




Typ modułu kształcenia (obowiązkowy/ fakultatywny)

obowiązkowy, studia I stopnia

Rok studiów

II

Semestr

1 i 2

Imię i nazwisko osoby/osób prowadzących moduł

dr Maciej Ślusarek, dr Lech Duraj, dr Grzegorz Gutowski

Imię i nazwisko osoby/osób egzaminującej/egzaminujących bądź udzielającej zaliczenia, w przypadku gdy nie jest to osoba prowadząca dany moduł

dr Maciej Ślusarek

Sposób realizacji

wykład, laboratorium

Wymagania wstępne i dodatkowe

Podstawy Programowania, Metody programowania

Rodzaj i liczba godzin zajęć dydaktycznych wymagających bezpośredniego udziału nauczyciela akademickiego i studentów, gdy w danym module przewidziane są takie zajęcia

Wykład 60 godzin

Laboratorium 60 godzin



Liczba punktów ECTS przypisana modułowi

11

Bilans punktów ECTS

Udział w wykładach - 60 godz.

Udział w zajęciach laboratoryjnych – 60 godz.

Samodzielna implementacja zadań programistycznych – 110 godz.

Samodzielne rozwiązywanie zadań tablicowych– 60 godz.

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

Łączny nakład pracy studenta: 330 godzin , co odpowiada 11 punktom ETCS



Stosowane 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


Metody sprawdzania i kryteria oceny efektów kształcenia uzyskanych przez studentów

Kolokwia (E1-E10)

Samodzielnie implementowane zadania programistyczne (E1-E6, E8-E11)

Samodzielne rozwiązywanie zadań tablicowych (E1-E10)

Dyskusja podczas zajęć (E8, E9, E10)

Egzamin (E1-E10)

Dokładne kryteria oceny ustala wykładowca.



Forma i warunki zaliczenia modułu, w tym zasady dopuszczenia do egzaminu, zaliczenia, a także forma i warunki zaliczenia poszczególnych zajęć wchodzących w zakres danego modułu

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 pisemnego.


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.

10. Wyszukiwanie wzorca: prefikso-sufiksy, metoda KMP, automat Aho-Corasic, algorytm Karpa-Rabina.

11. Struktury danych dla wyszukiwania - 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.

12. Podstawowe techniki geometrii obliczeniowej: wyznacznik wektorów, zamiatanie. Zastosowanie: algorytmy wypukłej otoczki i znajdowania przecięć odcinków.

13. 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.

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

15. Liczby pierwsze, test Millera-Rabina.

16. Szybkie przekształcenie Fouriera.

17. Podstawowe klasy złożoności i ich inkluzje. Klasa NP. Problemy NP-zupełne, przykłady dowodów NP-zupełności.

18. Algorytmy aproksymacyjne.

19. Podstawy obliczeń współbieżnych: algorytmy równoległe, obliczenia wielowątkowe.


Wykaz literatury podstawowej i uzupełniającej, obowiązującej do zaliczenia danego modułu

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, 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..

Wymiar, zasady i forma odbywania praktyk, w przypadku, gdy program kształcenia przewiduje praktyki

Nie dotyczy





©snauka.pl 2016
wyślij wiadomość