Suchergebnisse

Zitat: „Original von Ark @Acrobat reader: Es geht darum, wie "schwierig" es ist, verschiedene Probleme zu lösen. In der Kryptographie baut man auf eher "schwierige" Probleme. Wäre nun P = NP, so wären viele Verschlüsselungsverfahren für den Allerwertesten, weil das auch hieße, dass die angeblich "schwierigen" Probleme gar nicht so schwierig sind. (Viel Spaß dann beim nächsten E-Mail-Abruf.) “ Naja, du hast zwar Recht, dass in der Kryptographie viel auf "schwierige" Probleme gesetzt wird, aber we…

Klar will ich Ich probiers mal. Erstmal sollte man sich darüber klar werden, dass es in der Informatik nicht darum geht, möglichst viele Programmiersprachen zu lernen, tolle Websites zu basteln, die neueste Hardware zu kennen oder sonstige computertechnische Problemchen lösen zu können. Ein Informatiker ist kein Computertechniker Die meisten Informatiker können sowas zwar, aber dass ist eher ein "Abfallprodukt", sag ich mal Nettes Zitat von Dijkstra (sehr bekannter Informatiker): "Informatik hat…

Zitat: „Original von Ark Hm, die Erklärung klingt so ein bisschen nach "weil das so ist". xD “ Naja, ich kann dir hier halt nicht 3/4 meiner Theoretischen Informatik Vorlesung innerhalb eines Posts zusammenfassen Da musst du dich dann schon selbst etwas einlesen Kurz zur Semi-Entscheidbarkeit vom Halteproblem: Es ist unentscheidbar, ob ein Programm irgendwann hält, daher kann man nicht sagen, ob es jemals halten wird - außer natürlich, wenn das Programm hält! D.h. man kann die Programme, die nac…

