Ich habe Theory of Computation zum Spaß überarbeitet und diese Frage hat mich eine Weile genervt (lustig, ich habe nie daran gedacht, als ich in meinem Grundstudium die Automatentheorie lernte). Warum untersuchen wir also genau deterministische und nicht deterministische endliche Automaten (DFA /...
Es ist meine erste Frage auf dieser Seite. Ich mache einen Masterstudiengang in Rechentheorie. Wie würden Sie einem 10-jährigen Kind das P = NP-Problem erklären und warum wird es mit so einer finanziellen Belohnung belohnt? Deine Meinung? Ich werde die Frage aktualisieren, sobald mein Kopf klar...
Die Chomsky (-Schützenberger) -Hierarchie wird in Lehrbüchern der theoretischen Informatik verwendet, deckt jedoch im Vergleich zum vollständigen Komplexitäts-Zoo-Diagramm offensichtlich nur einen sehr kleinen Teil der formalen Sprachen (REG, CFL, CSL, RE) ab . Spielt die Hierarchie in der...
Ich werde oft von meiner Abteilung gebeten, vor Schülern im letzten Schuljahr Vorträge über die mathematischeren Elemente der Informatik zu halten. Ich gebe mein Bestes, um Themen aus TCS auszuwählen, die ihr Interesse wecken könnten (was meistens etwas mit dem Halting-Problem zu tun hat), würde...
Es gibt immer eine Möglichkeit zur Anwendung in Themen der theoretischen Informatik. Lehrbücher und Grundstudiengänge erklären jedoch in der Regel nicht, warum die Automatentheorie ein wichtiges Thema ist und ob sie in der Praxis noch Anwendung findet. Daher haben Studenten im Grundstudium...
Diese Frage richtet sich an Personen, die Probleme zuweisen: Lehrer, studentische Hilfskräfte, Tutoren usw. Das ist mir in meiner 12-jährigen Professorkarriere schon ein paar Mal passiert: Ich habe schnell ein Problem anhand des Textes "Das sieht gut aus" zugewiesen. Dann wurde mir später klar,...
Wenn wir die Standardlehrbücher oder Tradition folgen, lehren die meisten von uns die folgenden Definition von Big-Oh - Notation in den ersten Vorlesungen eines Algorithmen Klasse: Vielleicht geben wir sogar die ganze Liste mit all ihren Quantifizierern an:f= O ( g) iff ( ∃ c > 0 ) ( ∃ n0≥ 0 )...
Ich schätze, es ist unwahrscheinlich, dass es eine häufige Frage ist, aber ich frage mich, ob jemand Material gesehen hat, das eindeutig gemacht wurde, um dieses Publikum auf sinnvolle Weise
Ich unterrichte einen Kurs über fortgeschrittene Algorithmen und möchte einige Themen im Zusammenhang mit maschinellem Lernen behandeln, die für meine Studenten von Interesse sind. Infolgedessen würde ich gerne die Meinung der Leute zu den derzeit interessantesten / größten algorithmischen...
Ich habe gerade den Karger-Stein Randomized Mincut-Algorithmus in meiner Abschlussklasse unterrichtet. Dies ist ein echtes Juwel in Sachen Algorithmus , daher kann ich es nicht lehren, aber es macht mich immer frustriert, weil ich keine anderen Anwendungen der Haupttechnik kenne. (Daher ist es...
Ich habe Schwierigkeiten, das Konzept berechenbarer Funktionen zu vermitteln. Ich versuchte die Idee zu entwickeln, warum Forscher wie Hilbert / Ackermann / Godel / Turing / Church / ... den Begriff der "Berechenbarkeit" erfanden. Die Schüler fragten sofort: "Was bedeutet Berechenbarkeit?" und ich...
Gegenwärtig unterrichte ich einen kleinen Kurs (vier zweistündige Vorlesungen auf der Masters-Ebene) über logische Methoden in der Sicherheit , obwohl der Titel formale Methoden in der Sicherheit geeigneter sein könnte. Es werden kurz die folgenden Themen behandelt (mit den zugehörigen logischen...
Ich werde nächstes Semester eine Standard-Grundstudienklasse für Sprachen und Automaten unterrichten und würde es vorziehen, einen legitimen kostenlosen oder kostengünstigen Text zu verwenden. Irgendwelche Vorschläge? Ich liebe den Sipser-Text, aber die neueste Ausgabe kostet 196 US-Dollar, was im...
Ich habe eine vernünftige Grundausbildung in Mathematik, war aber noch nie zu 100% mit abstrakter Algebra (der Mathematik von Gruppen, Ringen, Feldern usw.) vertraut. Ich denke, dies war zum Teil so, wie ich es brauchte, um Anwendungen zu sehen, und alle, die ich finden konnte, befanden sich in der...
Mir wurde angeboten, ein neuartiges TCS-Highschool-Programm zu unterrichten, für das ein Lehrplan erstellt werden muss. Ich würde sehr gerne Meinungen und Vorschläge dazu hören. Erstens, kennt jemand Hochschulen, an denen ein TCS-Programm erfolgreich (oder erfolglos) unterrichtet wurde? Die Idee...
k = √max{k,n/k}max{k,n/k}\max \left\{k, n/k\right\}k=n−−√k=nk=\sqrt n Baby-Step-Riesenschritt-Algorithmus zur Berechnung des diskreten Logarithmus in ,O(n−−√)O(n)O(\sqrt n) statische orthogonale 2D-Bereichszählung in -Zeit und -Speicher,O(n)O(n−−√)O(n)O(\sqrt n)O(n)O(n)O(n) Prioritätswarteschlange...
Ich bin ein ziemlich erfahrener Softwareentwickler, aber ich kenne nicht viel Theorie. Ich möchte mehr Theorie lernen. Bestimmte Themen, die mich interessieren, sind: Komplexität der Berechnungen, formale Sprachen und Typentheorie. Aber ich bin ratlos, wie ich anfangen soll, über diese Felder zu...
Ich suche nach Beispielen für Ergebnisse, die gegen die Intuition der Menschen für ein allgemeines Publikumsgespräch verstoßen. Ergebnisse, die, wenn Sie von Nicht-Experten gefragt werden, "Was sagt Ihnen Ihre Intuition?", Fast alle falsch machen würden. Die Aussage der Ergebnisse sollte für...
Jedes Mal, wenn ich NP-Vollständigkeit unterrichte, fragen die Schüler: "Gibt es Probleme, von denen bekannt ist , dass sie nicht zu NP gehören?" Wie würden Sie antworten? Normalerweise gebe ich ihnen ein unentscheidbares Problem als Beispiel, aber dies stellt sich oft nicht gut heraus: (a) Wenn...
Angenommen, Sie treffen sich mit Programmierern, die einige professionelle Programmierkurse besucht haben (/ self thought), aber kein Mathematikstudium auf Universitätsniveau absolviert haben. Um ihnen die Schönheit von TCS zu zeigen, möchte ich einige nette Ergebnisse / offene Fragen von TCS...