Informatik-Abitur-Wiederholung: Unterschied zwischen den Versionen
Zeile 77: | Zeile 77: | ||
# '''Erläutere, ob sich die Modellierung in 1., 2. oder 3. Normalform befindet.''' | # '''Erläutere, ob sich die Modellierung in 1., 2. oder 3. Normalform befindet.''' | ||
# '''Überführe nötigenfalls schrittweise in 3. Normalform.''' | # '''Überführe nötigenfalls schrittweise in 3. Normalform.''' | ||
=Automaten= | |||
==Deterministische / Nicht-Deterministische Endliche Automaten== | |||
# Ein deterministischer endlicher Automat erhält Zahlen als Eingabe. Er soll überprüfen, ob die Zahl durch drei teilbar ist. Dafür überprüft er die Quersumme der Zahl: Ist die Quersumme durch drei teilbar, dann ist auch die Zahl selber durch drei teilbar. '''Zeichne den Übergangsgraph für diesen deterministischen endlichen Automaten.''' | |||
# '''Erläutere den Unterschied zwischen einem nicht-deterministischen endlichen Automaten und einem deterministischen endlichen Automaten.''' | |||
# Gesucht wird ein endlicher Automat, der erkennt, ob eine eingegebene Zeichenkette das Wort '''LOL''' enthält. | |||
## '''Zeichne dafür den Übergangsgraph eines <u>Nicht</u> deterministischen endlichen Automaten.''' | |||
## '''Erläutere, warum die zugrunde liegende Sprache regulär ist.''' | |||
==Reguläre Grammatik== | |||
# '''Welche Bedingungen muss eine Grammatik erfüllen, um regulär zu sein?''' | |||
# Das Alphabet der folgenden Sprachen besteht nur aus den Buchstaben a und b. '''Welche der folgenden Sprachen ist regulär? Begründe. Gib ggf. eine reguläre Grammatik an.''' | |||
## Akzeptiert wird jedes Wort beliebiger Länge, das mindestens 2 a und 2 b enthält. | |||
## Akzeptiert wird jedes Wort beliebiger Länge, das mehr a als b enthält. | |||
## Akzeptiert werden nur Wörter, die höchstens 6 Zeichen haben. | |||
## Akzeptiert werden nur Wörter, die am Anfang gleich viele a haben wie am Ende. |
Version vom 9. April 2015, 10:15 Uhr
Auf dieser Seite werden Fragen zusammengestellt, die auf die "Basics" im Informatik-Abitur abzielen.
Keine Garantie für Vollständigkeit!
Modellierung
PriorityQueue
Es soll eine Klasse PriorityQueue
erstellt werden, in der Objekte nach einer Priorität gespeichert werden sollen. Die Klasse soll u.a. über die Methoden public Object getFirst()
und public void insert(Object pObject, int pPriority)
verfügen. Die Klasse PriorityQueue
soll auf der Basis der Klasse List
oder Queue
implementiert werden.
Entscheide dich für eine der folgenden Möglichkeiten und begründe:
PriorityQueue
erbt vonList
PriorityQueue
erbt vonQueue
PriorityQueue
hat ein Objekt vom TypList
PriorityQueue
hat ein Objekt vom TypQueue
Monopoly
Bei Monopoly gibt es 40 Felder. Das sind z.T Straßen (wie z.B. die Poststraße) und z.T. Bahnhöfe (wie z.B. der Westbahnhof). Die anderen Felder (wie z.B. Elektrizätswerk, Los, Frei Parken, Gemeinschaftsfeld) werden hier der Einfachheit halber nicht betrachtet. Wenn man auf ein Feld kommt, dann kann man es kaufen, wenn es noch nicht verkauft ist. Wenn man auf einen Bahnhof oder eine Straße eines anderen Spielerst tritt, dann muss man bezahlen. Bei den Straßen hängt das davon ab, wie viele Häuser schon gebaut wurden. Bei den Bahnhöfen hängt es davon ab, wie viele Bahnhöfe der Besitzer hat. Wenn man auf eine eigene Straße tritt, dann kann man ein Haus bauen und muss dafür bezahlen.
- Entscheide dich begründet für eine Datenstruktur für die 40 Felder des Monopoly-Spiels.
- Zeichne ein Klassendiagramm mit den Klassen
MonopolyFeld
,Strasse
undBahnhof
und einer weiteren sinnvollen Klasse, die du selber einführst. Gib für die KlassenStrasse
,Bahnhof
und die von dir eingeführte Klasse auch die Attribute und Methoden an.
lineare Datenstrukturen
eine lineare Datenstruktur implementieren
- Erläutere anhand des Implementationsdiagramms die Implementationsstrategie für die Klasse
Queue
. - Implementiere die folgenden Methoden:
public boolean isEmpty()
public void enqueue(Object pObject)
public void dequeue()
public Object top()
- Die Klasse
Node
ist dabei transparent. Erläutere, was das bedeutet.
eine Liste durchlaufen
Die Klasse Bibliothek
hat ein Attribut buecherListe
vom Typ List
. In buecherListe
sind die Bücher gespeichert und zwar alphabetisch nach Titel sortiert.
Implementiere die folgenden Methoden. Verwende, wenn möglich, eine for-Schleife. Erläutere, welche Rolle Casting hier spielt.
public Bibliothek()
: Der Konstruktor erzeugt eine Bibliothek; diebuecherListe
ist zu Anfang leer. Das hat nichts mit Listendurchlauf zu tun, ist aber trotzdem wichtig...public boolean enthaelt(String pTitel)
public void einfuegen(Buch pBuch)
: FügtpBuch
an der richtigen Stelle in die Bibliothek ein.
eine Methode erläutern
Erläutere die Methode einfuegen
(s.o.) unter Verwendung der wesentlichen Fachbegriffe.
Ein Beispiel dafür findet sich unter Quelltextanalyse (Java).
Datenbanken
Entity-Relationship-Modellierung
Eine Firma möchte die Ausleihe der Dienstwagen mit einer Datenbank verwalten. Für Mitarbeiter wird Name, Vorname und Telefon gespeichert. Von den Dienstwagen das Kennzeichen und die Anzahl der Sitzplätze. Immer wenn ein Mitarbeiter einen Dienstwagen benötigt, werden das Startdatum und das Enddatum für die Ausleihe gespeichert.
Zeichne ein ER-Modell für die folgenden zwei Fälle. Begründe jeweils die Kardinalitäten.
- In der Datenbank soll nur der aktuelle Zustand gespeichert werden, d.h. es wird nur festgehalten, welcher Mitarbeiter den Dienstwagen gerade hat.
- In der Datenbank sollen auch Reservierungen für die Zukunft gespeichert werden.
Relationales Datenmodell
- Übertrage das Modell rechts in ein relationales Datenmodell.
- Erläutere, wie die Relation
belegt
in das relationale Datenmodell übertragen wird. Verwende die wesentlichen Fachbegriffe. - Was wäre die Konsequenz, wenn die Tabelle
belegt
als Primärschlüssel ein Attributid
hätte?
Normalisierung
- Benenne die Anforderungen der 1., 2. und 3. Normalform.
- Erläutere, wie man Verstöße gegen die 1., 2. und 3. Normalform feststellt.
Gegeben ist die folgende Modellierung:
- Kurs(id, bezeichnung, schuljahr, halbjahr, lehrer_kuerzel, lehrer_name)
- Leistung(↑kurs_id, schueler_id, name, vorname, note)
- Erläutere, ob sich die Modellierung in 1., 2. oder 3. Normalform befindet.
- Überführe nötigenfalls schrittweise in 3. Normalform.
Automaten
Deterministische / Nicht-Deterministische Endliche Automaten
- Ein deterministischer endlicher Automat erhält Zahlen als Eingabe. Er soll überprüfen, ob die Zahl durch drei teilbar ist. Dafür überprüft er die Quersumme der Zahl: Ist die Quersumme durch drei teilbar, dann ist auch die Zahl selber durch drei teilbar. Zeichne den Übergangsgraph für diesen deterministischen endlichen Automaten.
- Erläutere den Unterschied zwischen einem nicht-deterministischen endlichen Automaten und einem deterministischen endlichen Automaten.
- Gesucht wird ein endlicher Automat, der erkennt, ob eine eingegebene Zeichenkette das Wort LOL enthält.
- Zeichne dafür den Übergangsgraph eines Nicht deterministischen endlichen Automaten.
- Erläutere, warum die zugrunde liegende Sprache regulär ist.
Reguläre Grammatik
- Welche Bedingungen muss eine Grammatik erfüllen, um regulär zu sein?
- Das Alphabet der folgenden Sprachen besteht nur aus den Buchstaben a und b. Welche der folgenden Sprachen ist regulär? Begründe. Gib ggf. eine reguläre Grammatik an.
- Akzeptiert wird jedes Wort beliebiger Länge, das mindestens 2 a und 2 b enthält.
- Akzeptiert wird jedes Wort beliebiger Länge, das mehr a als b enthält.
- Akzeptiert werden nur Wörter, die höchstens 6 Zeichen haben.
- Akzeptiert werden nur Wörter, die am Anfang gleich viele a haben wie am Ende.