Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Wydział Informatyki - Informatyka (N1)
specjalność: Inżynieria systemów wbudowanych

Sylabus przedmiotu Algorytmy 1:

Informacje podstawowe

Kierunek studiów Informatyka
Forma studiów studia niestacjonarne Poziom pierwszego stopnia
Tytuł zawodowy absolwenta inżynier
Obszary studiów charakterystyki PRK, kompetencje inżynierskie PRK
Profil ogólnoakademicki
Moduł
Przedmiot Algorytmy 1
Specjalność przedmiot wspólny
Jednostka prowadząca Katedra Inżynierii Oprogramowania i Cyberbezpieczeństwa
Nauczyciel odpowiedzialny Jerzy Pejaś <Jerzy.Pejas@zut.edu.pl>
Inni nauczyciele Dariusz Frejlichowski <dfrejlichowski@wi.zut.edu.pl>, Przemysław Klęsk <pklesk@wi.zut.edu.pl>, Jerzy Pejaś <Jerzy.Pejas@zut.edu.pl>
ECTS (planowane) 6,0 ECTS (formy) 6,0
Forma zaliczenia egzamin Język polski
Blok obieralny Grupa obieralna

Formy dydaktyczne

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
ćwiczenia audytoryjneA2 20 3,00,50zaliczenie
wykładyW2 20 3,00,50egzamin

Wymagania wstępne

KODWymaganie wstępne
W-1Wprowadzenie do informatyki
W-2Matematyka stosowana ze statystyką 1
W-3Programowanie 1

Cele przedmiotu

KODCel modułu/przedmiotu
C-1Praktyczne opanowanie zasad tworzenia algorytmów
C-2Nabycie umiejetnosci oceny i porównywania algorytmów ze wzgledu na czaso- i pamieciochłonnosc
C-3Zapoznanie studenta z zasadami formułowania zadan algorytmicznych, projektowania algorytmów do ich rozwiazywania i oceny tych algorytmów
C-4Zapoznanie studenta z podstawowymi algorytmami sortowania oraz strukturami danych (stos, kolejka, lista)

Treści programowe z podziałem na formy zajęć

KODTreść programowaGodziny
ćwiczenia audytoryjne
T-A-1Formułowanie i opis algorytmów (schematy blokowe, pseudokody, elementarne algorytmy sortowania)4
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)4
T-A-3Rekurencyjne i iteracyjne wersje algorytmów (porównanie własności)4
T-A-4Zł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)4
T-A-5Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej)2
T-A-6Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych2
20
wykłady
T-W-1Wprowadzenie: 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.2
T-W-2Sprawność 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.2
T-W-3Analiza iteracyjnych i rekurencyjnych wersji algorytmów: rozwiązywanie równań rekurencyjnych, twierdzenie o rekurencji uniwersalnej i jego zastosowania.2
T-W-4Poprawność algorytmu: poprawność częściowa (asercja i niezmienni pętli, poprawność całkowita (zbieżnik i problem stopu), przykłady analizy poprawności algorytmu.2
T-W-5Elementarne struktury liniowe: listy, stosy, kolejki i grafy (klasyfikacja grafów, reprezentacja grafów, drogi, cykle, grafy ważone, grafy acykliczne).2
T-W-6Strategie 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).2
T-W-7Strategie "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, mediana i problem wyboru, sortowanie przez kopcowanie2
T-W-8Strategia 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.2
T-W-9Algorytmy 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.2
T-W-10Programowanie dynamiczne: dyskretny problem plecakowy, problem wydawania reszty, algorytmy wyszukiwania najkrótszych ścieżek (algorytm Bellmana-Forda), łańcuchowe mnożenie macierzy.2
20

Obciążenie pracą studenta - formy aktywności

KODForma aktywnościGodziny
ćwiczenia audytoryjne
A-A-1Uczestnictwo w zajęciach20
A-A-2Praca własna55
75
wykłady
A-W-1Uczestnictwo w zajęciach20
A-W-2Konsultacje2
A-W-3Praca własna51
A-W-4Egzamin2
75

Metody nauczania / narzędzia dydaktyczne

