Module aus dem Wahlfachkatalog Informatik** - Exam.pdf

Aufgabe 1)

Du untersuchst eine fiktive Programmiersprache, die auf kontextfreien Grammatiken basiert. Diese Sprache enthält grundlegende Kontrollstrukturen wie Schleifen und Bedingungen. Es gibt zwei Aufgaben: (1) Die formale Spezifikation der Grammatik in erweiterter Backus-Naur-Form (EBNF) zu schreiben und (2) einen Syntaxbaum und die zugehörige operationale Semantik für ein gegebenes Codebeispiel zu erstellen.

a)

Gib die EBNF-Definition für die folgenden Sprachkonstrukte: Variablenzuweisung, If-Anweisung und While-Schleife. Nutze dazu die Notationen für Terminalsymbole, Nichtterminalsymbole, Optionale und Wiederholungen.

• Variablenzuweisung: Eine Variable wird mit einem Ausdruck versehen.
• If-Anweisung: Ein bedingter Ausdruck, der einen Block ausführen kann, wenn die Bedingung wahr ist, und optional einen anderen Block, wenn die Bedingung falsch ist.
• While-Schleife: Führt einen Block solange aus, wie die Bedingung wahr bleibt.

Lösung:

EBNF-Definition für Sprachkonstrukte

Im Folgenden findest Du die EBNF-Definitionen für Variablenzuweisungen, If-Anweisungen und While-Schleifen in der fiktiven Programmiersprache:

• Variablenzuweisung: Eine Variable wird mit einem Ausdruck versehen.

 ::=  '='  ';' ::=  ::=  |  '+'  |  '-'  ::=  |  '*'  |  '/'  ::=  |  | '('  ')' ::= letter {letter | digit} ::= digit {digit} ::= 'a' | 'b' | 'c' | ... | 'z' | 'A' | 'B' | 'C' | ... | 'Z' ::= '0' | '1' | '2' | ... | '9'

• If-Anweisung: Ein bedingter Ausdruck, der einen Block ausführen kann, wenn die Bedingung wahr ist, und optional einen anderen Block, wenn die Bedingung falsch ist.

 ::= 'if' '('  ')'  ['else' ] ::=    ::= '==' | '!=' | '<' | '>' | '<=' | '>=' ::= '{' {} '}' ::=  |  |  |  ';'

• While-Schleife: Führt einen Block solange aus, wie die Bedingung wahr bleibt.

 ::= 'while' '('  ')' 

b)

Zeichne einen Syntaxbaum für das folgende Codebeispiel unter Verwendung der in Subexercise 1 definierten Grammatik:

 if (x > 0)    y = y + 1;  else    y = y - 1;

Lösung:

Syntaxbaum für das Codebeispiel

Hier ist der Syntaxbaum für das gegebene Codebeispiel:

 if (x > 0)    y = y + 1;  else    y = y - 1;

• Root: if_statement
• Children:

• if:'if'
• condition:
• '('
• expression (x)
• rel_op ('>')
• expression (0)
• ')'
• block (if-true):
• '{'
• statement (variable_assignment)
• variable (y)
• '='
• expression
• term (y)
• '+'
• expression (1)
• ';'
• '}'
• else:'else'
• block (else):
• '{'
• statement (variable_assignment)
• variable (y)
• '='
• expression
• term (y)
• '-'
• expression (1)
• ';'
• '}'

c)

Beschreibe die operationale Semantik für das obige Codebeispiel. Gehe dabei detailliert auf die Zustandsänderungen ein, die bei der Ausführung des Codes auftreten. Berücksichtige dabei auch die Start- und Endzustände der Variablen.

Lösung:

Operationale Semantik für das Codebeispiel

Die operationale Semantik beschreibt, wie sich der Zustand des Programms Schritt für Schritt ändert, wenn der Code ausgeführt wird. Im vorliegenden Codebeispiel handelt es sich um eine If-Anweisung, die abhängig von der Bedingung entweder eine bestimmte Aktion ausführt oder eine alternative Aktion. Beschreiben wir die Zustandsänderungen im Detail:

 if (x > 0)    y = y + 1;  else    y = y - 1;

Initialzustand

• \textbf{Variable x}: Unbekannter Startwert
• \textbf{Variable y}: Unbekannter Startwert

Bedingungsprüfung

