Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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
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 kształcenia:

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 2019/2020 - sem. zimowy" (w trakcie)

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.