Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Einführung in die Informatik > Prüfungsfragen > Flashcards

Prüfungsfragen Flashcards

Fragen und Antworten

1
Q

Was versteht man unter dem Begriff “Informatik”

A

automatisierte Informatsionsverarbeitung in Natur, Technik und Gesellschaft
Verarbeitung von Daten und Informationen
Begriff aus: Information und Automatik

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Was versteht man unter dem Begriff “Algorithmus”?

A

Verarbeitungsvorschrift für ein Gerät (elektrisch, mechanisch) oder einen Menschen
Bestimmte Anzahl an Anweisungen oder Schritte zur Lösung eines Problems
Bsp: Kochrezept, mathematischer Lösungsweg

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Erklären Sie das von-Neumann’sche Rechnermodell!

A

Rechner (Zentraleinheit) besteht aus Komponenten: Steuerwerk, Rechenwerk, Speicher, Ein- und Ausgabegeräte; Verbindungssystem
Steuer- und Rechenwerk bilden Prozessor
Früher Rechner: Dezimal und Mechanik
heute: Binärcode, Elektronik; gespeicherte Programme

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Nennen Sie Teilgebiete der Informatik

A

Angewandte I.
Technische I.
Praktische
Theoretische

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Problembetrachtung in der theoretischen Informatik

A

Automatentheorie (wie löst eine Maschine ein Problem?)
formale Sprachen (zur Beschreibung von Regeln für PS)
Berechenbarkeitstheorie (welche Probleme sind von der Maschine lösbar?)
Komplexitätstheorie (Komplex. und Güte von Algorithmen)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Problembetrachtung in der praktischen Informatik

A

Aufbau von: Programmiersprachen, Compilern, Interpretern
Algorithmen und Datenstrukturen
Betriebssysteme
Datenbanken

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Problembetrachtung in der technischen Informatik

A

Mikroprozessortechnik (Entwicklung von Rechner, Speicherchips, Prozessoren, Festplatten, Bildschirmen..)
Rechnerkommunikation (Datenaustauch zw. versch. Rechnern)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Problembetrachtung in der angewandten Informatik

A

Wirtschaftliche, kommerzielle Anw. (Buchhaltung..)

Techn.-wissenschaftl. Anw. (Anlagensteuerung, Simulation)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Dokumentieren Sie, was die folgende Aussage bedeuten und wann sie wahr sind:
a. es regnet v Sie haben einen Schirm

A

die Aussage ist wahr, wenn “es regnet” wahr ist ODER “ich habe einen Schirm” wahr ist ODER beide Aussagen wahr sind

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Dokumentieren Sie, was die folgende Aussage bedeuten und wann sie wahr sind:
b. (Alter < 16) ^ (Zettel der Eltern ist vorhanden)

A

die Aussage ist wahr, wenn die Person unter 16 ist wahr ist UND “ein Elternzettel vorhanden ist” wahr ist

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Dokumentieren Sie, was die folgende Aussage bedeuten und wann sie wahr sind:
die Sonne scheint ^ Sie haben Sonnencreme

A

die Aussage ist wahr, wenn “die Sonne scheint” wahr ist UND “ich habe Sonnencreme” wahr ist

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Dokumentieren Sie, was die folgende Aussage bedeuten und wann sie wahr sind:
(Alter < 16) ^ (Ausweis zur Kontrolle ist vorhanden)

A

die Aussage ist wahr, wenn “Person jünger als 16” wahr ist UND “Ausweis vorhanden” wahr ist

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Dokumentieren Sie, was die folgende Aussage bedeuten und wann sie wahr sind:
(Größe > 120cm) ^ (Größe < 2,oo m)

A

die Aussage ist wahr, wenn beide Einzelaussagen wahr sind

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Not (Gewicht > 100) ^ NOT (Größe> 2,00)

A

die Aussage ist wahr, wenn die Person unter 100kg wiegt UND kleiner als 2,00 m ist

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Not (Gewicht > 100 ^ Größe > 2,00)

A

die Aussage ist wahr, wenn die Person unter 100kg wiegt UND kleiner als 2,00 m ist

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q
  1. Nennen und erläutern Sie die Schritte zum Programmentwurf!
