Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Theoretische Informatik
25
Theoretische Informatik
Tilmann Leichsner
Gliederung
1. Was ist Theoretische Informatik?
1.1 Grundlagen und Aufgaben
1.2 Abstraktion
1.3 Modellierung
2. Automatentheorie
3. Theorie der Formalen Sprachen
4. Berechenbarkeitstheorie
5. Komplexitätstheorie
6. Quellen
Grundlagen
und Aufgaben
Was ist Theoretische Informatik?
- Strukturwissenschaft
- Erforscht die der Informatik zugrundeliegenden Konzepte, Modelle und Vorgehensweisen
- Durch Modellierung und Abstraktion an der Schwelle zwischen Theorie und Praxis
- Grundlage für die Optimierung und Lösung von Problemen
- Durch enge Verbindung zur Mathematik schon seit 1931 aktiv
Abstraktion & Modellierung
- Beim Abstrahieren werden unwichtige Informationen ignoriert, um die Effizienz des Programms zu steigern.
Abstraktion & Modellierung
- Beim Modellieren wird ein Modell entwickelt, das nur die für die Aufgaben relevanten Aspekte abbildet.
Teilgebiete
Teilgebiete
Automatentheorie
- beschäftigt sich mit dem Studieren von Automaten, und mit den von denen lösbaren Problemen
Automat = Modell eines Rechners
Automaten-theorie
- Beispiel: Turingmaschine
= Modell, das eine abstrakte Maschiene definiert. Die Machine kann nach festgelegten Regeln Zeichen manipulieren.
Formale Sprachen
= Künstliche Sprachen, die es computern ermöglichen, Daten und Informationen zu Verarbeiten
Theorie der formalen Sprachen
- eine formale Sprache L besteht aus wörtern, die aus Zeichen des Alphabets der Sprache bestehen.
- nur durch das Zusammenspiel zwischen Syntax und Semantik kann eine Sprache funktionieren
Berechenbarkeitstheorie
- Teilgebiet der Theoretischen Informatik, das sich damit befasst, welche Probleme von einer Maschiene lösbar sind.
Berechenbar- keitstheorie
- Church-Turing-These:
alles was berechenbar ist, ist auch von einer Turingmaschiene berechenbar
Komplexitäts-
theorie
Komplexität = Ressourcenverbrauch
Komplexitäts- theorie
- Komplexität von Problemen, nicht von Algorithmen
- Zeitkomplexität, Platzkomplexität, ...
- Untere Schranken
Bsp.: Telefonbuch
einfach schwierig
Quellen:
Quellen
https://www.imn.htwk-leipzig.de/~schwarz/lehre/ws20/tim/tim20-all.pdf
[Stand: 12.09.2022]
https://www.informatik-verstehen.de/informatik-grundlagen/informatik-bestandteile/theoretische-informatik/
[Stand: 12.09.2022]
http://www.informatik.uni-bremen.de/tdki/lehre/ws09/theoinfAbschluss.pdf
[Stand: 12.09.2022]
https://www.schultreff.de/referate/informatik/r0296t00.htm
[Stand: 12.09.2022]
https://www.youtube.com/c/NLogSpace
[Stand: 12.09.2022]
https://imweb.imn.htwk-leipzig.de/~schwarz/lehre/ws21/tim/tim21-intro.pdf
[Stand: 12.09.2022]
https://de.wikipedia.org/wiki/Berechenbarkeitstheorie
[Stand: 13.09.2022]
https://de.wikipedia.org/wiki/Theoretische_Informatik
[Stand: 13.09.2022]
https://de.wikipedia.org/wiki/Formale_Sprache
[Stand: 13.09.2022]
https://de.wikipedia.org/wiki/Church-Turing-These
[Stand: 13.09.2022]
https://de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie
[Stand: 13.09.2022]
http://www.informatik.uni-bremen.de/tdki/lehre/ws09/theoinf/Abschluss.pdf
[Stand: 13.09.2022]
https://www.springerprofessional.de/theoretische-informatik/15981504
[Stand: 13.09.2022]
https://www.schultreff.de/referate/informatik/r0296t00.htm
[Stand: 13.09.2022]
https://www.memecreator.org/meme/danke-frs-zuhren-ihr-seid-super/
[Stand: 13.09.2022]
https://turingmachinesimulator.com/
[Stand: 13.09.2022]