Zitat: „Original von Ark Frage, mal wieder zur Chomsky-Hierarchie (ich sollte einen Sammelthread aufmachen xD): Standardbeispiel für eine, äh, "Struktur", die durch eine Typ-3-Grammatik beschrieben wird: a^n Standardbeispiel für Typ 2 (und nicht mehr Typ 3): a^n b^n Standardbeispiel für Typ 1 (und nicht mehr Typ 2): a^n b^n c^n Gibt es auch ein Standardbeispiel für Typ 0? Und wenn ja: welches? Ark“ Ein oft genanntes Beispiel ist das Halteproblem (eine kurze Erklärung, wie man das als Sprache int…

Ne, ich glaub nicht, dass das ein Blasinstrument ist. Dazu fehlt der "luftige Klang". Zumindest keine Flöte oder sowas, eher sowas wie ne Uillean Pipe. Für mich hörts sich aber schon fast mehr nach nem Streichinstrument an, evtl. vielleicht auch ne Drehleier. Aufgrund der Soundqualität (die machts eigentlich schon fast ziemlich unmöglich genau sagen zu können, was das ist) der sonstigen Musik würd ich aber am ehesten noch auf eine Keyboard-Simulation eines solchen Instruments tippen.

Zitat: „Original von Ark @Pan: So, ich habe mal strikt alle m durch n ersetzt, weiß aber nicht, ob das so richtig ist. “ Alles richtig bis auf die Induktionsannahme, soweit ich das sehe. Da muss Quellcode (1 Zeile) hin Zitat: „ Was mir noch auffiel: Ganz unten heißt es Quellcode (1 Zeile) Müssten da a und a' nicht vertauscht werden? “ Hm? Nein, dass stimmt so schon. a' ist das, was übrigbleibt, wenn man a modulo n rechnet. Formal korrekter wärs gewesen, wenn ich geschrieben hätte: Quellcode (1 Z…

Zitat: „Original von Ark @Pan: 1. Könntest du bitte den verbesserten(!) Quelltext hier reinstellen (in eine code-Umgebung)? Das wäre sehr hilfreich. “ Sorry, nein, kann ich nicht, wäre kein Problem, aber ich hab den Quelltext leider nicht mehr. Ich habs über ein Online-Tool eingegeben und den Quelltext nicht gespeichert, da ich kein Tex auf'm Rechner hab. Hätte ich den Quelltext noch gehabt, dann hätte ich logischerweise direkt die Grafik verbessert, anstatt die Edits hinzuzufügen. Nochmal einti…

Zitat: „Original von Ark Ark hat mal wieder eine Frage. Und es geht mal wieder um Informatik. Und zwar gleich im DOPPELPACK. “ Und ich hab mal wieder - zumindest teilweise - eine Antwort Zitat: „ Okay, okay, genug der Vorrede, hier die Fragen: Die erste Frage betrifft RSA. Es geht um den Ausdruck a^x mod n. Ein bisschen Rumprobieren ließ uns (die ganze Klasse) vermuten, dass a^x mod n = (a mod n)^x mod n gilt. Leider fehlt uns der Beweis, wir wissen es also nicht genau, und wir können es leider …

Zitat: „Original von Ark Eine Funktion funktioniert. Eine Relation ... relativiert? Ark“ Im mathematischen Sinne? Dann würde ich eher sagen: Eine Funktion bildet (Funktionen heissen auch Abbildungen) von der Definitionsmenge in die Zielmenge ab. Eine Relation beschreibt eine Beziehung zwischen zwei Objekten (z.B. ist "<" eine Ordnungsrelation).

Zitat: „Original von Ark Wie sieht eine solche Grammatik aus? Ark“ Vermutlich unglaublich kompliziert Ich hab jetzt länger drüber nachgedacht, aber ich bin auf keine Lösung gekommen. Eine entsprechende Grammatik dürfte wirklich verdammt kompliziert werden und ich hab nur nach einer Grammatik für a & b als Terminale gesucht. Bei noch größerem Terminal-Alphabet wirds noch komplizierter. Die Grammatik dürfte auf jedenfall eine riesige Menge von Produktionen haben Mir ist leider nicht wirklich was d…

Ach, Mist, ich sollte doch eigentlich für die Technische Informatik Klausur lernen... aber das hier ist viel interessanter Zitat: „Original von Ark So, ich hoffe, der hier funktioniert. “ Ja, der Link geht! Also ausgehend von der Verwendung des Begriffs hier und in dem Buch, was Luna verlinkt hat, würde ich sagen, die Ausdrucksstärke beschreibt, wieviel Anforderungen ich an eine Sprache stellen kann. In Chomsky-3 kann ich keine korrekten Klammerpaare verlangen, in Chomsky-2 schon => Chomsky-2 is…

Zitat: „Original von Ark So weit mir bekannt ist, kann man mit den Regex aus der Unix-Welt genau Typ 3 abdecken. Typ 2 geht schon mal gar nicht, und kontextsensitive Regeln lassen sich nur in diversen Erweiterungen festlegen (für die wiederum Typ 3 reichen muss). Die Quantoren sind einfach nur Potenzen, die ihr an der Uni auch behandelt haben dürftet (nehme ich jetzt einfach mal an xD). Ich habe es auf einem gerade direkt vor mir liegenden Zettel mal nachvollzogen und für alle Unix-Regex (ohne k…

SelfHTML kennt dafür auch keine Tags, von daher geh ich auch mal davon aus, dass das nicht geht.

Ach, reguläre Ausdrücke... und ich dachte mir heute morgen noch "Oder sind vielleicht reguläre Ausdrücke gemeint?" Reguläre Ausdrücke sind in der theoretischen Informatik leicht anders definiert, als die Unix-RegEx. Insbesondere gibts dort keine Quantoren die sagen "Zeichen X muss so und so oft vorkommen". Die Definition für Reguläre Ausdrücke bei uns an der Uni gelehrt wird, ist insbesondere so, dass man nur reguläre Sprachen darstellen kann. Also nur Sprachen vom Typ Chomsky-3. Die Unix-RegEx …

Zitat: „Original von Luna Alles Folgende ohne Gewaehr ... xD [ab]* laesst sich auf [abc]* reduzieren, weil alles, was aus [ab]* erzeugt werden kann, auch aus [abc]* erzeugt werden kann. Die Worte aus [ab]* sind ja automatisch auch ⊂ [abc]*. Daher ist L([ab]*) <= L([abc]*). Sicher, im Endeffekt nennt man beides "abzaehlbar unendlich", aber es laesst sich ja ganz einfach sehen, dass L([abc]*) mehr Worte enthaelt als L([ab]*), weil man alle Worte aus [ab]* bekommt und ausserdem noch die Moeglichkei…