Informatik A: Fragen zur Wiederholung

Die folgenden Fragen sind zur Wiederholung der Theorie gedacht und stammen größtenteils aus den Übungen. Danke für eure Mitarbeit!

Die Fragen sollten mit dem bisherigen Vorlesungsstoff bzw. dem Skript zu beantworten sein. Die Liste wird entsprechend mit der Zeit erweitert. Wir empfehlen jedem, sich diese Fragen selbst zu stellen und offen bleibende Fragen zu klären! Selbstverständlich können in der Klausur allerdings auch andere als diese Fragen vorkommen.

Aussagenlogik

1. Welche Operatoren gibt es?
2. Was ist ein Literal?
3. Was ist eine Klausel?
4. Wann liegt eine Klausel in konjunktiver bzw. disjunktiver Form vor?
5. Was ist eine Intepretation?
6. Wo ist der Zusammenhang zwischen Interpretationen und Wahrheitstafeln?
7. Was ist ein Modell?
8. Was ist eine Tautologie?
9. Wann ist eine Formel erfüllbar, wann unerfüllbar?
10. Welche Beweisverfahren haben wir kennengelernt?
11. Was ist der Modus Ponens?
12. Was ist der Modus Tollens?
13. Wo ist der Unterschied zwischen logischer Äquivalenz und logischer Konsequenz?
14. Was ist eine Theorie?
15. Was ist der Unterschied zwischen Theorie und Axiomensystem?
16. Was ist der Unterschied zwischen Herleitbarkeit (bzw. Ableitbarkeit) und logischer Konsequenz?
17. Wann ist ein Axiomensystem korrekt?
18. Wann ist ein Axiomensystem vollständig?
19. Wann ist ein Axiomensystem inkonsistent?
20. Wann ist ein Axiomensystem Basis einer Theorie?
21. Wie funktioniert die Grundresolution?
22. Warum braucht man für Grundresolution die konjunktive Form?
23. Warum ist eine Formel ((A oder B) und (nicht B oder C)) unerfüllbar, wenn (A oder C) unerfüllbar ist?
    (Tipp: Beweise, dass (A oder C) aus ((A oder B) und (nicht B oder C)) logisch folgt. Was bedeutet logische Konsequenz? Was bedeutet Unerfüllbarkeit?)
24. Warum kann man bei der Grundresolution nicht einfach zwei Variablen auf einmal weglassen?
    (Tipp: Beweise, dass C keine logische Konsequenz aus ((A oder B oder C) und (nicht A oder nicht B oder C)) ist. Was bedeutet das für die Resolution?)
25. Was ist eine Hornklausel?

Prädikatenlogik

26. In der Aussagenlogik bestand eine atomare Formel aus genau einer einzelnen Aussagenvariable. Wie sehen atomare Formeln (d.h. die kleinsten möglichen Aussagen) in der Prädikatenlogik aus?
27. Was ist ein Term?
28. Welche Quantoren gibt es?
29. Was ist der Unterschied zwischen Variablen und Konstanten?
30. Was ist der Unterschied zwischen Funktionen und Prädikaten?
31. Kann man Terme mit logischen Junktoren verknüpfen?
32. Bei welcher Programmiersprache gibt es einen direkten Zusammenhang zur Prädikatenlogik? Welchen?
33. Darf man in der Prädikatenlogik erster Stufe über Variablen quantifizieren? Über Konstanten? Über Prädikate? Über Funktionen?
34. Darf man Funktionen verschachteln, d.h. das Ergebnis einer Funktion einer weiteren Funktion als Parameter übergeben?
35. Darf man Prädikate verschachteln?

Boolesche Algebra

36. Kennst Du die 16 möglichen booleschen Funktionen, mindestens mit logischer und algebraischer Notation?

Zahlendarstellungen

37. Angefangen bei der Zahl 0, wie hoch kannst du mit deinen 10 Fingern zählen?
38. Wozu gibt es die Hexadezimal- und die Oktalzahldarstellung?
39. In welchen Bereich wird die Zahl verschoben, um normalisierte Floatingpointdarstellungen nach IEEE 754 zu erhalten?
40. Was ist der Unterschied zwischen normalisierter und denormalisierter Floatingpointdarstellungen nach IEEE 754?
41. Was bedeutet der Begriff Überlauf bei der Addition von Zahlen fester Länge?
42. Kann auch bei der Subtraktion ein Überlauf auftreten?

Boolesche Funktionen und Schaltnetze

