Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych (I)
Koordynator przedmiotu:
Roman PODRAZA
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne - podstawowe
Kod przedmiotu:
AISDI
Semestr nominalny:
1 / rok ak. 2018/2019
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Udział w wykładach: 15 * 2 h = 30 h Udział w ćwiczeniach: 7 * 2 h + 1h = 15 h Udział w laboratorium: 7 * 2 h = 14 h Przygotowanie do wykładu, przeglądanie materiałów internetowych , podręczników: 15 h Przygotowanie do ćwiczeń, rozwiązywanie zadań domowych: 20 h Przygotowanie do laboratorium, rozwiązywanie zadań laboratoryjnych w domu: 25 h Przygotowanie do sprawdzianu na ćwiczeniach: 3 h Przygotowanie do egzaminu: 6 h Razem: 30 h + 15 h + 14 h + 15 h + 20 h + 25 h + 3 h + 6 h = 128 h
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Udział w wykładach: 15 * 2 h = 30 h Udział w ćwiczeniach: 7 * 2 h + 1h = 15 h Udział w laboratorium: 7 * 2 h = 14 h w sumie 59h co daje ok. 2 ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Udział w ćwiczeniach: 7 * 2 h + 1h = 15 h Udział w laboratorium: 7 * 2 h = 14 h Przygotowanie do ćwiczeń, rozwiązywanie zadań domowych: 20 h Przygotowanie do laboratorium, rozwiązywanie zadań laboratoryjnych w domu: 25 h w sumie 74h co daje ok. 2,5 ECTS
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia15h
  • Laboratorium15h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Znajomość programowania w C++
