Algorytmy i struktury danych

Program zajęć:

• Wprowadzenie,
• Problem "Wież Hanoi",
• Sumy,
• Meotda czynnika sumacyjnego,
• Szeregi: arytmetyczny, geometryczny, harmoniczny.

Polecana literatura:

• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Graham R. L., Knuth D. E., Patashnik O.: Matematyka konkretna, PWN, Warszawa 1996.
• Reingold E. M., Nievergelt J., Deo N.: Algorytmy kombinatoryczne, PWN, Warszawa 1985.

• Hofstadter R. D.: Metamagical themas, Scientific American, 248(2):16--22, Marzec 1983 — historia problemu wież Hanoi,
• The On-Line Encyclopedia of Integer Sequences,
• Wolfram Math World.

Program zajęć:

• Wprowadzenie,
• Algorytmy wzynaczania elementu minimalnego i maksymalnego: minmax1, minmax2, minmax3,
• Algorytm sortowania oparty na wyznaczaniu elementu minimalnego i maksymalnego.

Polecana literatura:

• Bentley J.: Perełki oprogramowania, WNT, Warszawa 1992.
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Harel D.: Rzecz o istocie informatyki: algorytmika, WNT, Warszawa 1992.
• Sedgewick R.: Algorytmy w C++, Wydawnictwo RM Sp. z o.o., Warszawa 1999.
• Wirth N.: Algorytmy + struktury danych = programy, WNT, Warszawa 2000.

Program zajęć:

• Wprowadzenie,
• Sortowanie przez proste wybieranie,
• Sortowanie przez proste wstawianie bez wartownika,
• Sortowanie przez proste wstawianie z wartownikiem,
• Sortowanie Shella,
• Porównanie złożoności algorytmów sortowania.

Polecana literatura:

• Banachowski L., Diks K., Rytter W.: Algorytmy i struktury danych, WNT, Warszawa 1996.
• Bentley J.: Perełki oprogramowania, WNT, Warszawa 1992.
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Knuth D. E.: Sztuka programowania tom III: Sortowanie i Wyszukiwanie, WNT, Warszawa 2002.
• Sedgewick R.: Algorytmy w C++, Wydawnictwo RM Sp. z o.o., Warszawa 1999.

• http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html — demonstracja działania algorytmów sortowania.

Program zajęć:

• 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.

Polecana literatura:

• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Sedgewick R.: Algorytmy w C++, Wydawnictwo RM Sp. z o.o., Warszawa 1999.
• Wirth N.: Algorytmy + struktury danych = programy, WNT, Warszawa 2000.

• http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html — demonstracja działania algorytmów sortowania,
• Sort Benchmark Home Page.

Program zajęć:

• 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,
• Listy z przeskokami.

Polecana literatura:

• Aho A. V., Hopcroft J. E., Ullman J.D.: Projektowanie i analiza algorytmów, Wydawnictwo Helion, Gliwice 2003.
• Brass P.: Advanced data structures, draft (pełna wersja), 2007.
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Sedgewick R.: Algorytmy w C++, Wydawnictwo RM Sp. z o.o., Warszawa 1999.
• Wirth N.: Algorytmy + struktury danych = programy, WNT, Warszawa 2000.

• http://www.ececs.uc.edu/~franco/C321/html/RedBlack/ — demonstracja działania drzew czerwono-czarnych

Program zajęć:

• Pojęcie tablicy mieszaj+/-cej i funkcji mieszającej, cechy dobrej funkcji mieszającej,
• Kolizje i metody ich rozwiązywania:
• metoda łańcuchowa: wstawianie, wyszukiwanie, usuwanie,
• adresowanie liniowe: wstawiania, wyszukiwanie, usuwanie,
• 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.

Polecana literatura:

• Brass P.: Advanced data structures, draft (pełna wersja), 2007.
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Sedgewick R.: Algorytmy w C++, Wydawnictwo RM Sp. z o.o., Warszawa 1999.
• Wirth N.: Algorytmy + struktury danych = programy, WNT, Warszawa 2000.

Program zajęć:

• Wprowadzenie,
• 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.

Polecana literatura:

• Aho A. V., Hopcroft J. E., Ullman J.D.: Projektowanie i analiza algorytmów, Wydawnictwo Helion, Gliwice 2003.
• Banachowski L., Diks K., Rytter W.: Algorytmy i struktury danych, WNT, Warszawa 1996.
• Bentley J.: Perełki oprogramowania, WNT, Warszawa 1992.
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007,
• Sysło M.M.: Piramidy, szyszki i inne konstrukcje algorytmiczne, Wydawnictwa Szkole i Pedagogiczne, Warszawa 1998.

Program zajęć:

• 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.

Polecana literatura:

• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Lipski W.: Kombinatoryka dla programistów, WNT, Warszawa 2004.
• Sedgewick R.: Algorytmy w C++. Grafy, Wydawnictwo RM Sp. z o.o., Warszawa 2003.

Program zajęć:

• Wprowadzenie,
• 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.

Polecana literatura:

• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Reingold E. M., Nievergelt J., Deo N.: Algorytmy kombinatoryczne, PWN, Warszawa 1985.
• Wirth N.: Algorytmy + struktury danych = programy, WNT, Warszawa 2000.

• Mastering the Game. A History of Computer Chess.

Program zajęć:

• Wprowadzenie,
• Problemy P, NP, NP-zupełne,
• Problem wydawania reszty,
• Kolorowanie grafu na przykładzie projektowania sekwencji zmiany świateł na skrzyżowaniu,
• Problem komiwojażera.

Polecana literatura:

• Aho A. V., Hopcroft J. E., Ullman J. D.: Algorytmy i struktury danych, Wydawnictwo Helion, Gliwice 2003.
• Bryant V.: Aspekty kombinatoryki, WNT, Warszawa 1997.
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Davis P. J., Hersh R.: Świat matematyki, PWN, Warszawa 1994.
• Kubale M., i in.: Optymalizacja dyskretna. Modele i metody kolorowania grafów, WNT, Warszawa 2002.
• Sysło M.M.: Piramidy, szyszki i inne konstrukcje algorytmiczne, Wydawnictwa Szkole i Pedagogiczne, Warszawa 1998.
• Wilson R. J.: Wprowadzenie do teorii grafów, PWN, Warszawa 1998.

• A compendium of NP optimization problems,
• TSPBIB Home Page.

Program zajęć:

• Wprowadzenie,
• Generowanie permutacji,
• Generowanie podzbiorów,
• Generowanie kombinacji.

Polecana literatura:

• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Knuth D. E.: Sztuka programowania tom IV, z. 2: Generowanie wszystkich krotek i permutacji, WNT, Warszawa 2007.
• Lipski W.: Kombinatoryka dla programistów, WNT, Warszawa 2004.
• Reingold E. M., Nievergelt J., Deo N.: Algorytmy kombinatoryczne, PWN, Warszawa 1985.

Program zajęć:

• Wprowadzenie.
• Miara kompresji.
• Podstawowe metody kompresji.
• Kodowanie RLE.
• Kodowanie Huffmana.
• Kodowanie słownikowe (LZSS, LZW).
• Kodowanie arytmetyczne.

Polecana literatura:

• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa 2004.
• Czech Z.J., Deorowicz S., Fabian P., Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Skrypt nr 2400, 2007.
• Skarbek W.: Metody reprezentacji obrazów cyfrowych, Akademicka Oficyna Wydawnicza PLJ, Warszawa 1993.
• Sayood K.: Kompresja danych. Wprowadzenie, Wydawnictwo RM, Warszawa 2002.