A
  • im Softwarelebenszyklus beschrieben
  • Anforderungsnalayse: Sammeln der Anforderung an das Programm, Ergebnis ist Anforderungsspezifikation
  • Systementwurf: Aufteilung der Aufgaben in Module (Strukturierung der Anwendung), Ergebnis: Systemspezifikation
  • Programmentwurf: Module verfeinern, Algorithmen und Datenstrukturen festlegen, Ergebnis ist Programmspezifikation
  • Implementierung und Test: Module werden programmiert und anhand ihrer Spezifikation getestet
  • Betrieb und Wartug: Pflege der Software im Betrieb, u.U. Behebung von Fehlern
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q
  1. Erläutern Sie die Funktionsweise eines Compilers!
A

Ein Compiler ist ein Computerprogramm, das Quellcodes einer bestimmten Programmiersprache in eine Form übersetzt, die von einem Computer ausgeführt werden kann.

  • Überführung eines Quellprogrammes (Software) in ein Maschinen- / Assemblerprogramm
    1. Analyse des Quellprogrammes und Erzeugen eines Zwischenprogrammes (Parse tree)
    1. Synthese: aus dem Parse tree wird das gewünschte Zielprogramm zusammen gelinkt
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q
  1. Erläutern Sie die Funktionsweise eines Linkers!
A
  • der Linker bindet die vom Compiler bereitgestellten Objektdateien in ein ablauffähiges Programm zusammen
  • statisches Linken: alle benötigten Funktionen werden sofort fest zu einem Programm zusammen gelinkt
  • dynamisches Linken: nicht alle benötigten Funktionen werden sofort fest zusammengelinkt, sondern in separaten Bibliotheken zur Verfügung gestellt
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q
  1. Erläutern Sie die Funktionsweise eines Laders!
A
  • liest ein assembliertes und gelinktes Programm Befehl für Befehl ein und trägt den Maschinencode an die jeweilige Stelle im Hauptspeicher ein (= Speicheradresse) - Programm ist startbereit
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q
  1. Erläutern Sie die Funktionsweise eines Debuggers!
A
  • Programmierwerkzeug, das die Möglichkeit bietet, das Programm schrittweise zu durchlaufen und jeden Schritt (Befehl in Hochsprache, Assembler) zu analysieren
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q
  1. Welche Eigenschaften sollte die Spezifikation einer Aufgabenstellung (für die Programmierung eines zu lösenden Programms) haben?
A
  • Spezifikation sollte eine vollständige, detaillierte, unzweideutige Problembeschreibung sein
  • vollständig: alle relevanten Informationen sind berücksichtigt
  • detailliert: alle Hilfsmittel und Grundaktionen sind aufgelistet, die zur Lösung zugelassen sind
  • unzweideutig: Festlegen von klaren Kriterien, wann eine Lösung akzeptabel ist
22
Q
  1. Definieren Sie, was man unter einem Algorithmus versteht (formale Beschreibung)
A
  • Ein A. ist eine endliche, deterministische und effektive Vorschrift zur Lösung eines Problems, die effiezient sein sollte
  • endlich: nach einer endlichen Zeit wird der Algorithmus beendet
  • Deterministisch: eindeutige Bestimmung des nächsten Schrittes
  • Effektiv: eindeutige Ausführbarkeit der Einzelschritte
    Effizient: geringer Verbrauch an Ressourcen wie Speicherplatz und Rechenzeit
23
Q
  1. Definieren Sie, was man unter einem Programm versteht
A
  • Programm = Daten (Objekte ) + Algorithmus

- Algorithmus, der Operationen an den Objekten (Daten) festlegt

24
Q
  1. Erläutern Sie, was man unter einer Datenstruktur versteht!
A
  • Datenstruktur = Daten + Operationen

- Versteht man den Datentyp zusammen mit der Menge an Operationen, die auf ihm erlaubt sind

25
Q
  1. Erläutern Sie den Aufbau von Listen und die Funktion Einfügen und Löschen
