Prüfungsteilnehmer

Kennzahl:

Prüfungstermin

Frühjahr

Kennwort:

200r

Einzelpräfungsn[mmer

66113

Arbeitsplatz-Nr.:

Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen
PrüfungsaufgabenFach:

Informatik (vertieft studiert)

Einzelprüfung:

Rechnerarchitelilur,Datenb.rBetriebssys.

Aruatrl der gestelltenThemen(Aufgaben): 2
Anzatrlder DruckseitendieserVorlage:

6

Bitte wenden!

Früttjattr2001

Seite:2

66113
Einzelprüfungsnummer:

Thema Nr. 1
S?imtlicheTeilaufgaben sind zu bearbeiten!

Teilgebiet1: Rechnerarchilelüur und Rechnerne%e
Aufgabe 1.1: Komnunikation in Rechnernetzen
Neuwerk soll mit einemWal serverversehen
Ein lokales, nachaußenabgeschottetes
werden. Dazu wird auf einembestimmtenRechnerein Dienst installiert, der von allen
anderenRechnemmittels Fernaufruf(remoteprocedurecall, RPC) genutztwird.
Der Dienst soll zwei Prozedurenzur Verfügungstellen:
-

und enthalteals Parameterden Namendes
vote: Die Prozedurdient zur Stimmenabgabe
Kandidaten(als Zeichenkette)und eineWahlnummer(als ganzeZahl), um mehrfache
verhindernzu können.
Stimmenabgabe

-

result: Die Prozedurenthalteals Parameterden NameneinesKandidatenund als
Stimmen.
Ergebnisparameterdie Zahl der für ihn abgegebenen
Der Server führe zwei Listen, närnlichein Wählerverzeichniszur Verhinderungmehrfacher
Stimmabgabeund eine Stimmenliste,in der zu jedem Kandidatendie für ihn abgegebenen
Stimmenmitgezähltwerden.

1.1.1

Man entwerfe für die Prozedurvote ein Flussdiagrammfür den Fall, dassdie Femaufrufe
vom Serverserialisiertwerden.

1.1.2

WelcheErgänzungensind erforderlich, wenn Fernaufrufenebenläufigabgewickeltwerden?

1.1.3

'at least once' oder 'at most oncet ist für die
lVelche der Aufrufsemantiken'maybe',
Lösungder Aufgabenstellungam bestengeeignet?Begründung!

1.1.4

wärenerforderlich, wenn dasNetzwerk
Welchezusätzlichen(Schutz-)Maßnahmen
Unbefugtenzugänglichwäre, und wie könntensie realisiertwerden?

Teilgebiet2: Datenbankzn
Artrgabe 2.1: Schemaentwur:fim Relationenmodell
soll durch eine Datenbankunterstätrt
Die EntrvicklungeinesgroßenProgrammsystems
werden. Sie so[ fesrhalten,welcheKomponentenvon den einzelnenEntwicklern
beigesteuertwerdenund auf welchenRechnerndie Komponentengespeichertsind.
Außerdemsoll sie Auskunft über die Zerlegungvon Komponentenin Teilkorponenten
geben.Zur LösungdieserAufgabewurde folgendesEntity-Relationship-Diagrrmentwickelt:

FortsetzungnächsteSeite!

Frühjattr2001

Seite:3

66113
Eiruelprüfungsnummer:

Entwickler

trägt bei

bestehtaus
Komponente

Rechner

Z.LJ

dasdiesemDiagrammentspricht.
EntwerfenSie ein SchemanachdemRelationenmodell,
BestimmenSie die Primär-und Fremdschlüssel.
Entwickler(E) habedie AttributeENR, Name(ENAME) und Ort (EORT).
(KBEZ), Programmiersprache
Komponente(K) habedie AttributeKNR, Bezeichnung
Compiler(KCOMP).
(KSPRA)und venvendeter
(KNR).
Rechner(R) besteheausIP-Adresse(RADR)und Komponentennummer
(DATUM)
beschrieben.
Beitrag(B) wird durchENR, KNR und Darum
(OKl.i) und Teilkomponente
(KL)
Ober-Komponente
die
Attribute
hat
Komponentenliste
(TKN).

Z.L.Z

Formulierungaus:
DrückenSie die folgendenbeidenAnfragenin umgangssprachlicher
Kt))
1. nrrcn(Kl. lxlorcN=ttcNTrtrN(KL lt<lorcN=trN7[trN 6oKN='Abrechnung'
2. nneon(Rlxlruvn=rNn (B l><l oEoRT='B*gh"tor"'E))

Aufgabe 2.22 Bibliothelisdatenbank
Zur Verwaltung des Ausleihwesensbenutzt eine Universitäts-Bibliothek folgende
Datenbank:

LESER:
BUCH:
EXEMPLAR:
AUSLEIHE:

L (LSNR,NAME, VORNAME,WOHNORT)
B q!EN, TITEL, VERLAG, EXEMPLARE)
STANDORT)
EW,
A (LSNR,ISBN, EXPNR,DATUM)

FormulierenSiefolgendeAnfragenin SQL:
2.2.I

vorhanden?
WelcheBüchersindan mehrerenStandorten

2.2.2

Von welchenBuchtitelnsindsämtlicheExemplareausgeliehen?

FortsetnrngnächsteSeite!

66113
Eirzelprüfungsnummer:

Frühjah 2001

Seite:4

Aufgabe 2.3: AlgebraischeOptimierung
werdefolgendeDatenbankbenutzt:
Zur OrganisationdesPrüfungswesens

2.3.1

Professor:
Student:
Fachbereich:

P
S
F

Prüfung:

PR

(PNAME, FBNR)
(MATRNR, NAME, VORNAME, FBNR)
(FBNR, FNAME, DEI(AN)
(PNAME, MATRNR, NOTE)

FolgendeAnfragesoll nachdenHeuristiken,Selektionmöglichstfrüh" und ,Projektion
möglichstspät' optimiertwerden.
S l><l F
tTMATRNR.
VoRNAMEoFNAME='1n1o-r61'
NAME.

sind.)
(Liste der Studenten,die im Fachbereichlnformatik eingeschrieben
2.3.2

ErläuternSie an demBeispiel,inwiefernobigeHeuristiken(evtl. abhängigvom
Mengengerüst)zu einer Optimierungder Anfrage führen.

Teilgebiet3: Betriebssysteme
Aufgabe3.1: Prozess/Thread
3.1.1

und UnterschiedezwischeneinemProzessund eiBeschreibenSie die Gemeinsamkeiten
nem Thread.

3.L.2

WelcheZuständekann ein ThreadwährendseinerLaufzeit annehmen?

Aufgabe 3.2: Koordinierung
SkizzierenSie ein Programm-Modul(Klasse),das einenRingpuffer implementiert,mit den
Prozeduren(Methoden): einfügenElementund entnehnenElement. Die Prozedurensollen
von mehrerenThreadsparallel aufrufbar sein, d.h. Siemüsseninsbesondereauf die Koordinierung achten.Als ElementkönnenSie einenbeliebigenDatenrypwählen.
3.2.1 SkizzierenSie in einer lhnen geläufigenProgrammiersprache
Ozw. in einer ProgrammierDatenstru"knren.
verwendeten
sprachenähnlichenNotation) die
3.2.2 SkuzierenSie in ähnlicherNotation ("prozedural") die beidenProzeduren(Methoden)zum
Einfügenund EntferneneinesElements.Der Schwerpunktsoll auchhierbei auf den notwenliegen.
digen Koordinierungsmaßnahmen
3.2.3 BeschreibenSie die Funktionsweisedesvon Ihnen verwendetenKoordinierungsmechanismus.

-5Frühjahr 2001

Einzelprüfungsnummer:
66113

Seite:5

ThemaNr.2
Sämtliche Teilaufgaben sind zu bearbeiten!

Aufgabe 1: Addierwerke und Multiplexer
Ein Halbaddiererbildet für Bit-Paaredie Summemod2und den übertrag.
a) Man synthetisiereauszwei HalbaddiererndasSchaltnetzfür die Bin:iraddition (Volladdierer).
b) Man synthetisiereHalb- und Volladdierer ausschließlichausNAND-Gattern.
Man zeige, wie sich mit Hilfe desVolladdierers
c) ein serielles4-Bit Addierwerk,
d) ein paralleles4-Bit Addierwerk aufbauenlässt.
e) Man zeichnedas Schdtnetzfür einenMultiplexer mit 8 Eingängenein.

