AKs Flashcards
Nennen Sie die einzelnen Bestandteile des klassischen Konzepts des von Neumann-Rechners.
- Speicherwerk
- Rechenwerk
- Steuerwerk (Leitwerk)
- Ein- und Ausgabewerk
Angenommen, jemand beweist, dass für eine Sprache L0 die Pump-Eigenschaft des Pumping-Lemmas für EA-Sprachen erfüllt ist. Argumentieren Sie, dass es dennoch sein kann, dass L0 nicht regulär ist.
Das Pumping-Lemma für EA-Sprachen ist lediglich eine notwendige, aber keine hinreichende Bedingung. Das bedeutet, dass eine Sprache durchaus das Pumping-Lemma für EA Sprachen erfüllen kann, selbst jedoch nicht regulär ist.
Bezeichne pP die Klasse der Entscheidungsprobleme, die von einer probabilistischen Turingmaschine in Polynomialzeit mit einer vorgegebenen Wahrscheinlichkeit größer gleich p korrekt gelöst werden.
(a) Begründen Sie, warum P /teilmengegleich pP gilt (unabhängig vom Wert von p).
Eine deterministische Turingmaschine kann als Spezialfall einer probabilistischen Turingmaschine betrachtet werden, die in jedem Zustand eine Folgekonfiguration mit der Wahrscheinlichkeit eins wählt.
Folglich muss P eine Teilmenge von pP sein.
Bezeichne pP die Klasse der Entscheidungsprobleme, die von einer probabilistischen Tur- ingmaschine in Polynomialzeit mit einer vorgegebenen Wahrscheinlichkeit größer gleich p korrekt gelöst werden.
(b) Begründen Sie, warum pP /teilmengegleich NP gilt (unabhängig vom Wert von p).
Eine probabilistische Turingmaschine kann hingegen als Spezialfall einer nichtdeterministischen Turingmaschine betrachtet werden, die bei jeder Ausführung immer nur einen zufällig gewählten Ableitungsbaum durchläuft . Falls ein Problem also von einer probabilistischen Turingmaschine mit einer beliebigen Wahrscheinlichkeit in Polynomialzeit gelöst werden kann, so kann es auch von einer nichtdeterministischen Turingmaschine in Polynomialzeit gelöst werden . Folglich muss pP eine Teilmenge von NP sein.
synchroner JK-Flip-Flop
Signalverläufe
- s kommt nach j und nur bis Taktende
- r kommt nach k, nur bis Taktende
- q kommt nach s bis r fertig
- q /strich gespiegelt q
CPU, Register, Cache, Arbeitsspeicher
Preis pro Bit, Zugriffszeit, Kapazität
Nennen Sie die drei typischen Datensammel- wege heutiger Rechner und beschreiben Sie kurz deren Aufgabe
- Datenbus: bidirektionale Übertragung von Daten
- Adressbus: Übertragung der von der CPU berechneten Speicheradresse
- Kontrollbus / Steuerbus: Übermittlung von Steuersignalen zwischen der CPU und den anderen Funktionseinheiten
Was bedeutet es, wenn di eZuordnungsfunktion F(/sigma ) für die Seite den Ungültigkeitswert n liefert?
Es tritt ein Seitenfehler auf, d.h. die Seite /sigma ist nicht im Hauptspeicher.
Welche zwei Fälle können unterschieden werden, wenn F(/sigma ) = n ist? Wie ist das jeweilige Vorgehen?
(1) es gibt einen freien Seitenrahmen: Seite /sigma wird in den Seitenrahmen kopiert
(2) es gibt keinen freien Seitenrahmen: befüllter Seitenrahmen p wird in den Hintergrundspeicher kopiert (Strategie zur Auswahl von p: least frequently used, least recently used, . . . ); Seite wird in Seitenrahmen p kopiert