• Der Ausdruck (x > 0) wird ausgewertet:
• Falls x > 0 wahr ist:
• Die Anweisung y = y + 1; wird ausgeführt:
• Der aktuelle Wert von y wird um 1 erhöht.
• Neuer Wert von y: y + 1

• Sonst (falls x > 0 falsch ist):

Die Anweisung y = y - 1; wird ausgeführt:

• Der aktuelle Wert von y wird um 1 verringert.
• Neuer Wert von y: y - 1

Endzustand

• \textbf{Variable x}: Bleibt unverändert (gleich dem Startwert)
• \textbf{Variable y}: Wird entweder um 1 erhöht oder um 1 verringert, abhängig davon, ob die Bedingung x > 0 wahr oder falsch ist

Zusammenfassend führen die einzelnen Schritte zu einer Zustandsänderung, die davon abhängt, ob der Wert der Variablen x größer als 0 ist oder nicht. Diese Änderung wird durch die entsprechende Anweisung (Erhöhung oder Verringerung von y) umgesetzt.

Aufgabe 2)

Gegeben: Ein ungerichteter Graph G(V,E) mit den Knoten V und den Kanten E. Wir möchten verschiedene Operationen auf diesem Graphen durchführen, darunter das Auffinden des kürzesten Pfades, das Sortieren der Knoten in einer bestimmten Ordnung und das effiziente Suchen nach einem bestimmten Knoten.

a)

A: Implementiere den Algorithmus von Dijkstra zur Bestimmung der kürzesten Pfade von einem Startknoten s zu allen anderen Knoten in G. Zeige die Schritte des Algorithmus anhand eines Beispielgraphen mit mindestens 5 Knoten und 7 Kanten.

'def dijkstra(graph, start):  import heapq  priority_queue = []  heapq.heappush(priority_queue, (0, start))  distances = {vertex: float('infinity') for vertex in graph}  distances[start] = 0  while priority_queue:      current_distance, current_vertex = heapq.heappop(priority_queue)      if current_distance > distances[current_vertex]:          continue      for neighbor, weight in graph[current_vertex].items():          distance = current_distance + weight          if distance < distances[neighbor]:              distances[neighbor] = distance              heapq.heappush(priority_queue, (distance, neighbor))  return distances'

Lösung:

Gegeben: Ein ungerichteter Graph G(V,E) mit den Knoten V und den Kanten E. Wir möchten verschiedene Operationen auf diesem Graphen durchführen, darunter das Auffinden des kürzesten Pfades, das Sortieren der Knoten in einer bestimmten Ordnung und das effiziente Suchen nach einem bestimmten Knoten.

A: Implementiere den Algorithmus von Dijkstra zur Bestimmung der kürzesten Pfade von einem Startknoten s zu allen anderen Knoten in G. Zeige die Schritte des Algorithmus anhand eines Beispielgraphen mit mindestens 5 Knoten und 7 Kanten.

Hier ist der Python-Code, der den Dijkstra-Algorithmus implementiert:

def dijkstra(graph, start):  import heapq  priority_queue = []  heapq.heappush(priority_queue, (0, start))  distances = {vertex: float('infinity') for vertex in graph}  distances[start] = 0  while priority_queue:      current_distance, current_vertex = heapq.heappop(priority_queue)      if current_distance > distances[current_vertex]:          continue      for neighbor, weight in graph[current_vertex].items():          distance = current_distance + weight          if distance < distances[neighbor]:              distances[neighbor] = distance              heapq.heappush(priority_queue, (distance, neighbor))  return distances

Um den Algorithmus zu demonstrieren, betrachten wir den folgenden Beispielgraphen:

• Knoten: V = {A, B, C, D, E}
• Kanten: E = {(A, B, 1), (A, C, 4), (B, C, 2), (B, D, 5), (C, D, 1), (C, E, 3), (D, E, 2)}

Der Graph kann als Dictionary dargestellt werden:

graph = {    'A': {'B': 1, 'C': 4},    'B': {'A': 1, 'C': 2, 'D': 5},    'C': {'A': 4, 'B': 2, 'D': 1, 'E': 3},    'D': {'B': 5, 'C': 1, 'E': 2},    'E': {'C': 3, 'D': 2}}

