Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Wydział Informatyki - Informatyka (S1)

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

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
wykładyW3 30 1,90,62egzamin
laboratoriaL3 15 1,10,38zaliczenie

Wymagania wstępne

KODWymaganie wstępne
W-1Podstawowe umiejętności programowania w języku C/C++
W-2Zaliczenie kursu "Wstęp do algorytmizacji" lub równoważnego
W-3Zaliczenie kursu "Matematyka dyskretna" lub równoważnego
W-4Znajomość podstaw informatyki

Cele przedmiotu

KODCel modułu/przedmiotu
C-1Zapoznanie z zasadami tworzenia złożonych struktur danych
C-2Zapoznanie z cechami konstrukcyjnymi najważniejszych struktur danych
C-3Zapoznanie z klasyfikacją i metodami oceny złożoności obliczeniowej
C-4Nabycie umiejętności wyboru struktur danych odpowiednich dla problemu algorytmicznego i środowiska implementacyjnego

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

KODTreść programowaGodziny
laboratoria
T-L-1Wprowadzenie. Tablice wskaźników i sortowanie2
T-L-2Lista liniowa, dwukierunkowa i cykliczna2
T-L-3Zwykłe drzewo poszukiwań binarnych2
T-L-4Dokładne wyważanie drzewa BST, rotacje, algorytm DSW2
T-L-5Samoorganizujące się drzewa BST, drzewo "splay"2
T-L-6Wstawianie i usuwanie węzłów w drzewie AVL4
T-L-7Podsumowanie cyklu laboratoryjnego1
15
wykłady
T-W-1Pojęcia podstawowe (typy danych, operatory,moc typu)1
T-W-2Złożone struktury/typy danych (typ wyliczeniowy, typ zbiorowy, tablica, rekord, stos, kolejka, kolejka priorytetowa, plik sekwencyjny, listy)5
T-W-3Drzewa 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-4Drzewa wielokierunkowe (B-drzewa, B*-drzewa, B+-drzewa, drzewa prefiksowe, kopce dwumianowe, a-b drzewa)4
T-W-5Mieszanie (funkcje mieszające, struktury danych wykorzystywane do implementacji tablic mieszania, rozwiązywanie i usuwanie problemów kolizji)2
T-W-6Grafy (reprezentacja grafów, przechodzenie grafów, grafy ważone, grafy acykliczne, drzewa rozpinające grafów, algorytmy wyszukiwania ścieżek)5
T-W-7Zł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

KODForma aktywnościGodziny
laboratoria
A-L-1Implementacja algorytmów obsługujących struktury danych podczas zajęć laboratoryjnych - udział w zajęciach dydaktycznych15
A-L-2Przygotowanie do rozwiązania wskazanych problemów implementacyjnych10
A-L-3Optymalizacja rozwiązań uzyskanych podczas zajęć laboratoryjnych5
A-L-4Udział w konsultacjach2
32
wykłady
A-W-1Udział w wykładach30
A-W-2Analiza i rozwiązywanie problemów rozszerzających materiał wykładowy (praca własna)12
A-W-3Przygotowanie się do egzaminu i udział w egzaminie10
A-W-4Konsultacje4
56

Metody nauczania / narzędzia dydaktyczne

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

Sposoby oceny

KODSposób oceny
S-1Ocena formująca: Sprawdzian przygotowania do zajęć laboratoryjnych
S-2Ocena formująca: Ocena wykonania poszczególnych implementacji
S-3Ocena podsumowująca: Egzamin pisemny z zadaniami i problemami otwartymi

Zamierzone efekty kształcenia - wiedza

