| Pole | KOD | Znaczenie kodu |
|---|
| Zamierzone efekty uczenia się | Itest_1A_C03.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 | Ma zaawansowaną i uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu fundamentalnych obszarów 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-A-1 | Formułowanie i opis algorytmów (schematy blokowe, pseudokody, elementarne algorytmy sortowania) |
|---|
| 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-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-7 | Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych |
| T-A-6 | Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej) |
| 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-W-5 | Elementarne struktury liniowe: listy, stosy, kolejki i grafy (klasyfikacja grafów, reprezentacja grafów, drogi, cykle, grafy ważone, grafy acykliczne). |
| T-W-6 | 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 grafu w głąb (DFS) i wszerz (BFS). |
| T-W-10 | Programowanie dynamiczne: dyskretny problem plecakowy, problem wydawania reszty, algorytmy wyszukiwania najkrótszych ścieżek (algorytm Bellmana-Forda), łańcuchowe mnożenie macierzy, porównania sekwencji DNA. |
| T-W-7 | Strategie "zmniejszaj i zwyciężaj” (ang. decrease and conquer) oraz „transformuj i zwyciężaj” (ang. transform and conquer): potęgowanie, największy wspólny dzielnik, sortowanie przez wstawianie, sortowanie topologiczne, generowanie permutacji i podzbiorów, kod Greya, wyszukiwanie binarne, mediana i problem wyboru, sortowanie przez kopcowanie, schemat Hornera, potęgowanie binarne. |
| T-W-9 | Algorytmy zachłanne: problem wydania reszty, problem budowniczych kolei, drzewa rozpinające grafów (algorytmy Prima i Kruskala), problem najkrótszych ścieżek z jednego źródła (algorytm Dijkstry), kody Huffmana. |
| T-W-8 | 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-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 algorytmicznych, przegląd fundamentalnych strategii i metod projektowania 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-2 | Sprawność algorytmów (analiza algorytmów): „dokładny” czas wykonania algorytmu mierzony w liczbie akcji podstawowych, asymptotyczna ocena czasu wykonania algorytmu (notacje “duże O”, “duża Omega“ i “duże Theta“), empiryczne pomiary czasu wykonania algorytmów. |
| Metody nauczania | M-1 | Wykład informacyjno-konwersatoryjny |
|---|
| M-2 | Ćwiczenia audytoryjne |
| Sposób oceny | 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). |
| S-1 | Ocena formująca: Ocena na podstawie umiejętności rozwiazywania zadan formułowanych podczas ćwiczeń. |
| 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 |