Diskussion:Theoretische Informatik/Archiv

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Theoretische Informatik/Archiv#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Theoretische_Informatik/Archiv#Thema_1

Einheitliche Terminologie und Notation

Ich bin relativ neu bei Wikipedia und wollte in den vergangenen Tagen einige Artikel zu den Themen "Übersetzerbau", "Attributgrammatik" und "LR(k)-Zerteiler" bearbeiten. Ich konnte aber trotz Recherche keine Informationen zu einer verbindlichen Notation für Grammatiken und Sprachen finden, was ich allerdings für nötig halte, um Verwirrung auszuschließen. Gibt es da bereits eine Seite, die ich bisher nicht gefunden habe? Falls dem nicht so ist, möchte ich hier schon mal einige Dinge anregen, die mir aufgefallen sind:

• Meiner Meinung macht es keinen Sinn, bei der Definition von Grammatiken für Terminale den grichischen Buchstaben $\Sigma$ zu verwenden. Dies ist zwar in vor allem älterer Literatur üblich, macht aber meiner Meinung nach insbesondere bei Wikipedia keinen Sinn. Zudem wird auch in neueren Veröffentlichungen meist ein einfaches $T$ verwendet, also $G=(T,N,P,Z)$.

Außerdem sollte habe ich in einigen Artikeln bei der Formulierung von Produktionen die BNF, in anderen wiederum eine Notation mit $\rightarrow$ gefunden. Hierbei sind sicherlich beide Notationen sinvoll, es sollte sich jedoch geeinigt werden, wann welche Notation verwendet wird. Üblich ist dabei doch $\rightarrow$ für theoretische Dinge (Definitionen, Beweise, usw.) und (E)BNF für die Beschreibung von eher praktischen Problemen (Grammatiken für Programmiersprachen, Übersetzerbau, usw.) Vielleicht wäre aber die Entscheidung für nur eine Form sinnvoll, in diesem Fall würde ich für die $\rightarrow$ Form plädieren. In einigen Artiklen werden zudem Funtionen wie $first(..)$, $Anfang(...)$ oder $beginn(...)$ teilweise ohne Definition verwendet, oder nur für den Kontext eines Artikels definiert. Das halte ich auch für wenig sinnvoll, da die Semantik dieser Funktionen - zumindest mehrheitlich - ja eigentlich klar ist. Es sollte also meiner Meinung nach auch eine Seite zur Definition dieser, meist in Beweisen und Definitionen verwendeten, Funktionen geben. Ich hoffe, dass ich mit diesem Beitrag irgend einen Admin erreiche, der eine solche Seite anlegt, oder mir den entsprechenden Ort mitteilt, falls es sie schon gibt ;-)
(Der vorstehende Beitrag stammt von Kaihuener – 12:17, 6. Dez. 2005 (MEZ) – und wurde nachträglich unterschrieben.)

Geschichte und Entwicklung

Seit wann gibt es den Begriff "Theoretische Informatik"? Die geschichtliche Entwicklung dieser Disziplin könnte besser dargestellt werden. --RokerHRO 12:05, 30. Mär 2006 (CEST)

Ich bin auch gerade auf dieses Manko gestoßen und möchte diese Forderung unterstreichen. 89.50.35.122 00:09, 24. Jul. 2007 (CEST)

Die Geschichte der theoretischen Informatik ist auch im Buch Gödel, Escher, Bach beschrieben. Das Buch ist ein Amerikanisches Politikum. Dieses Buch beschreibt in offen gelegten Fällen, nach der Bhuddistischer Lehre Zen Koans, die unter karmischen Gesichtspunkten, die die Geschichte der theoretischen Informatik in beispielhaften, vielleicht wahrhaftigen Ereignissen beschreiben. Auch das Schicksal von Alan Turing einem Pionier der theoretischen Informatik ist darin beschrieben.

(Der vorstehende Beitrag stammt von 84.157.255.57 – 23:03, 27. Mai 2008 (MESZ) – und wurde nachträglich unterschrieben.)

Die von Transmeta entwickelte Technik des Code Morphing könnte auch zur Geschichte der theoretischen Informatik oder des Turing Tests zählen.
(Der vorstehende Beitrag stammt von 84.157.255.57 – 23:16, 27. Mai 2008 (MESZ) – und wurde nachträglich unterschrieben.)