KODMetoda nauczania / narzędzie dydaktyczne
M-1Wykład informacyjno-konwersatoryjny
M-2Ćwiczenia audytoryjne

Sposoby oceny

KODSposób oceny
S-1Ocena formująca: Ocena na podstawie umiejętności rozwiazywania zadan formułowanych podczas ćwiczeń.
S-2Ocena formująca: Udział w dyskusjach prowadzonych w trakcie zajęć.
S-3Ocena podsumowująca: Egzamin - test (jednokrotnego lub wielokrotnego wyboru) oraz pytania otwarte (zadania problemowe).

Zamierzone efekty uczenia się - wiedza

Zamierzone efekty uczenia sięOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
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).
I_1A_W02C-1, C-2, C-3, C-4T-A-3, T-A-1, T-A-2, T-A-6, T-A-5, T-A-4, T-W-5, T-W-6, T-W-10, T-W-8, T-W-9, T-W-1, T-W-3, T-W-4, T-W-2M-1, M-2S-2, S-3, S-1

Zamierzone efekty uczenia się - umiejętności

Zamierzone efekty uczenia sięOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
Itest_1A_C03.1_U01
Student potrafi formułować i rozwiązywać zadania algorytmiczne, projektować algorytmy, badać ich poprawność i sprawność, ulepszać ich działanie, zastosować podstawowe struktury danych do rozwiązywania zadań algorytmicznych.
I_1A_U05C-1, C-3T-A-3, T-A-1, T-A-2, T-A-6, T-A-5, T-A-4, T-W-6, T-W-10, T-W-9, T-W-1, T-W-3, T-W-4, T-W-2M-2S-3

Kryterium oceny - wiedza

Efekt uczenia sięOcenaKryterium oceny
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).
2,0nie spełnia kryteriów okreslonych dla oceny 3
3,0potrafi 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,5potrafi 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,0potrafi 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,5potrafi 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,0speł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

Kryterium oceny - umiejętności

Efekt uczenia sięOcenaKryterium oceny
Itest_1A_C03.1_U01
Student potrafi formułować i rozwiązywać zadania algorytmiczne, projektować algorytmy, badać ich poprawność i sprawność, ulepszać ich działanie, zastosować podstawowe struktury danych do rozwiązywania zadań algorytmicznych.
2,0nie spełnia kryteriów określonych dla oceny 3
3,0potrafi formułować i rozwiązywać wybrane podstawowe zadania algorytmiczne; potrafi obliczyć złożoność czasową wybranych podstawowych algorytmów
3,5potrafi formułować i rozwiazywać dowolne podstawowe zadania algorytmiczne; potrafi obliczyc złozonosc czasowa dowolnych podstawowych algorytmów
4,0potrafi zastosowac metode projektowania dziel i zwyciezaj oraz metody siłowe (ang. brute force) i pełnego przeszukiwania do rozwiazania wybranych podstawowych zadań algorytmicznych; spełnia wymagania na ocene 3,5 oraz dodatkowo potrafi zweryfikować poprawność wybranych podstawowych algorytmów
4,5potrafi zastosowac metode projektowania dziel i zwyciezaj oraz metody siłowe (ang. brute force) i pełnego przeszukiwania do rozwiazania dowolnych zadań algorytmicznych, które poddaja sie tym metodą; spełnia wymagania na ocene 4,0 oraz dodatkowo potrafi zweryfikować poprawność dowolnych algorytmów
5,0potrafi zastosowac metodę programownaia dydnamicznego oraz metodę "zmniejszaj i zwyciężaj” (ang. decrease and conquer) do zaprojektowania wybranych podstawowych zadan algorytmicznych; spełnia wymagania na ocene 4,5 oraz dodatkowo potrafi wprowadzić usprawnienia podnoszące sprawność działania algorytmów

Literatura podstawowa

  1. Anany Levitin, Introduction to The Design and Analysis of Algorithms, Addison Wesley, 2012, III
  2. Steven S. Skiena, The Algorithm Design Manual, Springer-Verlag, London, 2008, II
  3. Richard Neapolitan, Kumarss Naimipour, Podstawy algorytmów z przykładami w C++, Helion, 2008, III

