Wydział Informatyki - Informatyka (N1)
specjalność: systemy komputerowe i oprogramowanie
Sylabus przedmiotu Struktury danych i złożoność obliczeniowa:
Informacje podstawowe
Kierunek studiów | Informatyka | ||
---|---|---|---|
Forma studiów | studia niestacjonarne | 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. Tabliice 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 | 2 |
T-L-7 | Podsumowanie cyklu laboratoryjnego | 2 |
T-L-8 | Wprowadzenie. Tablice wskaźników i sortowanie | 2 |
16 | ||
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) | 1 |
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ń) | 4 |
T-W-4 | Drzewa wielokierunkowe (B-drzewa, B*-drzewa, B+-drzewa, drzewa prefiksowe, kopce dwumianowe, a-b drzewa) | 2 |
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) | 2 |
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ść) | 2 |
14 |
Obciążenie pracą studenta - formy aktywności
KOD | Forma aktywności | Godziny |
---|---|---|
laboratoria | ||
A-L-1 | Udział w zajęciach | 16 |
A-L-2 | Implementacja algorytmów obsługujących struktury danych podczas zajęć laboratoryjnych - udział w zajęciach dydaktycznych | 5 |
A-L-3 | Przygotowanie do rozwiązania wskazanych problemów implementacyjnych | 5 |
A-L-4 | Optymalizacja rozwiązań uzyskanych podczas zajęć laboratoryjnych | 5 |
A-L-5 | Udział w konsultacjach | 2 |
33 | ||
wykłady | ||
A-W-1 | Udział w wykładach | 14 |
A-W-2 | Analiza i rozwiązywanie problemów rozszerzających materiał wykładowy (praca własna) | 10 |
A-W-3 | Przygotowanie się do egzaminu i udział w egzaminie | 6 |
A-W-4 | Konsultacje | 4 |
34 |
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/05_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-8, T-L-3, T-L-4, T-L-2, T-L-5, T-W-1, T-W-5, T-W-2, T-W-6, T-W-4, T-W-3 | M-2, M-1 | S-1, S-3 |
I_1A_C/05_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-L-8, T-L-3, T-L-4, T-L-6, T-L-2, T-L-5, T-W-7, T-W-5, T-W-4, T-W-3 | M-2, M-1 | 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/05_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/05_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-3, T-L-4, T-L-2, T-L-5, T-W-7, T-W-5, T-W-6, T-W-4, T-W-3 | M-2, M-1 | S-1, S-3 |
Kryterium oceny - wiedza
Efekt kształcenia | Ocena | Kryterium oceny |
---|---|---|
I_1A_C/05_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/05_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/05_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/05_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