Wenn wir den Algorithmus von Dijkstra für den Startknoten 'A' anwenden, erhalten wir die kürzesten Distanzen zu allen anderen Knoten:

distances = dijkstra(graph, 'A')print(distances)

Die Ausgabe zeigt die kürzesten Distanzen von 'A' zu allen anderen Knoten:

{ 'A': 0, 'B': 1, 'C': 3, 'D': 4, 'E': 6 }

Dies bedeutet, dass der kürzeste Pfad von 'A' zu 'B' eine Distanz von 1 hat, von 'A' zu 'C' eine Distanz von 3, und so weiter.

b)

B: Sortiere die Knoten des Graphen topologisch, falls der Graph ein DAG (gerichteter, azyklischer Graph) ist. Erläutere den Algorithmus und seine Komplexität. Demonstriere den Algorithmus anhand eines Graphen mit mindestens 6 Knoten und 8 Kanten.

Lösung:

Gegeben: Ein ungerichteter Graph G(V,E) mit den Knoten V und den Kanten E. Wir möchten verschiedene Operationen auf diesem Graphen durchführen, darunter das Auffinden des kürzesten Pfades, das Sortieren der Knoten in einer bestimmten Ordnung und das effiziente Suchen nach einem bestimmten Knoten.

B: Sortiere die Knoten des Graphen topologisch, falls der Graph ein DAG (gerichteter, azyklischer Graph) ist. Erläutere den Algorithmus und seine Komplexität. Demonstriere den Algorithmus anhand eines Graphen mit mindestens 6 Knoten und 8 Kanten.

Der Algorithmus zur topologischen Sortierung eines gerichteten, azyklischen Graphen (DAG) kann mit einem Tiefensuche-Algorithmus (DFS) oder mit dem Kahn-Algorithmus durchgeführt werden. Hier werden wir die DFS-basierte Methode erläutern:

1. Algorithmus:

• Initialisiere einen leeren Stack und eine Besuchsmarkierung für alle Knoten.
• Führe eine DFS für jeden unbesuchten Knoten aus. Markiere den aktuellen Knoten als besucht.
• Für jeden Nachbarn des aktuellen Knotens, führe rekursiv eine DFS aus.
• Nach der Bearbeitung aller Nachbarn, füge den aktuellen Knoten zum Stack hinzu.
• Am Ende der DFS-Rekursion, gibt das Stapelmuster die topologische Sortierung der Knoten an.

Die Zeitkomplexität des Algorithmus ist O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.

Hier ist der Python-Code, um die topologische Sortierung durchzuführen:

def topological_sort(graph):  def dfs(vertex, visited, stack):    visited.add(vertex)    for neighbor in graph.get(vertex, []):      if neighbor not in visited:        dfs(neighbor, visited, stack)    stack.append(vertex)  visited = set()  stack = []  for vertex in graph:    if vertex not in visited:      dfs(vertex, visited, stack)  stack.reverse()  return stack

Um den Algorithmus zu demonstrieren, betrachten wir den folgenden Beispielgraphen:

• Knoten: V = {A, B, C, D, E, F}
• Kanten: E = {(A, B), (A, C), (B, D), (C, D), (D, E), (E, F), (C, F), (B, E)}

Der Graph kann als Dictionary dargestellt werden:

graph = {  'A': ['B', 'C'],  'B': ['D', 'E'],  'C': ['D', 'F'],  'D': ['E'],  'E': ['F'],  'F': []}

Wenn wir die Methode zur topologischen Sortierung anwenden, erhalten wir die folgende Sequenz:

sorted_nodes = topological_sort(graph)print(sorted_nodes)

Die Ausgabe zeigt die topologische Sortierung der Knoten:

['A', 'B', 'C', 'D', 'E', 'F']

Dies bedeutet, dass Knoten 'A' vor 'B' und 'C' kommen muss, 'B' und 'C' vor 'D', und so weiter.

c)

C: Führe eine binäre Suche auf einer sortierten Liste der Knoten des Graphen durch, um nach einem bestimmten Knoten x zu suchen. Zeige die Schritte der binären Suche und analysiere ihre Zeitkomplexität.

'def binary_search(sorted_list, target):  left, right = 0, len(sorted_list) - 1  while left <= right:      mid = (left + right) // 2      if sorted_list[mid] == target:          return mid      elif sorted_list[mid] < target:          left = mid + 1      else:          right = mid - 1  return -1'