Aufgabe 2: Pipelining
Die Abarbeitungeiner Maschineninstrultionerforderenebendem Zugriff auf die Arbeitsregister,
''nd -ausfthrung.
auf den Operanden-und den kstrullionscache die Befehlsdecodierung
a) Man zeichnedas entsprechende
Phasendiagramm.
b) Man skizziereeine Befehlspipelinefür diesesPhasendiagramm
unter Beräcksichtigungvon ,lnternal Forwarding".
c) Man nenneund beschreibevier Arten von Pipeline-Konflikten,die den Fluss der Befehlsabarbeitung in einer Pipelinehemmenkönnen.
d) h einer fünf-stufigenBefehlspipelinewerdennachjedem bedingtenSpringbefehldrei "Sall"Zyklen eingeschoben.
Was sollen dieseZyklen bewirken?Man zeichnedie Phasendiagranmefür die Abarbeitungvon
vier Maschinenbefehlen,
von denender ersteein bedingterSprungist, mit und ohne Statlzyklen.
Wie sehrverminderndie Stallzyklendie Leistungder Pipeline, wenn 20 % der Instruktionenbedingte Sprüngesind?
e) Man bestimmedie Beschleunigung(Speed-Up)einer k-stufigenPipeline für die Abarbeitungvon
n Instruktionen,wenn keiae Hemmnisseaufoeteu.
Wie groß ist die maximalerreichbareBeschleunigung?

FortsetanngnächsteSeite!

Früldatr 200I

Eirzelprüfungsnummer
: 66L13

Seite:6

Aufgabe 3: Übertragungstheorie
1. Erstellen Sie ein Modell einer Übertragungsstrecke.
2. Welche Rolle erfüllt hierbei die
a) Quellcodierung?
b) Kanalcodierung?
c) Leitungscodierung?

Aufgabe 4: Kanalcodierung
1. GebenSie die Defrnitiot von Hamming-Disnnz an.
2. Wie groß ist die Hamming-Distanzbei einemCodemit einfacherParitätsprüfrrng?
3. Welche Hamming-Distanzhat ein zyklischer Hamming-Codeund welche Eigenschaftenlassen
sich darausableiten?
4. Ein zyklischer Hamming-Codewird durch dasGeneratorpolynomG(z) = u3 + u + I fesrgelegt.
a) Welche Eigenschaftenbesita das Generatoryolynom@..u)?
b) Wie ist die Anzahl von Nachrichten-und Kontrollstellenfür den durch (z) erzeugtenHamming-Code?
c) GebenSie die durch Qu) erzeuge Prüfuiatrix an.

Aufgabe 5: Quellcodienrng
1. DefinierenSie die folgendenBegriffe:
a) Informationsgehalt
b) Entscheidungsgehalt
c) Redundanz

2. CodierenSiedie Zeichender folgendenQuellenachdemVerfahrenvon Huffinanundberechaen
Siedie Redundanz.

xi

xr

P (x;)

0,3

X't

0,3

x3

0,2

x4

xs

0 , 1 5 0,05

3. Ist es immer möglicheine Quelleredundarzfreian codieren?