Algorytmy i struktury danych 17-DASD-IP1
Język algorytmiczny pojęcie zmiennej, instrukcja przypisania, instrukcje warunkowe, iteracje, operatory specjalne.
Struktury tablicowe, przykłady prostych algorytmów wykorzystujących tablice jako struktury danych.
Pojęcie procedury i funkcji. Deklaracja, parametry formalne, wywołanie, procedura funkcyjna (funkcja), matematyczne pojęcie rekurencji, procedury rekurencyjne.
Zagadnienie złożoności i poprawności, złożoność pamięciowa, złożoność
czasowa, notacja asymptotyczna, twierdzenie o rekurencji uniwersalnej, niezmiennik pętli.
Podstawowe metody projektowania algorytmów metoda dziel i zwyciężaj, programowanie dynamiczne.
Algorytmy sortowania sortowanie przez wstawianie, bąbelkowe, przez scalanie, szybkie, przez zliczanie.
Stosy, kolejki, listy, pojęcie zbioru dynamicznego, tablicowa implementacja stosu i operacje na stosie, tablicowa implemementacja kolejki i operacje kolejkowe, lista dwukierunkowa z dowiązaniami, operacje na listach, listy z
wartownikiem.
Grafy, podstawowe pojęcia grafowe, reprezentacja grafów w komputerze,
drzewa ukorzenione.
Przykłady wykorzystania struktur dynamicznych. Problem otoczki wypukłej, przeszukiwanie grafu wszerz, przeszukiwanie grafu w głąb.
Kopce, kolejki priorytetowe kopce binarne typu min i max, przywracanie własności kopca binarnego, sortowanie przez kopcowanie, implementacja kolejki priorytetowej za pomocą kopca binarnego.
Drzewa wyszukiwań binarnych. Podstawowe własności drzew BST, operacje na drzewach BST, sortowanie drzewiaste.
Drzewa czerwono-czarne. Podstawowe własności, operacje rotacji, wstawianie i usuwanie węzła.
Haszowanie. Adresowanie bezpośrednie, tablice z haszowaniem, metoda
łańcuchowa, adresowanie otwarte, funkcje haszujące, haszowanie
doskonałe.
Metoda zachłanna, algorytm Prima, algorytm Kruskala, algorytm Huffmana.
Metoda z powrotami, problem królowych, problem sumy podzbiorów, problem plecakowy.
Cele kształcenia
Informacja o tym, gdzie można zapoznać się z materiałami do zajęć
Kierunek studiów
Metody prowadzenia zajęć umożliwiające osiągnięcie założonych EK
Nakład pracy studenta (punkty ECTS)
Poziom przedmiotu
Rok studiów (jeśli obowiązuje)
Wymagania wstępne w zakresie wiedzy, umiejętności oraz kompetencji
Koordynatorzy przedmiotu
W cyklu 2024/SZ: | W cyklu 2018/SZ: | W cyklu 2020/SZ: | W cyklu 2023/SZ: | W cyklu 2021/SZ: | W cyklu 2022/SZ: | W cyklu 2019/SZ: |
Efekty kształcenia
E01-zna i stosuje podstawowe konstrukcje algorytmiczne, zapisuje je w
pseudokodzie.
E02-ma wiedzę w zakresie znaczenia i wykorzystania pojęcia rekurencji.
E03-wykorzystuje procedury i funkcje do formułowania algorytmów,
stosuje rekurencję.
E04-zna i stosuje proste i złożone struktury danych, w tym struktury
dynamiczne.
E05-zna podstawowe techniki projektowania algorytmów i stosuje wiedzę
matematyczną do formułowania i rozwiązywania zadań
algorytmicznych.
E06-konstruuje algorytmy dla średniozaawansowanego problemu
algorytmicznego.
E07-ocenia poprawność i złożoność czasową algorytmów, potrafi
krytycznie ocenić skonstruowany algorytm.
E08-ma świadomość ważności algorytmiki w informatyce i rozumie
potrzebę dalszego kształcenia algorytmicznego.
Kryteria oceniania
zadania algorytmiczne podczas laboratoriów, ćwiczenia z algorytmów, zaliczenie ćwiczeń w formie testu
Literatura
1. T. Cormen, Algorytmy bez tajemnic, Helion, Gliwice 2013.
2. T. Cormen, Ch. Leiserson, R. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwa Naukowo-
Techniczne, Warszawa 2012.
3. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, Wydawnictwa Naukowo-Techniczne,
Warszawa 2006.
4. N. Wirth, Algorytmy + struktury danych = programy, Wydawnictwa Naukowo -Techniczne, Warszawa 2000.
5. D. Knuth, Sztuka programowania, Tom 3: Sortowanie i wyszukiwanie, Wydawnictwa Naukowo-Techniczne,
Warszawa 2002.
6. D. Harel, Y. Feldman, Rzecz o istocie informatyki. Algorytmika, Wydawnictwa Naukowo-Techniczne,
Warszawa 2008.
7. R. Neapolitan, K. Naimipour, Podstawy algorytmów z przykładami w C++, Helion, Gliwice 2004.
8. J. Bentley, Perełki oprogramowania, Wydawnictwa Naukowo-Techniczne, Warszawa 2001.
9. V.A. Spraul, Myśl jak programista. Techniki kreatywnego rozwiązywania problemów, Helion, Gliwice 2013.
10. W. Anggoro, C++ Struktury danych i algorytmy, Helion, Gliwice 2019.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: