Algorytmy i złożoność obliczeniowa
Informacje ogólne
| Kod przedmiotu: | MFI-I.2S.160 |
| Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
| Nazwa przedmiotu: | Algorytmy i złożoność obliczeniowa |
| Jednostka: | Wydział Matematyki, Fizyki i Informatyki |
| Grupy: | |
| Punkty ECTS i inne: |
7.00
|
| Język prowadzenia: | polski |
| Wymagania wstępne: | Umiejętność programowania w C++. Znajomość podstaw algorytmiki. |
| Godzinowe ekwiwalenty punktów ECTS: | Godziny realizowane w obecności nauczyciela: Wykład: 30 godzin. Laboratorium: 30 godzin. Łącznie 60 godziny i 2 punkty ETCS. Godziny poświęcone na pracę indywidualną studenta : Czas przeznaczony na pisanie programów zaliczeniowych: 105h. Przygotowanie do laboratorium: 15h łącznie 120 godzin i 4 punkty ETCS. Czas wymagany do przygotowania się i do uczestnictwa w procesie oceniania: Nauka przed egzaminem: 27,5 godziny. Odpowiedź ustna na temat przesłanych programów 30 minut. Egzamin 2h Łącznie 30 godzin i 1 punkt ETCS Łącznie 210 godziny i 7 punktów ECTS. |
| Sposób weryfikacji efektów kształcenia: | W1: egzamin. W2: egzamin. U1: praca na zajęciach, programy zaliczeniowe, kolokwia. U2: praca na zajęciach, programy zaliczeniowe, kolokwia. K1: praca na zajęciach, programy zaliczeniowe. |
| Pełny opis: |
Wykład ma na celu zaznajomienie studentów z elementami algorytmiki i teorii złożoności. W szczególności zostaną poruszone następujące zagadnienia: 1. Różne rodzaje pomiaru złożoności obliczeniowej algorytmów i programów. 2. Klasy złożoności obliczeniowej. 3..Algorytmy sortujące. 4. Sumy prefiksowe, drzewa przedziałowe. 5. Algorytmy grafowe (szukanie najkrótszej ścieżki, minimalnego drzewa rozpinającego). 6. Kopce Fibonacciego. 5. Tablice asocjacyjne (drzewa BST, drzewa splay, drzewa trie). 6. Algorytmy tekstowe (algorytm Aho-Corasicka). |
| Literatura: |
Literatura Slajdy z wykładu. Christos H. Papadimitriou, Złożonośc obliczeniowa, dowolne wydanie. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Wprowadzenie do algorytmów, dowolne wydanie. Literatura uzupełniająca L.Banachowski, K.Diks, W.Rytter Algorytmy i struktury danych, dowolne wydanie. D.Knuth Sztuka programowania, dowolne wydanie. D. Harel Rzecz o istocie informatyki. Algorytmika, dowolne wydanie. |
| Efekty uczenia się: |
WIEDZA W1. Zna wybrane algorytmy i struktury danych. K_W01, K_W02, K_W06, K_W07, K_W09, K_W11 W2. Zna wybrane sposoby szacowania złożoności obliczeniowej oraz klasy złożoności. K_W01, K_W06, K_W10 UMIEJĘTNOŚCI U1. Potrafi zaimplementować znane algorytmy i oszacować ich złożoność. K_U01, K_U03, K_W03, K_W04, U2. Potrafi wybrać właściwy algorytm do rozwiązania zadanego problemu.K_U01, K_U02 KOMPETENCJE SPOŁECZNE K1. Jest świadomy konieczności pogłębiania swojej wiedzy, korzystania z aktualnej literatury i wiedzy ekspertów. K_K01, K_K02 |
Zajęcia w cyklu "Semestr zimowy 2024/2025" (zakończony)
| Okres: | 2024-10-01 - 2025-02-03 |
 
PN WT ŚR CZ PT |
| Typ zajęć: |
Laboratorium, 30 godzin
Wykład, 30 godzin
|
|
| Koordynatorzy: | Jacek Krzaczkowski | |
| Prowadzący grup: | Jacek Krzaczkowski, Marcin Kurzyna | |
| Lista studentów: | (nie masz dostępu) | |
| Zaliczenie: |
Przedmiot -
Egzamin
Laboratorium - Zaliczenie na ocenę Wykład - Egzamin |
Zajęcia w cyklu "Semestr zimowy 2025/2026" (w trakcie)
| Okres: | 2025-10-01 - 2026-02-24 |
PN W
LB
LB
WT LB
ŚR CZ PT |
| Typ zajęć: |
Laboratorium, 30 godzin
Wykład, 30 godzin
|
|
| Koordynatorzy: | Jacek Krzaczkowski | |
| Prowadzący grup: | Jacek Krzaczkowski, Marcin Kurzyna | |
| Lista studentów: | (nie masz dostępu) | |
| Zaliczenie: |
Przedmiot -
Egzamin
Laboratorium - Zaliczenie na ocenę Wykład - Egzamin |
Właścicielem praw autorskich jest Uniwersytet Marii Curie-Skłodowskiej w Lublinie.
