Zaawansowane algorytmy


Informacje ogólne

Typ:specjalnościowy
Kierunek: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).