Hľadaj Zobraz: Univerzity Kategórie Rozšírené vyhľadávanie

45 035   projektov
0 nových

Zložitosť - príklady z Programovacej techniky

«»
Prípona
.doc
Typ
výpočet
Stiahnuté
62 x
Veľkosť
0,2 MB
Jazyk
slovenský
ID projektu
1272
Posledná úprava
13.07.2015
Zobrazené
3 093 x
Autor:
-
Facebook icon Zdieľaj na Facebooku
Detaily projektu
Popis:
Príklady zo zložitosti k predmetu Programovacie techniky

Príklad 1: Analyzujte zložitosť pre program RAM na výpočet faktoriálu čísla n ( n!)
Riešenie:
a) algoritmus v PL jazyku:
begin
read r1 ;
r2 ß 1 ;
if r1 £ 1 then write 1;
else begin
for r3 » 1 step 1 until r1
r2 » r2 * r3 ;
write r2 ;
end
end

Kľúčové slová:

programovacie techniky

uniformná zložitosť

algoritmus

RAM

výpočet

program

determinant

Turingov stroj



Obsah:
  • Príklad 1: Analyzujte zložitosť pre program RAM na výpočet faktoriálu čísla n ( n!)
    Príklad 2: Analyzujte zložitosť programu RAM, ktorý rozpoznáva jazyk L = 1n 2 n^2 0 .
    Príklad 3: Zostrojte program v PL na výpočet nn o uniformnej zložitosti (časovej) O (log n ).
    Príklad 4: Zostrojte program v PL aj RAM na výpočet súčtu 1+2 + . . . . .+n a analyzujte jeho zložitosť.
    Príklad 5: Napíšte program v PL aj v RAM na výpočet nájdenia maximálneho prvku vstupného reťazca prirodzených čísel dĺžky n . Analyzujte zložitosť .
    Príklad 6: Napíšte program v PL aj RAM na výpočet 2 n kde n je vstupný údaj. Analyzujte zložitosť.
    Príklad 7: Napíšte program v PL a RAM na výpočet súčtu 1 + 3 + …. + (2n + 1), n je vstupný údaj. Analyzujte zložitosť.
    Príklad 8: Analyzujte zložitosť lineárneho RAM programu na výpočet determinantu rozmerov n x n.
    Príklad 9: Zostrojte rozhodovací strom pre usporiadanie 4 čísel a, b, c, d.
    Príklad 10: Napíšte binárny program a logickú schému pre násobenie dvoch dvojbitových čísel [a1a0], [b1b0].
    Príklad 11: Simulujte viacpáskovým Turingovým strojom RAM inštrukciu ADD *20.
    Príklad 12: Simulujte viacpáskovým Turingovým strojom RAM inštrukciu STORE 30.
    Príklad 13: Simulujte RAM ADD *i na RASP stroji. Nech n je počet inštrukcií programu.
    Príklad 14: Simulácia RASP -RAM. Simulujte na RAM stroji RASP inštrukciu ADD i.