Fragen, die sich aus Anwendungen der theoretischen Informatik in anderen Bereichen der Informatikforschung / -praxis oder anderen Fächern ergeben.
Um die Bedeutung von Algorithmen zu demonstrieren (z. B. für Studierende und Professoren, die keine theoretischen Kenntnisse besitzen oder aus ganz anderen Bereichen stammen), ist es manchmal hilfreich, eine Liste von Beispielen zur Hand zu haben, in denen Kernalgorithmen in kommerziellen,...
Für das Problem des maximalen Durchflusses scheint es eine Reihe sehr ausgefeilter Algorithmen zu geben, von denen mindestens einer erst im letzten Jahr entwickelt wurde. Orlins Max. Fließt in O (mn) Zeit oder besser ergibt einen Algorithmus, der in O (VE) läuft. Auf der anderen Seite sind die...
Das Studium von Ökologie und Evolution wird immer mathematischer, aber die meisten theoretischen Werkzeuge scheinen aus der Physik zu stammen. In vielen Fällen sind die Probleme jedoch sehr diskret (siehe z. B. SLBS00 ) und könnten aus Informatiksicht von Nutzen sein . Dennoch sind mir nur wenige...
Ich bin kein Theoretiker der Informatik, aber denke, dass dieses Problem der realen Welt hierher gehört. Das Problem Meine Firma hat mehrere Einheiten im ganzen Land. Wir haben den Mitarbeitern die Möglichkeit geboten, an einer anderen Einheit zu arbeiten. Aber es gibt eine Bedingung: Die...
Ich habe daran gearbeitet, einige Ergebnisse aus der Komplexität von Berechnungen in die theoretische Biologie, insbesondere Evolution und Ökologie , einfließen zu lassen , mit dem Ziel, für Biologen interessant / nützlich zu sein. Eine der größten Schwierigkeiten, mit denen ich konfrontiert war,...
In letzter Zeit habe ich mich mit Approximationsalgorithmen für NP-schwierige Probleme befasst und mich über die theoretischen Gründe für deren Untersuchung Gedanken gemacht. (Die Frage soll nicht entzündlich sein - ich bin nur neugierig). Einige wirklich schöne Theorien sind aus der Untersuchung...
Wurden Untersuchungen zur Implementierung von Zufallsextraktorkonstruktionen durchgeführt? Es scheint, dass Extractor-Proofs Big-Oh verwenden, was die Möglichkeit für große versteckte Konstanten lässt und programmatische Implementierungen möglicherweise unrealistisch macht. Kontext: Ich bin daran...
Ich möchte einen mathematischen Vortrag über das Git Revisionskontrollsystem halten. Es ist heute weit verbreitet in der Mathematik sowie in der Informatikindustrie. Zum Beispiel wird es von der HoTT-Community (Homotopy Type Theory) verwendet und ist das Go-to-System für die gemeinsame Bearbeitung...
Gibt es einen Standardverweis, um Ökonomen von der Relevanz der Komplexitätstheorie im Druck zu überzeugen? Ich kenne Noam Nisans Blogpost , Tim Roughgardens Umfrage und Kapitel 11 von Scott Aaronsons Aufsatz . Diese Stellen sind für Informatiker zugänglich, verwenden jedoch nicht die Sprache von...
Nehmen wir an, wir haben einen universellen Quantencomputer gebaut. Abgesehen von sicherheitsrelevanten Problemen (Kryptografie, Datenschutz, ...), welche aktuellen Probleme der realen Welt können davon profitieren? Ich interessiere mich für beides: Probleme, die derzeit für einen praktischen...
Ich habe diese Frage vor einiger Zeit bei Stack Overflow gestellt: Problem: Bobs Verkauf . Jemand schlug vor, die Frage auch hier zu posten. Jemand hat hier bereits eine Frage zu diesem Problem gestellt - Unterwald mit minimalem Gewicht und gegebener Kardinalität -, aber soweit ich das verstehe,...
Was sind einige reale Probleme, die mit einem genetischen Algorithmus gelöst wurden? Worin besteht das Problem? Was ist der Fitnesstest, um dieses Problem zu
Das Konzept eines geheimen Freigabeschemas wird häufig Shamir (A. Shamir, How to share a secret , Comm. ACM, 22 (1979), S. 612-613) und Blakey (GR Blakey, Safeguarding cryptographic keys , in Proc. NCC, Bd. 48, 1979, S. 313-317.). Die Gesamtidee ist, dass den Teilnehmern, die stattdessen jeweils...
Betrachten Sie das folgende Problem, Bei einem Satz von n=kmn=kmn = k m positiven Zahlen {a1,…,an}{a1,…,an}\{ a_1, \dots, a_n \} , in denen k≥3k≥3k \ge 3 eine Konstante ist, wollen wir die Menge in partitionieren mmm Teilmengen der Größe kkk , so dass das Produkt aus der Summe der einzelnen...
Sei x1, … , Xnx1,…,xnx_1, \ldots, x_n Punkte in der Ebene . Betrachten Sie einen vollständigen Graphen mit den Punkten als Eckpunkten und mit Kantengewichten von . Finden Sie immer ein Stück Gewicht, das mindestens des Gesamtgewichts beträgt? Wenn nicht, welche Konstante soll die \ frac 2 3...
Ich suche eine hocheffiziente Datenstruktur zur Speicherung von Daten ähnlich der folgenden. ID Tags Order1 Order2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 1,7 4 7 4 6 3 0 Ich muss in der Lage sein, diese Struktur so abzufragen, dass ich eine Liste aller IDs bekomme, die einen Ausdruck von...
Ich interessiere mich für die kombinatorischen Eigenschaften sozialer Netzwerke als Grafiken. Die Leute haben sich Dinge wie die Verteilung der Grade, den Clustering-Koeffizienten und die Kompressibilität dieser Graphen angesehen. Eine grundlegende Frage lautet: Sind diese Diagramme normalerweise...
Sei ein Vektor boolescher Variablen. Sei zwei boolesche Schaltungen auf . Sagen Sie, dass ähnlich ist, wenn:x=(x1,…,xn)x=(x1,…,xn)x=(x_1,\dots,x_n)C,DC,DC,DxxxCCCDDD Pr[C(x)≠D(x)]Pr[C(x)≠D(x)]\Pr[C(x) \ne D(x)] ist exponentiell klein, wenn xxx gleichmäßig zufällig aus \ {0,1 \} ^ n gezeichnet wird...
Ich bin ein CS-Student. Wir haben Graphentheorie in einem Kurs gemacht. Ich fand es interessant. Was sind die wirklichen Anwendungen der Graphentheorie in der Informatik? Ich fand zum Beispiel heraus, dass einige Konzepte in der Graphentheorie zum Entwerfen von Netzwerken verwendet werden können....
Diese Frage wurde durch eine Frage zum Stapelüberlauf motiviert . Angenommen, Sie erhalten einen Wurzelbaum (dh es gibt eine Wurzel und Knoten haben Kinder usw.) auf n Knoten (mit 1 , 2 , … , n bezeichnet ).TTTnnn1,2,…,n1,2,…,n1, 2, \dots, n Jedem Scheitelpunkt ist ein nicht negatives ganzzahliges...