Literatura dodatkowa

  1. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Algorytmy i struktury danych, Helion, 2003
  2. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, PWN, Warszawa, 2004
  3. Kyle Loudon, Algorytmy w C, Helion, 2003

Treści programowe - ćwiczenia audytoryjne

KODTreść programowaGodziny
T-A-1Formułowanie i opis algorytmów (schematy blokowe, pseudokody, elementarne algorytmy sortowania)4
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)4
T-A-3Rekurencyjne i iteracyjne wersje algorytmów (porównanie własności)4
T-A-4Zł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)4
T-A-5Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej)2
T-A-6Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych2
20

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Wprowadzenie: 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.2
T-W-2Sprawność 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.2
T-W-3Analiza iteracyjnych i rekurencyjnych wersji algorytmów: rozwiązywanie równań rekurencyjnych, twierdzenie o rekurencji uniwersalnej i jego zastosowania.2
T-W-4Poprawność algorytmu: poprawność częściowa (asercja i niezmienni pętli, poprawność całkowita (zbieżnik i problem stopu), przykłady analizy poprawności algorytmu.2
T-W-5Elementarne struktury liniowe: listy, stosy, kolejki i grafy (klasyfikacja grafów, reprezentacja grafów, drogi, cykle, grafy ważone, grafy acykliczne).2
T-W-6Strategie 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).2
T-W-7Strategie "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, mediana i problem wyboru, sortowanie przez kopcowanie2
T-W-8Strategia 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.2
T-W-9Algorytmy 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.2
T-W-10Programowanie dynamiczne: dyskretny problem plecakowy, problem wydawania reszty, algorytmy wyszukiwania najkrótszych ścieżek (algorytm Bellmana-Forda), łańcuchowe mnożenie macierzy.2
20

Formy aktywności - ćwiczenia audytoryjne

