Projektowanie algorytmów

i metody sztucznej inteligencji

Prowadz¡cy: dr in». Tomasz Krysiak

Kontakt

pok. 312 C-3, tel. [phone]

E-mail: [e-mail]

Serwer FTP: ftp://sith.ict.pwr.wroc.pl/

/Automatyka i Robotyka/PAMSI/

Zaliczenie wykªadu:

Ocena z wykªadu = 60% oceny z kolokwium + 40% oceny z laborato-
rium

Kolokwium zaliczeniowe odb¦dzie si¦ na przedostatnim wykªadzie,

tj. 8.06.2011r..

Plan wykªadów

1. Wprowadzenie: zagadnienia natury kombinatorycznej, relacja pomi¦-

dzy problemami natury optymalizacyjnej i decyzyjnej, poj¦cie instancji i
algorytmu. Funkcja zªo»ono±ci obliczeniowej algorytmu.

2. Efektywno±¢ podstawowych operacji (dodawania i usuwania elementów,

wyszukiwania elementów, itp.) w wybranych strukturach danych (sto-
sach, listach, kolejkach, kopcach, tablicach haszuj¡cych, drzewach, gra-
fach, itd.).

3. Podstawowe algorytmy: wyszukiwanie, selekcja, sortowanie.

4. Algorytmy grafowe  znajdowanie minimalnego drzewa rozpinaj¡cego,

poszukiwanie najkrótszej ±cie»ki, przepªywy w grafach.

5. Eksplozja kombinatoryczna. Algorytmy wielomianowe i ponadwielomia-

nowe. Klasy zªo»ono±ci problemów decyzyjnych (P, NP, NP-zupeªne
i silnie NP-zupeªne). Relacja pomi¦dzy NP-zupeªno±ci¡ i NP-trudno±ci¡.

6. Przykªady problemów wielomianowo rozwi¡zywalnych i (silnie)

NP-trudnych. Transformacja wielomianowa. Zarys przeprowadzania
dowodów NP-trudno±ci.

7. Algorytmy aproksymacyjne i schematy aproksymacyjne.

8. Wybrane metody sztucznej inteligencji: drzewa poszukiwa«, algo-

rytm A*, elementy teorii gier, strategie gier dwuosobowych, algorytm
MINIMAKS, algorytm alfa-beta cut.

9. Kolokwium.

Literatura

1. T. Cormen, C.E. Leiserson, R.L. Rivest, Wprowadzenie do algoryt-

mów, WNT, Warszawa, 2003.

2. Maciej Sysªo, Narsingh Deo, Janusz Kowalik, Algorytmy optymalizacji

dyskretnej, PWN, 1999.

3. N. Wirth, Algorytmy + struktury danych = programy, WNT, War-

szawa, 2004.

4. Jacek Bªa»ewicz, Problemy optymalizacji kombinatorycznej, PWN, War-

szawa 1996.

5. Jacek Bªa»ewicz, Zªo»ono±¢ obliczeniowa problemów kombinatorycz-

nych, WNT, Warszawa 1988.

6. Adam Janiak, Wybrane problemy i algorytmy szeregowania zada« i roz-

dziaªu zasobów, Akademicka Ocyna Wydawn. PLJ, Warszawa 1999.

7. Jacek Bªa»ewicz, Wojciech Cellary, Roman Sªowi«ski, Jan W¦glarz,

Badania operacyjne dla informatyków, WNT, Warszawa 1983.

8. Tadeusz Sawik, Badania operacyjne dla in»ynierów zarz¡dzania, Wy-

dawnictwa AGH, Kraków 1998.

9. Czesªaw Smutnicki, Algorytmy szeregowania, Akademicka Ocyna Wy-

dawnicza EXIT, Warszawa 2002.