Limit liczby studentów:
120
Cel przedmiotu:
Praktyczne zapoznanie studentów z wybranymi typowymi strukturami danych i przykładowymi algorytmami operującymi na tych strukturach oraz wykorzystaniem struktur danych w kontekście projektowania obiektowego programów komputerowych.
Treści kształcenia:
Treść wykładu: 1. Przegląd struktur danych: typ danych, system typów danych, obiekt, struktura danych, liniowe struktury danych, drzewiaste struktury danych, grafowe struktury danych, koszt i rząd kosztu przetwarzania struktur (2h). 2. Liniowe struktury danych: listy jednokierunkowe i dwukierunkowe, pierścienie, stosy, kolejki i kolejki priorytetowe z operacjami przeglądania struktury, wyszukiwania, wstawiania i usuwania elementu. Biblioteka STL w C++. (6h). 3. Algorytmy sortowania: Insertion Sort, Selection Sort, Bubble Sort, Quicksort, Merge Sort, Heap Sort, Straight Radix Sort, Radix Exchenge Sort, Shell Sort (6h). 4. Algorytmy wyszukiwania: wyszukiwanie liniowe, binarne, interpolacyjne, z podziałem Fibonacciego, zastosowania funkcji mieszającej (ang. hashing) (2h). 5. Algorytmy rekurencyjne, zasada „dziel i rządź” (2h). 6. Drzewa: drzewa binarne BST, Binary Tree Sort, drzewa o dowolnej liczbie następników, drzewa zrównoważone (AVL, czerwono-czarne, 2-3-4, B, BB) z operacjami przeglądania struktury, wyszukiwania, wstawiania i usuwania elementu (8h). 7. Grafy: metody implementacji grafów, przeglądanie w głąb (DFS), przeglądanie wszerz (BFS), algorytm badania osiągalności węzłów, wyznaczenie wszystkich ścieżek, wyszukiwanie najkrótszej ścieżki w grafie, algorytm Dijkstry (4h). Zakres ćwiczeń: 1. Szablony (ang. templates) w C++. 2. Operacje na listach jednokierunkowych. 3. Definiowanie typów danych z wykorzystaniem struktur liniowych oraz implementacje wybranych operacji. 4. Projektowanie i implementacja algorytmów rekurencyjnych. 5. Sprawdzian – struktury liniowe i rekurencja. 6. Definiowanie typów danych z wykorzystaniem drzew oraz implementacje wybranych operacji. 7. Wybrane algorytmy grafów. Zakres laboratorium: 1. Zajęcia organizacyjne – instrukcje dotyczące środowiska programowania. 2. Implementacja określonego typu danych (wykazu) przy pomocy tablicy. 3. Implementacja określonego typu danych (wykazu) przy pomocy listy jednokierunkowej. 4. Implementacja określonego typu danych (wykazu) przy pomocy pierścienia dwukierunkowego. 5. Implementacja określonego typu danych (wykazu) przy pomocy drzewa BST. 6. Algorytmy z zastosowaniem rekurencji. 7. Implementacja grafu z wybranymi algorytmami.
Metody oceny:
Ocena egzaminu: 0 - 50 p. Ocena sprawdzianu: 0 - 15 p. Ocena laboratorium: 0 - 30 p. Ocena aktywności na ćwiczeniach: 0 - 5 p. Łącznie: 100 p. (w tym 50 z pracy w semestrze). Skala ocen: ocena 5,0: 91 - 100 p. ocena 4,5: 81 - 90 p. ocena 4,0: 71 - 80 p. (w tym więcej niż 25 p. z pracy w semestrze) ocena 3,5: 61 - 70 p. (w tym więcej niż 25 p. z pracy w semestrze) ocena 3,0: 51 - 60 p. (w tym więcej niż 25 p. z pracy w semestrze) ocena 2,0: poniżej 51 p. łącznie lub poniżej 26 p. z pracy w semestrze)
Egzamin:
tak
Literatura:
[1] L. Nyhoff “ADTs, Data Structures, and Problem Solving with C++”, Prentice-Hall, 2005. [2] M. A. Weiss, “Data Structures and Problem Solving Using C++”, Second Edition, Addison Wesley Longman, Inc., 2000. [3] T. Budd, “Data Structures in C++ Using the Standard Template Library”, Addison Wesley Longman, Inc., 1998. [4] S. Sengupta, C. Ph. Korobkin, “C++ Object-Oriented Data Structures”, Springer-Verlag, 1994. [5] P. Wróblewski, “Algorytmy, struktury danych i techniki programowania”, Helion, 1996. [6] L. Banachowski, K. Diks, W. Rytter, “Algorytmy i struktury danych”, WNT, Warszawa, 1996. [7] N. Wirth, “Algorytmy + struktury danych = programy”, WNT, Warszawa, 1980. [8] B. Stroustrup, “The C++ Programming Language”, Second Edition, Addison Wesley, 1991.
Witryna www przedmiotu:
https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103C-INxxx-ISP-AISDI
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka AISDI_W01
Student, który zaliczył przedmiot, posiada podstawową wiedzę na temat: Liniowych struktur danych: - przeglądania struktury - wyszukiwania, wstawiania i usuwania elementu - sortowania - wydajności stosowania
Weryfikacja: Ocena egzaminu Ocena sprawdzianu Ocena Lab. 2.-4.
Powiązane charakterystyki kierunkowe: K_W09
Powiązane charakterystyki obszarowe: I.P7S_WG
Charakterystyka AISDI_W02
Student, który zaliczył przedmiot, posiada podstawową wiedzę na temat: Podstawowych drzewiastych struktur danych: - przeglądania struktury - wyszukiwania, wstawiania i usuwania elementu - wydajności stosowania
Weryfikacja: Ocena egzaminu Ocena Lab. 6.
Powiązane charakterystyki kierunkowe: K_W09
Powiązane charakterystyki obszarowe: I.P7S_WG
Charakterystyka AISDI_W03
Student, który zaliczył przedmiot, posiada podstawową wiedzę na temat: Formułowania prostych algorytmów rekursywnych
Weryfikacja: Ocena egzaminu Ocena Lab. 5.-6.
Powiązane charakterystyki kierunkowe: K_W09
Powiązane charakterystyki obszarowe: I.P7S_WG
Charakterystyka AISDI_W04
Student, który zaliczył przedmiot, posiada podstawową wiedzę na temat: Struktur grafowych: - sposobów implementacji - przeglądania
Weryfikacja: Ocena egzaminu Ocena Lab. 7.
Powiązane charakterystyki kierunkowe: K_W09
Powiązane charakterystyki obszarowe: I.P7S_WG

Profil ogólnoakademicki - umiejętności

Charakterystyka AISDI_U01
Student, który zaliczył przedmiot, potrafi zaimplementować w języku C++: Funkcje realizujące - operacje przeglądania struktur danych - operacje wyszukiwania elementu w podstawowych struktur danych - operacje wstawiania elementu do podstawowych struktur danych - operacje usuwania elementu z podstawowych struktur danych
Weryfikacja: Ocena egzaminu Ocena sprawdzianu Ocena Lab. 2.-5.
Powiązane charakterystyki kierunkowe: K_U13
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.3.o
Charakterystyka AISDI_U02
Student, który zaliczył przedmiot, potrafi zaimplementować w języku C++: Proste algorytmy rekursywne
Weryfikacja: Ocena egzaminu Ocena sprawdzianu Ocena Lab. 6.
Powiązane charakterystyki kierunkowe: K_U13
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.3.o