Theoretische Informatik – die besten Beiträge

Hallo,

Ich habe Probleme diese Aufgabe zu lösen und weiß nicht, wie ich das am besten machen kann. Kann das jemand lösen? Es reicht, wenn nur das Zeichen pro Nummer mit Begründung geschrieben wird.

Meine Antwort dazu wäre:

1. x (A C B)

2. x (A C B)

3. x (A C B)

4. x (B C A)

5. x (B C A)

6. =

Was heißt es:

man kann jedes Problem in P auf jedes andere Problem in P reduzieren

?

Angenommen als Beispiel:

• L1 ist die Entscheidung, ob eine Zahl z1 gerade ist
• L2 ist die Entscheidung ob eine Zahl z2 prim ist

Ich kann nun spaßhalber eine Reduktion von L1 -> L2 machen, indem ich

zuest L1(z1) löse und wenn das Ergebnis

• ja ergibt, füttere ich L2 mit dem Input 3
• nein ergibt, füttere ich L2 mit dem Input 6

Dann habe ich L1 in Polyzeit auf L2 reduziert: man schreibt



bzw. man sagt

" L2 ist mindestens so schwierig wie L1"

Ich könnte aber auch umgekehrt eine Reduktion von L2 -> L1 machen, indem ich

zuest L2(z2) löse (wie auch immer, aber eben in Polyzeit) und wenn das Ergebnis

• ja ergibt, füttere ich L1 mit dem Input 2
• nein ergibt, füttere ich L1 mit dem Input 1

Dann würde ich schreiben können:



bzw. sagen

L1 ist mindestens so schwierig wie L2"

Das würde bedeuten, dass P1 und P2 gleich schwierig sind, was aber klarerweise nicht der Fall ist. Hab ich da was falsch verstanden?

Wie ist das also diese Notation zu interpretrieren?? Irgendwas stimmt doch hier nicht...wo bin ich falsch abgebogen?

Die Turing-Maschine ist scheinbar ein wichtiges Konzept in der theoretischen Informatik. Ich selbst bin ein kompletter Laie in der Informatik, habe aber in anderen Zusammenhängen immer wieder davon gehört. Bisher habe ich aber nie verstanden, wozu man das Konzept einer "nicht-deterministischen Turing Maschine" (NTM) benötigt: Soweit ich laienhaft verstanden habe, tut man so, als könne diese NTM Ergebnisse für eine Eingabe quasi erraten (Orakel) und dann schnell auf Akzeptanz prüfen. Was meint man hier mit erraten? Wo ist der konzeptionelle Unterschied zu deterministischedn TMs? Auch dort kann ich ja auf beliebig viele Berechnungspfade aufspalten (Speicher ist ja unbegrenzt) und quasi "parallel" rechnen. Es geht ja bei NTM nicht darum wie effizient diese sind - aber dann verstehe ich nicht, was daran so interessant ist.

Kann mir jemand ein konkretes Beispiel liefern, sodass ich den Vorteil des Konzepts erkennen kann?

Ich habe an der Uni eine Aufgabe erhalten und sitze jetzt schon seit mehreren Stunden daran, aber ich habe absolut keine Idee, wie ich sie lösen soll.

Kann mir jemand helfen?

Folgender selbst selbst erdachter NEA akzeptiert die Sprache die aus den Wörtern die mit 01 oder 11 beginnen.

Wenn ich den in ein DEA umwandeln möchte, bin ich mir nicht sicher, wie ich mit nicht definierten Übergängen (In dem Fall 0 bei q1) umgehen soll.

Gibt es vielleicht hier Mathematiker die beides belegt haben, wenn ja was empfindet Ihr als entspannter?

Verstehe ich das richtig, wenn ich z. B. ein Array mit 8 Elementen habe, z. B.

11, 25, 33, 42, 54, 58, 67, 96, und jetzt wissen will, wie viele Vergleiche die Binäre Suche braucht, um das Element 11 zu finden, kann ich dann einfach die Komplexitätsklasse zu Hilfe nehmen? Also hier O(log n) und da es 8 Elemente sind, brauche ich hier 3 Vergleiche, da O(log2(8)) = 3 ist? In dem Fall haut es doch hin, da es bei der Suche der 11 nicht um den Best Case O(1) handelt, weil die 11 nicht in der Mitte steht.

Falls das richtig ist, klappt das immer? Also bei anderen Algorithmen auch, zumindest wenn ich den Fall (Best, Worst und Average) erkenne und dann die entsprechende Komplexität nutze?

for i := 0; i < len(n); i++ { // O(n)

  for j := 0; j < len(n); j++ { // O(n)

    if x >= 30 { // O(1)

      for k := 0; k < len(n); k++ { // O(n)

        value = value + 10 // O(1)

      }

    } else {

      value = value + 2 // O(1)

    }

  }

}

ich hab den code und soll die Komplexitätsfunktion angeben ansich komm ich klar nur hab ein ein problem bzw ich stimme nicht mit chat gpt ein er sagt nähmlich=