Überarbeiten-Baustein: Track B fehlt, Games fehlt

Es gibt in der European Association for Theoretical Computer Science folgende grobe Aufteilung des Gebiets theoretische Informatik:

• Track A: Algorithms, Automata, Complexity and Games
• Track B: Logic, Semantics and Theory of Programming

Mir scheint, der Wikipedia-Artikel und die Mindmap setzen theoretische Informatik mit Track A gleich. Wenn der Artikel seinen Namen verdienen soll, müsste Track B genauso abgehandelt werden (und nicht nur am Anfang kurz und stiefmütterlich erwähnt werden). --Tillmo 06:50, 9. Okt. 2007 (CEST)

Da dieses Defizit schwerwiegend ist, habe ich einen Überarbeiten-Baustein eingefügt. --Tillmo 12:29, 11. Nov. 2007 (CET)

In Büchern und Vorlesungen über Theoretische Informatik kommte es vor, dass der von Dir genannte Track B vorausgesetzt und implizit angewendet wird, ohne ihn richtig eizuführen. Im bisherigen Artikel ist der Logik, Semantik und Programmiertheorieteil teilweise unausgesprochen eingewoben und doch nicht ersichtlich. Auch ich schlage vor diese Themenbereiche der Theoretischen Informatik explizit darzustellen, damit der Artikel für die Leser die entsprechende Struktur und Qualität bekommt. --80.128.252.11 11:46, 21. Nov. 2007 (CET)

Ich kenn das auch so, dass Track B ein "richtiger" gleichberechtigter Bestandteil der theoretischen Informatik ist, mit eigenen Vorlesungen usw. Leider hab ich zuwenig Ahnung von dem Kram, als dass ich da viel beitragen koennte... --Wutzofant (grunz) 00:45, 5. Dez. 2007 (CET)

Ich habe einen kurzen Abschnitt zu formalen Semantik hinzugefügt, bei den anderen Bereichen reicht mE die Verlinkung in der Einleitung, daher habe ich den Baustein wieder rausgenommen. --84.57.160.221 12:02, 18. Feb. 2008 (CET)

Gut, aber die Mindmap müsste auch noch angepasst werden. --Tillmo 00:02, 19. Feb. 2008 (CET)

Wieso? Sie erhebt ja nicht den Anspruch vollständig zu sein und könnte das auch sowieso nie erreichen. Vielleicht sollte sie jedoch ein wenig weiter unten im Artikel platziert werden. --84.57.142.199 00:05, 19. Feb. 2008 (CET)

Für einen Leser ohne Vorkenntnisse sieht es so aus, als ob die Mindmap einen Überblick über die wichtigsten Gebiete der theoretischen Informatik gibt. Das tut sie aber nicht. Sie müsste daher erweitert oder so platziert werden, dass klar erkenntlich ist, dass sie nur einen Teilbereich abdeckt. --Tillmo 19:57, 21. Feb. 2008 (CET)

Die Mindmap umfaßt einen Ausschnitt des Wissens des an manchen Unis im Grundstudium gelehrt wird. Theoretische Informatik ist ein grundsätzlich endloses Thema, da (wohl jegliche) mathematische Formel mathematischen Spielregeln unterworfen ist, die die theoretische Informatik selbst wieder "REGULIERT" und auch automatisierten Semantiken zugänglich macht. Gödels Unvollständigkeitssatz beweist die Existenz eines Horizonts, der die widerspruchsfreien Aussagen, welche die theo. Inf. zum Thema hat eben für unvollständig erklärt. -- Es handelt sich hier aber nur um so etwas wie eine Meinung.--84.157.240.71 11:14, 6. Jun. 2008 (CEST)

Ich kann nur nochmal wiederholen: die ICALP, die führende europäische Theoriekonferenz, und die "Theoretical Computer Science", eine wichtige Theoriezeitschrift, beide von der European Association for Theoretical Computer Science organisiert bzw. herausgegeben, teilen die theoretische Informatik in Track A: Algorithms, Automata, Complexity and Games und Track B: Logic, Semantics and Theory of Programming auf (teils kommt noch ein Track C hinzu, der aber eher aktuelle Trends abdeckt). Die Mindmap stellt nun ausschließlich Track A dar. Diese Einseitigkeit ist nicht mit "Theoretische Informatik ist ein grundsätzlich endloses Thema" entschuldbar. Nur wenn klar gemacht wird, dass die Mindmap nur eine Hälfte abdeckt, ist sie OK. --Tillmo 20:02, 7. Jun. 2008 (CEST)