A
  • Liste ist eine sortierte Folge von Elementen, die durch Zeiger vorwärts und rückwärts verkettet sind
  • Einfügen:
    a. Stelle in der Liste suchen, an der das neue Element eingefügt werden soll
    b. Das Element einfügen und
    c. die Verkettung wieder herstellen, so dass eine korrekt sortierte Liste entsteht
  • Löschen:
    d. Stelle des zu löschenden Elementes in der Liste suchen
    e. Element löschen
    f. Zeiger wieder so zusammensetzen, dass die Sortierung erhalten bleibt
26
Q
  1. Erläutern Sie den Aufbau eines Stacks und die Funktionen Einfügen und Löschen!
A
  • Stack (eine Datenstruktur) ist ein Stapel mit den Operationen/Elementen push, pop, top
  • Einfügen:
    a. mittels push ein Element an oberste Stelle auf den Stapel legen
    Löschen:
    b. Solange Elemente vom Stapel nehmen (mit pop) bis gesuchtes Element gefunden
    c. Gesuchtes Element vom Stapel entfernen
    d. alle anderen Elemente wieder auf den Stapel legen

LIFO = last in first out - Datenstruktur, bei der immer das entnommen wird, was zuletzt eingefügt wurde

27
Q
  1. Erläutern sie den Aufbau einer Warteschlange und die Funktionen Einfügen und Löschen
A
  • Queue = Warteschlange mit FIFO-Prinzip (hinten anfügen, vorne entfernen)
  • Einfügen: mit put ein Element hinten anfügen
  • Löschen: mit get:
    a. Schlange durchsuchen nach Element
    b. Alle Elemente löschen bis Element gefunden (get)
    c. dann Element löschen (get)
    d. Restliche Elemente wieder anfügen (put)
28
Q
  1. Erläutern Sie den Aufbau von Bäumen und die Funktionen Einfügen und Löschen
A
  • Baum = nichtleere Menge von Knoten und Kanten
  • es gibt einen Wurzelknoten
  • vom Wurzelknoten ausgehend gibt es Kindknoten, die wiederum Kindknoten haben
  • Einfügen: Stelle im Baum suchen, wo der Knoten eingefügt werden soll und einfügen
  • Löschen:
    a. Stelle im Baum suchen, wo sich zu löschender Knoten befindet
    b. Knoten löschen
    c. Sortierung wieder herstellen
29
Q
  1. Erläutern Sie den Aufbau von Binär-Bäumen und die Funktionen Einfügen und Löschen
A
  • Binärbaum ist eine nichtleere Menge von Knoten und Kanten
  • Es gibt einen Wurzelknoten
  • Es gibt Innere-Knoten (mit max. 2 Kindsknoten) und äußere Knoten (ohne Kindsknoten)
  • Einfügen:
    a. Stelle im Baum suchen, in die der Knoten eingefügt werden soll
    b. Knoten einfügen
    c. Baum-Ordnung wieder herstellen
  • Löschen:
    d, gewünschtes Blatt löschen und fertig
    e. oder Knoten suchen, löschen und Baum-Struktur neu ordnen
30
Q
  1. Erläutern Sie die Vorteile von Datenbanken
A
  • Geringer Erstellungs- und Verwaltungsaufwand
  • Sichere Realisierung des gleichzeitigen Zugriffs auf Daten durch mehrere Programme.
  • Änderungen der Daten ziehen keine Änderungen in den zugreifenden Programmen nach sich &raquo_space;>Datenunabhängigkeit«<
  • Vermeidung von Redundanzen, da zu jedem Objekt in der realen Welt ein Satz an Daten in der Datenbank existiert.
  • Zugriffssicherung und Zugriffskontrolle, für die gesamte Datenbank
31
Q
  1. Was versteht man unter Datenunabhängigkeit im Kontext von Datenbanksystemen?
A

Unter Datenunabhängigkeit versteht man die Unabhängigkeit von Anwendungsprogrammen und den Daten, die die Anwendungsprogramme benötigen.

vertikal logisch: Anwendungsprogramme und Daten sind unabhängig. Werden Daten aus der Datenbasis entfernt, die in keinem anderen Programm mehr benötigt werden, so ist dies möglich. Benötigt andererseits eine Anwendung neue Daten, so wird die bestehende Datenbasis um eben diese neuen Daten ergänzt.
horizontal logisch: Anwendungsprogramme untereinander sind unabhängig, was heißt, dass Änderungen in einem Programm keine Änderungen in einem anderen Programm nach sich ziehen. Benötigt z.B. eine Anwendung neue Daten, so werden diese in die Datenbasis aufgenommen, die SQL-Anfragen (SELECT-Ausdrücke) und DML-Anweisungen in den anderen Programmen bleiben unberührt.
physisch: Die (logische) Datendarstellung, die für die Anwendungsprogramme, ist unabhängig von der Form der physischen Speicherung. SQL-Anfragen (SELECT-Ausdrücke) und DML-Anweisungen im Anwendungsprogramm müssen nicht angepasst werden, wenn die physikalische Speicherform geändert wird, wenn z.B. von einer ISAM-Speicherung auf ein B-Baum-Struktur umgestellt wird oder ähnliches.
32
Q

30 a. Wo werden Datenbanken eingesetzt?

A
  • In datenintensiven Anwendungen wie z.B. Shop-Systemen, in Finanz-Anwendungen (Banken), in ERP–Anwendungen (Enterprise-Resource-Planning), Lagerwirtschaft, Internet
  • Anwendungen, …
33
Q
  1. Wozu wird das Entity-Relationship-Modell genutzt?
A

Nutzen: für Projekte, um einen relevanten Auschnitt der realen Welt zu beschreiben

  • Entitäten sind Abstraktionen der realen Welt; dargestellt werden Entitäten und deren Beziehungen untereinander; sowie deren Attribute (Attributsmengen)
  • Durch Beziehungen lassen sich Zusammenhänge zwischen den Entitäten herstellen. Beziehungen lassen sich auch Beziehungsmengen und Typen unterteilen.
34
Q
  1. Wie ist das relational Modell aufgebaut?
A
  • Relationale Modelle listen Entitäten in Tabellen auf. Jede Tabelle stellt Beziehungen zwischen den Werten der Entitäten her und wird somit als Relation bezeichnet.
  • Jedes Attribut wird als Spalte und jede Entitätsprägung als Zeile dargestellt
35
Q
  1. Wozu werden UML-Diagramme genutzt?
A
  • = Unified Modelling Language
  • UML-Diagramme helfen der “Objektorientierung” durch geeignete Kapselung von Daten und zugehörigen Operatoren eine möglichst geringe Fehlerwahrscheinlichkeit und bessere Erweiterbarkeit der Software zu erreichen.
  • UML-Diagramme bieten einen guten Ansatz für die modellbasierte Softwareentwicklung, um große Komplexität und durch abstrakte, funktionelle, strukturelle und verhaltensbasierte Sichten den Sachverhalt zu veranschaulichen und exakter definierbar zu machen
36
Q
  1. Was versteht man unter Modell-getriebener Softwareentwicklung?
A
  • Unter Modell-getriebener Softwareentwicklung (MDA=model driven architecture) versteht man, dass das Modell fachlich so exakt beschrieben wird, das sich daraus (zumindest teilweise) der zu erstellende Programmcode generieren lässt.
37
Q
  1. Was versteht man unter Reverse Engineering?
A

= umgekehrt entwickeln; also vom fertigen Modell oder Produkt wird auf die Struktur und Entwicklung geschlossen
Hier lässt sich aus dem weiterentwickelten Programmcode das Modell wieder auf einen Stand bringen, so dass insgesamt eine sogenannte Road Trip Engineering möglich ist

38
Q
  1. Erläutern Sie den Begriff “Requirements Engineering”
A
  • Requirements Engineering umfasst das Ermitteln, Analysieren, Spezifizieren und Validieren aller Eigenschaften und Rahmenbedingungen einer zu entwickelnden Software.
  • Hierbei liegen die Informationen in den Geschäftsanforderungen (Business Requirements), den Arbeitsabläufen (Workflows) und den Anwendungsfällen (Use cases), definiert durch bestimmte Abläufe (Szenarios) des Kunden
39
Q
  1. Was beschreibt ein UML-Case?