KODForma aktywnościGodziny
A-A-1Uczestnictwo w zajęciach20
A-A-2Praca własna55
75
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1Uczestnictwo w zajęciach20
A-W-2Konsultacje2
A-W-3Praca własna51
A-W-4Egzamin2
75
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięItest_1A_C03.1_W01Student 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ówI_1A_W02Ma zaawansowaną i uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu fundamentalnych obszarów informatyki.
Cel przedmiotuC-1Praktyczne opanowanie zasad tworzenia algorytmów
C-2Nabycie umiejetnosci oceny i porównywania algorytmów ze wzgledu na czaso- i pamieciochłonnosc
C-3Zapoznanie studenta z zasadami formułowania zadan algorytmicznych, projektowania algorytmów do ich rozwiazywania i oceny tych algorytmów
C-4Zapoznanie studenta z podstawowymi algorytmami sortowania oraz strukturami danych (stos, kolejka, lista)
Treści programoweT-A-3Rekurencyjne i iteracyjne wersje algorytmów (porównanie własności)
T-A-1Formuł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-6Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych
T-A-5Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej)
T-A-4Zł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-5Elementarne struktury liniowe: listy, stosy, kolejki i grafy (klasyfikacja grafów, reprezentacja grafów, drogi, cykle, grafy ważone, grafy acykliczne).
T-W-6Strategie 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-10Programowanie dynamiczne: dyskretny problem plecakowy, problem wydawania reszty, algorytmy wyszukiwania najkrótszych ścieżek (algorytm Bellmana-Forda), łańcuchowe mnożenie macierzy.
T-W-8Strategia 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-9Algorytmy 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-1Wprowadzenie: 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-3Analiza iteracyjnych i rekurencyjnych wersji algorytmów: rozwiązywanie równań rekurencyjnych, twierdzenie o rekurencji uniwersalnej i jego zastosowania.
T-W-4Poprawność algorytmu: poprawność częściowa (asercja i niezmienni pętli, poprawność całkowita (zbieżnik i problem stopu), przykłady analizy poprawności algorytmu.
T-W-2Sprawność 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 nauczaniaM-1Wykład informacyjno-konwersatoryjny
M-2Ćwiczenia audytoryjne
Sposób ocenyS-2Ocena formująca: Udział w dyskusjach prowadzonych w trakcie zajęć.
S-3Ocena podsumowująca: Egzamin - test (jednokrotnego lub wielokrotnego wyboru) oraz pytania otwarte (zadania problemowe).
S-1Ocena formująca: Ocena na podstawie umiejętności rozwiazywania zadan formułowanych podczas ćwiczeń.
Kryteria ocenyOcenaKryterium oceny
2,0nie spełnia kryteriów okreslonych dla oceny 3
3,0potrafi 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,5potrafi 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,0potrafi 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,5potrafi 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,0speł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
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięItest_1A_C03.1_U01Student potrafi formułować i rozwiązywać zadania algorytmiczne, projektować algorytmy, badać ich poprawność i sprawność, ulepszać ich działanie, zastosować podstawowe struktury danych do rozwiązywania zadań algorytmicznych.
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_U05Potrafi zaplanować i zrealizować eksperymenty w zakresie oceny wydajności, złożoności, efektywności systemów informatycznych i ich składowych.
Cel przedmiotuC-1Praktyczne opanowanie zasad tworzenia algorytmów
C-3Zapoznanie studenta z zasadami formułowania zadan algorytmicznych, projektowania algorytmów do ich rozwiazywania i oceny tych algorytmów
Treści programoweT-A-3Rekurencyjne i iteracyjne wersje algorytmów (porównanie własności)
T-A-1Formuł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-6Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych
T-A-5Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej)
T-A-4Zł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-6Strategie 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-10Programowanie dynamiczne: dyskretny problem plecakowy, problem wydawania reszty, algorytmy wyszukiwania najkrótszych ścieżek (algorytm Bellmana-Forda), łańcuchowe mnożenie macierzy.
T-W-9Algorytmy 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-1Wprowadzenie: 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-3Analiza iteracyjnych i rekurencyjnych wersji algorytmów: rozwiązywanie równań rekurencyjnych, twierdzenie o rekurencji uniwersalnej i jego zastosowania.
T-W-4Poprawność algorytmu: poprawność częściowa (asercja i niezmienni pętli, poprawność całkowita (zbieżnik i problem stopu), przykłady analizy poprawności algorytmu.
T-W-2Sprawność 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 nauczaniaM-2Ćwiczenia audytoryjne
Sposób ocenyS-3Ocena podsumowująca: Egzamin - test (jednokrotnego lub wielokrotnego wyboru) oraz pytania otwarte (zadania problemowe).
Kryteria ocenyOcenaKryterium oceny
2,0nie spełnia kryteriów określonych dla oceny 3
3,0potrafi formułować i rozwiązywać wybrane podstawowe zadania algorytmiczne; potrafi obliczyć złożoność czasową wybranych podstawowych algorytmów
3,5potrafi formułować i rozwiazywać dowolne podstawowe zadania algorytmiczne; potrafi obliczyc złozonosc czasowa dowolnych podstawowych algorytmów
4,0potrafi zastosowac metode projektowania dziel i zwyciezaj oraz metody siłowe (ang. brute force) i pełnego przeszukiwania do rozwiazania wybranych podstawowych zadań algorytmicznych; spełnia wymagania na ocene 3,5 oraz dodatkowo potrafi zweryfikować poprawność wybranych podstawowych algorytmów
4,5potrafi zastosowac metode projektowania dziel i zwyciezaj oraz metody siłowe (ang. brute force) i pełnego przeszukiwania do rozwiazania dowolnych zadań algorytmicznych, które poddaja sie tym metodą; spełnia wymagania na ocene 4,0 oraz dodatkowo potrafi zweryfikować poprawność dowolnych algorytmów
5,0potrafi zastosowac metodę programownaia dydnamicznego oraz metodę "zmniejszaj i zwyciężaj” (ang. decrease and conquer) do zaprojektowania wybranych podstawowych zadan algorytmicznych; spełnia wymagania na ocene 4,5 oraz dodatkowo potrafi wprowadzić usprawnienia podnoszące sprawność działania algorytmów