TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Antworten zum Einführungstest WS08

Antworten zum Einführungstest WS08

• Weblink: https://tuwel.tuwien.ac.at/

Vorwort

Zur Erläuterung: Ich habe das Wiki hier kurzerhand für meine Zwecke zur Protokollierung der "Welche ist die richtige, aufsteigende Reichenfolge..." verwendet, weil ich diese nicht geschafft habe.
Im Zuge dessen, ist gleich das Andere mit entstanden.
Wen's stört, der möge die Seite bitte entfernen lassen.

Die Logarithmen waren für mich persönlich auch umständlich. Aber bitte, ist meine Meinung.
Greez

Welche ist die richtige, aufsteigende Reihenfolge folgender Laufzeiten:

Bsp1

$\mathrm {O} (n^{2}),\mathrm {O} (\log _{2}(n)),\mathrm {O} (n!),\mathrm {O} (4^{n}),\mathrm {O} ({\sqrt[{4}]{(}}n)),\mathrm {O} (2^{n}),\mathrm {O} (\log _{4}(n))$

• Falsche Antwort(en):
  • $\mathrm {O} ({\sqrt[{4}]{(}}n))<\mathrm {O} (\log _{2}(n))<\mathrm {O} (\log _{4}(n))<\mathrm {O} (n^{2})<\mathrm {O} (2^{n})<\mathrm {O} (4^{n})<\mathrm {O} (n!)$
  • $\mathrm {O} ({\sqrt[{4}]{(}}n))<\mathrm {O} (\log _{2}(n))<\mathrm {O} (\log _{4}(n))<\mathrm {O} (n^{2})<\mathrm {O} (2^{n})=\mathrm {O} (4^{n})<\mathrm {O} (n!)$
  • $\mathrm {O} (n^{2})<\mathrm {O} (\log _{2}(n))<\mathrm {O} (n!)<\mathrm {O} (4^{n})<\mathrm {O} ({\sqrt[{4}]{(}}n))<\mathrm {O} (2^{n})<\mathrm {O} (\log _{4}(n))$

• Richtig

• • $\mathrm {O} (\log _{2}(n))=\mathrm {O} (\log _{4}(n))<\mathrm {O} ({\sqrt[{4}]{(}}n))<\mathrm {O} (n^{2})<\mathrm {O} (2^{n})<\mathrm {O} (4^{n})<\mathrm {O} (n!)$

Bspr2

$\mathrm {O} (n^{3}),\mathrm {O} (n\log(n)),\mathrm {O} (n),\mathrm {O} (3^{n}),\mathrm {O} ({\sqrt[{3}]{(}}n)),\mathrm {O} (5^{n}),\mathrm {O} (3\log(n))$

• Falsche Antwort(en):
  • $\mathrm {O} ({\sqrt[{3}]{(}}n))<\mathrm {O} (n)<\mathrm {O} (3\log(n))<\mathrm {O} (n\log(n))<\mathrm {O} (n^{3})<\mathrm {O} (3^{n})<\mathrm {O} (5^{n})$

• • $\mathrm {O} ({\sqrt[{3}]{(}}n))<\mathrm {O} (3\log(n))<\mathrm {O} (n)<\mathrm {O} (n\log(n))<\mathrm {O} (n^{3})<\mathrm {O} (3^{n})=\mathrm {O} (5^{n})$

• richtige Antwort
  • • $\mathrm {O} (3\log(n))<\mathrm {O} ({\sqrt[{3}]{(}}n))<\mathrm {O} (n)<\mathrm {O} (n\log(n))<\mathrm {O} (n^{3})<\mathrm {O} (3^{n})<\mathrm {O} (5^{n})$

Welche Laufzeit hat folgender Algorithmus in Abhängigkeit von n

k = 2 * n;
for (a = 1 ... 30) {
    while (k > 0) {
        k = k - 1;
        z = z * 2;
    }
}

• Richtige Antwort:
  
  • $\Theta (n)$

Welche Laufzeit hat folgender Algorithmus in Abhängigkeit von n

z = n * 3;
while ( l > 0 ) {
             a = a + 2
             l = $\lfloor$ l / 3 $\rfloor$ ;

}

• Richtige Antwort:
  
  • $\Theta (log_{3}(n))$

Welche Laufzeitabschätzung gilt für die beiden linearen Laufzeitfunktionen l(n) und m(n)?

• Richtige Antwort(en)

• • $m(n)=\Omega (l(n))$
  • $m(n)=\mathrm {O} (l(n))$
  • $l(n)=\Omega (m(n))$
  • $l(n)=\Theta (m(n))$

Welche der folgenden Definitionen ist korrekt:

• Richtige Antwort:
  • $\Omega (h(n))=\{j(n)|(\exists c,n_{0}>0),(\forall n\geq n_{0}):0\leq ch(n)\leq j(n)\}$

• • $\Theta (h(n))=\{j(n)|(\exists c_{1},c_{2},n_{0}>0),(\forall n\geq n_{0}):0\leq c_{1}h(n)\leq j(n)\leq c_{2}h(n)\}$

• • $\Omega (h(n))=\{j(n)|(\exists c,n_{0}>0),(\forall n\geq n_{0}):0\leq ch(n)\leq j(n)\}$

Wie kann man folgenden term umformen?

$\log({\sqrt {\frac {a\cdot b}{c}}})$

• Richtige Antworten:
  • $(\log(a^{\frac {1}{2}})+\log(b^{\frac {1}{2}})-\log(c^{\frac {1}{2}}))$

• • ${\frac {1}{2}}*(\log(a)+\log(b)-\log(c))$

Wie kann man den angegebenen Term anders darstellen?

${\sqrt[{4}]{x^{3}}}$

• Richtige Antwort:
  • $x^{\frac {3}{4}}$

Wie kann man den folgenden Term anders darstellen?

${\frac {x^{2}+x^{3}}{\sqrt {x^{3}}}}$

• Richtige Antworten:
  • $x^{\frac {1}{2}}+x^{\frac {3}{2}}$ UND
  • ${\frac {x+x^{2}}{\sqrt {x}}}$

Wie lautet das Ergebnis folgender Summe:

$S=\sum _{i=0}^{\infty }{\frac {1}{2^{i}}}$

• Richtige Antwort:
  • $S=2$

Welche Aussagen sind korrekt?

• Falsche Antworten:
  • $-4{\bmod {7}}=(7+4){\bmod {7}}$
  • $-4{\bmod {7}}=4{\bmod {7}}$

• Richtige Antworten:
  • $-4{\bmod {7}}=3{\bmod {7}}$
  • $-4{\bmod {7}}=(7+3){\bmod {7}}$

• Anderes Bsp.:
• Teilweise Richtig:
  • $-4{\bmod {7}}=(7+3){\bmod {7}}$

• Anderes Bsp.:
  • Richtig:
  • $22{\bmod {4}}=(16{\bmod {4}})+(6{\bmod {4}})$
  • $22{\bmod {4}}=(-11{\bmod {4}})*(-2{\bmod {4}})$