Lösung:

Gegeben: Ein ungerichteter Graph G(V,E) mit den Knoten V und den Kanten E. Wir möchten verschiedene Operationen auf diesem Graphen durchführen, darunter das Auffinden des kürzesten Pfades, das Sortieren der Knoten in einer bestimmten Ordnung und das effiziente Suchen nach einem bestimmten Knoten.

C: Führe eine binäre Suche auf einer sortierten Liste der Knoten des Graphen durch, um nach einem bestimmten Knoten x zu suchen. Zeige die Schritte der binären Suche und analysiere ihre Zeitkomplexität.

Hier ist der Python-Code, der die binäre Suche implementiert:

def binary_search(sorted_list, target):  left, right = 0, len(sorted_list) - 1  while left <= right:      mid = (left + right) // 2      if sorted_list[mid] == target:          return mid      elif sorted_list[mid] < target:          left = mid + 1      else:          right = mid - 1  return -1

Um den Algorithmus zu demonstrieren, nehmen wir an, die Knoten des Graphen sind alphabetisch sortiert:

sorted_nodes = ['A', 'B', 'C', 'D', 'E', 'F']

Wir möchten beispielsweise nach dem Knoten 'D' suchen:

target = 'D'

Die Schritte der binären Suche sind wie folgt:

• Initialisiere left mit 0 und right mit 5 (Index des letzten Elements).
• Berechne den Mittelwert: mid = (0 + 5) // 2 = 2. Vergleiche sorted_nodes[2] ('C') mit dem Zielknoten 'D'. Da 'C' < 'D', setze left auf mid + 1 = 3.
• Berechne den Mittelwert: mid = (3 + 5) // 2 = 4. Vergleiche sorted_nodes[4] ('E') mit dem Zielknoten 'D'. Da 'E' > 'D', setze right auf mid - 1 = 3.
• Berechne den Mittelwert: mid = (3 + 3) // 2 = 3. Vergleiche sorted_nodes[3] ('D') mit dem Zielknoten 'D'. Da sie übereinstimmen, gib den Index 3 zurück.

Die Ausgabe zeigt den Index des Zielknotens:

index = binary_search(sorted_nodes, target)print(index)  # Ausgabe: 3

Da der Index 3 zurückgegeben wird, haben wir den Knoten 'D' erfolgreich gefunden.

Komplexitätsanalyse:

• Die Zeitkomplexität der binären Suche ist O(log n), wobei n die Anzahl der Elemente in der Liste ist. Dies liegt daran, dass der Suchbereich in jeder Iteration halbiert wird.
• Die Raumkomplexität ist O(1), da nur eine konstante Menge an zusätzlichem Speicher benötigt wird.

Aufgabe 3)

Datenbankdesign und Normalisierung:Datenbankdesign bezieht sich auf die Strukturierung von Datenbanken zur effizienten und widerspruchsfreien Speicherung von Daten. Die Normalisierung ist ein Prozess, der Redundanzen und Inkonsistenzen durch die Aufteilung in kleinere, miteinander verknüpfte Tabellen eliminiert. Die Hauptziele sind Redundanzfreiheit, Konsistenz, Flexibilität und Performance. Die Normalformen helfen bei diesem Prozess:

• 1NF (Erste Normalform): Elimination von Wiederholungsgruppen. Jedes Attribut enthält nur atomare, unteilbare Werte.
• 2NF (Zweite Normalform): Elimination partieller Abhängigkeiten. Eine Tabelle ist in 2NF, wenn sie in 1NF ist und alle Nicht-Schlüsselattribute voll funktional vom Primärschlüssel abhängig sind.
• 3NF (Dritte Normalform): Elimination transitiver Abhängigkeiten. Eine Tabelle ist in 3NF, wenn sie in 2NF ist und keine Nicht-Schlüsselattribute transitiv abhängig sind.

Der gesamte Prozess soll Inkonsistenzen und Anomalien vermeiden.

a)

