Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Wydział Biotechnologii i Hodowli Zwierząt - Bioinformatyka (S1)
specjalność: Systemy informatyczne w biologii

Sylabus przedmiotu Struktury danych:

Informacje podstawowe

Kierunek studiów Bioinformatyka
Forma studiów studia stacjonarne Poziom pierwszego stopnia
Tytuł zawodowy absolwenta inżynier
Obszary studiów nauk przyrodniczych, nauk technicznych, studiów inżynierskich
Profil ogólnoakademicki
Moduł
Przedmiot Struktury danych
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) 2,0 ECTS (formy) 2,0
Forma zaliczenia zaliczenie Język polski
Blok obieralny 7 Grupa obieralna 4

Formy dydaktyczne

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
laboratoriaL3 15 1,00,41zaliczenie
wykładyW3 15 1,00,59zaliczenie

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-1Lista liniowa, dwukierunkowa i cykliczna2
T-L-2Zwykłe drzewo poszukiwań binarnych2
T-L-3Dokładne wyważanie drzewa BST, rotacje, algorytm DSW2
T-L-4Samoorganizujące się drzewa BST, drzewo "splay"2
T-L-5Wstawianie i usuwanie węzłów w drzewie AVL4
T-L-6Podsumowanie cyklu laboratoryjnego1
T-L-7Wprowadzenie. Tablice wskaźników i sortowanie2
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)1
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ń)4
T-W-4Drzewa wielokierunkowe (B-drzewa, B*-drzewa, B+-drzewa, drzewa prefiksowe, kopce dwumianowe, a-b drzewa)3
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)2
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ść)2
15

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 implementacyjnych8
A-L-3Optymalizacja rozwiązań uzyskanych podczas zajęć laboratoryjnych5
A-L-4Udział w konsultacjach2
30
wykłady
A-W-1Udział w wykładach15
A-W-2Analiza i rozwiązywanie problemów rozszerzających materiał wykładowy (praca własna)6
A-W-3Przygotowanie się do egzaminu i udział w egzaminie5
A-W-4Konsultacje4
30

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
BI_1A_BI-S-O4.3_W01
zna zasady tworzenia prostych i złożonych typów danych
BI_1A_W10P1A_W04, P1A_W07, T1A_W02, T1A_W03, T1A_W04, T1A_W05, T1A_W07InzA_W01, InzA_W02C-1, C-2T-L-1, T-L-2, T-L-3, T-L-4, T-L-7, T-W-1, T-W-2, T-W-3, T-W-4, T-W-5, T-W-6M-1, M-2S-1, S-3
BI_1A_BI-S-O4.3_W02
zna algorytmy manipulujące określonymi strukturami danych i sposoby oceny ich złożoności obliczeniowej
BI_1A_W10P1A_W04, P1A_W07, T1A_W02, T1A_W03, T1A_W04, T1A_W05, T1A_W07InzA_W01, InzA_W02C-2, C-3, C-4T-L-1, T-L-2, T-L-3, T-L-4, T-L-5, T-L-7, T-W-3, T-W-4, T-W-5, T-W-7M-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
BI_1A_BI-S-O4.3_U01
ma świadomość barier obliczeniowych związanych ze złożonością problemów obliczeniowych
BI_1A_U10P1A_U03, P1A_U11, P1A_U12, T1A_U01, T1A_U05, T1A_U08, T1A_U10, T1A_U15, T1A_U16C-4T-W-7M-1, M-2S-2
BI_1A_BI-S-O4.3_U02
umie dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego
BI_1A_U11P1A_U05, P1A_U09, T1A_U01, T1A_U13, T1A_U16InzA_U03, InzA_U05, InzA_U08C-3, C-4T-L-1, T-L-2, T-L-3, T-L-4, T-W-3, T-W-4, T-W-5, T-W-6, T-W-7M-1, M-2S-1, S-3

Kryterium oceny - wiedza

