Zaawansowane algorytmy
Informacje ogólne
Typ:specjalnościowyKierunek:Informatyka studia licencjackie
Specjalność:Algorytmy i struktury danych
Semestr:6
Wymiar zajęć:30 godz. wykładu, 30 godz. laboratorium
Punkty ECTS:6
Wymogi wstępne
- Matematyka dyskretna.
- Algorytmy i struktury danych.
- Teoria grafów i sieci.
- Wymagana jest umiejętność programowania.
Założenia i cele przedmiotu
Przegląd zaawansowanych technik algorytmicznych, struktur danych oraz algorytmów na przykładzie zastosowań w teorii grafów i geometrii obliczeniowej.Program
- Przekształcanie problemów.
- Geometryczne struktury danych.
- Technika "dziel i zwyciężaj".
- Technika zamiatania.
- Programowanie dynamiczne.
- Algorytmy aproksymacyjne.
- Schematy aproksymacyjne.
- Algorytmy randomizowane.
- Algorytmy on-line.
Sposób zaliczenia
Wykład: egzamin ustny.Laboratorium: implementacja wybranych algorytmów.
Umiejętności i kompetencje
Znajomość różnych technik algorytmicznych i umiejętność ich zastosowania przy rozwiązywaniu prostych problemów algorytmicznych.Literatura
- M. de Berg et al. Geometria obliczeniowa: algorytmy i zastosowania. WNT (2007).
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Wprowadzenie do algorytmów. WNT (2004).
- S. Daugupta, C.H. Papadimitriou, U.V. Vazirani. Algorithms. McGraw-Hill (2006).
- R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press (1995).
- F.P. Preparata, M.I. Shamos. Geometria obliczeniowa - wprowadzenie. Helion (2003).
- V.V. Vazirani. Algorytmy aproksymacyjne. WNT (2005).
