Zkouška MJ 27. 1. 10

Pokračování přednášky TIN060 Algoritmy a datové struktury I
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Zkouška MJ 27. 1. 10

Příspěvek od peci1 »

Ahoj, o pohodovosti zkousky netreba referovat =)

1) Goldberg (napsat zneni invariantu a lemmat; 1-2 z nich MJ vybral a ty chtel dokazat); jak se chova na siti s jednotkovymi kapacitami?

Ty jednotkove kapacity zaridi, ze nemame nenasycena prevedeni. To by nam zbyvala slozitost O(N^3 + NM). Jde to ale i na O(NM), kdyz si trosku vylepsime odhad poctu zvednuti. Diky implementaci nas jedno zvednuti stoji <= N. Kazda hrana ma dva vrcholy a kolikrat muzeme zvednout vrchol, uz vime, ze? Takze pro kazdou hranu mame <= 4N zvednuti, tedy cas na zvedani taky O(NM). MJ mi rikal jeste jinou verzi dukazu O(NM) zvednuti, a to pres scitani vstupnich a vystupnich stupnu vrcholu - nicmene uvedeny postup je taky spravny.

2) DFT (2,1,2,1,2,1,2,1) - spocist libovolnym zpusobem

Ja to resil vyuzitim toho, ze DFT je linearni. Rozdelil jsem si to na 3/2*(1,1,1,1,1,1,1,1) + 1/2(1,-1,1,-1,1,-1,1,-1). Na cvikach jsme si ukazali (a to MJ jako dukaz stacilo :) ), ze DFT(1,1,1,1,1,1,1,1) = (8,0,0,0,0,0,0,0) a DFT(1,-1,1,-1,1,-1,1,-1) = (0,0,0,0,8,0,0,0), tedy po secteni (12,0,0,0,4,0,0,0).

3) Hradlova sit pro porovnani dvou n-bitovych cisel (vraci 1, pokud je 1. cislo ostre vetsi).

Reseni se prekvapive podobalo paralelnimu scitani. Kdyz se clovek zamysli nad tim, jak u porovnavani vypadaji bloky a jak se skladaji, ma vyhrano. Pak jeste finta s reprezentaci pomoci p,q a mame vyhrano. Sit je dokonce jednodussi nez u scitani, nebot nas zajima jen "prenos" z jedineho bloku velikosti n.

4) Dokazte NP-uplnost nebo najdete pnm algoritmus pro hledani nezavisle mnoziny v grafu se stupni <= 4.

Prevedeme na to 3,3-SAT (2 hrany ma kazdy vrchol v trojuhelniku a dale muze byt spojen s nejvyse 2 svymi negacemi, tj. nevytvorime vic nez 4 hrany).
vexis
Matfyz(ák|ačka) level I
Příspěvky: 18
Registrován: 2. 2. 2009 21:53
Typ studia: Informatika Bc.

Re: Zkouška MJ 27. 1. 10

Příspěvek od vexis »

Jak mela teda vypadat ta hradlova sit?
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“