Gegeben sei die folgende Tabelle einer Datenbank, die Informationen zu den Kursen an der TU München speichert:

 KursID | KursName            | Dozent       | DozentenTel | StudentID | StudentName | Studienfach | Note  ------------------------------------------------------------------------------------------  1    | Datenbankdesign    | Dr. Müller   | 1234567    | 1001      | Anna Schmidt| Informatik  | 1.3 1    | Datenbankdesign    | Dr. Müller   | 1234567    | 1002      | Max Mustermann | Informatik  | 2.0 2    | Algorithmen        | Dr. Meier    | 7654321    | 1003      | Maria Klein   | Mathematik  | 2.5 2    | Algorithmen        | Dr. Meier    | 7654321    | 1004      | Julia Neu     | Informatik  | 1.7

• Analysiere die Tabelle und bestimme, ob sie in der ersten Normalform (1NF) ist. Wenn nicht, zeige detailliert, wie sie in die 1NF überführt werden kann.

Lösung:

Unterübung: Analyse und Überführung in die 1. Normalform

Analyse der Tabelle:Wir haben eine Tabelle mit den folgenden Spalten:

 KursID | KursName    | Dozent     | DozentenTel | StudentID | StudentName | Studienfach | Note  

• KursID: Eindeutige Kennung für jeden Kurs.
• KursName: Name des Kurses.
• Dozent: Name des Dozenten, der den Kurs unterrichtet.
• DozentenTel: Telefonnummer des Dozenten.
• StudentID: Eindeutige Kennung für jeden Studenten.
• StudentName: Name des Studenten.
• Studienfach: Fachrichtung des Studenten.
• Note: Note, die der Student im Kurs erhalten hat.

Prüfung auf die 1. Normalform (1NF):Eine Tabelle ist in der 1NF, wenn sie keine Wiederholungsgruppen enthält und alle Attribute atomare, unteilbare Werte enthalten. Die gegebene Tabelle enthält bereits atomare Werte, aber es könnte Verwirrung entstehen, wenn Kurse mehrfach in der Tabelle vorkommen (wie bei KursID = 1 mit unterschiedlichen Studenten). Hier sind jedoch die Werte korrekt atomar, und die Struktur der Daten entspricht den Anforderungen der 1NF.Beispiel für die aktuelle Tabelle:

KursID | KursName          | Dozent      | DozentenTel | StudentID | StudentName   | Studienfach | Note------------------------------------------------------------------------------------------ 1    | Datenbankdesign  | Dr. Müller  | 1234567    | 1001      | Anna Schmidt  | Informatik  | 1.3 1    | Datenbankdesign  | Dr. Müller  | 1234567    | 1002      | Max Mustermann| Informatik  | 2.0 2    | Algorithmen      | Dr. Meier   | 7654321    | 1003      | Maria Klein   | Mathematik  | 2.5 2    | Algorithmen      | Dr. Meier   | 7654321    | 1004      | Julia Neu     | Informatik  | 1.7

Die Tabelle entspricht der 1. Normalform, da alle Daten atomar und jede Zeile einzigartig identifizierbar ist.

b)

Überführe die Tabelle, die nun in 1NF ist, in die zweite Normalform (2NF). Zeige den Übergang und die resultierenden Tabellen. Begründe jede deiner Schritte präzise.

Lösung:

Überführung der Tabelle in die zweite Normalform (2NF)

Nachdem die Tabelle bereits in der ersten Normalform (1NF) ist, arbeiten wir nun daran, sie in die zweite Normalform (2NF) zu überführen. Dabei eliminieren wir partielle Abhängigkeiten – dies bedeutet, dass alle Nicht-Schlüsselattribute voll funktional vom Primärschlüssel abhängen müssen.

• Schritt 1: Bestimmung der Primärschlüssel:Angenommen, der Primärschlüssel unserer ursprünglichen Tabelle ist die Kombination aus KursID und StudentID, da diese Kombination jede Zeile eindeutig identifiziert.

• Schritt 2: Überprüfung der Abhängigkeiten:Die Abhängigkeiten in der Tabelle sind wie folgt:
• KursID → KursName, Dozent, DozentenTel
• StudentID → StudentName, Studienfach
• (KursID, StudentID) → Note

Wir sehen, dass Dozent und DozentenTel von KursID abhängen und StudentName und Studienfach von StudentID abhängen. Diese Abhängigkeiten sind partiell, da sie nicht von der gesamten Primärschlüsselkombination, sondern nur von einem Teil abhängig sind.

