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

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 103B-TExxx-ISP-AISDE Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy i struktury danych
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Algorytmy i techniki programowania )-Elektronika, Telekomunikacja-inż.-EITI
( Przedmioty podstawowe )-Mikroelektronika, fotonika i nanotechnologie-mgr.-EITI
( Przedmioty techniczne )---EITI
Punkty ECTS i inne: 4.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

AISDE

Numer wersji:

2

Skrócony opis:

Celem przedmiotu jest zapoznanie studentów z podstawami teorii algorytmów, teorii złożoności obliczeniowej, metodami tworzenia algorytmów poprawnych i zasadami działania podstawowych klas algorytmów nienumerycznych. Omawiane są zasady działania algorytmów, ich złożoności, podawane są przykłady kodów. Na laboratorium studenci badają praktycznie na komputerach właściwości omawianych algorytmów.

Pełny opis:

Celem przedmiotu jest zapoznanie studentów z podstawami teorii algorytmów, teorii złożoności obliczeniowej, metodami tworzenia algorytmów poprawnych i zasadami działania podstawowych klas algorytmów nienumerycznych. Omawiane są zasady działania algorytmów, ich złożoności, podawane są przykłady kodów. Na laboratorium studenci badają praktycznie na komputerach właściwości omawianych algorytmów.


Treść wykładu

  • Problemy abstrakcyjne, teoria algorytmów, złożoność obliczeniowa

  • Algorytmy teorio-liczbowe

  • Algorytmy oparte na metodzie "dziel i zwyciężaj"

  • Sortowanie: przez selekcje, przez wstawianie

  • Sortowanie: przez scalanie, kopcowanie, szybkie

  • Sortowanie w czasie liniowym

  • Słowniki: definicje, implementacja, tablice dynamiczne

  • Słowniki: drzewa BST, tablice z haszowaniem

  • Wyszukiwanie wzorca: algorytm naiwny, Rabina Karpa

  • Wyszukiwanie wzorca: algorytm KMP

  • Algorytmy grafowe: wypisywanie, przeszukiwanie wszerz, w głąb

  • Algorytmy grafowe: sortowanie topologiczne, algorytm Dijkstry



Zakres projektu
Ćwiczenie 1 - wstępne, badanie złożoności prostych algorytmów

Ćwiczenie 2 - badanie złożoności obliczeniowej algorytmów rekurencyjnych

Ćwiczenie 3 - badanie algorytmów sortowania

Ćwiczenie 4 - badanie algorytmów przeszukiwania słowników

Ćwiczenie 5 - badanie algorytmów wyszukiwania wzorca

Ćwiczenie 6 - badanie algorytmów grafowych


Przedmioty podobne
Kod przedmiotuNazwa przedmiotuDyskonto ECTS
103A-CSCSN-ISA-EADSAlgorithms & Data Structures4
103C-INxxx-ISP-AISDIAlgorytmy i struktury danych4
103B-INxxx-ISP-AISDIAlgorytmy i struktury danych4
103B-CTxxx-ISA-EADSAlgorithms & Data Structures4

Literatura:

    1. T. Adamski, J. Ogrodzki, Wprowadzenie do algorytmów komputerowych i struktur danych, skrypt PW, Oficyna Wywawnicza PW, Warszawa 2005

    2. A.V. Aho, J.E. Hopcroft, J.D. Ulman; Projektowanie i analiza
      algorytmów komputerowych; PWN, Warszawa 1983.

    3. T. H. Cormen, C.E. Leiserson, R.L. Rivest; Wprowadzenie do
      algorytmów; WNT, Warszawa 1997.

    4. L. Banachowski, K. Diks, W. Rytter; Algorytmy i struktury danych;
      WNT, Warszawa 1996.

    5. P. Wróblewski; Algorytmy, struktury danych i technik
      programowania; Helim, 1996.

    6. J. Bentley; Perełki oprogramowania; WNT, 1992.

    7. C.H. Popadimitriov; Złożoność obliczeniowa; WNT, Warszawa 2002.

    8. D.E. Knuth; Sztuka programowania; WNT, 2002

    9. N. Wirth; Algorytmy + struktury danych= programy; WNT, Warszawa,
      2002.

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ęć: Laboratorium, 15 godzin, 200 miejsc więcej informacji
Wykład, 30 godzin, 200 miejsc więcej informacji
Koordynatorzy: Jan Ogrodzki, Artur Tomaszewski
Prowadzący grup: Dariusz Bursztynowski, Jan Ogrodzki, Artur Tomaszewski, Mateusz Żotkiewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103300 - Instytut Systemów Elektronicznych
103600 - Instytut Telekomunikacji

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ęć: Laboratorium, 15 godzin, 180 miejsc więcej informacji
Wykład, 30 godzin, 180 miejsc więcej informacji
Koordynatorzy: Adam Wojtasik
Prowadzący grup: Dominik Kasprowicz, Krzysztof Siwiec, Adam Wojtasik
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103500 - Instytut Mikroelektroniki i Optoelektroniki

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ęć: Laboratorium, 15 godzin, 190 miejsc więcej informacji
Wykład, 30 godzin, 190 miejsc więcej informacji
Koordynatorzy: Jan Ogrodzki, Artur Tomaszewski
Prowadzący grup: Jan Ogrodzki, Artur Tomaszewski, Mateusz Żotkiewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103300 - Instytut Systemów Elektronicznych
103600 - Instytut Telekomunikacji

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