Zamierzone efekty kształceniaOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
I_1A_C/05_W01
zna zasady tworzenia prostych i złożonych typów danych
I_1A_W05T1A_W03, T1A_W07InzA_W02C-1, C-2T-W-4, T-W-5, T-W-6, T-W-1, T-W-2, T-W-3, T-L-2, T-L-3, T-L-4, T-L-5, T-L-1M-1, M-2S-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_W05T1A_W03, T1A_W07InzA_W02C-2, C-3, C-4T-W-4, T-W-5, T-W-7, T-W-3, T-L-6, T-L-2, T-L-3, T-L-4, T-L-5, T-L-1M-1, M-2S-1, S-3

Zamierzone efekty kształcenia - umiejętności

Zamierzone efekty kształceniaOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
I_1A_C/05_U01
ma świadomość barier obliczeniowych związanych ze złożonością problemów obliczeniowych
I_1A_U19T1A_U13, T1A_U15, T1A_U16InzA_U05, InzA_U07, InzA_U08C-4T-W-7M-1, M-2S-2
I_1A_C/05_U02
umie dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego
I_1A_U19T1A_U13, T1A_U15, T1A_U16InzA_U05, InzA_U07, InzA_U08C-3, C-4T-W-4, T-W-5, T-W-7, T-W-6, T-W-3, T-L-2, T-L-3, T-L-4, T-L-5M-1, M-2S-1, S-3

Kryterium oceny - wiedza

Efekt kształceniaOcenaKryterium oceny
I_1A_C/05_W01
zna zasady tworzenia prostych i złożonych typów danych
2,0nie spełnia kryteriów określonych dla oceny 3,0
3,0potrafi wymienić i zdefiniować wybrane podstawowe pojecia dotyczace prostych i złożonych typów danych
3,5potrafi wymienić i zdefiniować wszystkie podstawowe pojecia dotyczace tworzenia i własności prostych i złożonych typów danych
4,0zna 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,5zna 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,0opanował 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,0nie spełnia kryteriów określonych dla oceny 3,0
3,0potrafi okreśić sposoby postępowania podczas wstawiania usuwania i wyszukiwania określonych elementów składowych w wybranych strukturach danych
3,5potrafi 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,0potrafi ocenić złożoność obliczeniową algorytmów manipulowania wybranymi strukturami danych
4,5potrafi ocenić złożoność obliczeniową algorytmów manipulowania dowolnymi strukturami danych ujętymi w programie kursu
5,0opanował 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łceniaOcenaKryterium oceny
I_1A_C/05_U01
ma świadomość barier obliczeniowych związanych ze złożonością problemów obliczeniowych
2,0nie spełnia kryteriów okreslonych dla oceny 3
3,0umie ocenić złożność elementarnych algorytmów i odróżniać algorytmy "łatwe" od "trudnych" obliczeniowo
3,5potrafi porównać algorytmy rozwiązujące ten sam problem ze względu na ich zlożoność
4,0potrafi powiązać złożoność algorytmu z cechami środowiska, w którym są wykonywane obliczenia
4,5umie wskazać znaczenie czynników losowych w uzyskaniu skuteczniejszej od deterministycznej metody rozwiązania problemu
5,0w 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,0nie spełnia kryteriów okreslonych dla oceny 3
3,0potrafi wybrać właściwą dla danego problemu strukturę danych spośród wskazanych
3,5potrafi wybrać właściwą dla danego problemu strukturę danych na podstawie jego analizy
4,0potrafi dokonać wyboru i racjonalnie uzasadnić na podstawie analizy problemu wybór właściwej dla danego problemu struktury danych spośród wskazanych
4,5potrafi dokonać wyboru i racjonalnie uzasadnić na podstawie analizy problemu wybór właściwej dla danego problemu struktury danych spośród wskazanych
5,0umie w uzasadniony i racjonalny sposób dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego

Literatura podstawowa

  1. T.H. Cormen, Ch.E.Leiserson, R.I.Rivest, C.Stein, Wprowadzenia do algorytmów, WNT, Warszawa, 2002
  2. M.Sipser, Wprowadzenie do teorii obliczeń, WNT, Warszawa, 2009

