algoritmi izpit 3 rok 2014

algs_3_rok_resitve_2014

algoritmi izpit 3 rok 2014

Se vedno nism zih ce je to prav ker enih stvari niti asistent ne zna razlozit.

1)  a) integrala ni mozno zracunat zato je blo pravilno da si zapisal vse do izracuna (temu primerno je bil znizan kriterij)  p == 2
    b) n*loglog(n) * C(n) treba je pa se utemeljit tesno mejo
    c) n*loglog(n) * A(n)

2)  a)  S->aSa | bSb | cSc | aAa | bAb | cAc
        A-> a | b | c | e
    b)  S->bSb->bcScb->bcaAacb->bcaaacb
    c) z lemo o napihovanju  mors dokazat za poljubno besedo torej pogoj |xy| < n   in moras tudi napisat primer take besede  recimo aaaabaaaa
    primer za splosno je "a^n b a^n". za x lah vzames prazno, y vzames nekaj levih ajev in za z b in ostale ajev. Ko napihnes na xy^2z vids da ni vec palindrom.

3)
    a) primer: 2 mnozici hash setov recimo. Mnozica A(dopoldne) in B(popoldne). V hash setu hranis udelzence, vsak hash set predstavlja eno dejavnost, pa pol lah menjuvas iz ene mnozice v drugo v casu O(1), moras pa pol iterirat cez vse udelezence v O(n) ko zadeve prestavljas. Povedat je treba kaj je sosescina recimo prestavitev enga hashseta iz ene mnozice v drugo, konkretno: dejavnost 3 iz mnozice A v B. Nujno je treba povedat kaj je kriterijska funkcija: Preverimo vse mozne menjave dejavnosti iz ene mnozice v drugo, in izberemo najbolso, v nasem primeru tista kjer je najvec udelezencev na obeh aktivnostih.
    b) seznam stanj dolzine C. Vsako resitev ki jo obiscemo jo damo na seznam primer    101101|011011|1001010 ...    kjer ena pomeni aktivnost v mnozici A nic pa aktivnost v mnozici B. Torej eno stanje je 101101.
    c) nevem

4) primer funkcija ki z bisekcijo isce poisce X. prvi klic rekurzije paraleliziramo z klicem spawn.