Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Wydział Informatyki - Informatyka (S1)

Sylabus przedmiotu Algorytmy 1:

Informacje podstawowe

Kierunek studiów Informatyka
Forma studiów studia stacjonarne 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
Nauczyciel odpowiedzialny Włodzimierz Chocianowicz <Wlodzimierz.Chocianowicz@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) 5,0 ECTS (formy) 5,0
Forma zaliczenia zaliczenie Język polski
Blok obieralny Grupa obieralna

Formy dydaktyczne

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
ćwiczenia audytoryjneA2 30 2,00,50zaliczenie
wykładyW2 30 3,00,50zaliczenie

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-4Algorytmy dla grafów (problemy osiągalności, maksymalnego przepływu, dopasowania)4
T-A-5Zł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)7
T-A-6Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej)5
T-A-7Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych2
30
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 (sortowanie, wyszukiwanie, przetwarzanie napisów, problemy grafowe), przegląd fundamentalnych strategii i metod projektowania algorytmów)3
T-W-2Sprawność 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)2
T-W-3Analiza iteracyjnych i rekurencyjnych wersji algorytmów (rozwiązywanie równań rekurencyjnych, twierdzenie o rekurencji uniwersalnej i jego zastosowania)4
T-W-4Poprawność algorytmu (poprawność częściowa: asercja i niezmiennik 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)3
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 w głąb (DFS) i wszerz (BFS))3
T-W-7Strategia "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)2
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)3
T-W-9Strategia transformuj i zwyciężaj (ang. transform and conquer) (schemat Hornera, potęgowanie binarne)2
T-W-10Programowanie dynamiczne (dyskretny problem plecakowy, algorytmy wyszukiwania najkrótszych ścieżek: Dijkstry i Bellmana-Forda, łańcuchowe mnożenie macierzy, porównania sekwencji DNA)4
T-W-11Algorytmy zachłanne (problem wydania reszty, problem budowniczych kolei, drzewa rozpinające grafów (algorytmy Prima i Kruskala, kody Huffmana)2
30

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

KODForma aktywnościGodziny
ćwiczenia audytoryjne
A-A-1uczestnictwo w zajęciach30
A-A-2przygotowanie do cwiczen - praca własna studenta18
A-A-3Udział w konsultacjach i w zaliczeniu formy zajec2
50
wykłady
A-W-1uczestnictwo w zajęciach30
A-W-2zapoznanie się ze wskazaną literaturą / materiałami dydaktycznymi23
A-W-3przygotowanie do zaliczenia18
A-W-4udział w konsultacjach2
A-W-5Uczestnitwo w zaliczeniu2
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
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).
I_1A_W02C-1, C-2, C-3, C-4T-A-1, T-A-3, T-A-4, T-A-2, T-A-7, T-A-6, T-A-5, T-W-5, T-W-6, T-W-11, T-W-7, T-W-10, T-W-8, T-W-1, T-W-3, T-W-4, T-W-2, T-W-9M-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
I_1A_C04.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_U06C-1, C-3T-A-1, T-A-3, T-A-4, T-A-2, T-A-7, T-A-6, T-A-5, T-W-6, T-W-11, T-W-10, T-W-8, T-W-1, T-W-3, T-W-4, T-W-2, T-W-9M-2S-3

Kryterium oceny - wiedza

Efekt uczenia sięOcenaKryterium oceny
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).
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
I_1A_C04.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-4Algorytmy dla grafów (problemy osiągalności, maksymalnego przepływu, dopasowania)4
T-A-5Zł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)7
T-A-6Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej)5
T-A-7Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych2
30

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 (sortowanie, wyszukiwanie, przetwarzanie napisów, problemy grafowe), przegląd fundamentalnych strategii i metod projektowania algorytmów)3
T-W-2Sprawność 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)2
T-W-3Analiza iteracyjnych i rekurencyjnych wersji algorytmów (rozwiązywanie równań rekurencyjnych, twierdzenie o rekurencji uniwersalnej i jego zastosowania)4
T-W-4Poprawność algorytmu (poprawność częściowa: asercja i niezmiennik 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)3
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 w głąb (DFS) i wszerz (BFS))3
T-W-7Strategia "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)2
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)3
T-W-9Strategia transformuj i zwyciężaj (ang. transform and conquer) (schemat Hornera, potęgowanie binarne)2
T-W-10Programowanie dynamiczne (dyskretny problem plecakowy, algorytmy wyszukiwania najkrótszych ścieżek: Dijkstry i Bellmana-Forda, łańcuchowe mnożenie macierzy, porównania sekwencji DNA)4
T-W-11Algorytmy zachłanne (problem wydania reszty, problem budowniczych kolei, drzewa rozpinające grafów (algorytmy Prima i Kruskala, kody Huffmana)2
30

Formy aktywności - ćwiczenia audytoryjne

KODForma aktywnościGodziny
A-A-1uczestnictwo w zajęciach30
A-A-2przygotowanie do cwiczen - praca własna studenta18
A-A-3Udział w konsultacjach i w zaliczeniu formy zajec2
50
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1uczestnictwo w zajęciach30
A-W-2zapoznanie się ze wskazaną literaturą / materiałami dydaktycznymi23
A-W-3przygotowanie do zaliczenia18
A-W-4udział w konsultacjach2
A-W-5Uczestnitwo w zaliczeniu2
75
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięI_1A_C04.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_W02Posiada 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 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-1Formułowanie i opis algorytmów (schematy blokowe, pseudokody, elementarne algorytmy sortowania)
T-A-3Rekurencyjne i iteracyjne wersje algorytmów (porównanie własności)
T-A-4Algorytmy 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-7Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych
T-A-6Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej)
T-A-5Zł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 w głąb (DFS) i wszerz (BFS))
T-W-11Algorytmy zachłanne (problem wydania reszty, problem budowniczych kolei, drzewa rozpinające grafów (algorytmy Prima i Kruskala, kody Huffmana)
T-W-7Strategia "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-10Programowanie 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-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-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 (sortowanie, wyszukiwanie, przetwarzanie napisów, problemy grafowe), 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 niezmiennik 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 (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-9Strategia transformuj i zwyciężaj (ang. transform and conquer) (schemat Hornera, potęgowanie binarne)
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ęI_1A_C04.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_U06Potrafi rozwiązywać podstawowe problemy algorytmiczne z uwzględnieniem ich złożoności posługując się kluczowymi językami programowania.
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-1Formułowanie i opis algorytmów (schematy blokowe, pseudokody, elementarne algorytmy sortowania)
T-A-3Rekurencyjne i iteracyjne wersje algorytmów (porównanie własności)
T-A-4Algorytmy 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-7Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych
T-A-6Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej)
T-A-5Zł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 w głąb (DFS) i wszerz (BFS))
T-W-11Algorytmy zachłanne (problem wydania reszty, problem budowniczych kolei, drzewa rozpinające grafów (algorytmy Prima i Kruskala, kody Huffmana)
T-W-10Programowanie 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-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-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 (sortowanie, wyszukiwanie, przetwarzanie napisów, problemy grafowe), 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 niezmiennik 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 (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-9Strategia transformuj i zwyciężaj (ang. transform and conquer) (schemat Hornera, potęgowanie binarne)
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