Literatura dodatkowa

  1. D.Harel, Rzecz o istocie informatyki - algorytmika, WNT, Warszawa, 2000
  2. N.Wirth, Algorytmy + struktury danych = programy, WNT, Warszawa, 2001
  3. A.V.Aho, J.E.Hopcroft, J.D.Ullman, Algorytmy i struktury danych, Helion, Gliwice, 2003

Treści programowe - laboratoria

KODTreść programowaGodziny
T-L-1Wprowadzenie. Tablice wskaźników i sortowanie2
T-L-2Lista liniowa, dwukierunkowa i cykliczna2
T-L-3Zwykłe drzewo poszukiwań binarnych2
T-L-4Dokładne wyważanie drzewa BST, rotacje, algorytm DSW2
T-L-5Samoorganizujące się drzewa BST, drzewo "splay"2
T-L-6Wstawianie i usuwanie węzłów w drzewie AVL4
T-L-7Podsumowanie cyklu laboratoryjnego1
15

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Pojęcia podstawowe (typy danych, operatory,moc typu)1
T-W-2Złożone struktury/typy danych (typ wyliczeniowy, typ zbiorowy, tablica, rekord, stos, kolejka, kolejka priorytetowa, plik sekwencyjny, listy)5
T-W-3Drzewa 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-4Drzewa wielokierunkowe (B-drzewa, B*-drzewa, B+-drzewa, drzewa prefiksowe, kopce dwumianowe, a-b drzewa)4
T-W-5Mieszanie (funkcje mieszające, struktury danych wykorzystywane do implementacji tablic mieszania, rozwiązywanie i usuwanie problemów kolizji)2
T-W-6Grafy (reprezentacja grafów, przechodzenie grafów, grafy ważone, grafy acykliczne, drzewa rozpinające grafów, algorytmy wyszukiwania ścieżek)5
T-W-7Zł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

Formy aktywności - laboratoria

