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

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 1120-MA000-LSP-0547 Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy i struktury danych
Jednostka: Wydział Matematyki i Nauk Informacyjnych
Grupy: Przedmioty obieralne uruchomione w semestrze zimowym 2021/2022
Przedmioty obieralne, wydz. MiNI PW
Punkty ECTS i inne: 5.00 LUB 4.00 (zmienne w czasie)
zobacz reguły punktacji
Język prowadzenia: polski
Skrócony opis:

Celem przedmiotu jest istotne pogłębienie i rozszerzenie wiedzy słuchaczy w zagadnieniach algorytmiki i struktur danych oraz metod weryfikacji programów i analizy ich złożoności.

Wymagania wstępne / przedmioty poprzedzające: Podstawy programowania i przetwarzania danych, Matematyka dyskretna

Pełny opis:

Wykład:

1. Podstawy analizy poprawności algorytmów (metoda niezmienników).

2. Postawy złożoności obliczeniowej algorytmów (złożoność czasowa, pamięciowa, kryteria złożoności).

3. Struktura kopca.

4. Problem sortowania

a. Nieelementarne algorymy sortowania (sortowanie szybkie, sortowanie przez kopcowanie, sortowanie przez scalanie).

b. Elementarne algorytmy sortowania (sortowanie przez wybór, sortowanie przez wstawianie, sortowanie bąbelkowe).

c. Sortowanie kubełkowe.

d. Sortowanie plików.

4. Metody selekcji

a. algorytm Hoare'a, Hadiana-Sobela, "magicznych piątek".

6. Struktury listowe.

7. Struktury drzewiaste:

a. drzewa poszukiwań binarnych BST, drzewa wyważone AVL,

b. B-drzewa,

c. drzewa PATRICIA.

8. Haszowanie i metody usuwania kolizji.

9. Metody reprezentacji grafów i podstawowe algorytmy teoriografowe

a. obchodzenie grafów,

b. algorytm Dijkstry, Floyda, Kruskala, problem komiwojażera

c. algorytmy wyznaczania cykli Eulera i Hamiltona.

d. algorytm kolorowania grafu.

Ćwiczenia: Studenci samodzielnie rozwiązują przy tablicy zaproponowane przez prowadzącego zadania z tematyki objętej ostatnim wykładem. Podejmowane są także dyskusje nawiązujące bezpośrednio do wykłady (np. propozycje dowodów, metod modelowania zjawisk).

Projekt: W ramach zajęć projektowych studenci przygotowują programy o tematyce zaproponowanej przez prowadzącego lub samodzielnie wybranej i uzgodniony z prowadzącym.

Literatura:

1. Lech Banachowski, Krzysztof Diks, Wojciech Rytter (1996) Algorytmy i Struktury Danych. Wydawnictwo Naukowo-Techniczne, Warszawa. 2. A. V. Aho, J. E, Hopcroft, J. D. Ullman (2003) Projektowanie i analiza algorytmów, Wydawnictwo Helion. 3. A. V. Aho, J. E, Hopcroft, J. D. Ullman (2003) Algorytmy i struktury danych, Wydawnictwo Helion. 4. T. H. Cormen, Ch. E. Leiserson, R. L. Rivest (1996) Wprowadzenie do algorytmów i struktur danych, Wydawnictwo Naukowo-Techniczne, Warszawa 5. R. Sedgewick (1999) Algorytmy w C++. Oficyna Wydawnicza READ ME, Warszawa. 6. S. Even (2011) Graph algorithms. Cambridge University Press.

Efekty uczenia się:

1. Ma wiedzę w zakresie podstaw algorytmiki:

• podstawowe struktury danych: stosy, kolejki, kopce, słowniki (listy, drzewa BST, AVL, PATRICIA, B-drzewa).

• podstawowe techniki programowania i ich zastosowania: metoda „dziel i zwyciężaj”, metoda zachłanna, programowanie dynamiczne, metody z nawracaniem

• algorytmy sortowania (wewnętrznego, zewnętrznego)

• algorytmy selekcji

• podstawowe metody haszowania.

• wybrane algorytmy grafowe.

2. Zna podstawowe metody teoretycznej analizy algorytmów w zakresie semantycznej poprawności oraz czasowej i pamięciowej złożoności obliczeniowej.

3. Zna i rozumie pojęcia z zakresu relacji porządku (częściowego, liniowego), grafów i ich typów i własności, równań rekurencyjnych.

4. Potrafi przedstawić poprawne rozumowanie matematyczne i powiązać wybrane problemy matematyczne (rachunek zdań, indukcja matematyczna, rekurencja) dla potrzeb rozwiązania i analizy problemu algorytmicznego.

5. Posiada umiejętność analizy algorytmu w zakresie

• semantycznej poprawności

• złożoności obliczeniowej (czasowej i pamięciowej).

6. Potrafi samodzielnie

• zapisać w pseudokodzie rozwiązanie prostych problemów algorytmicznych i je zaimplementować w języku programowania.

• wykorzystać dostępne klasy, struktury, funkcje dla rozwiązania prostych problemów algorytmicznych.

7. Rozumie potrzebę uczenia się przez całe życie

8. Potrafi współdziałać i pracować w grupie, przyjmując w niej różne role.

9. Rozumie potrzebę podnoszenia kompetencji zawodowych i osobistych

Metody i kryteria oceniania:

Zajęcia oceniane są punktowo za: 1. Aktywność na zajęciach – max.10p 2. Test – max. 20p 3. Projekty – max.20p (jeśli 2 zadnia – każde po 10p) Ocena końcowa z przedmiotu wynika z sumy uzyskanych punktów: 26-30 – 3 31-35 – 3.5 36-40 – 4 41-45 – 4.5 ponad 46 – 5. Szczegółowy regulamin zaliczenia podawany jest na początku semestru.

Zajęcia w cyklu "rok akademicki 2021/2022 - sem. zimowy" (w trakcie)

Okres: 2021-10-01 - 2022-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Projekt, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Anna Radzikowska
Prowadzący grup: Anna Radzikowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

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

Okres: 2020-10-01 - 2021-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Laboratorium, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Anna Radzikowska
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

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ęć: Ćwiczenia, 30 godzin więcej informacji
Laboratorium, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Anna Radzikowska
Prowadzący grup: Rafał Adasiewicz, Anna Radzikowska, Kacper Sarnacki
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

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ęć: Ćwiczenia, 30 godzin więcej informacji
Laboratorium, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Anna Radzikowska
Prowadzący grup: Rafał Adasiewicz, Anna Radzikowska, Kacper Sarnacki
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

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ęć: Ćwiczenia, 30 godzin, 150 miejsc więcej informacji
Laboratorium, 15 godzin, 150 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Anna Radzikowska
Prowadzący grup: Pavel Kuzmich, Anna Radzikowska, Przemysław Rząd, Kacper Sarnacki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Ocena łączna
Ćwiczenia - Zaliczenie
Laboratorium - Zaliczenie
Wykład - Egzamin

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ęć: Ćwiczenia, 30 godzin, 150 miejsc więcej informacji
Laboratorium, 15 godzin, 150 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Anna Radzikowska
Prowadzący grup: Anna Radzikowska, Przemysław Rząd, Piotr Waszkiewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie
Laboratorium - Zaliczenie
Wykład - Egzamin
Semestr:

3

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ęć: Ćwiczenia, 30 godzin, 150 miejsc więcej informacji
Laboratorium, 15 godzin, 150 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Anna Radzikowska
Prowadzący grup: Anna Radzikowska, Agnieszka Żychowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie
Laboratorium - Zaliczenie
Wykład - Egzamin

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ęć: Ćwiczenia, 30 godzin, 150 miejsc więcej informacji
Laboratorium, 15 godzin, 150 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Anna Radzikowska
Prowadzący grup: Anna Radzikowska, Agnieszka Żychowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie
Laboratorium - Zaliczenie
Wykład - Egzamin

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ęć: Ćwiczenia, 30 godzin, 150 miejsc więcej informacji
Laboratorium, 15 godzin, 150 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Anna Radzikowska
Prowadzący grup: Anna Radzikowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie
Laboratorium - Zaliczenie
Wykład - Egzamin

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ęć: Ćwiczenia, 30 godzin, 150 miejsc więcej informacji
Laboratorium, 15 godzin, 150 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Anna Radzikowska
Prowadzący grup: Anna Radzikowska, Przemysław Szałaj, Małgorzata Śleszyńska-Nowak
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie
Laboratorium - Zaliczenie
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.