Was ist Informatik, seit wann gibt es sie, was wird in der Informatik mit Informationen getan?
Wissenschaft von der systematischen Verarbeitung von Informationen, besonders der automatischen Verarbeitung mit Hilfe von Digitalrechnern (Computern).
Die Informatik war zunächst Teilgebiet von anderen Wissenschaftlichen Disziplinen. (1960)
„Informationen“ verwaltet (gespeichert), verarbeitet, übertragen, präsentiert genutzt.
Teilgbiete der Informatik:
Theoretische Informatik:
Berechenbarkeitstheorie
Algorithmen und Komplexitätstheorie
Automatentheorie
Formale Sprachen
Praktische Informatik:
Programmiersprachen, Übersetzer
Betriebssysteme, Verteilte Systeme
Datenbanken, Informationssysteme
Künstliche Intelligenz
Technische Informatik:
Rechnerarchitektur
Mikroprozessoren
Entwurf Integrierter Schaltungen
Angewandte Informatik:
Anwendung von Methoden der Informatik in bestimmten Anwendungsbereichen
Wirtschaftsinformatik, Medizininformatik, Rechtsinformatik
Wie werden in der Informatik Daten Transformiert?
Mithilfe von in programmen realisierten Algorithmen.
—> Dieser Algorithmus arbeitet mit Zustandsrepräsentationen.
—> Zusatandsübergänge sind durch Programmanweisungen definiert
—> Programmiersprache mit sytax und Semantik
Automatische Programmausführung ist der Kern der “Digitalisierung”.
The discipline of computing is the systematic study of algorithmic processes that describe and transform information : their theory, analysis, design, efficiency, implementation, and application. The fundamental question underlying all of computing is, “What can be (efficiently) automated?”
Denning
—> siehe Langfristzielsetzung der WI ist die “sinnhafte Vollautomation”
Wann gilt ein Problem als berechenbar?
Was sind Algorithmen?
Eindeutig beschriebene, „mechanisch“ nachvollziehbare Verfahren zur Lösung bestimmter Klassen von Problemen.
—> möglich: für den Mensch beschrieben (semi formal/formal)
in Form von Bsp.: Pseudocode oder für den Rechner beschrieben (formal) in Form von Programmiersprachen
Was macht der Algorithmus von Euklid?
Erste Begriffsverwendung: Algorithmus von Euklid zur Ermittlung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen.
Bsp.: 20 und 30 —>größter gemeinsamer Teiler = 10
Was sind Kriterien für einen Algorithmus?
Was kann bei Algorithmen zu Problemen führen?
Kriterien:
Eindeutige Beschreibung von Input und Output
Terminierung (endliche Anzahl an ausgeführten Operationen)
Eindeutige Beschreibung der Operationen
Effektive Ausführbarkeit von Operationen
Probleme:
Nicht beantwortbarkeit (Gott/Wahr/Falsch)
Keine endlichen Stellen einer Zahl (Periodisch = Sqrt(2))
—> werden dann meist auf 20 Stellen limitiert
Ein formal definiertes Problem in der Form einer entsprechenden Funktion f wird als berechenbar definiert, …
Wie oft wird folgende Schleife durchlaufen?
Einmal!
Grundsätzlich sind nur +1 und -1 erluabt, da wir eine sehr stark vereinfachte Version von Python verwenden. Gibt es trotzdem die Möglichkeiten Multiplikationen zu verwirklichen?
Ja, das geht, es kann mit “While” Schleifen verwirklicht werden.
(Wird sehr schnell sehr unübersichtlich.)
Was ist die Turing Maschine?
Man hat ein (unendlich)langes Band mit Zeichen, die gelöscht und geschrieben werden können. An diesem band befindet sich ein Schreibe- und Lesekopf. Die Grundsätzliche Bewegung ist 1x nach rechts oder 1x nach links.
Ein Programm gibt Anweisungen darüber was der Schreibe-Lesekopf basierend auf seinem gerade eingelesenem Zustand machen soll. (schrieben/links/rechts/lesen/Zusatnd wechseln)
Anweisungen liegen vor in Form von Auflistung.
Als was gelten alle Probleme die mit einer Turing Maschine berechenbar sind?
Als Turing-berechenbar: Bsp.: Primzahl Bestimmung; Alle Python Programme.
Alle Turing-berechenbaren Probleme sind auch Python-ausführbar.
Gleiches gilt für gewöhnliche Mikroprozessoren.
Was besagt die Churchsche These?
Jede im intuitiven Sinne berechenbare Funktion ist Turing-berechenbar.
Alle bisher untersuchten hinreichend mächtigen Konkretisierungen des Begriffs Algorithmus sind gleichwertig im Hinblick auf die prinzipielle Berechenbarkeit.
—> Alle Arten sind gleichwertig/gleichmächtig , auch wenn das eine vielleicht länger braucht/ müsamer ist.
Gibt es grundsätzliche Grenzen für die Berechenbarkeit?
Es gbt mehr Funktionen/Problemstellungen als es algorithmen gibt, daher sind nicht alle Funktionen/Problemstellungen lösbar.
—> Es gibt prinzipiell Probleme die prinzipiell nicht lösbar sind.
Gibt es ein Beispiel für ein prinzipiell nicht lösbares Problem?
Halteproblem: Programm, das überprüft, ob ein bestimmtes Programm P für alle Eingaben sicher irgendwann anhält?
Äquivalenzproblem: Gibt es Programm das entscheidet, ob zwei beliebige Programme dieselbe Funktion berechenen.
Überprüfen auf semantische Korrektheit: Programm, das entscheidet, ob ein gegebenes Programm eine Funktion gemäß seiner gegebenen formalen Spezifikation berechnet
Welche Probleme sind berechenbar?
Wie kann man den Rechenaufwand für ein bestimmtes lösbares Problem quantifizieren?
n beschreibt die Problemgröße (z.B. Anzahl der zu sortierenden Zahlen)
T(n) : zeitlicher Aufwand in „Elementaroperationen“
—> In der Regel wird eine “Worst Case” Abschätzung getroffen
(Alternativ: durchschnitt bilden/amortisieren)
Warum ist der Aufwand für die Nutzug von Algorithmen relevant?
Rechenzeit
(Speicherplatz)
(Kommunikation)
Welche laufzeit hat das folgende python Programm?
Das “+1” kommt davon, dass das while nochmal überprüft wird.
Was gibt es für Typische Laufzeitkomplexitäten?
Diese Laufzeitkomplexitäten sind bereits in der richtigen Reihenfolge: Oben wächst am langsamsten für jedes hinzugefügte n, unten am schnellsten.
Kann es manchmal passieren, das Algorithmen mit einer worst Case Laufzeit von O(n^2) schneller ist, als einer mit der Laufzeit O(log n)?
Ja, es handelt sich um eine Worst Case Angabe.
Bsp.: Der Quicksort läuft im Worst Case O(n^2) und im Average Case O(log n)
Welche Laufzeit liegt vor?
2+n(3+3*4+1)= 2+16*n —> O(n)
—> n wird in der zweiten Schleife nicht erneut aufgegriffen, innere Schleife bewirkt konstanten Aufwand
Geben sie für O(log n) und O(n) ein Beispiel an.
O(log n): Zuegnisse sind nach matrikelnummern sortiert, man schlägtdas mittlere auf—> größer oder kleiner Suche
O(n): Man sucht einen Namen im zeugnisstapel —> Man muss alle Zeugnisse durchegehen
Wie groß ist die maximal lösbare Problemgröße n in Abhängigkeit von der Laufzeitkomplexität und der verfügbaren Rechenzeit?
[Annahme: je Millisekunde kann eine Elementaroperation ausgeführt werden]
Hinweis: Normal, Wurzel, Logarithmus dualis
—> Durch schnellere Rechner bleiben schwer lösbare Probleme trotzdem schwer lösbar.
Wann gelten Algotithmen als effizient?
Welche Algorithmen sind effizient?
Bsp.: Dijkstra, Algorithmus zur Matrix multiplikation, Algorithmen zum Zahlen sortieren
(Kein n in der Potenz)
—> Auch bekannt als Problemklasse P-schwerer Probleme
Wann gelten Algorithmen als nicht handhabbar?
Geben sie Bespiele für Probleme an, die nur mit Algorithmen gelöst werden können, die nicht handhabbar sind.
Bsp.: Travelling Salesman Problem, Steiners Problem in Graphen, Rucksack Problem —> Alle haben Exponentielle Laufzeit
Bisher haben wir die Komplexität von Algorithmen bestimmt, nicht aber von Problemen.
Für die meisten Probleme ist die genaue Komplexität noch nicht bekannt, Bsp.: multiplizieren von zwei Matrizen (O n^3 bzw. Tendenz schneller).
Für das sogenannte Sortierproblem ist die genaue Komplexität bereits bekannt, (schnellste Möglichkeit dieses Problem sicher zu lösen).
Was ist Steiners problem in Graphen?
Bestimmte Knoten sollen mit minimal möglichem gewocht verbunden werden.
Erklären sie das Bild.
P:
Die Klasse der Probleme, die effizient lösbar sind, d. h., für die ein Algorithmus existiert, der sie in polynomialer Zeit löst.
NP:
Die Klasse der Probleme, deren Lösungen effizient überprüfbar sind, d. h., wenn eine Lösung vorliegt, kann sie in polynomialer Zeit überprüft werden.
P ⊆ NP:
Alle Probleme in P sind automatisch in NP, weil ein Problem, das effizient lösbar ist, auch effizient überprüfbar ist.
P = NP?:
Die offene Frage ist, ob alle Probleme, deren Lösungen effizient überprüfbar sind (NP), auch effizient lösbar sind (P). Anders gesagt:
P = NP: Alle NP-Probleme können effizient gelöst werden.
P ≠ NP: Es gibt Probleme in NP, die nicht effizient lösbar sind.
NP bedeutet nichtdeterministisch polynomial
NP-schwere Probleme
NP-schwere Probleme sind eine Klasse von Problemen, für die kein effizienter Algorithmus bekannt ist.
Viele dieser Probleme sind „äquivalent schwer“, da sie sich effizient ineinander transformieren lassen.
Es bleibt offen, ob NP-schwere Probleme effizient lösbar sind (P=NP?).
Heuristiken: Näherungslösungen
Da NP-schwere Probleme keine effiziente Lösung haben, verwenden Heuristiken Näherungsmethoden.
Ziel ist es, in vertretbarer Zeit „hinreichend gute“ Lösungen zu finden, ohne optimale Lösungen zu garantieren.
Beispiele für Metaheuristiken sind lokale Suche, Tabu-Suche und genetische Algorithmen.
Was versteht man unter dem Begriff „Berechnung“?
Antwort: Berechnung ist der Prozess der Transformation von Eingaben zu Ausgaben durch einen Algorithmus. Ein Problem ist berechenbar, wenn ein Algorithmus existiert, der für jede Eingabe in endlicher Zeit eine korrekte Ausgabe liefert. Beispiel: Überprüfung, ob eine Zahl eine Primzahl ist.
Was ist die Churchsche These, und welche Bedeutung hat sie?
Antwort: Die Churchsche These besagt, dass jede intuitiv berechenbare Funktion auch durch eine Turing-Maschine berechnet werden kann. Sie verbindet die informelle Vorstellung von Berechenbarkeit mit formalen Maschinenmodellen.
Wie definiert man einen Algorithmus?
Antwort: Ein Algorithmus ist eine eindeutige, endliche Folge von Anweisungen zur Lösung eines Problems. Er muss eine klare Beschreibung von Input, Output, Operationen und eine Terminierung aufweisen.
Welche Grenzen gibt es für die Berechenbarkeit von Problemen?
Antwort: Einige Probleme sind nicht berechenbar, wie das Halteproblem. Es existieren wohldefinierte Probleme, für die kein Algorithmus existiert, der sie für alle Eingaben lösen kann.
Was ist die O-Notation, und wofür wird sie verwendet?
Antwort: Die O-Notation beschreibt das asymptotische Laufzeitverhalten eines Algorithmus in Abhängigkeit von der Problemgröße nnn. Sie gibt die obere Schranke der Laufzeit für große nnn an und dient zur Klassifizierung von Algorithmen hinsichtlich ihrer Effizienz.
Welche typischen Laufzeitklassen gibt es, und was bedeuten sie?
Was ist der Unterschied zwischen den Klassen P und NP?
P: Probleme, die effizient lösbar sind (polynomial in der Laufzeit).
NP: Probleme, deren Lösungen effizient überprüfbar sind, aber nicht unbedingt effizient lösbar.
Was bedeutet die Frage „P = NP?“
Antwort: Sie fragt, ob alle Probleme in NPNPNP, deren Lösungen effizient überprüfbar sind, auch effizient lösbar sind (PPP). Diese Frage ist bis heute ungelöst.
Was versteht man unter NP-schweren Problemen?
Antwort: NP-schwere Probleme sind mindestens so schwer wie alle Probleme in NP. Sie müssen nicht selbst in NP liegen, aber eine effiziente Lösung eines NP-schweren Problems würde alle NP-Probleme effizient lösbar machen.
Last changed3 days ago