KODForma aktywnościGodziny
A-L-1Implementacja algorytmów obsługujących struktury danych podczas zajęć laboratoryjnych - udział w zajęciach dydaktycznych15
A-L-2Przygotowanie do rozwiązania wskazanych problemów implementacyjnych10
A-L-3Optymalizacja rozwiązań uzyskanych podczas zajęć laboratoryjnych5
A-L-4Udział w konsultacjach2
32
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1Udział w wykładach30
A-W-2Analiza i rozwiązywanie problemów rozszerzających materiał wykładowy (praca własna)12
A-W-3Przygotowanie się do egzaminu i udział w egzaminie10
A-W-4Konsultacje4
56
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_C/05_W01zna zasady tworzenia prostych i złożonych typów danych
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_W05ma wiedzę w zakresie algorytmizacji i zasad tworzenia struktur danych
Odniesienie do efektów zdefiniowanych dla obszaru kształceniaT1A_W03ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu studiowanego kierunku studiów
T1A_W07zna podstawowe metody, techniki, narzędzia i materiały stosowane przy rozwiązywaniu prostych zadań inżynierskich z zakresu studiowanego kierunku studiów
Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraInzA_W02zna podstawowe metody, techniki, narzędzia i materiały stosowane przy rozwiązywaniu prostych zadań inżynierskich z zakresu studiowanego kierunku studiów
Cel przedmiotuC-1Zapoznanie z zasadami tworzenia złożonych struktur danych
C-2Zapoznanie z cechami konstrukcyjnymi najważniejszych struktur danych
Treści programoweT-W-4Drzewa wielokierunkowe (B-drzewa, B*-drzewa, B+-drzewa, drzewa prefiksowe, kopce dwumianowe, a-b drzewa)
T-W-5Mieszanie (funkcje mieszające, struktury danych wykorzystywane do implementacji tablic mieszania, rozwiązywanie i usuwanie problemów kolizji)
T-W-6Grafy (reprezentacja grafów, przechodzenie grafów, grafy ważone, grafy acykliczne, drzewa rozpinające grafów, algorytmy wyszukiwania ścieżek)
T-W-1Pojęcia podstawowe (typy danych, operatory,moc typu)
T-W-2Złożone struktury/typy danych (typ wyliczeniowy, typ zbiorowy, tablica, rekord, stos, kolejka, kolejka priorytetowa, plik sekwencyjny, listy)
T-W-3Drzewa 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ń)
T-L-2Lista liniowa, dwukierunkowa i cykliczna
T-L-3Zwykłe drzewo poszukiwań binarnych
T-L-4Dokładne wyważanie drzewa BST, rotacje, algorytm DSW
T-L-5Samoorganizujące się drzewa BST, drzewo "splay"
T-L-1Wprowadzenie. Tablice wskaźników i sortowanie
Metody nauczaniaM-1Wykład informacyjno-konwersatoryjny
M-2Ćwiczenia laboratoryjne
Sposób ocenyS-1Ocena formująca: Sprawdzian przygotowania do zajęć laboratoryjnych
S-3Ocena podsumowująca: Egzamin pisemny z zadaniami i problemami otwartymi
Kryteria ocenyOcenaKryterium oceny
2,0nie spełnia kryteriów określonych dla oceny 3,0
3,0potrafi wymienić i zdefiniować wybrane podstawowe pojecia dotyczace prostych i złożonych typów danych
3,5potrafi wymienić i zdefiniować wszystkie podstawowe pojecia dotyczace tworzenia i własności prostych i złożonych typów danych
4,0zna 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,5zna 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,0opanował w pełnym zakresie materiał merytoryczny dotyczący zasad tworzenia prostych i złożonych typów (struktur) danych
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_C/05_W02zna algorytmy manipulujące określonymi strukturami danych i sposoby oceny ich złożoności obliczeniowej
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_W05ma wiedzę w zakresie algorytmizacji i zasad tworzenia struktur danych
Odniesienie do efektów zdefiniowanych dla obszaru kształceniaT1A_W03ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu studiowanego kierunku studiów
T1A_W07zna podstawowe metody, techniki, narzędzia i materiały stosowane przy rozwiązywaniu prostych zadań inżynierskich z zakresu studiowanego kierunku studiów
Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraInzA_W02zna podstawowe metody, techniki, narzędzia i materiały stosowane przy rozwiązywaniu prostych zadań inżynierskich z zakresu studiowanego kierunku studiów
Cel przedmiotuC-2Zapoznanie z cechami konstrukcyjnymi najważniejszych struktur danych
C-3Zapoznanie z klasyfikacją i metodami oceny złożoności obliczeniowej
C-4Nabycie umiejętności wyboru struktur danych odpowiednich dla problemu algorytmicznego i środowiska implementacyjnego
Treści programoweT-W-4Drzewa wielokierunkowe (B-drzewa, B*-drzewa, B+-drzewa, drzewa prefiksowe, kopce dwumianowe, a-b drzewa)
T-W-5Mieszanie (funkcje mieszające, struktury danych wykorzystywane do implementacji tablic mieszania, rozwiązywanie i usuwanie problemów kolizji)
T-W-7Zł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ść)
T-W-3Drzewa 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ń)
T-L-6Wstawianie i usuwanie węzłów w drzewie AVL
T-L-2Lista liniowa, dwukierunkowa i cykliczna
T-L-3Zwykłe drzewo poszukiwań binarnych
T-L-4Dokładne wyważanie drzewa BST, rotacje, algorytm DSW
T-L-5Samoorganizujące się drzewa BST, drzewo "splay"
T-L-1Wprowadzenie. Tablice wskaźników i sortowanie
Metody nauczaniaM-1Wykład informacyjno-konwersatoryjny
M-2Ćwiczenia laboratoryjne
Sposób ocenyS-1Ocena formująca: Sprawdzian przygotowania do zajęć laboratoryjnych
S-3Ocena podsumowująca: Egzamin pisemny z zadaniami i problemami otwartymi
Kryteria ocenyOcenaKryterium oceny
2,0nie spełnia kryteriów określonych dla oceny 3,0
3,0potrafi okreśić sposoby postępowania podczas wstawiania usuwania i wyszukiwania określonych elementów składowych w wybranych strukturach danych
3,5potrafi 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,0potrafi ocenić złożoność obliczeniową algorytmów manipulowania wybranymi strukturami danych
4,5potrafi ocenić złożoność obliczeniową algorytmów manipulowania dowolnymi strukturami danych ujętymi w programie kursu
5,0opanował 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
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_C/05_U01ma świadomość barier obliczeniowych związanych ze złożonością problemów obliczeniowych
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_U19ma umiejętność wyboru algorytmu i struktur danych do rozwiązania określonego zadania inżynierskiego
Odniesienie do efektów zdefiniowanych dla obszaru kształceniaT1A_U13potrafi dokonać krytycznej analizy sposobu funkcjonowania i ocenić - zwłaszcza w powiązaniu ze studiowanym kierunkiem studiów - istniejące rozwiązania techniczne, w szczególności urządzenia, obiekty, systemy, procesy, usługi
T1A_U15potrafi ocenić przydatność rutynowych metod i narzędzi służących do rozwiązania prostego zadania inżynierskiego o charakterze praktycznym, charakterystycznego dla studiowanego kierunku studiów oraz wybrać i zastosować właściwą metodę i narzędzia
T1A_U16potrafi - zgodnie z zadaną specyfikacją - zaprojektować oraz zrealizować proste urządzenie, obiekt, system lub proces, typowe dla studiowanego kierunku studiów, używając właściwych metod, technik i narzędzi
Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraInzA_U05potrafi dokonać krytycznej analizy sposobu funkcjonowania i ocenić - zwłaszcza w powiązaniu ze studiowanym kierunkiem studiów - istniejące rozwiązania techniczne, w szczególności urządzenia, obiekty, systemy, procesy, usługi
InzA_U07potrafi ocenić przydatność rutynowych metod i narzędzi służących do rozwiązania prostego zadania inżynierskiego o charakterze praktycznym, charakterystycznego dla studiowanego kierunku studiów oraz wybrać i zastosować właściwą metodę i narzędzia
InzA_U08potrafi - zgodnie z zadaną specyfikacją - zaprojektować proste urządzenie, obiekt, system lub proces, typowe dla studiowanego kierunku studiów, używając właściwych metod, technik i narzędzi
Cel przedmiotuC-4Nabycie umiejętności wyboru struktur danych odpowiednich dla problemu algorytmicznego i środowiska implementacyjnego
Treści programoweT-W-7Zł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ść)
Metody nauczaniaM-1Wykład informacyjno-konwersatoryjny
M-2Ćwiczenia laboratoryjne
Sposób ocenyS-2Ocena formująca: Ocena wykonania poszczególnych implementacji
Kryteria ocenyOcenaKryterium oceny
2,0nie spełnia kryteriów okreslonych dla oceny 3
3,0umie ocenić złożność elementarnych algorytmów i odróżniać algorytmy "łatwe" od "trudnych" obliczeniowo
3,5potrafi porównać algorytmy rozwiązujące ten sam problem ze względu na ich zlożoność
4,0potrafi powiązać złożoność algorytmu z cechami środowiska, w którym są wykonywane obliczenia
4,5umie wskazać znaczenie czynników losowych w uzyskaniu skuteczniejszej od deterministycznej metody rozwiązania problemu
5,0w pełni rozumie ograniczenia i bariery związane ze złożonością czasową i pamięciową algorytmów rozwiązujących problemy obliczeniowe
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_C/05_U02umie dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_U19ma umiejętność wyboru algorytmu i struktur danych do rozwiązania określonego zadania inżynierskiego
Odniesienie do efektów zdefiniowanych dla obszaru kształceniaT1A_U13potrafi dokonać krytycznej analizy sposobu funkcjonowania i ocenić - zwłaszcza w powiązaniu ze studiowanym kierunkiem studiów - istniejące rozwiązania techniczne, w szczególności urządzenia, obiekty, systemy, procesy, usługi
T1A_U15potrafi ocenić przydatność rutynowych metod i narzędzi służących do rozwiązania prostego zadania inżynierskiego o charakterze praktycznym, charakterystycznego dla studiowanego kierunku studiów oraz wybrać i zastosować właściwą metodę i narzędzia
T1A_U16potrafi - zgodnie z zadaną specyfikacją - zaprojektować oraz zrealizować proste urządzenie, obiekt, system lub proces, typowe dla studiowanego kierunku studiów, używając właściwych metod, technik i narzędzi
Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraInzA_U05potrafi dokonać krytycznej analizy sposobu funkcjonowania i ocenić - zwłaszcza w powiązaniu ze studiowanym kierunkiem studiów - istniejące rozwiązania techniczne, w szczególności urządzenia, obiekty, systemy, procesy, usługi
InzA_U07potrafi ocenić przydatność rutynowych metod i narzędzi służących do rozwiązania prostego zadania inżynierskiego o charakterze praktycznym, charakterystycznego dla studiowanego kierunku studiów oraz wybrać i zastosować właściwą metodę i narzędzia
InzA_U08potrafi - zgodnie z zadaną specyfikacją - zaprojektować proste urządzenie, obiekt, system lub proces, typowe dla studiowanego kierunku studiów, używając właściwych metod, technik i narzędzi
Cel przedmiotuC-3Zapoznanie z klasyfikacją i metodami oceny złożoności obliczeniowej
C-4Nabycie umiejętności wyboru struktur danych odpowiednich dla problemu algorytmicznego i środowiska implementacyjnego
Treści programoweT-W-4Drzewa wielokierunkowe (B-drzewa, B*-drzewa, B+-drzewa, drzewa prefiksowe, kopce dwumianowe, a-b drzewa)
T-W-5Mieszanie (funkcje mieszające, struktury danych wykorzystywane do implementacji tablic mieszania, rozwiązywanie i usuwanie problemów kolizji)
T-W-7Zł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ść)
T-W-6Grafy (reprezentacja grafów, przechodzenie grafów, grafy ważone, grafy acykliczne, drzewa rozpinające grafów, algorytmy wyszukiwania ścieżek)
T-W-3Drzewa 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ń)
T-L-2Lista liniowa, dwukierunkowa i cykliczna
T-L-3Zwykłe drzewo poszukiwań binarnych
T-L-4Dokładne wyważanie drzewa BST, rotacje, algorytm DSW
T-L-5Samoorganizujące się drzewa BST, drzewo "splay"
Metody nauczaniaM-1Wykład informacyjno-konwersatoryjny
M-2Ćwiczenia laboratoryjne
Sposób ocenyS-1Ocena formująca: Sprawdzian przygotowania do zajęć laboratoryjnych
S-3Ocena podsumowująca: Egzamin pisemny z zadaniami i problemami otwartymi
Kryteria ocenyOcenaKryterium oceny
2,0nie spełnia kryteriów okreslonych dla oceny 3
3,0potrafi wybrać właściwą dla danego problemu strukturę danych spośród wskazanych
3,5potrafi wybrać właściwą dla danego problemu strukturę danych na podstawie jego analizy
4,0potrafi dokonać wyboru i racjonalnie uzasadnić na podstawie analizy problemu wybór właściwej dla danego problemu struktury danych spośród wskazanych
4,5potrafi dokonać wyboru i racjonalnie uzasadnić na podstawie analizy problemu wybór właściwej dla danego problemu struktury danych spośród wskazanych
5,0umie w uzasadniony i racjonalny sposób dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego