Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: WM-I-ASD Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy i struktury danych
Jednostka: Wydział Matematyczno-Przyrodniczy. Szkoła Nauk Ścisłych
Grupy:
Strona przedmiotu: https://zdanowski.blog.uksw.edu.pl/
Punkty ECTS i inne: 0 LUB 5.00 (w zależności od programu)
zobacz reguły punktacji
Język prowadzenia: polski
Poziom przedmiotu:

średnio-zaawansowany

Symbol/Symbole kierunkowe efektów uczenia się:

wykład: I1_W05, I1_W06, I1_W07, I1_K01, I1_K02

ćwiczenia: I1_U02, I1_U03, I1_U04, I1_U05, I1_K01, I1_K02, I1_K03


Skrócony opis:

Tematem kursu są struktury danych, algorytmy, sposoby ich projektowania, metody analizy kosztów algorytmów, metody weryfikacji algorytmów.

Zostaną przedstawione techniki służące rozwiązywaniu takich problemów jak wyszukiwanie, sortowanie, reprezentowanie i obliczenia na grafach. Będzie mowa o sposobach przechowywania i o organizacji danych. Przedstawione przykłady pozwolą uczestnikom kursu poznać klasyczne sposoby rozwiązywania problemów algorytmicznych. Zwrócimy też uwagę na ograniczenia złożonościowe algorytmów.

Po zakończeniu kursu student powinien umieć oszacować koszt prostego algorytmu, powinien rozumieć potrzebę uzasadniania poprawności algorytmów, umieć zastosować poznane techniki konstrukcji algorytmów i algorytmy do rozwiązywania nowych problemów.

Pełny opis:

Wymagania wstępne

Przedmiot ma charakter podstawowy. Do zrozumienia treści wykładu niezbędna jest jednak znajomość

* elementów matematyki dyskretnej,

* elementów analizy matematycznej i algebry,

* programowania w zakresie podstawowym.

Program wykładu

1. Podstawowe motywacje. Asympotyczna szybkość wzrostu funkcji, duże i małe „o”. Wprowadzenie do analizy złożoności algorytmów, metoda niezmienników.

2. Podstawowe techniki programowania: rekursja, dziel i rządź, programowanie dynamiczne. Twierdzenie o rekursji uniwersalnej.

3. Podstawowe struktury danych i operacje na nich: lista, stos, kolejka.

4. Definicja problemu sortowania. Sortowanie przez scalanie i jego złożoność.

5. Sortowanie szybkie i jego złożność. Modyfikacje sortowania szybkiego.

6. Implementacja kolejki przy użyciu kopca. Sortowanie przez kopcowanie.

7. Dolne ograniczenie na szybkość sortowania przy pomocy porównań i przestawień. Sortowanie pozycyjne i kubełkowe.

8. Struktury słownikowe. Definicja oraz implementacje drzewa. Problem wyszukiwania. Wyszukiwanie przez połowienie oraz drzewa poszukiwań (BST).

9. Podstawowe operacje na drzewie BST oraz ich złożoność: wstawianie, wyszukiwanie, usuwanie. Metody przeglądania drzewa.

10. Zrównoważone drzewo wyszukiwań binarnych (AVL).

11. Drzewa 2-3. Drzewa czerwono-czarne. B drzewa.

12. Definicja grafu oraz metody jego reprezentacji. Metody przeglądania grafu: w głąb (DFS) i w szerz (BFS).

13. Implementacja DFS i BFS przy użyciu kolejki i stosu. Sortowanie topologiczne grafu.

14. Konstrukcja minimalnego drzewa rozpinającego. Algorytm Prima i jego złożoność. Opis algorytmu Kruskala.

15. Podstawy szybkiej transformaty Fouriera (FFT).

Literatura:

1. Cormen T., C. Leiserson, R. Rivest, Wprowadzenie do algorytmów, Wydawnictwa Naukowo - Techniczne 1999.

2. Sedgewick, Wayne, Algorytmy, Helion, 2012.

3. Dasgupta, Papadimitriou, Vazirani, Algorytmy, WN PWN, 2018

4. Knuth D., Sztuka programowania, WNT, tomy I-IV, 2002-2007.

5. Aho A., Hopcroft J., Ullman J., Projektowanie i analiza algorytmów komputerowych, PWN.

6. Banachowski, Diks, Rytter, Algorytmy i struktury danych, PWN 2017.

7. Harel, Feldman, Rzecz o istocie informatyki. Algorytmika, WNT.

Efekty kształcenia i opis ECTS:

Zna i rozumie różne techniki algorytmiczne (rekursja, dziel i rządź, programownie dynamiczne, itp ), zna metody analizy własności programu i jego złożoności jak np metoda niezmienników, twierdzenie o rekursji uniwersalnej. (I1_W05)

Zna i rozumie podstawowe struktury danych, operacje na nich oraz ich złożoność, wie w jakich sytuacjach należy z nich skorzystać. (I1_W06)

Zna i rozumie algorytmy służące do rozwiązywania typowych problemów informatycznych jak sortowanie, implementacja słownika, problemy teoriografowe. (I1_W07)

Jest gotów poznawać ograniczenia wynikające z trudności różnych problemów

obliczeniowych, jest gotów poznawać nowe rozwiązania w dziedzinie algorytmiki. (I1_K01)

Jest gotów do analizy problemu pod kątem metod potrzebnych do jego reprezentacji i rozwiązania, szuka niewyspecyfikowanych ograniczeń, które mogą ułatwić rozwiązanie problemu. (I1_K02)

Metody i kryteria oceniania:

Egzamin pisemny.

Zajęcia w cyklu "Semestr letni 2019/20" (zakończony)

Okres: 2020-02-01 - 2020-09-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Konrad Zdanowski
Prowadzący grup: Konrad Zdanowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzaminacyjny
E-Learning:

E-Learning (pełny kurs) z podziałem na grupy

Typ przedmiotu:

obowiązkowy

Grupa przedmiotów ogólnouczenianych:

nie dotyczy

Zajęcia w cyklu "Semestr letni 2020/21" (zakończony)

Okres: 2021-02-01 - 2021-06-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Konrad Zdanowski
Prowadzący grup: Konrad Zdanowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzaminacyjny
E-Learning:

E-Learning (pełny kurs) z podziałem na grupy

Typ przedmiotu:

obowiązkowy

Grupa przedmiotów ogólnouczenianych:

nie dotyczy

Zajęcia w cyklu "Semestr letni 2021/22" (jeszcze nie rozpoczęty)

Okres: 2022-02-01 - 2022-06-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Konrad Zdanowski
Prowadzący grup: Marek Fałda, Konrad Zdanowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzaminacyjny
Typ przedmiotu:

obowiązkowy

Grupa przedmiotów ogólnouczenianych:

nie dotyczy

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie.