Algorytmy i struktury danych

Technologie informatyczne - studia inżynierskie

I stopień

Zapoznanie studentów z podstawowymi metodami budowy algorytmów i wykorzystaniem prostych oraz różnego rodzaju złożonych struktur danych. Wykształcenie umiejętności konstruowania średniozaawansowanych algorytmów oraz ocenę ich złożoności i poprawności.

I rok

brak

Platforma MS Teams

wykłady, konwersatoria, ćwiczenia, laboratoria

6

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.

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.

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.

zadania algorytmiczne podczas laboratoriów, ćwiczenia z algorytmów, zaliczenie ćwiczeń w formie testu