Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 103C-INxxx-ISP-AISDI
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy i struktury danych
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Metody programowania )-Informatyka-inż.-EITI
( Przedmioty podstawowe )-Informatyka w multimediach-mgr.-EITI
( Przedmioty podstawowe )-Inteligentne systemy-mgr.-EITI
( Przedmioty podstawowe )-Inżynieria systemów informatycznych-mgr.-EITI
( Przedmioty podstawowe )-Sztuczna inteligencja-mgr.-EITI
( Przedmioty techniczne )---EITI
Punkty ECTS i inne: 4.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.
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

AISDI

Numer wersji:

3

Skrócony opis:

Prezentacja struktur danych oraz algorytmów operujących na tych strukturach. Przegląd najważniejszych struktur i algorytmów w kontekście metodyki projektowania obiektowego programów. Zajęcia zostały przygotowane i będą prowadzone z wykorzystaniem technik przygotowania prezentacji oraz umiejętności prezentacyjnych.

Pełny opis:

Prezentacja struktur danych oraz algorytmów operujących na tych strukturach. Przegląd najważniejszych struktur i algorytmów w kontekście metodyki projektowania obiektowego programów. Zajęcia zostały przygotowane i będą prowadzone z wykorzystaniem technik przygotowania prezentacji oraz umiejętności prezentacyjnych.


Treść wykładu
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.
Typy danych: typy proste, kolekcje i kolekcje indeksowane.
Liniowe struktury danych: listy jednokierunkowe i dwukierunkowe, pierścienie, stosy, kolejki i kolejki priorytetowe.
Algorytmy sortowania: Insertion Sort, Selection Sort, Bubble Sort, Quicksort, Merge Sort, Heap Sort, Straight Radix Sort, Radix Exchenge Sort, Shell Sort.
Algorytmy wyszukiwania: wyszukiwanie liniowe, binarne, interpolacyjne, z podziałem Fibonacciego, zastosowania funkcji mieszającej (ang. hashing).
Drzewa: drzewa binarne, Binary Tree Sort, drzewa o dowolnej liczbie następników, AVL, B, BB, SBB.
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.


Zakres laboratorium
Praktyczne utrwalenie wiadomości z wykładu poprzez uzupełnienie przygotowanych szkieletów implementacji określonych typów danych przy pomocy różnych struktur danych
Cztery pierwsze zajęcia laboratoryjne są poświęcone implementacji jedne typu danych (wykazu) przy pomocy różnych struktur danych (tablica, lista jednokierunowa, pierścień dwukierunkowy, drzewo binarne) przy zachowaniu tych samych aksjomatów. Kolejne zajęcia mają na celu opanowanie programowania z wykorzystaniem rekursji oraz podstawowych algorytmów przetwarzania grafów.
Każde zajęcia laboratoryjne wymagają zakodowania w języku C++ algorytmów (zgodnie z aksjomatami) przetwarzania struktur danych oraz przeprowadzenia systematycznych testów.


Przedmioty podobne

Kod przedmiotuNazwa przedmiotuDyskonto ECTS
103A-CSCSN-ISA-EADSAlgorithms & Data Structures5
103A-CSCSN-ISA-EADSAlgorithms & Data Structures4
103B-TExxx-ISP-AISDEAlgorytmy i struktury danych4
103B-TExxx-ISP-AISDEAlgorytmy i struktury danych3
103B-CTxxx-ISA-EADSAlgorithms & Data Structures5
103B-CTxxx-ISA-EADSAlgorithms & Data Structures4

Literatura:

    1. M. A. Weiss: Data Structures and Problem Solving Using C++, Second Edition, Addison Wesley Longman Inc., 2000.
    2. S. Sengupta, C.Ph. Korobkin: C++, Object-Oriented Data Structures, Springer-Verlag, 1994.
    3. N. Wirth: Algorytmy + struktury danych=program, WNT, Warszawa, 1980.
    4. L. Banachowski, A. Kreczmar: Elementy analizy algorytmów, WNT, Warszawa, 1982.

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

Okres: 2020-02-22 - 2020-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 15 godzin, 30 miejsc więcej informacji
Laboratorium, 15 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Roman Podraza
Prowadzący grup: Waldemar Grabski, Karol Piczak, Roman Podraza
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
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:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 15 godzin, 150 miejsc więcej informacji
Laboratorium, 15 godzin, 150 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Waldemar Grabski, Roman Podraza, Dariusz Turlej
Prowadzący grup: Waldemar Grabski, Rajmund Kożuszek, Karol Piczak, Roman Podraza, Andrzej Ratkowski, Marcin Szlenk
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
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:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 15 godzin, 100 miejsc więcej informacji
Laboratorium, 15 godzin, 100 miejsc więcej informacji
Wykład, 30 godzin, 100 miejsc więcej informacji
Koordynatorzy: Andrzej Zalewski
Prowadzący grup: Waldemar Grabski, Andrzej Ratkowski, Marcin Szlenk, Andrzej Zalewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

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

Okres: 2018-10-01 - 2019-02-17
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 15 godzin, 150 miejsc więcej informacji
Laboratorium, 15 godzin, 150 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Waldemar Grabski, Roman Podraza, Dariusz Turlej
Prowadzący grup: Waldemar Grabski, Konrad Grochowski, Maciej Kulawik, Roman Podraza, Andrzej Ratkowski, Marcin Szlenk, Witold Wysota
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
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 7.0.0.0-7 (2024-03-18)