ALGORYTMY, STRUKTURY DANYCH i TECHNIKI PROGRAMOWANIA
dla Podyplomowego Studium Programowania i Systemów Baz Danych
Powrót
Informacje bieżące
Kryteria ocen
programy na ocenę 3:
Metoda bisekcji
Generowanie podciągów (test losowy)
Wyszukiwanie binarne
Numeryczne obliczanie pochodnych
Numeryczne obliczanie całek (metodą Monte Carlo)
programy na ocenę 4:
Sortowanie szybkie
(oraz programy na ocenę 3)
programy na ocenę 5:
Szukanie największej sumy w ciągłym podprzedziale wektora (metodą liniową)
Różne strategie optymalizacji kodu sortowania szybkiego
(oraz programy na ocenę 3 i 4)
Zadania dla zaawansowanych mogą zastąpić dwa dowolne zadania z powyższej listy, bądź posłużyć do uzyskania oceny celującej (5.5):
Sortowanie przez kopcowanie
Igła Buffona - obliczanie przybliżonej wartości liczby Pi
Dodatkowo należy być przygotowanym do rozmowy zaliczeniowej na tematy poruszane na wykładzie.
Zajęcia
15 godz. wykładu / 15 godz. laboratorium
- 15.10, 900 - 1435 (6 godz.), w sali 255GG.
- 12.11, 900 - 1500 (8 godz.), w sali 255GG.
- 13.11, 900 - 1500 (8 godz.), w sali 255GG.
- 27.11, 900 - 1200 (4 godz.), w sali 255GG.
- 15.01, 900 - 1200 (4 godz.), w sali 255GG.
Materiały do wykładu
[PDF]Część 1 - algorytm: definicja, poprawność;
przykłady sformułowania problemów algorytmicznych; sortowanie przez wstawianie; analiza algorytmów;
oszacowania asymptotyczne
[PDF]Część 2 - rekurencja; metoda dziel i zwyciężaj; sortowanie przez scalanie;
sortowanie szybkie - quicksort; sortowanie przez kopcowanie (stogowe); sortowanie przez zliczanie;
sortowanie pozycyjne; sortowanie kubełkowe
[PDF]Część 3 - metoda bisekcji; wyszukiwanie binarne; dowód poprawności algorytmu na przykładzie wyszukiwania binarnego; generowanie podciągów; problem komiwojażera; wieże Hanoi
[PDF]Część 4 - rozsądny a nierozsądny czas działania; klasyfikacja problemów algorytmicznych; problemy zamknięte, luka algorytmiczna; problemy decyzyjne; problemy nierozstrzygalne
[PDF]Część 5 - ogólne zasady projektowania algorytmów i programowania
[PDF]Część 5a - szukanie największej sumy w wektorze
[PDF]Część 5b - anagramy
[PDF]Część 6 - podstawowe struktury danych: stos, kolejka, lista
[PDF]Część 7 - haszowanie: tablice z haszowaniem, metody rozwiązywania kolizji, funkcje haszujące
[PDF]Część 8 - przykładowe metody numeryczne
[PDF]Część 9 - algorytmy ewolucyjne
[PDF]Część 10 - programowanie równoległe i współbieżne
Zasady zaliczenia przedmiotu
Wykład
- 80% obecności na zajęciach
- Rozmowa zaliczeniowa mająca na celu ocenę zrozumienia
algorytmów i technik programowania przedstawionych na zajęciach
Laboratorium
- 80% obecności na zajęciach.
- Praktyczne wykorzystanie wiedzy zdobytej na wykładzie: zaprogramowanie podanych algorytmów w języku C++, stosowanie odpowiednich do zadania struktur danych oraz wykorzystanie technik programowania w celu optymalizacji kodu.
- Sortowanie przez wstawianie
- Metoda bisekcji
- Generowanie podciągów (test losowy)
- Wyszukiwanie binarne
- Sortowanie szybkie + różne strategie optymalizacji kodu
- Sortowanie przez kopcowanie*
- Szukanie największej sumy w ciągłym podprzedziale wektora (metodą liniową)
- Numeryczne obliczanie pochodnych
- Numeryczne obliczanie całek (metodą Monte Carlo)
- Igła Buffona - obliczanie przybliżonej wartości liczby Pi*
* - zadanie dla zaawansowanych
Literatura
- T.H. Cormen i inni, Wprowadzenie do algorytmów, WNT 2005
- J. Bentley, Perełki oprogramowania, wyd. II, WNT 2001
- D. Harel, Rzecz o istocie informatyki. Algorytmika, WNT 2001
- P. Wróblewski, Algorytmy, struktury danych i techniki programowania, Helion 2001
- N. Wirth, Algorytmy + struktury danych = programy, WNT 2001
Powrót na początek strony