|
Zaliczenie:
Literatura:
N.
Wirth: "Algorytmy + struktury danych = programy",
WNT
L.
Banachowska, A. Kreczmar: "Elementy analizy algorytmów",
WNT
L.
Banachowski, K. DIks, W. Rytter: "Algorytmy i struktury
danych", WNT
P.Wróblewski:
Algorytmy struktury danych i techniki programowania",
Helion
T.
H. Cormen, C. E. Leiserson, R. L. Rivest: „Wprowadzenie
do algorytmów”, WNT 2000.
J.
Bentley: „Perełki oprogramowania”, WNT 1992.
D.
Harel: „Rzecz o istocie informatyki”, WNT 1992.
Program przedmiotu:
•
Wprowadzenie:
•
pojęcie algorytmu, analizy
algorytmów,
•
pojęcie złożoności
obliczeniowej, złożoności pamięciowej,
•
operacje jednostkowe, operacje
dominujące,
•
definicja O-notacji,
•
typowe funkcje złożoności, porównanie
typowych funkcji złożoności,
•
funkcje często spotykane przy
obliczaniu złożoności: sufit, podłoga,
•
problem wież Hanoi,
•
metody rozwiązywania równań
rekurencyjnych,
•
szeregi: arytmetyczny,
geometryczny, harmoniczny.
•
Rekurencja i złożoność
obliczeniowa:
•
metoda czynnika sumacyjnego,
•
obliczanie wartości wielomianu:
metoda bezpośrednia, schemat Hornera,
•
algorytmy wzynaczania elementu
minimalnego i maksymalnego: minmax1,
minmax2, minmax3,
•
algorytm sortowania oparty na
wyznaczaniu elementu minimalnego i maksymalnego.
•
Proste algorytmy sortowania:
•
sortowanie bąbelkowe,
•
sortowanie przez proste
wybieranie,
•
sortowanie przez proste wstawianie
bez wartownika,
•
sortowanie przez proste wstawianie
z wartownikiem,
•
sortowanie Shella.
•
Sortowanie szybkie:
•
ogólna wersja sortowania
szybkiego,
•
algorytm sortowania szybkiego,
•
wyznaczanie złożoności
sortowania szybkiego,
•
metody wyboru klucza osiowego,
•
algorytm wyznaczania k-tego co do
wielkości elementu w oczekiwanym
czasie liniowym.
•
Struktury drzewiaste:
•
drzewa,
•
drzewa poszukiwań binarnych:
•
wyszukiwanie elementu,
•
wybór elementu minimalnego,
•
wybór elementu maximum,
•
wybór poprzednika elementu,
•
wybór następnika elementu,
•
wstawianie nowego elementu,
•
usuwanie istniejącego elementu,
•
drzewa zrównoważone:
•
drzewa AVL, drzewa 2-3-4, splay
trees,
•
drzewa czerwono-czarne: właściwości
drzewa czerwono-czarnego, operacje
rotacji.
•
Programowanie dynamiczne:
•
wyznaczanie liczb Fibonacciego:
•
algorytm rekurencyjny,
•
algorytm nierekurencyjny,
•
wyznaczanie Najdłuższego Wspólnego
Podciągu:
•
obliczanie długości NWP,
•
drukowanie NWP,
•
optymalne nawiasowanie macierzy.
•
Tablice mieszające:
•
pojęcie tablicy mieszającej i
funkcji mieszającej, cechy dobrej funkcji mieszającej,
•
kolizje i metody ich rozwiązywania:
•
metoda łańcuchowa:
•
algorytm wstawiania elementu,
•
algorytm wyszukiwania elementu,
•
algorytm usuwania elementu,
•
adresowanie liniowe:
•
algorytm wstawiania elementu,
•
algorytm wyszukiwania elementu,
•
algorytm usuwania elementu,
•
adresowanie kwadratowe,
•
mieszanie podwójne,
•
przykładowe funkcje mieszające:
•
prosta funkcja mieszająca dla ciągu
znaków,
•
funkcja mieszająca wykorzystująca
generator liczb pseudolosowych dla ciągu znaków,
•
prosta funkcja mieszająca dla
liczb zmiennoprzecinkowych,
•
restrukturyzacja tablic mieszających,
•
minimalna doskonała funkcja
mieszająca.
•
Kopce:
•
pojęcie kopca, jego własności,
•
usuwanie największego elelemntu,
•
przemieszczanie elementu w dół,
•
wstawianie nowego elementu,
•
przemieszczanie elementu w górę,
•
budowanie kopca,
•
sortowanie przez kopcowanie,
•
kolejki priorytetowe
reprezentowane za pomocą kopca.
•
Grafy:
•
pojęcie grafu i podstawowe
definicje: graf skierowany, graf nieskierowany, stopień wierzchołka,
droga (ścieżka), prosta droga, cykl, cykl prosty, pętla,
graf spójny, drzewo,
las, graf ważony,
•
metody reprezentacji grafów w
pamięci: listy sąsiedztwa, macierz sąsiedztwa,
•
wyznaczanie najkrótszych dróg w
grafie ważonym:
•
najkrótsze drogi z jednym źródłem,
•
najkrótsze drogi z jednym
wierzchołkiem docelowym,
•
najkrótsza droga pomiędzy parą
wierzchołków,
•
najkrótsze drogi pomiędzy
wszystkimi parami wierzchołków,
•
algorytm Floyda-Warshalla,
•
algorytm Dijkstry,
•
przeszukiwanie grafu:
•
algorytm przeszukiwania grafu w głąb,
•
wyznaczanie składowych spójności,
•
algorytm przeszukiwania grafu
wszerz,
•
znajdowanie najkrótszej drogi
pomiędzy wierzchołkami w grafie nieważonym,
•
wyznaczanie minimalnego drzewa
rozpinającego — algorytm Kruskala,
•
algorytm wyznaczania cykli Eulera.
•
Algorytmy zachłanne:
•
problemy P, NP, NP-zupełne,
•
problem wydawania reszty,
•
kolorowanie grafu na przykładzie
projektowania sekwencji zmiany świateł na
skrzyżowaniu,
•
problem komiwojażera,
•
cykl Hamiltona,
•
problemy o złożoności wyższej
niż wykładnicza.
•
Wyszukiwanie wyczerpujące:
•
metoda powrotów:
•
algorytm nierekurencyjny,
•
algorytm rekurencyjny,
•
metoda podzia-u i ograniczeń,
•
szacowanie efektywności —
metoda Monte Carlo,
•
drzewa gier: strategia min-max,
alfa-beta obcięcie,
•
metoda sita — wyznaczanie
liczb pierwszych algorytmem Eratostatenesa.
|
