Algorytmy i struktury danych II
Informacje ogólne
Kod przedmiotu: | MFI-I.2L.002 |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Algorytmy i struktury danych II |
Jednostka: | Wydział Matematyki, Fizyki i Informatyki |
Grupy: | |
Strona przedmiotu: | https://kampus.umcs.pl/course/view.php?id=644 |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | polski |
Wymagania wstępne: | Umiejętność programowania w języku C++, znajomość podstaw matematyki oraz algorytmiki. Przedmioty wprowadzające: - Podstawy programowania. - Programowanie obiektowe. - Algebra liniowa z geometrią, - Logika i teoria mnogości - Matematyka dyskretna. - Algorytmy i struktury danych I |
Godzinowe ekwiwalenty punktów ECTS: | 1. Godziny kontaktowe z nauczycielem akademickim -wykład 30, -laboratorium 30, -konsultacje 2, -egzamin 3. Razem 65. 2. Samodzielna praca studenta - samodzielne rozwiązywanie zadań programistycznych 35, - przygotowanie się do laboratorium 10, - przygotowanie się do egzaminu 10. Razem 55. Samodzielna praca studenta + godziny kontaktowe = 120 Liczba punktów ECTS - 4 w tym 2,17 za godziny kontaktowe oraz 1,83 za samodzielną pracę studentów. |
Sposób weryfikacji efektów kształcenia: | Kartkówki - W1. Programy zaliczeniowe - W1, W2, U1, U2, K1, K2,K3. Aktywność - K1. Egzamin przy komputerach - W1, U1, U2, K1. |
Pełny opis: |
Celem przedmiotu jest zapoznanie studentów z podstawowymi strukturami danych i algorytmami. Wyrobienie u studentów umiejętności tworzenia, analizy i implementacji prostych algorytmów oraz ich wykorzystania do rozwiązywania problemów występujących w praktyce. Laboratoria są skorelowane z wykładem. Utrwala się na nich materiał poznany na wykładzie i rozwiązuje zadania algorytmiczne związane z tematami poszczególnych wykładów. Tematy poruszane na zajęciach: 1. Algorytmy grafowe: -znajdowanie najkrótszej ściezki (BFS, alg. Dijkstry, alg. Forda-Bellmana, alg. Floyda-Warshalla), -znajdowanie minimalnego drzewa rozpinającego graf (alg. Prima, alg. Kruskala), -znajdowanie maksymalnego przepływu w grafie, skojarzenia w grafie dwudzielnym (alg. Edmondsa-Karpa). 2. Słowniki - drzewa poszukiwań binarnych (BST), - drzewa czerwono-czarne, -drzewa splay, - B-drzewa, - drzewa trie, - tablice haszujące. 3. Algorytmy geometryczne (metoda zamiatania, metoda zamiatania polarnego, szukanie najmniej odległej pary punktów na płaszczyźnie, algorytm Grahama). 4. Algorytmy tekstowe (algorytm Morrisa-Pratta, algorytm Knutha-Morrisa-Pratta, algorytm Karpa-Rabina, algorytm Karpa-Millera-Rosenberga). 5. Algorytmy probabilistyczne (algorytmy Monte Carlo, algorytmy Las Vegas, problem pięciu filozofów, sprawdzanie pierwszości liczby, generatory liczb pseudolosowych). 6. Metody numeryczne (wzór Taylora, Metoda Newtona, interpolacja wielomianowa, całkowanie interpolacyjne). 7. Elementy teorii złożoności. |
Literatura: |
Literatura podstawowa: Cormen Thomas H.,Leiserson Charles E., Rivest Ronald L., Stein Clifford, Wprowadzenie do algorytmów, Wydawnictwo NT, Warszawa 2007. Slajdy z wykładu. Literatura uzupełniająca Lech Banachowski, Krzysztof Diks, Wojciech Rytter, Algorytmy i struktury danych, Wydawnictwo NT, Warszawa 2003. D.Knuth, Sztuka programowania, Wydawnictwo NT, Warszawa 2001. Ważniak -- http://wazniak.mimuw.edu.pl -- kursy: Metody programowania, Algorytmy i struktury danych, Zaawansowane algorytmy i struktury danych. |
Efekty uczenia się: |
WIEDZA W1. Zna podstawowe algorytmy, metody ich konstruowania oraz sposoby analizy - K_W02, K_W04, K_W05, K_W09, K_W10. W2. Zna dobre praktyki programistyczne - UMIEJĘTNOŚCI U1. Posiada umiejętność dobierania odpowiednich struktur danych i algorytmów do wskazanych problemów - K_U09; U2. Umie ułożyć i analizować algorytm zgodny ze specyfikacją oraz zaimplementować go w języku C++- K_U03, K_U05, K_U06; KOMPETENCJE SPOŁECZNE K1. Kreatywność w rozwiązywaniu problemów informatycznych – K_K02 K2. Systematyczność - K_K03 K3. Postępowanie zgodnie z zasadami etyki - K_K04. |
Właścicielem praw autorskich jest Uniwersytet Marii Curie-Skłodowskiej w Lublinie.