Zkouška - Mareš 21. 1. 2019

Pokračování přednášky TIN060 Algoritmy a datové struktury I
NeverNotBluu
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 4. 6. 2018 19:43
Typ studia: Informatika Bc.

Zkouška - Mareš 21. 1. 2019

Příspěvek od NeverNotBluu »

1) KMP - popis, analýza, ...
2) Předseda a tajemník - Máme množinu poslanců a množinu klubů, přičemž každý poslanec může být ve více klubech. Cílem je najít pro každý klub z jeho členů předsedu a tajemníka tak, aby žádný poslanec nezastával více než jednu funkci.
3) Najděte algoritmus, který hledá průsečíky kružnic (s nápovědou, že půjde o nějakou úpravu průniků přímek)
NeverNotBluu
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 4. 6. 2018 19:43
Typ studia: Informatika Bc.

Re: Zkouška - Mareš 21. 1. 2019

Příspěvek od NeverNotBluu »

Řešení:
2) Vyrobí se bipartitní graf, kde v levé partitě jsou všichni poslanci a v pravé pro každý klub vrchol předsedy a vrchol tajemníka. Hrany se natahají z těchto dvou vrcholů klubu do každého člena toho klubu. Graf se pak klasicky doplní na síť s jednotkovými kapacitami, najde se maximální tok a pozice se pak obsadí podle těch hran, kterými tok teče.

3) Základní myšlenka je taková, že když z kružnice odeberu nejvrchnější a nejspodnější bod, stanou se mi z ní dva oblouky, což už je skoro identická úloha. Stačí tedy zametat shora dolů a když najdeme vršek kružnice, vložíme si do průřezu odkazy na Klevá a Kpravá. Na spodku kružnice je pak samozřejmě zase zahodíme.
Tohle už funguje v podstatě identicky s průniky přímek, s tím rozdílem že dva oblouky mohou mít dva společné průsečíky. To ošetřím tak, že a) když najdu průsečíky dvou oblouků, naplánuji si do kalendáře jenom ten nejvrchnější, a b) když narazím na průsečík, musím další průsečíky hledat i v té dvojici, kterou jsem právě prohodil.
Odpovědět

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