• Schritt 3: Aufteilung der Tabelle:Um die Tabelle in die 2NF zu überführen, zerlegen wir sie in mehrere Tabellen, sodass keine partielle Abhängigkeit mehr vorhanden ist:

• Tabelle: Kurs

   KursID | KursName          | Dozent      | DozentenTel----------------------------------------------------------- 1    | Datenbankdesign  | Dr. Müller  | 1234567 2    | Algorithmen      | Dr. Meier   | 7654321

• Tabelle: Student

   StudentID | StudentName   | Studienfach-------------------------------------------- 1001      | Anna Schmidt  | Informatik 1002      | Max Mustermann| Informatik 1003      | Maria Klein   | Mathematik 1004      | Julia Neu     | Informatik

• Tabelle: Kurs_Student

   KursID | StudentID | Note------------------------------- 1    | 1001      | 1.3 1    | 1002      | 2.0 2    | 1003      | 2.5 2    | 1004      | 1.7

Jetzt haben wir die ursprüngliche Tabelle in drei Tabellen aufgeteilt:

• Die Tabelle „Kurs“, die Informationen über die Kurse und deren Dozenten enthält und in der KursID der Primärschlüssel ist.
• Die Tabelle „Student“, die Informationen über die Studenten und deren Studienfächer enthält und in der StudentID der Primärschlüssel ist.
• Die Tabelle „Kurs_Student“, die die Noten der Studenten in den jeweiligen Kursen enthält und in der die Kombination aus KursID und StudentID der Primärschlüssel ist.

Durch diese Aufteilung haben wir alle partiellen Abhängigkeiten eliminiert und die Tabellen befinden sich nun in der zweiten Normalform (2NF).

c)

Nach der Überführung in die 2NF, überführe die neuen Tabellen in die dritte Normalform (3NF). Zeige ebenfalls deine Schritte und erkläre, warum diese notwendig sind.

Lösung:

Überführung der Tabellen in die dritte Normalform (3NF)

Nachdem die Tabellen nun in der zweiten Normalform (2NF) sind, arbeiten wir daran, sie in die dritte Normalform (3NF) zu überführen. Bei diesem Schritt eliminieren wir transitive Abhängigkeiten – das bedeutet, dass keine Nicht-Schlüsselattribute von anderen Nicht-Schlüsseln abhängen dürfen.

• Schritt 1: Identifikation transitiver Abhängigkeiten:Sehen wir uns die Tabellen an:

• Tabelle: Kurs

   KursID | KursName         | Dozent     | DozentenTel----------------------------------------------------------- 1    | Datenbankdesign | Dr. Müller | 1234567 2    | Algorithmen     | Dr. Meier  | 7654321

In der Tabelle „Kurs“ liegt eine transitive Abhängigkeit vor: Dozent → DozentenTel. Dies bedeutet, dass die Telefonnummer des Dozenten von der Identität des Dozenten abhängt und nicht direkt von KursID.

• Tabelle: Student

   StudentID | StudentName   | Studienfach---------------------------------------- 1001      | Anna Schmidt  | Informatik 1002      | Max Mustermann| Informatik 1003      | Maria Klein   | Mathematik 1004      | Julia Neu     | Informatik

In der Tabelle „Student“ gibt es keine transitiven Abhängigkeiten.

• Tabelle: Kurs_Student

   KursID | StudentID | Note------------------------------- 1    | 1001      | 1.3 1    | 1002      | 2.0 2    | 1003      | 2.5 2    | 1004      | 1.7

In der Tabelle „Kurs_Student“ gibt es ebenfalls keine transitiven Abhängigkeiten.

• Schritt 2: Aufteilung der Tabelle „Kurs“:Da in der Tabelle „Kurs“ eine transitive Abhängigkeit besteht, teilen wir die Tabelle weiter auf:

• Tabelle: Kurs

   KursID | KursName       | DozentID------------------------------------ 1    | Datenbankdesign | 1 2    | Algorithmen     | 2

• Tabelle: Dozent

   DozentID | Dozent      | DozentenTel------------------------------------- 1        | Dr. Müller | 1234567 2        | Dr. Meier  | 7654321

• Begründung: Indem wir die Tabelle „Kurs“ aufteilen, eliminieren wir die transitive Abhängigkeit. „Dozent“ und „DozentenTel“ werden in eine separate Tabelle ausgelagert, die nur die Informationen über die Dozenten enthält. „Kurs“ enthält nur die DozentID als Fremdschlüssel.