Ich habe folgende Vorschläge:
(1) Die verallgemeinernden Formulierungen und der mancherorts informelle Stil sind für den Wikiuser der einen schnellen Eindruck haben will gut. Die Aussagen über eine formale Wissenschaft sollten durch Quellen belegt werden. Vielleicht kann jemand die abstrahierten Aussagen im Artikel geschickt belegen oder schlechtesten Falls widerlegen. Ich fordere die Autorenschaft auf, den Artikel zu "stählen" und zu erweitern, denn er sollte auch der kritischen Betrachtung der Profis standhalten .
(2) Prof. Uwe Schönings Bücher Logik für Informatiker und Perlen der Theoretischen Informatik, sowie Cormen-Leiserson-Rivests Introduction to Algorithms, das auch auf Deutsch erschienen ist, könnte in die Literaturliste eingefügt werden. Dort finden sich vermutlich viele Erkenntniss, die auch für den Artkel relevant sein könnten. --80.128.243.30 11:43, 21. Feb. 2008 (CET)

Automatentheorie und Formale Sprachen

Die eigentlichen Automaten und deren Eigenschaften im zweiten Absatz, der die Automatentheorie beschreiben soll, sind nicht augeführt und erläutert. Weiter unten werden nur die Automaten, die zusammen die Chomsky-Hierarchie bilden, aufgezählt und mit Grammatik-Klassen in Verbindung gebraucht. Es fehlen die Aussagen, welche die Forschungen der Automatentheorie geliefert haben, und die Verlinkung auf die dazu gehörenden Artikel. Die Kategorie "Theoretische Informatik" ist reich an Artikeln, die vom Artikel "Theoretische Informatik" nicht direkt erreicht werden können. Ich schlage eine Anreicherung von Aussagen und entsprechende Links im ganzen Artikel "Theoretische Informatik" vor. --80.128.225.54 13:33, 20. Jan. 2008 (CET)

Einleitung

Die aufgeführten Teilgebiete in der Einleitung sind wohl zu unvollständig für einen enzyklopaedischen Artikel. Kann ein Kenner der Materie die Kernforschungsgebiete vervollstängigen? Vielleicht gibt es auch Dokumente im Web, die die Angaben überprüfbar machen.
Hier beispielsweise sind Forschungsgebiete wie Datenbanktheorie aufgeführt --80.128.195.106 11:14, 6. Feb. 2008 (CET)

Habe die Einleitung um einige Links erweitert, obwohl ich teilweise nur danach gegoogelt habe und sie in einer UnterKategorie von -Theoretische Informatik- gefunden habe. Soviele Leute haben zu der Kategorie -Theoretische Informatik- in der wikipedia beigetragen und der Hauptartikel wird stiefmütterlich gepflegt. Go go go folks... --80.128.203.95 12:43, 7. Feb. 2008 (CET)

Hier ein Teil der Beschreibung aus des englischsprachigen Artikels:

Scope It is not easy to circumscribe the theory areas precisely; the ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT), which describes its mission as the promotion of theoretical computer science, says

"The field of theoretical computer science is interpreted broadly so as to include algorithms, data structures, computational complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor."

Even so, the "theory people" in computer science self-identify as different. Some characterize themselves as doing the "'science' underlying the field of computing"[1], although this neglects the experimental science done in non-theoretical areas such as software system research.

Die Links haben alle existierende Artikel. (Klick for yourself) Auf der linken Seite des Artikels geht's natürlich auch...
(Der vorstehende Beitrag stammt von 80.128.203.95 – 17:58, 7. Feb. 2008 (MEZ) – und wurde nachträglich unterschrieben.)

Die Einleitung mit einer ellenlangen Aufzählung zu beginnen ist nicht gerade schön. Hier wären Schwerpunkte zu setzen. Alauda 22:58, 25. Aug. 2008 (CEST)

User Alauda vermuxt hier die Einleitung - hatte aber geringsten Anteil am Artikel. Soll Er/Sie doch hier darüber Diskutieren, ob mit einem Bruchteil der Inhalte der Theoretischen Informatik auch ein Enzyklopädischer Artikel über ein ganzes Fach möglich ist. Am Interesse für diesem Murx finde ich keine vernünftige Erklärung.--84.157.252.124 10:18, 26. Aug. 2008 (CEST)