O(n)(O(n)(O(1)+O(n)O(1)+O(1)))+O(1)

ich verstehe aber das erste + net ich hätte jetzt mal gesagt

also: O(n)(O(n)(O(1)*(O(n)O(1))+O(1)))+O(1)

G = ⟨{S}, {a, b, c, d}, {S → aSc | bSd | ε}, S⟩

Welche Sprache werde von dieser Grammatik generiert?

Ich verstehe welche Sprache damit erzeugt wird, da sie auch recht simpel ist, jedoch weiß ich nicht wie ich das aufschreiben soll. Kann mir Jemand weiterhelfen?

Vorab: Es geht um Reguläre Ausdrücke im Sinne der theoretischen Informatik.

Der "+"-Operator ist doch bei Anwendungen von Reguläre Ausdrücke wie ein XOR zu betrachten. "a+b" enthält die Wörter a und b aber nicht ab. (a+b)* würde a,b,ab,abab... wiederum enthalten. Oder sehe ich das falsch?

Bei Flaci, das ist ein Tool für sowas, ehemals auch AtoCC wird mir bei a+b nur ab als Wort der Sprache L angezeigt

Ein Eisenbahnzug besteht aus einer Reihe verschiedener Wagons. Er beginnt mit mindestens einer oder auch mehreren Lokomotiven, welche dann von null oder mehreren Guterwagons gefolgt werden. Nach diesen kann optional ein Begleitwagen kommen oder sofort eine Reihe von einem oder mehreren Personenwagons. Sind Personenwagons vorhanden, werden diese jedenfalls von einem Begleitwagen abgeschlossen. Beschreiben Sie diese Folge in Form einer Wirth’schen EBNF. Sie können folgendes Alphabet benutzen:

Σ = {Locomotive, GoodsTruck, PassengerCoach, GuardsVan}. GuardsVan bedeutet Begleitwagen. Sie können Σ aber auch erweitern, falls dies notwendig sein sollte

Ist nicht jede Sprache eine reguläre Sprache?

Man kann doch einfach folgenden DFA konstruieren:

Startzustand gleichzeitig akzeptierter Zustand, Übergangsfunktion verweist für jede Eingabe auf den Startzustand. Ist das denn nicht etwas witzlos?

Grammatik für Uhrzeit (HH:MM:SS) aufstellen und welcher Typ

Ich weiß die Stunden können von 00 bis 24 gehen, die Minuten von 00 bis 59 und die Sekunden von 00 bis 59

S -> A

A -> ...

Wie krieg ich das als Grammatik einer formalen Sprache hin?

Wie viele Äquivalenzklassen dieser regulären Sprache gibt es, die Lösung ist nachfolgend angegeben.

Lösung:

Wie man sieht gibt es hier genau 3 Äquivalenzklassen.

Was mich verwundert ist, warum man hier epsilon selbst als Äquivalenzklasse berücksichtigt? epsi mit Präfix ac steht doch nicht in Relation zu epsi mit präfix abc oder epsi mit Präfix abbc ...?

Anderes Bsp. Sprache ist wieder regulär

....

Es gibt unendlich viele Äquivalenzklassen. Soweit klar!

Warum berücksichtig man jetzt hier in dem Bsp. nicht epsilon selbst als Äquivalenzklasse, wie in dem Bsp. zuvor

epsi + Präfix ab oder epsi + Präfix aabb oder epsi + Präfix aaabbb...

Kann mir dies bitte jemand erklären. Danke!

Es geht um Modul: Theoretische Informatik. Ich lerne gerade für die Klausur. Ist es so richtig? Leider habe ich keine Lösung dazu, deswegen bin ich mir unsicher.. Danke im voraus ❤

Ich verstehe die Rechnung aber was wenn das Codewert mit 1 endet anstatt mit 0, am Ende wird ja dann eine 1 runtergezogen anstatt die 0. Hieße das das der Codewort falsch ist?

Wenn bei der Zerlegung x y z das |y| > 0 sein soll. warum darf man dann bei einem Beweis von L = {a^n b^n | n>= 0} und einem ansatz von a^p b^p wobei p = die anzahl der Zustände ist, x y^0 z wählen?

Ich mein wenn |y| nicht 0 betragen darf warum darf ich dann y^0 setzen? Ist doch ein wiederspruch oder?

Hi,
kann uns jemand hier erklären, wie man bestimmt welche Flags zu welchen Signalen gehören?
Wir haben im Netz rechachiert, was die Flags machen, aber können es trotzdem nicht richtig zuteilen, weil wir nicht wissen, wie man richtig vorgeht..

LG und vielen Dank!

Alphabet sigma = {0, 1}

Für d) L4 beinhaltet doch alle Wörter über sigma oder?

Für c) Die Wörter in L2 werden ja aus dreier Blöcke gebildet (sigma^3)

Wenn L3= sigma* \ L2 gilt sollte doch Wörter der Länge != 3n , die 101 als Teilwort enthalten, auch in L3 liegen. Dann gilt aber L3 = L2^c. Welcher ist richtig?