Tomas Oberhuber's Homepage

Algoritmus obarvování grafu lze implementovat jako standardní prohledavání do hloubky. Vstupem do algoritmu je graf a posloupnost vrcholů, která určuje pořadí, ve kterém je vrcholům přiřazována barva. Uspořádání této posloupnosti má zásadní vliv na rychlost algoritmu – osvědčené je například sestupné uspořádání podle stupně vrcholu.

Cílem této zápočtové práce pro předmět PAA je tvorba programu, který je schopen pomocí barev vrcholově obarvit graf a to paralelně. Vrcholové obarvení grafu pomocí TeX Embedding failed! barev je NP-úplný problém. To znamená, že pro rozsáhlejší grafy tento program slouží spíše jako demonstrace možností paralelizace než jako pratická metoda řešení.

Autor: Vojtěch Holub
Rok: 2009

Na této stránce lze najít informace týkající se cvičení k přednášce Základy algoritmizace vyučované na katedře matematiky Fakulty jaderné a fyzikálně inženýrské.

Podmínky k udělení zápočtu:

1. Jsou povoleny maximálně dvě omluvené absence.
2. Je nutné vypracovat semestrální program podle níže uvedeného zadání.

Zadání semestrálního programu

Implementujte strukturu pro uložení řídké čtvercové matice NxN tj. takové, která má na každém řádku jen pár nenulových prvků.

Velké množství reálných problémů vyžaduje, aby se stroj při vykonávání zadaného úkonu v určitém místě rozhodnul a navrhnul v nějakém smyslu optimální pokračování dosavadní činnosti. Ať už jde o řízení robotů nebo šachový automat, všude je nutné se na základě vstupních parametrů a znalosti problému dobrat řešení. Aby bylo možné popsat obecně algoritmy zabývající se těmito postupy, je nutné definovat některé základní pojmy.

Definice

Definice 1 Stavový prostor TeX Embedding failed! je dán konečnou množinou stavů TeX Embedding failed! a konečnou množinou

V posledním týdnu zkouškového období tj. 14. - 18. září 2009 jsem na dovolené. Zápočty z PAA tedy budu udělovat jen do pátku 11. září 2009.

Přednáška z PAA ve středu 3. 6. 2009 od 13:30 odpadá.

Termíny závěrečných testů budou vypsány na těchto stránkách. Pokud se dohodne větší skupina na nějaký termín, pište mi na mail.

Na této stránce jsou informace o zkouškách z předmětu PNLA.

Termíny pro psaní závěrečných testů pro rok 2013:

Společnost Google nabízí až jednoleté stáže ve svých vývojářských a výzkumných centrech.