43. Was ist der Unterschied zwischen einer Booleschen Funktion und einer Schaltfunktion?
44. Wieviele zweistellige Boolesche Funktionen gibt es?
45. Was bedeutet der Begriff funktional vollständig im Zusammenhang mit booleschen Operatoren?
46. Überlege dir 3 funktional vollständige Mengen von Operatoren.
47. Was ist ein einschlägiger Index?
48. Was sind Minterme, was sind Maxterme?
49. Wie ist die Disjunktive Normalform einer Funktion definiert?
50. Wie ist die Konjunktive Normalform einer Funktion definiert?
51. Wie ist die Ringsummennormalform einer Funktion definiert?
52. Wie kommt man von der Menge der einschlägigen Indizes einer Booleschen Funktion zu der Disjunktiven Normalform der Funktion?
53. Wie kommt man von der Menge der einschlägigen Indizes einer Booleschen Funktion zu der Konjunktiven Normalform der Funktion?
54. Wie kommt man von den einschlägigen Indizes einer Funktion zur Ringsummennormalform?
55. Wie kommt man von der Disjunktiven Normalform zu den einschlägigen Indizes? Und von der Konjunktiven Normalform? Und von der Ringsummennormalform?
56. Welcher Zusammenhang besteht zwischen Aussagenlogik und Boolescher Algebra?
57. Was ist der wesentliche Unterschied zwischen der Konjunktiven Form in der Aussagenlogik und der Konjunktiven Normalform bei den Booleschen Funktionen?
58. Wie setzt man eine Schaltfunktion als Schaltnetz um?
59. Was ist eine Kostenfunktion für ein Schaltnetz?
60. Welche Verfahren gibt es, um Boolesche Funktionen hinsichtlich der Kosten zu optimieren? Welche der vorgestellten Kostenfunktionen kommt dabei implizit zum Einsatz?
61. Welches Prinzip liegt sowohl dem Karnaugh-Verfahren, als auch dem Verfahren von Quine und McCluskey zugrunde?
62. Wann braucht man unbedingt Quine und McCluskey?
63. Was sind die Regeln für die Optimierung einer Schaltfunktion mittels Karnaugh im Falle einer DNF bzw. RNF?
64. Wie funktioniert das Karnaugh-Verfahren, und warum?
65. Wie funktioniert das Quine-McCluskey-Verfahren, und warum?
66. Kann man mit dem Quine-McCluskey-Verfahren auch eine RNF optimieren?
67. Was sind die Voraussetzungen für die Anwendbarkeit des Karnaugh-Verfahrens?
68. Was sind die Voraussetzungen für die Anwendbarkeit des Quine-McCluskey-Verfahrens?
69. Was sind Implikanten und Primimplikaten?
70. Was ist ein Dont-Care?
71. Wie stellt man eine Schaltfunktion bzw. deren Schaltnetz als Graph dar?

Fehler und Hazards

72. Was sind schaltungsabhängige Fehler, und wie sucht man danach?
73. Was sind schaltungsunabhängige Fehler, und wie sucht man danach?
74. Was ist ein Hazard?
75. Was ist der Unterschied zwischen Hazards und Fehlern?
76. Was ist der Unterschied zwischen Funktions- und Schaltungshazards?
77. Was ist der Unterschied zwischen statischen und dynamischen Hazards?
78. Wie sucht man nach statischen bzw. nach dynamischen Hazards?
79. Wann ist ein statischer Hazard vermeidbar/unvermeidbar? Wann ein dynamischer?

Schaltwerke

80. Was ist der Unterschied zwischen einem Schaltnetz und einem Schaltwerk?
81. Warum will man bei der bistabilen Kippstufe die Eingabe (0,0) ausschließen?
82. Wie kommt man von einer bistabilen Kippstufe zu einem RS-Flip-Flop?
83. Ist eine bistabile Kippstufe schon ein Flip-Flop?
84. Die folgenden Fragen zu Flip-Flops stammen von den Vorlesungsteilnehmer(inne)n vom 10.05.2005. Danke für die Mitarbeit!
85. Flip-Flop-Fragen, die aus dem Vorlesungsstoff bzw. dem Skript zu beantworten sein sollten:
84. Was genau ist ein Flip-Flop?
85. Wozu braucht man Flip-Flops?
86. Wozu braucht man den Takt?
87. Welche Flip-Flop-Typen sind aus der Vorlesung bekannt?
88. Was sind jeweils die Besonderheiten der einzelnen Flip-Flop-Typen?
89. Warum ist beim RS-Flip-Flop die Eingabe (1,1) verboten? Warum ist hier ein anderes Eingabepaar verboten als bei der bistabilen Kippstufe?
90. Gibt es auch beim JK-Flip-Flop bzw. beim Delay-Flip-Flop unzulässige Eingaben?
91. Wie berechnet man die Wertetabellen für die einzelnen Flip-Flop-Typen? Was sind dabei jeweils die Eingabe-Variablen, und was die Ausgabe-Variablen?
92. Welche Flip-Flop-Typen enthalten jeweils schon ein anderes Flip-Flop als Baustein?
93. Wie berechnet man die Wertetabelle eines Flip-Flops, das schon ein anderes Flip-Flop enthält?
94. Was begrenzt die Maximalfrequenz des Taktes?
95. Was ist der wesentliche Unterschied zwischen einem RS-Flip-Flip und einem JK-Flip-Flop?
96. Wozu benötigt man überhaupt Delay-Flip-Flops, wenn doch die Ausgabe (Q) immer gleich der Eingabe (D) ist?
97. Wozu braucht man JK-Flip-Flops?
98. Was bedeutet "lesen" im Zusammenhang mit dem JK-Flip-Flop?
99. Wie kann man Schaltungen mit potentiell unterschiedlichen Signallaufzeiten mit Hilfe von Flip-Flops am einfachsten synchronisieren?
100. Lassen sich mit Flip-Flops Schieberegister konstruieren? Wenn ja, was ist das Prinzip? Wo wird da geschoben?
101. Wie erreicht man bei dem in der Vorlesung vorgestellten Register, dass bei E=0 seriell gelesen wird, bei E=1 aber parallel?
102. Flip-Flop-Fragen zum Nachschlagen und Weiterdenken:
102. Welche Flip-Flop-Typen außer den in der Vorlesung vorgestellten gibt es noch?
103. Wofür stehen J und K beim JK-Flip-Flop?
104. Kann ein Delay-Flip-Flop mit weniger Bausteinen als vorgeführt realisiert werden?
105. Wie problematisch ist die Fehlersuche bei Flip-Flops?
106. Warum unterscheidet man beim vorgestellten Schieberegister zwischen parallelem und seriellem Lesen?
107. Warum braucht man beim vorgestellten Schieberegister verschiedene Eingänge? Warum zusätzlich zu den parallelen noch den seriellen?

