| Pole | KOD | Znaczenie kodu |
|---|
| Zamierzone efekty uczenia się | I_1A_C04.1_W01 | Student rozumie pojęcia złożoności i sprawności oraz ich praktyczne znaczenie w analizie algorytmów; potrafi definiować zadania algorytmiczne oraz zaproponować odpowiednią technikę algorytmiczną do jego rozwiązania; zna podstawowe algorytmy sortowania oraz elementarne struktury danych (tablica, rekord, stos, kolejka, lista). |
|---|
| Odniesienie do efektów kształcenia dla kierunku studiów | I_1A_W02 | Posiada wiedzę w zakresie projektowania, analizy i implementacji algorytmów, struktur danych oraz konstrukcji programistycznych, zna podstawowe problemy algorytmiczne występujące w obszarze informatyki. |
|---|
| Cel przedmiotu | C-1 | Praktyczne opanowanie zasad tworzenia algorytmów |
|---|
| C-2 | Nabycie umiejetnosci oceny i porównywania algorytmów ze wzgledu na czaso- i pamieciochłonnosc |
| C-3 | Zapoznanie studenta z zasadami formułowania zadan algorytmicznych, projektowania algorytmów do ich rozwiazywania i oceny tych algorytmów |
| C-4 | Zapoznanie studenta z podstawowymi algorytmami sortowania oraz strukturami danych (stos, kolejka, lista) |
| Treści programowe | T-W-1 | Wprowadzenie (koncepcja i właściwości algorytmu, rola algorytmów w procesie rozwiązywania problemów, specyfikacja i sposoby opisu algorytmów, kryteria porównania algorytmów, ważne typy problemów (sortowanie, wyszukiwanie, przetwarzanie napisów, problemy grafowe), przegląd fundamentalnych strategii i metod projektowania algorytmów) |
|---|
| T-W-2 | Sprawność algorytmów (analiza algorytmów) („dokładny” czas wykonania algorytmu mierzony w liczbie akcji podstawowych (przypadek najlepszy, najgorszy i oczekiwany), asymptotyczna ocena czasu wykonania algorytmu (notacje “duże O”, “duża Omega“ i “duże Theta“), empiryczne pomiary czasu wykonania algorytmów) |
| T-W-3 | Analiza iteracyjnych i rekurencyjnych wersji algorytmów (rozwiązywanie równań rekurencyjnych, twierdzenie o rekurencji uniwersalnej i jego zastosowania) |
| T-W-4 | Poprawność algorytmu (poprawność częściowa: asercja i niezmiennik pętli, poprawność całkowita: zbieżnik i problem stopu, przykłady analizy poprawności algorytmu) |
| T-W-5 | Elementarne struktury liniowe (listy, stosy, kolejki, przykłady zastosowań – turniej, sito Eratostenesa) |
| T-W-6 | Grafy (klasyfikacja grafów i pojęcia podstawowe, reprezentacja grafów, abstrakcyjny typ danych „graf”, drogi, cykle, grafy ważone, grafy acykliczne, porządkowanie topologiczne grafów) |
| T-W-7 | Strategie siłowe (ang. brute force) i pełnego przeszukiwania (ang. exhaustive search) (sortowanie przez wybieranie, sortowanie bąbelkowe, wyszukiwanie sekwencyjne i dopasowywanie ciągów, problem komiwojażera, problem plecakowy, przeszukiwanie w głąb (DFS) i wszerz (BFS)) |
| T-W-8 | Strategia "zmniejszaj i zwyciężaj” (ang. decrease and conquer) (potęgowanie, największy wspólny dzielnik, sortowanie przez wstawianie, sortowanie topologiczne, generowanie permutacji i podzbiorów, kod Grey’a, wyszukiwanie binarne, mediana i problem wyboru) |
| T-W-9 | Strategia dziel i zwyciężaj (ang. divide and conquer) (sortowanie przez scalanie, szybkie sortowanie, mnożenie dużych liczb całkowitych, algorytm Strassena, najbliższe punkty) |
| T-W-10 | Strategia transformuj i zwyciężaj (ang. transform and conquer) (schemat Hornera, potęgowanie binarne) |
| T-W-11 | Programowanie dynamiczne (dyskretny problem plecakowy, algorytmy wyszukiwania najkrótszych ścieżek: Dijkstry i Bellmana-Forda, łańcuchowe mnożenie macierzy, porównania sekwencji DNA) |
| T-W-12 | Algorytmy zachłanne (problem wydania reszty, problem budowniczych kolei, drzewa rozpinające grafów (algorytmy Prima i Kruskala, kody Huffmana) |
| T-A-1 | Formułowanie i opis algorytmów (schematy blokowe, pseudokody, elementarne algorytmy sortowania) |
| T-A-2 | „Naturalna” ocena złożoności algorytmów (przypadek optymistyczny, pesymistyczny, średni,
wyszukiwanie „liniowe”, binarne, interpolacyjne, algorytmy liczbowe, problem wielkości liczby i wielkości jej reprezentacji w pamięci komputera) |
| T-A-3 | Rekurencyjne i iteracyjne wersje algorytmów (porównanie własności) |
| T-A-4 | Algorytmy dla grafów (problemy osiągalności, maksymalnego przepływu, dopasowania) |
| T-A-5 | Złożoność algorytmów rekurencyjnych (rozwiązywanie równań rekurencyjnych, twierdzenie o rekurencji uniwersalnej); przykłady zastosowań („wieże w Hanoi”, sortowanie przez scalanie, obliczanie wyrazów ciągu Fibonacciego) |
| T-A-6 | Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej) |
| T-A-7 | Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych |
| Metody nauczania | M-1 | Wykład informacyjno-konwersatoryjny |
|---|
| M-2 | Ćwiczenia audytoryjne |
| Sposób oceny | S-1 | Ocena formująca: Ocena na podstawie umiejętności rozwiazywania zadan formułowanych podczas ćwiczeń. |
|---|
| S-2 | Ocena formująca: Udział w dyskusjach prowadzonych w trakcie zajęć. |
| S-3 | Ocena podsumowująca: Egzamin - test (jednokrotnego lub wielokrotnego wyboru) oraz pytania otwarte (zadania problemowe). |
| Kryteria oceny | Ocena | Kryterium oceny |
|---|
| 2,0 | nie spełnia kryteriów okreslonych dla oceny 3 |
| 3,0 | potrafi wymienić i definiować wybrane podstawowe zadania algorytmiczne oraz proponować odpowiednie techniki algorytmiczne do ich rozwiązania; zna wybrane podstawowe struktury danych (stos, kolejka) oraz potrafi wyjaśnić działanie wybranych podstawowych iteracyjnych algorytmów sortowania |
| 3,5 | potrafi wymienić i zdefiniować dowolne podstawowe pojęcia dotyczące złożoności, sprawności i poprawności oraz ich praktyczne znaczenie w analizie algorytmów;
potrafi wymienić i definiować dowolne podstawowe zadania algorytmiczne oraz proponować odpowiednie techniki algorytmiczne do ich rozwiązania
zna dowolne podstawowe struktury danych (stos, jedno - dwukierunkowe kolejki i listy) oraz potrafi wyjaśnić działanie wybranych podstawowych iteracyjnych algorytmów sortowania |
| 4,0 | potrafi precyzyjnie opisać wybrane podstawowe pojęcia dotyczące złożoności, sprawności i poprawności oraz ich praktyczne znaczenie w analizie algorytmów;
potrafi precyzyjnie opisać wybrane podstawowe zadania algorytmiczne oraz proponować odpowiednie techniki algorytmiczne do ich rozwiązania;
potrafi opisać dowolne podstawowe struktury danych (stos, jedno - dwukierunkowe kolejki i listy) oraz wyjaśnić działanie wybranych podstawowych iteracyjnych i rekurencyjnych algorytmów sortowania |
| 4,5 | potrafi precyzyjnie opisać dowolne podstawowe pojęcia dotyczące złożoności, sprawności i poprawności oraz ich praktyczne znaczenie w analizie algorytmów
potrafi precyzyjnie opisać dowolne podstawowe zadania algorytmiczne oraz proponować odpowiednie techniki algorytmiczne do ich rozwiązania;
potrafi precyzyjnie opisać dowolne podstawowe struktury danych (stos, jedno - dwukierunkowe kolejki i listy) oraz precyzyjnie wyjaśnić działanie wybranych podstawowych iteracyjnych i rekurencyjnych algorytmów sortowania |
| 5,0 | spełnia wymagania na ocenę 4,5 oraz dodatkowo na poziomie podstawowym zna metody formalnego dowodzenia poprawności algorytmów;
na poziomie podstawowym potrafi zaproponować i wytłumaczyć działanie metody programowania dynamicznego na przykładzie wskazanego problemu algorytmicznego;
potrafi opisaći wyjaśnid działanie wybranych algorytmów sortowania wykraczajacych poza podstawowy zestaw algorytmów sortowania |