Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

Struktury danych

Informacje ogólne

Kod przedmiotu: 103A-INJEE-PNP-STD
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Struktury danych
Jednostka: Instytut Informatyki
Grupy: ( Semestr 2 )-Java EE - produkcja oprogramowania-pod.-EITI
Punkty ECTS i inne: 3.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
Język prowadzenia: polski
Kod wydziałowy:

STD

Liczba godzin zajęć praktycznych:

10

Liczba godzin zajęć teoretycznych:

6

Numer wersji:

1

Skrócony opis:

Cel przedmiotu

Zapoznanie słuchaczy z podstawowymi strukturami danych i algorytmami wykorzystującymi te struktury. Nacisk położony będzie na praktyczną obiektową realizację struktur w języku Java.

Pełny opis:

Wykład

Pojęcia podstawowe (1 godz.). Obiekty, typy, struktury danych, systemy typów w językach programowania i ich charakterystyka, metody agregowania typów podstawowych; struktury statyczne i dynamiczne; struktury liniowe, drzewiaste, grafowe; ocenianie złożoności pamięciowej i czasowej struktur i operacji na nich. Przegląd JCF (Java Collections Framework).

Struktury liniowe (1 godz.). Krotki, wektory, listy (jedno- i dwukierunkowe), stosy, kolejki i kopce (kolejki priorytetowe); operacje na strukturach liniowych: dodawanie, usuwanie elementów; szukanie logarytmiczne; interfejsy struktur liniowych w JCF.

Rekursja i drzewa (1 godz.). Myślenie i algorytmy rekurencyjne, metafora „dziel i rządź”, przykłady problemów i rozwiązań; drzewa, rekurencyjne scenariusze eksploracji; drzewa binarne szukania (BST), drzewa zrównoważone; zbiory i drzewa, operacje na zbiorach rozłącznych. Interfejsy java.util.Set, java.util.Map.

Sortowanie (1 godz.). Przegląd algorytmów sortowania (insertionSort, bubbleSort, quickSort, mergeSort, heapSort), złożoność pesymistyczna i oczekiwana, algorytmy sortowania dostępne w java.util.Arrays, java.util.Collections.

Grafy (2 godz.). Grafy skierowane, nieskierowane, ważone, koszt reprezentacji, operacje zwiedzania w głąb (DFS) i wszerz (BFS); badanie właściwości ekstremalnych grafu, metoda zachłanna, programowanie dynamiczne; wyznaczanie minimalnego drzewa rozpinającego, najkrótsze ścieżki w grafie, algorytmy Dijkstry i Floyda.


Laboratorium

Słuchaczom będą zaproponowane problemy algorytmiczne do indywidualnego opracowania i późniejszego porównania z rozwiązaniem wzorcowym.

Implementacja i testowanie struktur liniowych (3 godz.). Stos, kolejka, kopiec itp. w zastosowaniu do problemów ewaluacji wielomianów, dominacji punktów na płaszczyźnie.

Struktury drzewiaste (4 godz.). Implementacja struktur drzewiastych z wiązaniem przez referencje, organizacja zbioru punktów na płaszczyźnie, przepytywanie zakresowe; wyznaczanie kodu Huffmana.

Reprezentacje grafów (3 godz.). Grafy skierowane i nieskierowane; implementacja wybranych algorytmów grafowych (zwiedzanie grafu, MDR, Dijkstra, Floyd itp.).

Efekty uczenia się:

Wiedza i umiejetności, które student uzyskuje w wyniku zaliczenia przedmiotu

  • Zna interfejsy kolejkowe oraz kolekcje konkretne.
  • Zna algorytmy kolekcji.
  • Potrafi wybrać i zastosować właściwe kolekcje.

Zajęcia w cyklu "rok akademicki 2021/2022 - sem. letni" (zakończony)

Okres: 2022-02-23 - 2022-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Zajęcia zintegrowane, 16 godzin więcej informacji
Koordynatorzy: Andrzej Pająk, Dariusz Turlej
Prowadzący grup: Andrzej Pająk
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2020/2021 - sem. letni" (zakończony)

Okres: 2021-02-20 - 2021-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Zajęcia zintegrowane, 16 godzin więcej informacji
Koordynatorzy: Andrzej Pająk
Prowadzący grup: Andrzej Pająk
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. letni" (zakończony)

Okres: 2020-02-22 - 2020-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Zajęcia zintegrowane, 16 godzin więcej informacji
Koordynatorzy: Andrzej Pająk
Prowadzący grup: Andrzej Pająk
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. zimowy" (zakończony)

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Zajęcia zintegrowane, 16 godzin więcej informacji
Koordynatorzy: Andrzej Pająk
Prowadzący grup: Andrzej Pająk
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. letni" (zakończony)

Okres: 2019-02-18 - 2019-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Zajęcia zintegrowane, 16 godzin więcej informacji
Koordynatorzy: Andrzej Pająk
Prowadzący grup: Andrzej Pająk
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. zimowy" (zakończony)

Okres: 2018-10-01 - 2019-02-17
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Zajęcia zintegrowane, 16 godzin więcej informacji
Koordynatorzy: Andrzej Pająk
Prowadzący grup: Andrzej Pająk
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103200 - Instytut Informatyki

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.
pl. Politechniki 1, 00-661 Warszawa tel: (22) 234 7211 https://pw.edu.pl kontakt deklaracja dostępności USOSweb 6.8.0.0-7 (2022-11-16)