[NTIN017] - Paralelní algoritmy (19.6.2015)

Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
Příspěvky: 98
Registrován: 22. 9. 2010 16:07
Typ studia: Informatika Bc.
Kontaktovat uživatele:

[NTIN017] - Paralelní algoritmy (19.6.2015)

Příspěvek od Davpe »

1) Vyslovit a dokázat tvrzení že na součet n čísel je potřeba aspoň log n času
Ptal se na předpoklady, proč tahle věta plátí když jsme měli algoritmus na sčítání n čísel který byl rychlejší než log n, jak rychle a s jakým počtem procesorů umíme sčítat

2) Zjistit počet artikulací v grafu zadaném maticí sousednosti
Použiju algoritmus na komponenty 2-souvislosti. Pak se pro každý vrchol podívám na čísla komponent hran které z něj vycházejí a z těchto čísel vezmu minimum a maximum a porovnám je. Pokud jsou stejně, vrchol leží v jedné komponentě 2-souvislosti a tedy není artikulace, pokud se liší tak vrchol leží ve více komponentách souvisloti a je artikulace a zapíšu si do nějakého pomocného pole pro tento vrchol jedničku. Pak jen stačí spočítat součet tohoto pole. Taky je potřeba lepší datová struktura než jen zadaná matice sousednosti

Další otázky: Paralelní optimální třídění (dokázat nechtěl nic, jen vyslovit invarianty, proč mergewithhelp umíme udělat rychle, jaké jsou podmínky na vstupní posloupnosti, ukázat jak dlouho algoritmus trvá)

Nechodil jsem na přednášky (nějak jsem z tohohle předmětu neplánoval dělat zkoušku) takže pro mě byla ta zkouška docela těžká, slidy mi nepřijdou moc dostačující. Spoustu se toho dá najít v Jájovi (Třídění, Komponenty (dvou)souvislosti, min kostra), Eulerovy cykly jsou v "Finding euler circuits in logarithmic parallel time" (B. Awerbuch, A. Israeli, Y. Shiloach ), Rytterův algoritmus v " On the recognition of context-free languages " (Wojciech Rytter).
Mráz vyžaduje pochopení látky a hodně se vyptává, ale je hodný a ledacos odpustí.
Odpovědět

Zpět na „I1 Ostatní Teoretická informatika“