Resultierende Tabellen in 3NF:

• Tabelle: Kurs

   KursID | KursName       | DozentID------------------------------------ 1    | Datenbankdesign | 1 2    | Algorithmen     | 2

• Tabelle: Dozent

   DozentID | Dozent      | DozentenTel------------------------------------- 1        | Dr. Müller | 1234567 2        | Dr. Meier  | 7654321

• Tabelle: Student

   StudentID | StudentName   | Studienfach--------------------------------------- 1001      | Anna Schmidt  | Informatik 1002      | Max Mustermann| Informatik 1003      | Maria Klein   | Mathematik 1004      | Julia Neu     | Informatik

• Tabelle: Kurs_Student

   KursID | StudentID | Note------------------------------- 1    | 1001      | 1.3 1    | 1002      | 2.0 2    | 1003      | 2.5 2    | 1004      | 1.7

Jetzt befinden sich alle Tabellen in der dritten Normalform (3NF), da keine transitive Abhängigkeit mehr vorhanden ist und alle Nicht-Schlüsselattribute voll funktional vom Primärschlüssel abhängen.

Aufgabe 4)

Du bist als Data Scientist beauftragt, ein neuronales Netzwerk zu entwickeln, das handgeschriebene Ziffern erkennen soll. Dafür nutzt Du das MNIST-Datenset, das 60.000 Trainingsbilder und 10.000 Testbilder von Ziffern (0-9) enthält. Du entscheidest Dich für ein tiefes neuronales Netzwerk mit mehreren versteckten Schichten und verwendest Python mit Bibliotheken wie TensorFlow oder PyTorch. Der Ansatz soll folgende Schritte beinhalten: Datenerhebung und -vorverarbeitung, Modellarchitektur, Trainingsprozess, und Evaluierung.

a)

Beschreibe die Architektur des neuronalen Netzwerks, das Du entwickeln möchtest. Gib die Anzahl der Schichten (Input-, versteckte Schichten, Output-Schicht) an und erkläre die Funktion der Aktivierungsfunktionen, die Du verwenden wirst. Verwende Pseudo-Code, um Deine Architektur zu veranschaulichen.

Lösung:

• Architektur des neuronalen Netzwerks:

Für die Erkennung handgeschriebener Ziffern plane ich, ein tiefes neuronales Netzwerk zu erstellen. Die Architektur umfasst folgende Schichten:

• Input-Schicht: Diese Schicht nimmt die Eingangsdaten auf. Da die Bilder im MNIST-Datensatz eine Größe von 28x28 Pixeln haben, besteht die Eingabeschicht aus 784 Neuronen (28 * 28 = 784).
• Versteckte Schichten: Es werden mehrere versteckte Schichten verwendet, um die Komplexität der Daten zu lernen. In diesem Beispiel verwende ich drei versteckte Schichten: - Erste versteckte Schicht: 128 Neuronen - Zweite versteckte Schicht: 64 Neuronen - Dritte versteckte Schicht: 32 Neuronen
• Output-Schicht: Da es zehn Klassen (die Ziffern 0-9) gibt, hat die Ausgabeschicht 10 Neuronen.

• Aktivierungsfunktionen:

Aktivierungsfunktionen haben die Aufgabe, Nichtlinearitäten in das Modell einzuführen. In diesem Netzwerk werden folgende Aktivierungsfunktionen verwendet:

• ReLU (Rectified Linear Unit): Für die Neuronen der versteckten Schichten. ReLU ist eine weit verbreitete Aktivierungsfunktion, da sie die Berechnung vereinfacht und dazu beiträgt, das Modell schneller und effizienter zu trainieren.
• Softmax: Für die Neuronen in der Ausgabe-Schicht. Softmax wandelt die Ausgaben in Wahrscheinlichkeiten um, wobei die Summe der Ausgaben 1 beträgt und gewährleistet, dass eine einzige Klasse als die wahrscheinlichste identifiziert wird.

Nachfolgend ein Pseudo-Code zur Veranschaulichung der Architektur:

# Pseudo-Code zur Definition der Netzwerkarchitektur# Import der notwendigen Bibliothekimport tensorflow as tf# Initialisiere ein sequentielles Modellmodel = tf.keras.Sequential()# Input-Schichtmodel.add(tf.keras.layers.InputLayer(input_shape=(784,)))# Erste versteckte Schicht (128 Neuronen, ReLU)model.add(tf.keras.layers.Dense(128, activation='relu'))# Zweite versteckte Schicht (64 Neuronen, ReLU)model.add(tf.keras.layers.Dense(64, activation='relu'))# Dritte versteckte Schicht (32 Neuronen, ReLU)model.add(tf.keras.layers.Dense(32, activation='relu'))# Output-Schicht (10 Neuronen, Softmax)model.add(tf.keras.layers.Dense(10, activation='softmax'))# Kompiliere das Modell (Verwende Kreuzentropie als Verlustfunktion und Adam als Optimierer)model.compile(optimizer='adam', loss='sparse_categorical_crossentropy', metrics=['accuracy'])# Zeige die Modellzusammenfassungmodel.summary()

c)

Um Overfitting zu vermeiden, planst Du, Regularisierungstechniken und Dropout anzuwenden. Beschreibe, wie diese Techniken funktionieren und integriere sie in den Trainingsprozess. Diskutiere weiterhin, wie Du die Leistung des Modells auf dem Testdatensatz evaluieren wirst und welche Metriken Du dafür heranziehst.

Lösung:

• Regularisierungstechniken und Dropout:

Um Overfitting zu vermeiden, können wir Regularisierungstechniken wie L2-Regularisierung und Dropout verwenden:

• L2-Regularisierung (Ridge-Regularisierung):Bei der L2-Regularisierung wird ein Strafbegriff zur Verlustfunktion hinzugefügt, der die Summe der Quadrate der Gewichte ist. Dies verhindert, dass die Gewichte zu groß werden und das Modell somit überanpasst. Die modifizierte Verlustfunktion sieht wie folgt aus:

\[J(\theta) = J(\theta)_{original} + \frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2\]

Dabei ist \(\lambda\) der Regularisierungsparameter und \(m\) die Anzahl der Trainingsbeispiele.

• Dropout:

Dropout ist eine Technik, bei der während des Trainings zufällig bestimmte Neuronen deaktiviert werden. Dies verhindert, dass sich das Modell zu stark auf bestimmte Neuronen verlässt und somit überanpasst. Dropout wird nur während des Trainings angewandt und nicht während des Testens. Der Dropout-Layer kann einfach mit TensorFlow oder Keras integriert werden:

import tensorflow as tffrom tensorflow.keras.layers import Dense, Dropoutmodel = tf.keras.Sequential([  Dense(128, activation='relu', input_shape=(784,)),  Dropout(0.5),  Dense(64, activation='relu'),  Dropout(0.5),  Dense(10, activation='softmax')])

• Integrierung in den Trainingsprozess:

Der Trainingsprozess wird mit diesen Techniken wie folgt erweitert:

model.compile(optimizer='adam',           loss='sparse_categorical_crossentropy',           metrics=['accuracy'])history = model.fit(train_images, train_labels, epochs=20, validation_split=0.2)

• Evaluierung des Modells auf dem Testdatensatz:

Nach dem Training wird das Modell auf dem Testdatensatz evaluiert, um die Leistungsfähigkeit zu bestimmen:

• Wichtige Metriken:
• Accuracy (Genauigkeit): Misst den Anteil der korrekten Vorhersagen am Gesamtbestand der Vorhersagen.
• Confusion Matrix (Verwechslungs-Matrix): Eine Tabelle, die die Leistung des Klassifizierungsmodells darstellt und zeigt, wie viele der Vorhersagen jeder Klasse korrekt waren und wie viele falsch anderen Klassen zugeordnet wurden.

from sklearn.metrics import accuracy_score, confusion_matrixtest_loss, test_acc = model.evaluate(test_images, test_labels, verbose=2)y_pred = model.predict(test_images)conf_matrix = confusion_matrix(test_labels, y_pred.argmax(axis=1))print(f'Test Accuracy: {test_acc}')print(f'Confusion Matrix:{conf_matrix}')

Zusätzlich können Precision, Recall und F1-Score berechnet werden, um ein detaillierteres Bild der Modellleistung zu bekommen:

from sklearn.metrics import classification_reportprint(classification_report(test_labels, y_pred.argmax(axis=1)))