Theoretische Informatik – die besten Beiträge

Guten Tag an alle, ich hätte Mal eine Frage und zwar, kennt jemand eine Universität in Deutschland, wo man im Chemie Bachelor besonders wenig Laborpraktika hat bzw. Generell wenig Experimente, dafür aber besonders viel Physikalische, Theoretische und Rechnergestützte Chemie? Vielen Dank schonmal im Voraus für's Antworten.

Hallo zusammen!

Ich saß sehr lange an dieser Uniaufgabe, die ich zur Übung mache, da ich bald eine Prüfung schreibe und wollte sicher gehen, dass ich sie richtig gelöst habe. Ich bin mir echt nicht sicher, ob ich richtig vorgegangen bin, da unsere Beispiele in der Vorlesung m.M.n sehr viel leichter waren als diese Aufgabe hier:

Konstruieren Sie den Überdeckungsgraphen für das Petrinetz mit der angegebenen Anfangsmarkierung! (Sollten mehrere Wahlmöglichkeiten existieren, so beginnen Sie stets mit der Transition, welche alphabetisch zuerst kommt.)

Meine Lösung:

Ich habe mich so wie gut ich konnte an diesem Algorithmus orientiert:

Bis zur Markierung 01w war ich mir eigentlich sicher, dass es stimmt, da es ja eigentlich 011 wäre, dort jedoch die Bedingung erfüllt war mit:  undfür L = 010, da eben die Transition a dafür sorgt, dass zwei Tokens auf einmal hinzugefügt werden.

Ich hoffe meine Überlegungen ergeben etwas Sinn und jemand kann mir weiterhelfen, bzw. sagen wie gut meine Lösung bis jetzt ist.

(λab.aba)(λxyz .xzy)y(λab.ba)

kann mir jemand helfen, dass mit beta-Reduktion in Normalform umzuwandeln?

DANKE

kann jemand mir bei der Lösung helfen, ich kann es nicht.

Kann jemand mir bei diese Aufgabe helfen? Meine Proffesorin meinte:

für die Widerlegung, dass eine Sprache L regulär ist, wird ein Wort gewählt, aber für ALLE möglichen Zerlegungen mit w=xyz muss gezeigt werden, dass das Wort x(y^k)z nicht in L ist.

ZB beginnt w mit nicht-pumpbaren Zeichen, also die Sprache L ist so definiert, dann w=xxxa^p...

dann müssen alle Zerlegenungen betrachtet werden, das geht mit Fallunterscheidung

x= \epsilon

x=c^i für i=1,2,3

x=ccca^i 

Ich bereite mich für die Prüfung theoretische Informatik vor, aber ich komme mit dieser Aufgabe garnicht zurecht. kann jemand mir erklären und auch die Aufgabe lösen?

Geben Sie bitte eine Grammatik an, die

Kann evtl jemand, der sich mit dem Thema auskennt, einmal über den Beweis herüberschauen und bewerten, ob der korrekt geführt wurde?

TCF ist hierbei die Menge der total-berechenbaren-Funktionen

Ist das in Deutschland theoretisch und physikalisch möglich? Und wenn ja, wird es noch in diesem Jahrhundert geschehen?

(λabc.a(bb)c)(λxy.xya)(λa.a)

also meine Lösung:

gebunden: abcxy

frei: ab

ich bin mir bei dem b halt nicht sicher, wegen dem Ausdruck (bb) innerhalb eines Ausdrucks

Ich habe heute wohl einen Quanten-Tag.. :) ich versuche es mal kurz zu fassen:

Quanten = Wahrscheinlichkeiten, 1+1=2 = deterministisch

Wie geht das (so gut) zusammen? Danke. :)

Woran liegt es, wenn jemand zb ein Studium mit 1,0 abschließt, aber sein theoretisches Wissen nicht umsetzen kann und in Praktischer Arbeit völlig "unbrauchbar" ist?

Hallo zusammen
Wie wandle ich diese NEA in einem DEA um?

Leute, habt ihr Erfahrungen mit einer Bachelorarbeit in Informatik? (theoretische informatik)

Sollte ich meine Abbildungen selber erstellen, damit alles einheitlich ist? und habt ihr gute Tipps?

Ich verstehe das Konzept von Automaten nicht bzw ihren Sinn. Was genau sind Automaten in der Informatik? Für was gibt es sie? Und sind sie wichtig im beruflichen Leben als Informatiker?

Kann mir jemanden erklären, wie man das löst?

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?