Am Anfang der Einleitung findet sich nun eine Definition, wie sie auch in der wissenschaftlichen Literatur zu finden ist. Das ist sicherlich enzyklopischer als vorher. Die Aufzählung habe ich auch lediglich vom Anfang der Einleitung ans Ende der Einleitung verschoben. Es ist keine Information verschwunden. Und es spricht auch nichts dagegen, die Liste noch weiter zu vervollständigen. Zumindest wenn dabei - im übertragenen Sinne - nicht etwas rauskommt wie: Geographie beschäftigt sich mit räumlichen Strukturen, Vorgängen an der Erdoberfläche und mit Deutschland, Kuwait und Australien. Alauda 23:21, 26. Aug. 2008 (CEST)

Die Einleitung ist so völlig unhaltbar, siehe auch die Diskussion unten unter "Track B fehlt". Polemisch zusammengefasst sagt die aktuelle Einleitung folgendes aus: "Die theoretische Informatik befasst sich mit Track A-Themen. Track B-Themen nehmen nur einen unwichtigen Anteil ein, etwa so groß wie Kuwait in Bezug auf die Erdkugel." Die Track A-Arroganz könnte kaum größer sein! --Tillmo 10:16, 27. Aug. 2008 (CEST)

Die jetzige Einleitung gibt auf jedenfall ein falsches und unvollständiges Bild von der TI. Die vorige Einleitung war besser, muss ich sagen. --Revolus Echo der Stille 10:43, 27. Aug. 2008 (CEST)

Neuer Vorschlag

Die ICALP, immerhin eine der führenden europäischen Konferenzen über theoretische Informatik und die Hauptkonferenz der European Association for Theoretical Computer Science (EATCS) hat seit langem folgende Gliederung:

• Track A - Algorithms, Automata, Complexity and Games
• Track B - Logic, Semantics, and Theory of Programming

Seit kurzem gibt es auch einen Track C - Security and Cryptography Foundations. Die Zeitschrift "Theoretical Computer Science", ebenfalls von der EATCS herausgegeben, hat die gleiche Gliederung in Track A und Track B, allerdings lautet der -ebenfalls noch junge- Track C hier "Natural Computing". (Offenbar ist man sich noch nicht ganz einig, was die vielversprechendsten neuen Richtungen sind.)
Ich schlage vor, die Einleitung danach zu strukturieren, vielleicht sogar mit Verweis auf die EATCS. --Tillmo 18:09, 29. Aug. 2008 (CEST)

Grafik: Sprachen und Komplexitätsklassen

Diese Grafik, verwendet im Komlexitätstheorie Artikel, ist ziemich umfangreich. Vielleicht erscheint es manchem doppelt gemoppelt, hier den Vorschlag zu lesen, die Grafik und das Wissen dazu im Text einzubinden. Mal sehen welche Auswirkungen dieser Kristallisationspunkt auf Diskussionsseite und Artikel hat.
(Der vorstehende Beitrag stammt von 80.128.208.29 – 14:33, 22. Apr. 2008 (MESZ) – und wurde nachträglich unterschrieben.)

Das wäre eine zweite Grafik zum "Track A" (siehe oben). Zudem finde ich eine Doppelung nicht sinnvoll; lieber einen (weiteren) Verweis auf den Komlexitätstheorie-Artikel machen. Priorität sollte eine Grafik für "Track B" haben. --Tillmo 19:16, 11. Mai 2008 (CEST)

Berechenbarkeitstheorie

Zahlen- und Wortfunktion-Unterscheidung ist in Mindmap, nicht aber im Text.
(Der vorstehende Beitrag stammt von 84.157.249.75 – 15:00, 10. Mai 2008 (MESZ) – und wurde nachträglich unterschrieben.)

Mit Gödelnummern betrachtet ist das alles Jacke wie Hose. Und doch ist diese Unterscheidung für den Hausgebrauch ziemlich praktisch und üblich.--84.157.239.151 13:00, 18. Jun. 2008 (CEST)

Semantiken: Fixpunktsemantik

