Wydział Informatyki - Informatyka (N1)
specjalność: Inżynieria systemów informacyjnych
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 | ||
| 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
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | Wprowadzenie do informatyki |
| W-2 | Matematyka stosowana ze statystyką 1 |
| W-3 | Programowanie 1 |
Cele przedmiotu
| KOD | Cel modułu/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 z podziałem na formy zajęć
| KOD | Treść programowa | Godziny |
|---|---|---|
| ćwiczenia audytoryjne | ||
| T-A-1 | Formuł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) | 2 |
| T-A-3 | Rekurencyjne i iteracyjne wersje algorytmów (porównanie własności) | 2 |
| T-A-4 | Algorytmy dla grafów (problemy osiągalności, maksymalnego przepływu, dopasowania) | 2 |
| 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) | 2 |
| T-A-6 | Formalne badanie poprawności algorytmów (asercje, niezmiennik i zbieżnik pętli iteracyjnej) | 2 |
| T-A-7 | Zastosowanie różnych stategiii do rozwiązaywania problemów algorytmicznych | 4 |
| 18 | ||
| wykłady | ||
| 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) | 2 |
| 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) | 2 |
| T-W-3 | Analiza iteracyjnych i rekurencyjnych wersji algorytmów (rozwiązywanie równań rekurencyjnych, twierdzenie o rekurencji uniwersalnej i jego zastosowania) | 2 |
| 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) | 2 |
| T-W-5 | Elementarne struktury liniowe (listy, stosy, kolejki, przykłady zastosowań – turniej, sito Eratostenesa) | 2 |
| 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 w głąb (DFS) i wszerz (BFS)) | 2 |
| T-W-7 | 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) | 2 |
| T-W-8 | Programowanie dynamiczne (dyskretny problem plecakowy, algorytmy wyszukiwania najkrótszych ścieżek: Dijkstry i Bellmana-Forda) | 2 |
| T-W-9 | Algorytmy zachłanne (problem wydania reszty, problem budowniczych kolei, drzewa rozpinające grafów (algorytmy Prima i Kruskala, kody Huffmana) | 2 |
| 18 | ||
Obciążenie pracą studenta - formy aktywności
| KOD | Forma aktywności | Godziny |
|---|---|---|
| ćwiczenia audytoryjne | ||
| A-A-1 | uczestnictwo w zajęciach | 18 |
| A-A-2 | przygotowanie do cwiczen - praca własna studenta | 30 |
| A-A-3 | Udział w konsultacjach i w zaliczeniu formy zajec | 2 |
| 50 | ||
| wykłady | ||
| A-W-1 | uczestnictwo w zajęciach | 18 |
| A-W-2 | zapoznanie się ze wskazaną literaturą / materiałami dydaktycznymi | 29 |
| A-W-3 | przygotowanie do egzaminu | 24 |
| A-W-4 | udział w konsultacjach | 2 |
| A-W-5 | Uczestnitwo w egzaminie | 2 |
| 75 | ||
Metody nauczania / narzędzia dydaktyczne
| KOD | Metoda nauczania / narzędzie dydaktyczne |
|---|---|
| M-1 | Wykład informacyjno-konwersatoryjny |
| M-2 | Ćwiczenia audytoryjne |
Sposoby oceny
| KOD | 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). |
Zamierzone efekty uczenia się - wiedza
| Zamierzone efekty uczenia się | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Odniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżyniera | Cel przedmiotu | Treści programowe | Metody nauczania | Sposó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_W02 | — | — | C-1, C-2, C-3, C-4 | T-W-1, T-W-5, T-W-3, T-W-4, T-W-6, T-W-7, T-W-9, T-W-8, T-W-2 | M-1, M-2 | S-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ów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Odniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżyniera | Cel przedmiotu | Treści programowe | Metody nauczania | Sposó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_U06 | — | — | C-1, C-3 | T-A-1, T-A-2, T-A-3, T-A-4, T-A-5, T-A-6, T-A-7 | M-2 | S-3 |
Kryterium oceny - wiedza
| Efekt uczenia się | Ocena | Kryterium 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,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 |
Kryterium oceny - umiejętności
| Efekt uczenia się | Ocena | Kryterium 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,0 | nie spełnia kryteriów określonych dla oceny 3 |
| 3,0 | potrafi formułować i rozwiązywać wybrane podstawowe zadania algorytmiczne; potrafi obliczyć złożoność czasową wybranych podstawowych algorytmów | |
| 3,5 | potrafi formułować i rozwiazywać dowolne podstawowe zadania algorytmiczne; potrafi obliczyc złozonosc czasowa dowolnych podstawowych algorytmów | |
| 4,0 | potrafi 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,5 | potrafi 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,0 | potrafi 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
- Anany Levitin, Introduction to The Design and Analysis of Algorithms, Addison Wesley, 2012, III
- Steven S. Skiena, The Algorithm Design Manual, Springer-Verlag, London, 2008, II
- Richard Neapolitan, Kumarss Naimipour, Podstawy algorytmów z przykładami w C++, Helion, 2008, III
Literatura dodatkowa
- Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Algorytmy i struktury danych, Helion, 2003
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, PWN, Warszawa, 2004
- Kyle Loudon, Algorytmy w C, Helion, 2003