3307665906

Informatyka i Ekonometria, st. 2, 2009/2010

Metody algorytmiczne

TYP PRZEDMIOTU: DODATKOWY A

FORMA ZAJĘĆ	W	L
LICZBA GODZIN	15	30
FORMA ZALICZENIA	E	O
ECTS	7

SEMESTRY
1	2	3	4	5	6
		■

WYKŁADOWCA dr Florian Fabiś WYMAGANIA WSTĘPNE

Algorytmy i struktury danych. Rachunek prawdopodobieństwa.

EFEKTY KSZTAŁCENIA

Znajomość i umiejętność implementacji aproksymacyjnych algorytmów rozwiązywania problemów NP-trudnych.

Umiejętność stosowania zaawansowanych metod algorytmicznych do rozwiązywania różnych praktycznych problemów.

PROGRAM NAUCZANIA

1. Algorytmy aproksymacyjne. Problemy optymalizacyjne a problemy decyzyjne. Rozwiązania optymalne a rozwiązania przybliżone. Względne i bezwzględne gwarancje aproksymacji. Schematy aproksymacyjne: PTAS, FPTAS.

2. Algorytmy aproksymacyjne m.in. dla problemów: pokrycia wierzchołkowego (Vertex Cover), pokrycia zbioru (Set Cover), pakowania (Bin Packing), plecakowego (Knapsack), szeregowania (Multiprocessor Scheduling), kolorowania grafów (Graph Coloring), komiwojażera (Traveling Salesman).

3. Algorytmy Online. Analiza kosztu zamortyzowanego.

4. Metody algorytmiczne. Zachłanność. Przeszukiwanie z powracaniem. Metoda podziałów^: i ograniczeń. Programowanie dynamiczne. Algorytmy genetyczne. Algorytmy mrówkowe.

5. Zastosowania praktyczne.

LITERATURA

• V.V. Vazirani, Algorytmy aproksymacyjne, WNT, 2004.

• C.H. Papadimitriou, Złożoność obliczeniowa, WNT, 2002.

• T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, 1997.

• J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń. Wydawnictwo Naukowe PWN, 1994.

• Aho A., Hopcroft J.E., Ullman J.D., Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983.

• Banachowski L., Diks K., Ry tter W., Algorytmy i struktury danych, WNT, Warszawa 1996,

• Błażewicz J., Złożoność obliczeniowa problemów kombinatorycznych, WNT, Warszawa 1988.

• Cormen T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997.

• Knuth D ., Sztuka programowania, t. 1-3, WNT, Warszawa 2001.

WARUNKI ZALICZENIA

Warunkiem zaliczenia wykładu jest zdanie egzaminu. Egzamin odbywa się w formie pisemnej.