Matematické Fórum

diky moc, ale moc tomu nerozumim, navrhente mi nejaky postup jak na to a cim zacit?

↑ Kondr:
díky za odpoved. Resim tyz problem a obecne tápu v zapisu kodu stylem programovani v prologu. Coz ma nejspise byt vystupem prave tohoto ukolu. Nas vyucujici to nazyva pseudokodem. Napriklad takto:

Euclid(a, b)
1 if b = 0
2 then return a
3 else if a > b
4 then return Euclid(b, a − b)
5 else return Euclid(a, b − a)

pricemz tento "pseudokod" reprezentuje nalezeni NSD (nejmensi spolecny delitel). Můžu te požádat ješte o podrobnější analýzu? Případně další odkaz pokud znáš? Děkuju!

↑ Kondr:
a jak bys to prosim cinil s analyzou slozitosti toho algoritmu?

↑ Kromanon: Do každého vrcholu se vleze jen jednou, udělá se v něm konstantní počet operací a prohlédne se každá hrana, která z něho vede. Každá hrana se zkoumá nejvýš dvakrát (z jednoho a druhého konce), takže celková složitost O(V+E), standardní značení V=počet vrcholů, E=počet hran.

↑ kalkulacka:Já myslím že jo. Nepíše se polynomiální vzhledem k čemu, ale vzhledem k V to je určitě v O(V^2) (to je polynom druhého stupně) a vzhledem k E nejde složitost určit (i když má graf jedinou hranu, stejně je potřeba inicializovat pole tam i zpet).

Složitost je závislost doby běhu programu na "velikosti vstupu". Pokud je vstup jedno číslo, bere se za velikost vstupu počet jeho cifer, pokud je to více čísel, jejich počet, atd. Někdy může být vstupů více, pak se složitost bere vůči více parametrům. Třeba vynásobit čísla o M a N cifrách klasickým způsobem -- každou cifrou vždy  vynásobíme všechny ostatní, počítáme u toho přesahy, přičítáme je dál... pro každou dvojici cifer tedy uděláme cca 4 operace, celkem 4MN operací.  Nás ale zajímá pouze jak rychle to roste. Pokud nám složitos něčeho vyjde jako 7MN^3+15M+N^2+3Nlog(N), bereme pouze ty nejvýznamnější členy a navíc u nich nepočítáme koeficienty a píšeme je jako parametr funkce O -- v tomto případě O(MN^3). Přece jen sečtení dvou čísel znamená na různých procesorech/v různých programovacích jazycích různý počet instrukcí, proto ty koeficienty nejsou důležité. Polynomiální složitost je jakákoliv O(f), kde f vznikne konečným počtem sčítání a násobení parametrů -- tedy třeba O(N^3+M) je polynomiální, ale O(2^N) ne.

U grafů se složitost počítá vzhledem k V a E -- počtu vrcholů a hran.  Protože E<V^2, platí pro i>1 O(V^i+E)=O(V^i), takže člen E u složitějších algoritmů často můžeme zanedbat.

↑ Kondr:
prosím estě, graf tedy bude silně souvislý pokud bude mít alespoň jednu hranu a dva uzly? A to v každém případě? Díky

↑ Kondr:
Dobře. Mám - li Tarjanuv algoritmus:

index = 0                         // DFS node number counter
S = empty                         // An empty stack of nodes
forall v in V do
  if (v.index is undefined)       // Start a DFS at each node
    tarjan(v)                     // we haven't visited yet

procedure tarjan(v)
  v.index = index                 // Set the depth index for v
  v.lowlink = index
  index = index + 1
  S.push(v)                       // Push v on the stack
  forall (v, v') in E do          // Consider successors of v
    if (v'.index is undefined)  // Was successor v' visited?
        tarjan(v')                // Recurse
        v.lowlink = min(v.lowlink, v'.lowlink)
    elif (v' is in S)           // Was successor v' in stack S?
        v.lowlink = min(v.lowlink, v'.index)
  if (v.lowlink == v.index)       // Is v the root of an SCC?
    print "SCC:"
    repeat
      v' = S.pop
      print v'
    until (v' == v)

kam tedy vrazit tu modifikaci:
over(w)
    tam[w]:=true;
    pro všechny w' do kterych vede hrana z w
         pokud tam[w']=false
             over(w')
             pokud zpet[w']=true pak zpet[w]:=true;
end;

aby to mepozbylo vyznamu co se tyce overeni te silne souvislosti?

ja sem dement:-D Diky:-D

↑ tomajs:
prece neni treba nic prepisovat, jak Kondr pise v prispevku predchozim. Staci jen podstatne jednodussi algoritmus k reseni naseho problemu

Ahoj, ráda bych se taky na něco zeptala ohledně té složitosti. Není mi to totiž nějak vůbec jasné...
Nějak totiž asi nechápu rozdíl mezi tou složitostí, co se označuje O(n) a tou, co se označuje Theta(n).
Měla jsem za to, že O je složitost maximální, tzn, že když řeknu, že nějaký algoritmus má složitost v O(n^2), znamená to, možná trošku zjednodušeně, že algoritmus nikdy neprovede víc, než n^2 instrukcí. Nicméně klidně se může stát, že skončí třeba už po n instrukcích.
A pokud má algoritmus složitost v Theta(n^2), znamená to, že složitost toho algoritmu víceméně odpovídá n^2, takže taky neprovede víc, než n^2 instrukcí, ale nemělo by se ani stát, že skončí už po n. Protože by měl vždy skončit kolem někde kolem těch n^2.
Chápu to špatně?

A tak, jak je napsáno to zadání, bych to chápala tak, že se jedná právě o tu Theta složitost, takže ten hledaný algoritmus by měl být polynomiální, takže by měl mít složitost blízkou n^k. A pokud má tady ten vámi zmiňovaný algoritmus složitost O(V+E), tak má podle mě časovou složitost lineární a tak bych se obávala, jestli to skutečně není v rozporu se zadáním.
Pokud by se zadávajícímu jednalo o tu složitost O, pak by to bylo jistě v pořádku protože složitost O(lineární) jistě patří do O(polynomiální). Ale pokud by se mu jednalo o tu složitost Theta, pak podle mě složitost Theta(lineární) jistě nepatří do Theta(polynomiální).


Jste si jisti, že se to nedá chápat tak, jak jsem uvedla?