Erklärungen theoretische Informatik

[Revenant]

Hallo,

bin dabei mich auf meine Klausur in der Theoretischen Informatik ( X() vorzubereiten. Leider hat unser Prof kein Script o.ä. lediglich eine lose Sammlung von Folien. Natürlich kann ich jetzt nach Monaten das Ganze nicht mehr wirklich nachvollziehen. Vllt kann mir ja jemand helfen. Suche (vor allem) Links (notfalls auch Bücher) zu folgenden Themen:

Alghoritmeneigenschaften

• Komplexität
• Berechenbarkeit
• Korrektheit

Logik

• Aussagenlogik
• Aussagenkalkül
• Prädikatenlogik

kann leider nichts (einfach verständliches) finden.. ~~

 

[CDW]

> * Komplexität
Damit ist wohl das hier gemeint:
http://de.wikipedia.org/wiki/Komplexität_(Informatik)
also der Aufwand eines Algorithmus in Abhängigkeit von der Eingabe
Ich kenne es oft in Verbindung mit der Landau-Symbolen
http://de.wikipedia.org/wiki/Landau-Symbole
Ich weiß aber nicht, wie "kompliziert" Du es haben willst
Das wäre aus dem 1 Semester:

Meist geht es bei der Analyse der Komplexität von Algorithmen bzw. Problemklassen
darum, als Maß für den Aufwand eine Funktion
f : N ->; N
anzugeben, wobei f = a bedeutet:
?Bei einem Problem der Größe n ist der
Aufwand a?.
- Die?Problemgröße? n bezeichnet dabei in der Regel ein grobes Maß für den
Umfang einer Eingabe, z.B. die Anzahl der Elemente in einer Eingabeliste oder
dir Größe eines bestimmten Eingabewertes.
- Der?Aufwand? a ist in der Regel ein grobes Maß für die Rechenzeit, jedoch
ist auch der ben¨otigte Speicherplatz zuweilen Gegenstand der Analyse.

> * Berechenbarkeit
zu jeder beliebigen Eingabe existiert eine eindeutige Ausgabe

* Korrektheit

Der Nachweis der Korrektheit eines Algorithmus bezieht sich immer auf eine
Spezifikation dessen, was er tun soll. Insofern handelt es sich immer um eine
relative Korrektheit.
- Verifikation: formaler Beweis der Korrektheit bez¨uglich einer formalen Spezifi-
kation
- Validation: (nicht-formaler) Nachweis der Korrektheit bezüglich einer informellen
oder formalen Spezifikation (etwa systematisches Testen)

Es gibt da noch z.B die vollständige Induktion (für Sortieralgorithmen).

Zur Logik finde ich leider keine Folien (abgesehen von "digitale Logik").

 

[Heinzelotto]

das könnte dir auch behilflich sein: http://de.wikipedia.org/wiki/Formelsammlung_Logik
ihr müssst sicher eine logische gleichung vereinfachen, das kam bei uns auch dran

 

[01]

Um dich ein bißchen einzustimmen evtl. "Algorithmus der Woche" aus dem JdI2006