Okres: 2018-02-19 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 180 miejsc więcej informacji
Wykład, 30 godzin, 180 miejsc więcej informacji
Koordynatorzy: Adam Wojtasik
Prowadzący grup: Dominik Kasprowicz, Krzysztof Siwiec, Adam Wojtasik
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103500 - Instytut Mikroelektroniki i Optoelektroniki

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

Okres: 2017-10-01 - 2018-02-18
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 100 miejsc więcej informacji
Wykład, 30 godzin, 100 miejsc więcej informacji
Koordynatorzy: Jan Ogrodzki, Artur Tomaszewski
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103300 - Instytut Systemów Elektronicznych
103600 - Instytut Telekomunikacji

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

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


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 180 miejsc więcej informacji
Wykład, 30 godzin, 180 miejsc więcej informacji
Koordynatorzy: Adam Wojtasik
Prowadzący grup: Adam Wojtasik
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103500 - Instytut Mikroelektroniki i Optoelektroniki

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

Okres: 2016-10-01 - 2017-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 90 miejsc więcej informacji
Wykład, 30 godzin, 90 miejsc więcej informacji
Koordynatorzy: Jan Ogrodzki, Artur Tomaszewski
Prowadzący grup: Jan Ogrodzki, Artur Tomaszewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103300 - Instytut Systemów Elektronicznych
103600 - Instytut Telekomunikacji

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

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


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 150 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Adam Wojtasik
Prowadzący grup: Adam Wojtasik
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103500 - Instytut Mikroelektroniki i Optoelektroniki

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

Okres: 2015-10-01 - 2016-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 90 miejsc więcej informacji
Wykład, 30 godzin, 90 miejsc więcej informacji
Koordynatorzy: Jan Ogrodzki, Artur Tomaszewski
Prowadzący grup: Jan Ogrodzki, Artur Tomaszewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103300 - Instytut Systemów Elektronicznych
103600 - Instytut Telekomunikacji

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

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


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 140 miejsc więcej informacji
Wykład, 30 godzin, 140 miejsc więcej informacji
Koordynatorzy: Adam Wojtasik
Prowadzący grup: Adam Wojtasik
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103500 - Instytut Mikroelektroniki i Optoelektroniki

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

Okres: 2014-09-29 - 2015-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 100 miejsc więcej informacji
Wykład, 30 godzin, 100 miejsc więcej informacji
Koordynatorzy: Jan Ogrodzki, Artur Tomaszewski
Prowadzący grup: Jan Ogrodzki, Artur Tomaszewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103300 - Instytut Systemów Elektronicznych
103600 - Instytut Telekomunikacji

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

Okres: 2014-02-24 - 2014-09-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 145 miejsc więcej informacji
Wykład, 30 godzin, 145 miejsc więcej informacji
Koordynatorzy: Adam Wojtasik
Prowadzący grup: Adam Wojtasik
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103500 - Instytut Mikroelektroniki i Optoelektroniki

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

Okres: 2013-10-01 - 2014-02-23
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 90 miejsc więcej informacji
Wykład, 30 godzin, 90 miejsc więcej informacji
Koordynatorzy: Jan Ogrodzki, Artur Tomaszewski
Prowadzący grup: Jan Ogrodzki, Artur Tomaszewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103300 - Instytut Systemów Elektronicznych
103600 - Instytut Telekomunikacji

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

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


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 170 miejsc więcej informacji
Wykład, 30 godzin, 170 miejsc więcej informacji
Koordynatorzy: Adam Wojtasik
Prowadzący grup: Adam Wojtasik
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103500 - Instytut Mikroelektroniki i Optoelektroniki

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

Okres: 2012-10-01 - 2013-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 90 miejsc więcej informacji
Wykład, 30 godzin, 90 miejsc więcej informacji
Koordynatorzy: Jan Ogrodzki, Artur Tomaszewski
Prowadzący grup: Jan Ogrodzki, Artur Tomaszewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103300 - Instytut Systemów Elektronicznych
103600 - Instytut Telekomunikacji

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.