jenses-welt.de |
Sehschlange zu Grundlagen der Informatik | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Startseite Über Mich AHP4 Galerie Sehschlangen Tourenbuch Bookmarks Elektronik Bewertung Geschichten |
Klausur Informatik I Ecker/Falkemeier WS97/98
Aufgabe 1:
Aufgabe 2:Gegeben sei die folgende Nachricht: BCCADBDDEACCCBBACCAEBECCCEBCEC Gib die zugehörige Huffman-Kodierung an. Benutze dazu den in der Übung vorgegebenen Algorithmus. Aufgabe 3:Gegeben sei die Menge der Vorgänge: A = {A,B,C,D,E,F,G,H,I,J,K} mit den Zeitangaben: t(A) = 5, t(B) = 2, t(C) = 1, t(D) = 3, t(E) = 1, t(F) = 4, t(G) = 2, t(H) = 6, t(I) = 5, t(J) = 1 und t(K) = 2 Folgende Präzedenzen liegen vor: A<G, A<H, B<E, B<D, C<F, D<F, E<I, E<J, F<K, G<I, G<J, J<K Zeichne den Netzplan und ermittle die frühestmögliche und spätestmögliche Zeit der einzelnen Ereignisse sowie sämtliche kritischen Pfade anhand der Critical Path Method (CPM). Vorgänge ohne Vorgängervorgang sind: A, B und C. Vorgänge ohne Nachfolgevorgang sind: H, I und K. Hinweis: Die frühestmögliche Zeit eines Ereignisses E = {1, ..., m} ist gegeben durch: e(E) = 0 (für E = 1, (Anfangsereignis)) e(E) = max{e(E´) - t(A) | delta_null(A) = E und delta_eins(A) = E´} Die spätestmögliche Zeit eines Ereignisses E erhält man durch die Ausnutzung von Wartemöglichkeiten: l(E) = e(E) für E = m (Endereignis) l(E) = min{l(E´) - t(A) | delta_null(A) = E und delta_eins(A) = E´}
Aufgabe 4:Gegeben sei der folgende reguläre Ausdruck:01(((10)*|111)*|0)*1 Gib den zugeörigen deterministischen endlichen Automaten an. Die Überführungsfunktion soll sowohl als Transitionsdiagramm, als auch als Matrix angegeben werden.
Aufgabe 5:Gib den folgenden BOOLeschen Ausdruck in vollständiger konjunktiver Normalform an:(x1 <=> x2) => x3 Zeichne ferner zu dem obigen Ausdruck die äquivalente Schaltung. Verwende nur die DIN-Schaltsymbole für UND, ODER und NICHT.
Aufgabe 6:Zeichne zu folgendem Ausdruck ein Binary Decision Diagramm:((x1 xor x4) => (x2 and x3)) <=> ((x2 <=> x4) or (x1 => x3))
Aufgabe 7:Negiere folgenden Prädikatenlogischen Ausdruck:für alle x.((x or (not y)) => (x and z)) => es existiert y.(y and (z => x))
Aufgabe 8:Überprüfe mit Hilfe des Resolutionsverfahrens, ob folgender Ausdruck eine Tautologie ist:((A => B) or (B and D)) => (D or ((not A) and C))
Aufgabe 9:Bestimme den kürzesten Weg von A nach G in folgendem Graphen mit dem Verfahren von Dijkstra:
|
a) | Eine binäre Relation ist definiert als R enthalten im Kartesischen Produkt S1xS2, S1 und S2 sind Mengen. |
||||
b) | 1. Wertetabelle 2. Matrix |
||||
c) | Eine Ordnungsrelation ist reflexiv, transitiv und antisymmetrisch. | ||||
d) | Ein endlicher Automat ist definiert als Quintupel (Q, Sigma, delta, q0, F) wobei
|
||||
e) |
|
Das Alphabet Sigma ist {A, B, C, D, E }
Für jedes Zeichen aus Sigma muß nun die Wahrscheinlichkeit
ermittelt werden. Die Anzahl der Zeichen in der Nachricht beträgt n = 30.
pA | 4/30 |
pB | 6/30 |
pC | 12/30 |
pD | 3/30 |
pE | 5/30 |
Zeichen | Code | Länge |
A | 101 | 3 |
B | 111 | 3 |
C | 0 | 1 |
D | 100 | 3 |
E | 110 | 3 |
Der Netzgraph hat folgende Gestalt:
A | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
e(E) | 0 | 5 | 2 | 7 | 5 | 9 | 12 |
l(E) | 0 | 5 | 3 | 7 | 6 | 10 | 12 |
l(E) - e(E) | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
Sigma = {0, 1 }.
Es ergibt sich für den genannten regulären Ausdruck ein Automat
mit folgendem Transisitionsdiagramm und mit folgender Transitionsmatrix:
Um einen total definierten Automaten zu erhalten, muß
man einen Fehlerzustand q5 mit Trap einführen.
Delta | 0 | 1 |
q0 | q1 | q5 |
q1 | q5 | q2 |
q2 | q2 | q3 |
q3 | q2 | q4 |
q4 | q5 | q2 |
q5 | q5 | q5 |
x1 | x2 | x3 | x1 <=> x2 | E |
0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 1 | 0 |
1 | 1 | 1 | 1 | 1 |