Efekt kształceniaOcenaKryterium oceny
BI_1A_BI-S-O4.3_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
BI_1A_BI-S-O4.3_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
BI_1A_BI-S-O4.3_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
BI_1A_BI-S-O4.3_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-1Lista liniowa, dwukierunkowa i cykliczna2
T-L-2Zwykłe drzewo poszukiwań binarnych2
T-L-3Dokładne wyważanie drzewa BST, rotacje, algorytm DSW2
T-L-4Samoorganizujące się drzewa BST, drzewo "splay"2
T-L-5Wstawianie i usuwanie węzłów w drzewie AVL4
T-L-6Podsumowanie cyklu laboratoryjnego1
T-L-7Wprowadzenie. Tablice wskaźników i sortowanie2
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)1
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ń)4
T-W-4Drzewa wielokierunkowe (B-drzewa, B*-drzewa, B+-drzewa, drzewa prefiksowe, kopce dwumianowe, a-b drzewa)3
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)2
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ść)2
15

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 implementacyjnych8
A-L-3Optymalizacja rozwiązań uzyskanych podczas zajęć laboratoryjnych5
A-L-4Udział w konsultacjach2
30
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1Udział w wykładach15
A-W-2Analiza i rozwiązywanie problemów rozszerzających materiał wykładowy (praca własna)6
A-W-3Przygotowanie się do egzaminu i udział w egzaminie5
A-W-4Konsultacje4
30
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaBI_1A_BI-S-O4.3_W01zna zasady tworzenia prostych i złożonych typów danych
Odniesienie do efektów kształcenia dla kierunku studiówBI_1A_W10ma wiedzę z zakresu inżynierii systemów informacyjnych ze szczególnym uwzględnieniem systemów informatycznych oraz zna podstawowe metody gromadzenia i przetwarzania danych i informacji
Odniesienie do efektów zdefiniowanych dla obszaru kształceniaP1A_W04ma wiedzę w zakresie najważniejszych problemów z zakresu dziedzin nauki i dyscyplin naukowych, właściwych dla studiowanego kierunku studiów oraz zna ich powiązania z innymi dyscyplinami przyrodniczymi
P1A_W07ma wiedzę w zakresie podstawowych technik i narzędzi badawczych stosowanych w zakresie dziedzin nauki i dyscyplin naukowych, właściwych dla studiowanego kierunku studiów
T1A_W02ma podstawową wiedzę w zakresie kierunków studiów powiązanych ze studiowanym kierunkiem studiów
T1A_W03ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu studiowanego kierunku studiów
T1A_W04ma szczegółową wiedzę związaną z wybranymi zagadnieniami z zakresu studiowanego kierunku studiów
T1A_W05ma podstawową wiedzę o trendach rozwojowych z zakresu dziedzin nauki i dyscyplin naukowych, właściwych dla 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_W01ma podstawową wiedzę o cyklu życia urządzeń, obiektów i systemów technicznych
InzA_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-L-1Lista liniowa, dwukierunkowa i cykliczna
T-L-2Zwykłe drzewo poszukiwań binarnych
T-L-3Dokładne wyważanie drzewa BST, rotacje, algorytm DSW
T-L-4Samoorganizujące się drzewa BST, drzewo "splay"
T-L-7Wprowadzenie. Tablice wskaźników i sortowanie
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-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)
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łceniaBI_1A_BI-S-O4.3_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ówBI_1A_W10ma wiedzę z zakresu inżynierii systemów informacyjnych ze szczególnym uwzględnieniem systemów informatycznych oraz zna podstawowe metody gromadzenia i przetwarzania danych i informacji
Odniesienie do efektów zdefiniowanych dla obszaru kształceniaP1A_W04ma wiedzę w zakresie najważniejszych problemów z zakresu dziedzin nauki i dyscyplin naukowych, właściwych dla studiowanego kierunku studiów oraz zna ich powiązania z innymi dyscyplinami przyrodniczymi
P1A_W07ma wiedzę w zakresie podstawowych technik i narzędzi badawczych stosowanych w zakresie dziedzin nauki i dyscyplin naukowych, właściwych dla studiowanego kierunku studiów
T1A_W02ma podstawową wiedzę w zakresie kierunków studiów powiązanych ze studiowanym kierunkiem studiów
T1A_W03ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu studiowanego kierunku studiów
T1A_W04ma szczegółową wiedzę związaną z wybranymi zagadnieniami z zakresu studiowanego kierunku studiów
T1A_W05ma podstawową wiedzę o trendach rozwojowych z zakresu dziedzin nauki i dyscyplin naukowych, właściwych dla 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_W01ma podstawową wiedzę o cyklu życia urządzeń, obiektów i systemów technicznych
InzA_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-L-1Lista liniowa, dwukierunkowa i cykliczna
T-L-2Zwykłe drzewo poszukiwań binarnych
T-L-3Dokładne wyważanie drzewa BST, rotacje, algorytm DSW
T-L-4Samoorganizujące się drzewa BST, drzewo "splay"
T-L-5Wstawianie i usuwanie węzłów w drzewie AVL
T-L-7Wprowadzenie. Tablice wskaźników i sortowanie
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-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ść)
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łceniaBI_1A_BI-S-O4.3_U01ma świadomość barier obliczeniowych związanych ze złożonością problemów obliczeniowych
Odniesienie do efektów kształcenia dla kierunku studiówBI_1A_U10rozróżnia modele cyklu życia oprogramowania, ocenia poprawność wyników programowania
Odniesienie do efektów zdefiniowanych dla obszaru kształceniaP1A_U03wykorzystuje dostępne źródła informacji, w tym źródła elektroniczne
P1A_U11uczy się samodzielnie w sposób ukierunkowany
P1A_U12ma umiejętności językowe w zakresie dziedzin nauki i dyscyplin naukowych, właściwych dla studiowanego kierunku studiów, zgodne z wymaganiami określonymi dla poziomu B2 Europejskiego Systemu Opisu Kształcenia Językowego
T1A_U01potrafi pozyskiwać informacje z literatury, baz danych oraz innych właściwie dobranych źródeł, także w języku angielskim lub innym języku obcym uznawanym za język komunikacji międzynarodowej w zakresie studiowanego kierunku studiów; potrafi integrować uzyskane informacje, dokonywać ich interpretacji, a także wyciągać wnioski oraz formułować i uzasadniać opinie
T1A_U05ma umiejętność samokształcenia się
T1A_U08potrafi planować i przeprowadzać eksperymenty, w tym pomiary i symulacje komputerowe, interpretować uzyskane wyniki i wyciągać wnioski
T1A_U10potrafi - przy formułowaniu i rozwiązywaniu zadań inżynierskich - dostrzegać ich aspekty systemowe i pozatechniczne
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
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łceniaBI_1A_BI-S-O4.3_U02umie dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego
Odniesienie do efektów kształcenia dla kierunku studiówBI_1A_U11korzysta z różnego rodzaju systemów komputerowych, ocenia różnice między nimi
Odniesienie do efektów zdefiniowanych dla obszaru kształceniaP1A_U05stosuje podstawowe metody statystyczne oraz algorytmy i techniki informatyczne do opisu zjawisk i analizy danych
P1A_U09umie przygotować w języku polskim i języku obcym dobrze udokumentowane opracowanie problemów z zakresu dziedzin nauki i dyscyplin naukowych, właściwych dla studiowanego kierunku studiów
T1A_U01potrafi pozyskiwać informacje z literatury, baz danych oraz innych właściwie dobranych źródeł, także w języku angielskim lub innym języku obcym uznawanym za język komunikacji międzynarodowej w zakresie studiowanego kierunku studiów; potrafi integrować uzyskane informacje, dokonywać ich interpretacji, a także wyciągać wnioski oraz formułować i uzasadniać opinie
T1A_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_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_U03potrafi - przy formułowaniu i rozwiązywaniu zadań inżynierskich - dostrzegać ich aspekty systemowe i pozatechniczne
InzA_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_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-L-1Lista liniowa, dwukierunkowa i cykliczna
T-L-2Zwykłe drzewo poszukiwań binarnych
T-L-3Dokładne wyważanie drzewa BST, rotacje, algorytm DSW
T-L-4Samoorganizujące się drzewa BST, drzewo "splay"
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-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-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-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