A
  • Ein Anwendungsfall (Use Case) zeigt den Zusammenhang zwischen Anwendungsfällen und den daran beteiligten Akteuren.
  • Eine typische Situation zwischen Anwender (Akteur) und dem System, wird aus der Sicht des Akteurs dargestellt.
  • Der Akteur kann auch ein extern angeschlossenes System sein, der Use Case muss vom Akteur angestoßen und zu einem wahrnehmbaren Ergebnis führen
40
Q
  1. Was versteht man unter einem UML-Aktivitätsdiagramm?
A
  • Das UML-Aktivitätsdiagramm beschreibt die Ablaufmöglichkeiten eines Systems.
  • Es werden die einzelnen Aktionen und deren Zusammenhänge notiert, ob diese sequenziell bzw. parallel stattfinden oder von Bedingungen abhängig sind.
  • Wenn durch eine Aktion ein Zustandswechsel stattfindet, können diese Zustände ebenfalls im UML-Aktivitätsdiagramm eingetragen werden (SPez. Form heißt auch Zustandsdiagramm).
  • Im Gegensatz zu prozeduralen Flussdiagrammen sind hier Aktionen eindeutig Objekten zugeordnet.
41
Q
  1. Erläutern Sie, was man unter einer berechenbaren, überall definierten Funktion versteht
A
  • f: E* à(???) A* - (wobei E das Eingabe- und A das Ausgabealphabet ist)
  • werden alle Eingaben akzeptiert, so ist die Funktion überall definiert und berechenbar
  • Bsp. Die Funktion F(n)=2*n

Berechenbar ist ein Funktion f: M* Pfeil N* dann, wenn ein Algorithmus existiert, der für einen Eingabewert m Eurozeichen M* für den f(m) definiert ist, nach endlich vielen Schritten anhält und als Ergebnis f(m) liefert. In allen Fällen in denen f(m) nicht definiert ist, bricht der Algorithmus nicht ab.

Für jeden eingegebenen Wert m gibt es einen definierten Ausgabewert, z.B. f(n)=2xn oder f(n)=(4xn)/2.

42
Q
  1. Erläutern Sie, was man unter einer berechenbaren, aber nur partiell definierten Funktion versteht!
A
  • f: E* à A* wobei E das Eingabe- und das Ausgabealphabet ist
  • werden nicht alle Eingaben akzeptiert, so ist die Funktion nur partiell definiert und berechenbar
  • die Funktion F(n)=2/n ist für n=0 nicht definiert

Eine berechenbare partiell definierte Funktion ist eine Funktion für die ein Algorithmus existiert, welche aber als Ergebnis Definitionslücken aufweist, die eine Turing Maschine nicht wiedergeben/berechnen kann.
Definition: f::M* Pfeil N*
Beispiele: f(n)=1/n oder f(n)=100/n-1

43
Q
  1. Erläutern Sie, was man unter einer Turing-berechenbaren Funktion versteht!
A
  • ist eine Funktion, die von einer Turing-Maschine berechnet werden kann
  • beim Turing geht es darum, den Algorithmus-Begriff zu präzisieren

Um eine partielle Funktion f::N Dach k Pfeil N mit einer Turing-Maschine zu berechnen, schreibt man alle Argumente (n1,n2,…nk) €NDachk in der Form n1#…..

44
Q
  1. Definieren Sie, wodurch eine Turingmaschine gekennzeichnet ist
A

formal ist eine Turingmaschine ein 7-Tupel:

a. (Z, E, A, F, zo, #, X) mit
b. Z - endliche Menge von Zuständen
c. E - endliches Eingabealphabet mit E ist Teilmenge von A (E Zeichen wie € ohne Querstriche A)
d. A - endliches Bandalphabet
e. F - Überführungsfunktion mit F: Z x A à Z x A x geschweifte Klammer auf L,o,R geschweifte Klammer zu
f. zo - Startzustand mit zo € Z
g. # - leeres Feld
h. X - Menge der zu akzeptierenden Endzustände mit X c7 (unterstrichen)

Jede Turingmaschine besitzt ein nach beiden Seiten unbegrenztes Arbeitsband, das in Felder unterteilt ist und auf dem ein Lese/Schreib-Kopf nach links und rechts bewegt werden kann. Die Maschine befindet sich zu jedem Zeitpunkt in einem von endlich vielen Zuständen und der Lese/Schreib-Kopf steht jeweils über genau einem Feld des Bandes. Der Lese/Schreib-Kopf kann erkennen welches Zeichen auf dem Arbeitsfeld steht und kann es durch ein Zeichen überschreiben. Der Lese/Schreib-Kopf ist programmgesteuert, welches die Verarbeitung der Zeichen durchführt.

45
Q
  1. Erläutern Sie, was man unter Problemen der Klasse P und NP versteht
A

Es geht um Komplexität (um Laufzeitverhalten von Alg.; wie schnell lassen sich best. Probleme lösen, wenn ich die Datenmenge erhöhe)
P: Probleme der Klasse, die praktikabel (praktisch lösbar) sind und die durch einen Algorithmus gelöst werden können, der höchstens polynomialen Aufwand erfordert; P sind polynomial lösbare Probleme
- zB Probleme mit einer Komplexität von O(n) wie die sequentielle Suche (O ist Zeit und n ist Datenmenge)
zB Probleme mit einer Komplexität von O(n log n) wie Sortieralgorithmen
- Schnelles Potentieren nach Legendre mit O(log n)
Primzahlensieb des Eratosthenes mit O(nDach2)
Klassische Matrizenmultiplikation mit O(nDach3)

NP: Probleme, die gelöst werden können, wenn ich einen Algorithmus gefunden habe, der alle Wege zur selben Zeit durchgeht, bzw. Probleme, deren Lösg. ich in polynomialer Zeit testen kann
Probleme der Klasse NP sind nichtdeterministisch und wenn man eine Lösung gefunden hat, kann man feststellen, ob diese Lösung höchstens in polynomialer Zeit arbeitet
- sie sind impraktikabel (praktisch undurchführbar)
- Man kennt nur Algorithmen mit höchstens exponentieller Komplexität

46
Q
  1. Erläuten Sie, was man unter dem SAT-Problem versteht
A
  • das Erfüllbarkeitsproblem (SAT = satisfiability) ist zu testen, ob zu einem gegebenen boolschen Ausdruck eine Belegung mit den Werten true und false existiert, so das der Ausdruck den Wert true animmt
  • Ein Algorithmus, der alle Kombinationen von Belegungen überprüft, benötigt größenordnungsmäßig O(2 Dach n) Schritte, wobei n gleich der Anzahl der Variablen des Ausdrucks ist
47
Q
  1. Gilt P = NP?
A

ist noch unklar
es besteht die Hoffnung, das es gilt, denn das hieße, das die extrem schwierigen Probleme doch irgendwie lösbar sind
- eines der größten, ungelösten Rätsel der Informatik
- es spricht vieles für P ungleich NP
- es gilt für deterministische Probleme P ist Teilmenge von NP

48
Q
  1. Was beschreibt das Hamilton-Problem?
A

Hamilton path: in einem Graphen wird ein Weg gefunden; Regel: jeder Knoten wird besucht und zwar nur einmal

Hamilton-Circuit: wie Hamilton-path, Regel: ich ende am Anfangsknoten

Das Hamilton-Problem ist NP-vollständig, da es ein Spezialfall vom 3SAT Problem ist

49
Q
  1. Was beschreibt das 3SAT-Problem?
A

Das 3SAT Problem ist ein Spezialfall des SAT Problems
Zum Nachweis dieser Behauptung reicht es aus, eine Reduktion von SAT auf 3SAT durchzuführen (ist mit polynomialen (p) Aufwand möglich, deshalb NP vollständig)
SAT kleiner/gleich p 3SAT

Unterschied SAT / 3SAT: beim 3SAT-Problem sind im entsprechenden booleschen Ausdruck nur Klauseln (OR-Ausdrücke) mit max. 3 Literalen (Variablen) erlaubt, (auch 3KNF genannt)

50
Q
  1. Was beschreibt das Problem des Handlungsreisenden (TSP)?
A

TSP: ist ein Hamilton-Problem in einem gewichteten Graphen
man versucht das Gesamtgewicht oder die Gesamtentfernung zu minimieren;
Problem ist NP vollständig, dh. es gibt keinen Algorithmus dafür, man muss aproximieren und ausprobieren

Einführung in die Informatik (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions