Sylabus z przedmiotu
Algorytmy i struktury danych
(Forma dokumentu zgodna z Uchwałą Nr 95/2007 Państwowej Komisji Akredytacyjnej z dnia 8 lutego 2007 r.)
Nazwa jednostki prowadzącej kierunek:
Wydział Informatyki Wyższej Szkoły Technologii Informatycznych w Katowicach
Nazwa kierunku:
Informatyka
Nazwa przedmiotu:
Algorytmy i struktury danych
Nazwa i określenie przedmiotów wprowadzających z wymogami wstępnymi:
Algorytmy i struktury danych to przedmiot z grupy przedmiotów kierunkowych związany z przedmiotami dotyczącymi
programowania. Wymogi wstępne dotyczą wiedzy pobranej przez studentów w ramach przedmiotów: Teoretyczne podstawy
informatyki oraz Podstawy programowania.
Liczba godzin zajęć :
Tryb stacjonarny
Liczba godzin wykładów 45
Liczba godzin ćwiczeń 45
Liczba godzin razem 90
Semestr 2
Forma oceny zaliczenie i egzamin
Tryb niestacjonarny
Liczba godzin wykładów 25
Liczba godzin ćwiczeń 30
Liczba godzin razem 55
Semestr 2
Forma oceny zaliczenie i egzamin
Liczba punktów ECTS :
6
Założenie i cele przedmiotu :
Celem przedmiotu jest przekazanie studentom wiedzy na temat podstaw algorytmiki: począwszy od pojęcia i cech algorytmu,
poprzez metody weryfikacji poprawności i złożoności algorytmów do przeglądu algorytmów rozwiązujących różnorodne
problemy od najprostszych, do NP.-trudnych. Towarzyszy temu omówienie (przypomnienie) struktur danych, w
szczególności tablic, rekordów czy wskazników, za pomocą których zapisuje się przetwarzana dane. Studenci powinni
zapoznać się z szeroką gamą istniejących algorytmów zapisywanych w różnych notacjach (opis słowny, schematy blokowe,
pseudokody), aby potrafić je zastosować w praktyce (np. na przedmiotach związanych z programowaniem), a także aby
algorytmy te modyfikować lub na ich podstawie tworzyć nowe algorytmy rozwiązujące nowe zadania.
Metody dydaktyczne :
Przedmiot jest realizowany jest w formie wykładu i ćwiczeń. Na wykładzie są omawiane odpowiednie treści programowe, zaś
na ćwiczeniach studenci powinni analizować, modyfikować i rozszerzać podane algorytmy oraz budować ich nowe wersje
służące do rozwiązywania nowych problemów. W miarę możliwości i umiejętności programowania, niektóre algorytmy mogą
być zaprogramowane na komputer.
Forma i warunki zaliczenia przedmiotu :
Warunkiem zaliczenia przedmiotu jest uczestnictwo studenta na ćwiczeniach, wykazanie się wiedzą z zakresu przedmiotu
(kartkówki i kollokwia, premiowana jest umiejętność zaprogramowania algorytmów na komputer) i uzyskanie oceny
pozytywnej z egzaminu. Do egzaminu może przystąpić student, który uzyskał zaliczenie z ćwiczeń. Ocenę z egzaminu student
uzyskuje w skali wskazanej w Regulaminie Studiów.
Treści programowe :
Wykład:
1. Pojęcie algorytmu.
2. Cechy i rodzaje algorytmów.
3. Metody zapisu algorytmu: opis słowny, schematy blokowe, pseudokod.
4. Pojęcie typu danych.
5. Proste typy danych liczbowe, znakowe, logiczne.
6. Złożone typy danych tablice, rekordy, zbiory, pliki. Typy wskaznikowe
7. Reprezentacja fizyczna struktur danych.
8. Weryfikacja poprawności algorytmów. Pojęcie niezmiennika, metoda Floyda.
9. Złożoność obliczeniowa algorytmów pamięciowa i czasowa. Złożoność czasowa średnia, pesymistyczna.
10. O-notacja dla złożoności algorytmów. Podział algorytmów ze względu na złożoność. Problemy NP-zupełne,
nierozstrzygalność.
11. Przykłady szacowania złożoności czasowej.
12. Sortowanie: przez proste wstawianie, przez proste wybieranie, sortowanie bąbelkowe.
13. Sortowanie drzewiaste i stogowe (kopcowanie).
14. Metoda dziel i zwyciężaj - sortowanie szybkie.
15. Wyszukiwanie liniowe i binarne. Rola wartownika w wyszukiwaniu.
16. Haszowanie. Metody przezwyciężania kolizji. Doskonała, minimalna funkcja haszująca.
17. Wyszukiwanie wzorca w tekście, słowniki.
18. Abstrakcyjne struktury danych listy, stosy, kolejki, kolejki priorytetowe.
19. Realizacja fizyczna list, stosów i kolejek (wskazniki, tablice).
20. Grafy definicja, cechy, rodzaje.
21. Reprezentacje grafów skierowanych i nieskierowanych (wskazniki, tablice, uporządkowanie lewolistowe).
22. Podstawowe operacje na grafach, przeszukiwanie grafu w głąb, wszerz.
23. Pojęcie i definicje drzew. Cechy drzew wysokość, moment, rząd itd.
24. Drzewa binarne, reprezentacja tablicowa.
25. Zastosowanie drzew (np. drzewo rozbioru gramatycznego wyrażeń arytmetycznych, drzewa BST w sortowaniu i
wyszukiwaniu).
26. Generowanie kodu Huffmana algorytmem zachłannym z wykorzystaniem drzewa.
27. Znajdowanie minimalnego drzewa rozpinającego algorytmami Prima i Kruskala.
28. Znajdowanie cyklu Eulera w grafach.
29. Znajdowanie najkrótszej ścieżki w grafach (porównanie algorytmu zachłannego z programowaniem dynamicznym).
30. Znajdowanie cyklu Hamiltona w grafach.
31. Analiza problemu komiwojażera, zastosowanie heurystyki.
32. Zalety i wady rekurencji na przykładzie algorytmów (porównanie algorytmów rekurencyjnych i iteracyjnych):
a. silnia,
b. liczby Fibonacciego
c. wieże Hanoi.
33. Algorytmy tworzenia trójkąta Sierpińskiego i innych fraktali.
Ćwiczenia:
1. Konstrukcja algorytmów i ich zapis za pomocą metod: opis słowny, schematy blokowe, pseudokod.
2. Wyznaczanie złożoności obliczeniowej algorytmów średniej i pesymistycznej.
3. Analiza metod sortowanie: przez proste wstawianie, przez proste wybieranie, bąbelkowego, drzewiastego, stogowego
i szybkiego.
4. Analiza metod wyszukiwania: liniowego, binarnego.
5. Haszowanie. Metody przezwyciężania kolizji. Wyszukiwanie wzorca w tekście, słowniki.
6. Realizacja fizyczna list, stosów i kolejek (wskazniki, tablice).
7. Operacje na listach w reprezentacji ze wskaznikami osadzonymi i w reprezentacji tablicowej (Front, Push, Pop, Rear,
Inject, Eject).
8. Grafy przykłady, reprezentacja grafów skierowanych i nieskierowanych (wskazniki, tablice, uporządkowanie
lewolistowe).
9. Wykonywanie podstawowych operacji na grafach, przeszukiwanie grafu w głąb, wszerz.
10. Drzewa: cechy i metody zapisu, reprezentacja tablicowa, wskaznikowa, zapis lewolistowy.
11. Przykładowe zastosowania drzew (np. drzewo rozbioru gramatycznego wyrażeń arytmetycznych, drzewa BST w
sortowaniu i wyszukiwaniu).
12. Generowanie kodu Huffmana algorytmem zachłannym z wykorzystaniem drzewa.
13. Znajdowanie minimalnego drzewa rozpinającego algorytmami Prima i Kruskala.
14. Znajdowanie cyklu Eulera w grafach.
15. Znajdowanie najkrótszej ścieżki w grafach (porównanie algorytmu zachłannego z programowaniem dynamicznym).
16. Znajdowanie cyklu Hamiltona w grafach.
17. Rekurencyjne i iteracyjne realizacje algorytmów:
a. silnia,
b. liczby Fibonacciego,
c. wieże Hanoi.
18. Algorytmy tworzenia trójkąta Sierpińskiego i innych fraktali.
Wykaz literatury :
Literatura podstawowa
" Aho A.V., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza algorytmów komputerowych. PWN, Warszawa 1983.
" Banachowski L., Diks K., Rytter W.: Algorytmy i struktury danych . WNT, Warszawa 1996.
" Cormen T.H., Leiserson C.E., Rivest R.L.: Wprowadzenie do algorytmów . WNT, Warszawa 1997.
" Harel D.: Rzecz o istocie informatyki. Algorytmika, WNT, Warszawa 1992.
" Wilson R.J.: Wprowadzenie do teorii grafów, PWN, Warszawa 2002.
" Wirth N.: Algorytmy + struktury danych = programy. WNT, Warszawa 2004.
" Wróblewski P.: Algorytmy: struktury danych i techniki programowania. Helion, Gliwice 2003.
Literatura uzupełniająca
" Knuth D.E.: Sztuka programowania, WNT, Warszawa 2003.
" Czasopisma informatyczne.
" Zasoby sieci Internet.
Wyszukiwarka
Podobne podstrony:
Uzupe énienie do wyk éadu 1Algorytmy i struktury danych Programy do wykladu 3Pytania na zaliczenie wyk éaduInstrukcja IEF Algorytmy i struktury?nych lab1Algorytmy I Struktury Danych (Wyklady) infoInstrukcja IEF Algorytmy i struktury?nych lab2algorytmy i strukturyAlgorytmy i struktury danych Wyklad 4Algorytmy i struktury danych Wyklad 3Algorytmy Struktury?nychsql2 zad do wykAlgorytmy i struktury danych Prosty program Simulated Annealingnotatek pl W,matematyka,Algorytmy i Struktury Danychwięcej podobnych podstron