PLA

108. Wofür steht die Abkürzung PLA?
109. Wieso hat ein PLA zwei Ebenen, welche sind das?
110. Welche logischen Operationen unterstützt ein PLA?
111. Hat ein PLA mehr oder weniger Bauteile als eine entsprechender Aufbau mit Logikbausteinen?

Additions- und Multiplikationsalgorithmen

112. Welche Bauteile hat ein Von-Neumann-Addierwerk?
113. Arbeitet ein solches Addierwerk parallel oder seriell?
114. Was bestimmt die maximale Länge der Zahlen, die in einem Von-Neumann-Addierwerk addiert werden können?
115. Was sagt die Carry-Look-Ahead Methode vorher?
116. Wie viele Schritte werden bei der Carry-Look-Ahead-Addition benötigt?
117. Welche Bauteile hat der vorgestellte Von-Neumann-Multiplizierer?
118. Versuche, den Multiplikationsalgorithmus mit eigenen Worten zu beschreiben.

EBNF und Syntaxdiagramme

119. Welche Bedeutung haben die einzelnen Zeichen der EBNF?
120. Wie lässt sich eine Beschreibung in EBNF in ein Syntaxdiagramm überführen?
121. Sind EBNF und Syntaxdiagramme gleich mächtig?

(Mini-)Pascal

122. Wie ist die Grundstruktur eines Pascal-Programms?
123. Welche Arten von Schleifen kennt Pascal?
124. Welche Arten von Variablen gibt es?
125. Welche Arten von Datentypen gibt es?
126. Was ist der Unterschied zwischen Call by Value und Call by Reference?
127. Was sind Zeiger im Zusammenhang mit Pascal?
128. Was wird für den Umgang mit Listen benötigt?
129. Was unterscheidet Funktionen von Prozeduren?

Stapelmaschine

130. Lassen sich alle Mini-Pascal-Programme in Stapelmaschinencode übersetzen?
131. Welche Stapel besitzt die vorgestellte Stapelmaschine?
132. Welche Inhalte muss man angeben, um den Zustand einer Stapelmaschine zu beschreiben?
133. Was sind Zeiger im Zusammenhang mit Maschinencode?
134. Wie werden Variablen eines übergeordneten Programmteiles referenziert?
135. Welche Informationen enthält ein Aktivierungsblock, und wofür braucht man diese?
136. Welche Komponenten der Stapelmaschine werden bei einem JMP-Befehl verändert? Welche bei JLE?
137. Wie übersetzt man eine while-Schleife in Stapelmaschinencode?

Prolog

138. Was für eine Logik wird in den Logiksprachen verwendet?
139. Wie werden Algorithmen, Datentypen, Verzweigungen, Iterationen und Wertzuweisungen in Prolog umgesetzt?
140. Was wird stattdessen in der Wissensbasis gespeichert?
141. Aus welchen Teilen bestehen Prolog-Programme?
142. Was ist der Unterschied zwischen Regeln und Anfragen?
143. Wie unterscheiden sich die Namen von Prädikaten und konstanten Argumenten von den Namen von Variablen Argumenten?
144. Beschreibe den Aufbau von Fakten.
145. Womit werden Fakten abgeschlossen?
146. Was bewirken Regeln?
147. Wie bekommt man weitere Ausgaben zu Anfragen?
148. Wie sind rekursive Regeln aufgebaut?
149. Wie sind in Prolog Listen aufgebaut?
150. Wieviele Elemente kann der Kopf einer Liste enthalten?