Wydział Informatyki - Informatyka (S1)
specjalność: systemy komputerowe i oprogramowanie
Sylabus przedmiotu Struktury danych i złożoność obliczeniowa:
Informacje podstawowe
| Kierunek studiów | Informatyka | ||
|---|---|---|---|
| Forma studiów | studia stacjonarne | Poziom | pierwszego stopnia |
| Tytuł zawodowy absolwenta | inżynier | ||
| Obszary studiów | nauk technicznych, studiów inżynierskich | ||
| Profil | ogólnoakademicki | ||
| Moduł | — | ||
| Przedmiot | Struktury danych i złożoność obliczeniowa | ||
| Specjalność | przedmiot wspólny | ||
| Jednostka prowadząca | Katedra Inżynierii Oprogramowania | ||
| Nauczyciel odpowiedzialny | Włodzimierz Chocianowicz <Wlodzimierz.Chocianowicz@zut.edu.pl> | ||
| Inni nauczyciele | Włodzimierz Chocianowicz <Wlodzimierz.Chocianowicz@zut.edu.pl> | ||
| ECTS (planowane) | 3,0 | ECTS (formy) | 3,0 |
| Forma zaliczenia | egzamin | Język | polski |
| Blok obieralny | — | Grupa obieralna | — |
Formy dydaktyczne
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | Podstawowe umiejętności programowania w języku C/C++ |
| W-2 | Zaliczenie kursu "Wstęp do algorytmizacji" lub równoważnego |
| W-3 | Zaliczenie kursu "Matematyka dyskretna" lub równoważnego |
| W-4 | Znajomość podstaw informatyki |
Cele przedmiotu
| KOD | Cel modułu/przedmiotu |
|---|---|
| C-1 | Zapoznanie z zasadami tworzenia złożonych struktur danych |
| C-2 | Zapoznanie z cechami konstrukcyjnymi najważniejszych struktur danych |
| C-3 | Zapoznanie z klasyfikacją i metodami oceny złożoności obliczeniowej |
| C-4 | Nabycie umiejętności wyboru struktur danych odpowiednich dla problemu algorytmicznego i środowiska implementacyjnego |
Treści programowe z podziałem na formy zajęć
| KOD | Treść programowa | Godziny |
|---|---|---|
| laboratoria | ||
| T-L-1 | Wprowadzenie. Tablice wskaźników i sortowanie | 2 |
| T-L-2 | Lista liniowa, dwukierunkowa i cykliczna | 2 |
| T-L-3 | Zwykłe drzewo poszukiwań binarnych | 2 |
| T-L-4 | Dokładne wyważanie drzewa BST, rotacje, algorytm DSW | 2 |
| T-L-5 | Samoorganizujące się drzewa BST, drzewo "splay" | 2 |
| T-L-6 | Wstawianie i usuwanie węzłów w drzewie AVL | 4 |
| T-L-7 | Podsumowanie cyklu laboratoryjnego | 1 |
| 15 | ||
| wykłady | ||
| T-W-1 | Pojęcia podstawowe (typy danych, operatory,moc typu) | 1 |
| T-W-2 | Złożone struktury/typy danych (typ wyliczeniowy, typ zbiorowy, tablica, rekord, stos, kolejka, kolejka priorytetowa, plik sekwencyjny, listy) | 5 |
| T-W-3 | Drzewa i drzewa binarne (ogólna definicja drzewa, drzewa binarne: kopce i drzewa poszukiwań binarnych, implementacja drzew binarnych, wyszukiwanie w drzewie, przechodzenie drzewa, operacje wstawiania i usuwania elementów drzewa, wyważanie drzew poszukiwań binarnych, drzewa AVL, samoorganizujące się drzewa poszukiwań) | 9 |
| T-W-4 | Drzewa wielokierunkowe (B-drzewa, B*-drzewa, B+-drzewa, drzewa prefiksowe, kopce dwumianowe, a-b drzewa) | 4 |
| T-W-5 | Mieszanie (funkcje mieszające, struktury danych wykorzystywane do implementacji tablic mieszania, rozwiązywanie i usuwanie problemów kolizji) | 2 |
| T-W-6 | Grafy (reprezentacja grafów, przechodzenie grafów, grafy ważone, grafy acykliczne, drzewa rozpinające grafów, algorytmy wyszukiwania ścieżek) | 5 |
| T-W-7 | Złożoność obliczeniowa (definicja klas złożoności problemów oblicze-niowych, klasy P, NP, NP-zupełna, coNP, problemy NP-trudne, związki między złożonością czasową i pamięciową, klasy złożoności algorytmów niedeterministycznych, nierozstrzygalność i niezupełność) | 4 |
| 30 | ||
Obciążenie pracą studenta - formy aktywności
| KOD | Forma aktywności | Godziny |
|---|---|---|
| laboratoria | ||
| A-L-1 | Implementacja algorytmów obsługujących struktury danych podczas zajęć laboratoryjnych - udział w zajęciach dydaktycznych | 15 |
| A-L-2 | Przygotowanie do rozwiązania wskazanych problemów implementacyjnych | 10 |
| A-L-3 | Optymalizacja rozwiązań uzyskanych podczas zajęć laboratoryjnych | 5 |
| A-L-4 | Udział w konsultacjach | 2 |
| 32 | ||
| wykłady | ||
| A-W-1 | Udział w wykładach | 30 |
| A-W-2 | Analiza i rozwiązywanie problemów rozszerzających materiał wykładowy (praca własna) | 12 |
| A-W-3 | Przygotowanie się do egzaminu i udział w egzaminie | 10 |
| A-W-4 | Konsultacje | 4 |
| 56 | ||
Metody nauczania / narzędzia dydaktyczne
| KOD | Metoda nauczania / narzędzie dydaktyczne |
|---|---|
| M-1 | Wykład informacyjno-konwersatoryjny |
| M-2 | Ćwiczenia laboratoryjne |
Sposoby oceny
| KOD | Sposób oceny |
|---|---|
| S-1 | Ocena formująca: Sprawdzian przygotowania do zajęć laboratoryjnych |
| S-2 | Ocena formująca: Ocena wykonania poszczególnych implementacji |
| S-3 | Ocena podsumowująca: Egzamin pisemny z zadaniami i problemami otwartymi |
Zamierzone efekty kształcenia - wiedza
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżyniera | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|---|
| I_1A_C/5_W01 zna zasady tworzenia prostych i złożonych typów danych | I_1A_W05 | T1A_W03, T1A_W07 | InzA_W02 | C-2, C-1 | T-L-2, T-W-5, T-W-3, T-L-4, T-W-6, T-W-4, T-W-2, T-L-5, T-W-1, T-L-3, T-L-1 | M-1, M-2 | S-1, S-3 |
| I_1A_C/5_W02 zna algorytmy manipulujące określonymi strukturami danych i sposoby oceny ich złożoności obliczeniowej | I_1A_W05 | T1A_W03, T1A_W07 | InzA_W02 | C-4, C-3, C-2 | T-W-3, T-L-1, T-L-6, T-W-4, T-L-2, T-L-5, T-W-7, T-L-3, T-W-5, T-L-4 | M-1, M-2 | S-1, S-3 |
Zamierzone efekty kształcenia - umiejętności
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżyniera | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|---|
| I_1A_C/5_U01 ma świadomość barier obliczeniowych związanych ze złożonością problemów obliczeniowych | I_1A_U19 | T1A_U13, T1A_U15, T1A_U16 | InzA_U05, InzA_U07, InzA_U08 | C-4 | T-W-7 | M-2, M-1 | S-2 |
| I_1A_C/5_U02 umie dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego | I_1A_U19 | T1A_U13, T1A_U15, T1A_U16 | InzA_U05, InzA_U07, InzA_U08 | C-4, C-3 | T-L-5, T-W-4, T-L-3, T-L-4, T-L-2, T-W-6, T-W-3, T-W-7, T-W-5 | M-1, M-2 | S-3, S-1 |
Kryterium oceny - wiedza
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_1A_C/5_W01 zna zasady tworzenia prostych i złożonych typów danych | 2,0 | nie spełnia kryteriów określonych dla oceny 3,0 |
| 3,0 | potrafi wymienić i zdefiniować wybrane podstawowe pojecia dotyczace prostych i złożonych typów danych | |
| 3,5 | potrafi wymienić i zdefiniować wszystkie podstawowe pojecia dotyczace tworzenia i własności prostych i złożonych typów danych | |
| 4,0 | zna klasyfikację (i związane z nią cechy) drzewiastych struktur danych, sposoby rozwiązywania problemu kolizji w tablicach mieszających, sposoby reprezentowania informacji o strukturze grafów skierowanych i nieskierowanych | |
| 4,5 | zna uzasadnienie reguł obowiązujących przy tworzeniu drzewiastych struktur danych, rozwiązywania problemu kolizji w tablicach mieszających, podejmowaniu decyzji o wyborze sposobu reprezentowania informacji o strukturze grafów skierowanych i nieskierowanych | |
| 5,0 | opanował w pełnym zakresie materiał merytoryczny dotyczący zasad tworzenia prostych i złożonych typów (struktur) danych | |
| I_1A_C/5_W02 zna algorytmy manipulujące określonymi strukturami danych i sposoby oceny ich złożoności obliczeniowej | 2,0 | nie spełnia kryteriów określonych dla oceny 3,0 |
| 3,0 | potrafi okreśić sposoby postępowania podczas wstawiania usuwania i wyszukiwania określonych elementów składowych w wybranych strukturach danych | |
| 3,5 | potrafi okreśić sposoby postępowania podczas wstawiania usuwania i wyszukiwania określonych elementów składowych w dowolnych strukturach danych ujętych w programie kursu | |
| 4,0 | potrafi ocenić złożoność obliczeniową algorytmów manipulowania wybranymi strukturami danych | |
| 4,5 | potrafi ocenić złożoność obliczeniową algorytmów manipulowania dowolnymi strukturami danych ujętymi w programie kursu | |
| 5,0 | opanował w pełnym zakresie materiał merytoryczny dotyczący algorytmów manipulowania określonymi strukturami danych i sposobów oceny ich złożoności obliczeniowej |
Kryterium oceny - umiejętności
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_1A_C/5_U01 ma świadomość barier obliczeniowych związanych ze złożonością problemów obliczeniowych | 2,0 | nie spełnia kryteriów okreslonych dla oceny 3 |
| 3,0 | umie ocenić złożność elementarnych algorytmów i odróżniać algorytmy "łatwe" od "trudnych" obliczeniowo | |
| 3,5 | potrafi porównać algorytmy rozwiązujące ten sam problem ze względu na ich zlożoność | |
| 4,0 | potrafi powiązać złożoność algorytmu z cechami środowiska, w którym są wykonywane obliczenia | |
| 4,5 | umie wskazać znaczenie czynników losowych w uzyskaniu skuteczniejszej od deterministycznej metody rozwiązania problemu | |
| 5,0 | w pełni rozumie ograniczenia i bariery związane ze złożonością czasową i pamięciową algorytmów rozwiązujących problemy obliczeniowe | |
| I_1A_C/5_U02 umie dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego | 2,0 | nie spełnia kryteriów okreslonych dla oceny 3 |
| 3,0 | potrafi wybrać właściwą dla danego problemu strukturę danych spośród wskazanych | |
| 3,5 | potrafi wybrać właściwą dla danego problemu strukturę danych na podstawie jego analizy | |
| 4,0 | potrafi dokonać wyboru i racjonalnie uzasadnić na podstawie analizy problemu wybór właściwej dla danego problemu struktury danych spośród wskazanych | |
| 4,5 | potrafi dokonać wyboru i racjonalnie uzasadnić na podstawie analizy problemu wybór właściwej dla danego problemu struktury danych spośród wskazanych | |
| 5,0 | umie w uzasadniony i racjonalny sposób dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego |
Literatura podstawowa
- T.H. Cormen, Ch.E.Leiserson, R.I.Rivest, C.Stein, Wprowadzenia do algorytmów, WNT, Warszawa, 2002
- M.Sipser, Wprowadzenie do teorii obliczeń, WNT, Warszawa, 2009
Literatura dodatkowa
- D.Harel, Rzecz o istocie informatyki - algorytmika, WNT, Warszawa, 2000
- N.Wirth, Algorytmy + struktury danych = programy, WNT, Warszawa, 2001
- A.V.Aho, J.E.Hopcroft, J.D.Ullman, Algorytmy i struktury danych, Helion, Gliwice, 2003