Referenz wäre: Vorlesung Prof. Vogler Uni Dresden. Er stellte in einer Vorlesung eine Fixpunktsemantik vor mit deren Hilfe sich aus einer kontextfreien Grammatik und einer syntaktischen Variable die semantische Kategorie der Variable ableiten läßt. Wie weit sich diese Beschreibung einer Fixpunktsemantik - informell richtig beschrieben - verallgemeinern läßt, entzieht sich meiner Erkenntnis. Ein Artikel Fixpunktsemantik wäre interessant. Dresdner Studies sind hier gefragt...--84.157.252.96 20:12, 31. Mai 2008 (CEST)

Logik

Im Wort Logik steckt auch das griechische Logos. Diese Feststellung möchte ich benutzen, um eine Entzerrung, Strukturierung und Auslegungserweiterung in diesem Abschnitt anzuregen. Versteht mich nicht falsch - ich möchte vorschlagen die Natur der gefundenen Strukturen und Aussagen im Abschitt Logik informell darzustellen, soweit sie ohne formelhafte Beschreibung auskommen. Bereits untergeordnete Überschriften wären begrüßenswert, obwohl die Erkenntnisse der Untersuchungen von Logiken nicht unbedingt eine hierarchische Struktur der Ergebnisse implizieren/indizieren müssen. Auch ein mengenlehreartiges Diagramm oder ein Graph könnten helfen--84.157.240.71 12:04, 6. Jun. 2008 (CEST)

Weitere Thematik: Wortproblem

Vorschlag: Die Thematik um den Begriff "Wortproblem" könnte im Artikel erläutert und in den Kontext umgebender Absätze eingearbeitet werden.--84.157.235.182 21:40, 21. Jan. 2009 (CET)

Entfernter Abschnitt

Habe folgenden Abschnitt aus dem Text entfernt, da die Aufzählung überhaupt keinen Mehrwert bietet und eher verwirrt als zu helfen.

== Modelle für Rechensysteme ==

Stichpunkte wie Auftragssysteme, Funktionseinheiten, Nebenläufigkeit, Synchronisation, Unteilbarkeit, Wartesysteme (M/M/m/k), Bedienstrategien (M/G/1) etc.

Sollte jemand zu den Stichpunkten mehr zu sagen haben kann der Abschnitt ja einfach wieder eingefügt werden. --134.100.32.213 13:58, 31. Aug. 2009 (CEST)

Zoo von gelösten oder anstehenden Problemen der Theoretischen Informatik

Gibt es einen listenhaften wp-Artikel mit den gelösten und anstehenden Problemen, die in der Theoretischen Informatik beackert wurden, werden oder werden sollen? Wenn nicht wie wäre es mit einem; wenn der Artkiel bereits existiert sollte diesen ein wp-Autor im Text dieses Artikels verlinken.
Soweit mein Vorschlag.
MfG 79.250.172.115 11:36, 11. Jul. 2011 (CEST)

Siehe-auch-Liste

Kann bitte jemand mit entsprechendem Fachwissen die "siehe auch"-Liste kürzen, bzw. die Begriffe in den Text einarbeiten. --Caramdir 22:35, 5. Jul. 2003 (CEST)

Ab nächste Woche habe ich Semseterferien, dann mache ich mich daran. --WilliMuc 03:01, 9. Jul. 2003 (CEST)

Die Begriffe könnten in einem neuen Abschnitt unter der Überschrift "Geschichte der theoretischen Informatik" eingebunden werden. --zap 14:05, 13. Sep. 2004 (CEST)

Ich hab' mal einen ersten Versuch unternommen - vielleicht finden sich noch ein paar, die das weiter treiben. --TobiasEgg 14:39, 13. Sep. 2004 (CEST)

Ok, wenn ich in den nächsten Tagen Zeit finde mache ich da noch weiter. --zap 15:03, 13. Sep. 2004 (CEST)

Informationstheorie

Irgendwie wurde dieses Teilgebiet der Informatik komplett unterschlagen. Das sollte dringend mal jemand einbauen, oder?
-- Gruss sparti 14:09, 12. Nov. 2005 (CET)

Die Kryptologie könnte auch noch erwähnt werden, die ihrerseits von der Informationstheorie und von Ergebnissen der Komplexitätstheorie (u.a.) profitiert. --87.123.23.65 18:09, 3. Jan. 2006 (CET)