IOI 30.1.2014

Vše co se týká bakalářských státních závěrečných zkoušek.
Dr. Eddy

IOI 30.1.2014

Příspěvek od Dr. Eddy »

Dnes relativne snadne zadani:
  • 1) Grafy:
    a) Def. kostru grafu.
    b) Pro ktera n existuje graf s prave n ruznymi kostrami?
  • 2) Lingebra:
    Mame lin. zobrazeni f: R3 -> R3, (a+b,b+c,c+a) -> (a-b,b-c,c-a).
    a) je zobrazeni dobre definovane na celem R3?
    b) je na?
    c) je proste?
  • 3) Analyza:
    a) Def. parc. derivace.
    b) Napiste nutnou podminku lok. extremu funkce vice promennych.
    c) Naleznete lokalni a globalni extremy funkce f(x,y) = xy + 12/x + 18/y na intervalu (0, +nekonecno)
  • 4) Grupy:
    a) Def. grupu.
    b) Mame algebry A({0,1,2,3,4,5}, +(mod 6)) a B({1,2,3,4,5,6}, * (mod 7)). Ukazte, ze jsou to grupy.
    c) ???
    d) Jsou A, B izomorfni?
  • 5) Vyr. logika:
    a) Definujte dukaz a vysvetlete, co znamena |--- (symbol "dokazuje, je dokazatelne").
    b) Co je to spor? Co je nezavisla formule?
    c) Dokazte A->A pomoci zakladnich axiomu A->(B->A) a (A->(B->C))->((A->B)->(A->C)).
  • 6) Automaty:
    a) Definujte jazyk.
    b) Napiste gramatiku, ktera prijme jazyk {anbn; n prirozene, >= 1}. Do jake kategorie Chomskeho hierarchie patri?
    c) Napiste gramatiku, ktera prijme jazyk {anbncn; n prirozene, >= 1}. Do jake kategorie Chomskeho hierarchie patri?
  • 7) Heapsort:
    a) V pseudokodu napiste algoritmus pro Heapsort. Napiste jeho slozitost.
    b) Slozitost Heapsortu srovnejte s Quicksortem.
  • 8) Vlakna:
    a) Def. vlakno.
    b) Nasledujici kod opravte tak, aby bylo bezpecne jej spustit ve vice vlaknech:

    Kód: Vybrat vše

    int total = 0;
    int count = 1;
    
    int compute()
    {
        int result = main_computation();
    
        total = total + result;
        count = count + 1;
    }
    
    c) Odhadnete, v kolika vlaknech je omptimalni takovou funkci spustit, pokud vite, ze funkce main_computation() je velmi narocna na vypocet?
    Vysvetlete svuj odhad. Jak se Vas odhad zmeni, pokud bude funkce hodne pristupovat na disk? Vysvetlete.
matejcik
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 29. 8. 2006 10:20

Re: IOI 30.1.2014

Příspěvek od matejcik »

chybějící otázka u grup je:

c) Jsou A a B cyklické? Pokud ano, najděte alespoň jeden generátor.

v IP verzi byla místo automatů otázka na objektové programování:

Objektové programování:
a) Co znamená, že je třída abstraktní, a k čemu se používá?
b) K čemu slouží konstruktor a destruktor?
c) Který z následujících výstupů "" (prázdný), "A", "B", "AB", "BA", může vypsat následující kód:

Kód: Vybrat vše

public class A {
   public A() {
      System.out.print("A");
   }
}

public class B extends A {
   public B() {
      System.out.print("B");
   }
}

Object o = new B();
d) Může konstruktor selhat?


jaké je řešení toho 1b? tedy, pro která n existuje graf s právě n různými kostrami?
já jsem si myslel, že se ptají na úplné grafy, tak jsem tam napsal pokud n = k^(k-2), ale u ústního mi řekli, že tak to nebylo myšleno. doteď vlastně nevím, jakým způsobem by se to řešilo
Dr. Eddy

Re: IOI 30.1.2014

Příspěvek od Dr. Eddy »

no, odpoved na 1b taky nevim, napsal jsem tam peknou blbost... :)

Jinak vsem v budoucnu statnicujicim velmi doporucuji donest si vlastni svacinu. Budete tam od pul devaty treba az do jedny nebo i dele, v kuse, moc vas nikam nepusti. A take doporucuji, aby svacina obsahovala nejen jidlo, ktere vas zasyti, ale i nakrmi mozek (tedy hlavne cukr, ale ne hroznovy, ale normalni!).
Danstahr
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 26. 1. 2012 18:50
Typ studia: Informatika Bc.

Re: IOI 30.1.2014

Příspěvek od Danstahr »

1b) n = 0 platí pro nesouvislé grafy, n=1 pro libovolný strom. Pro n >= 3 je to kružnice o n vrcholech, vždycky odebereme právě jednu hranu a to můžeme udělat n způsoby. Jediná zapeklitost je s n = 2. Takový graf nemůže obsahovat kružnici, protože při její existenci bude mít alespoň 3 kostry, pokud je souvislý. Ale pokud neexistuje kružnice, je to strom, který má jen jednu kostru. Čili odpověď zní pro libovolné přirozené n kromě dvou.
Odpovědět

Zpět na „Bakalářské SZZ“