Theoretische Informatik – die besten Beiträge

Guten Abend,

ich würde gerne Informatik studieren an einer Hochschule, da der Matheanteil dort geringer ist und mehr Wert auf Programmieren gelegt wird.

Hier sind alle Module der Hochschule, ist der Matheanteil an dieser HS wirklich gering? Ich sehe nur drei Mathe-Module und der Rest scheint hauptsächlich IT zu sein. Ich habe im Mathe LK immer zwischen 10-13 Punkten bekommen aber Analysis, Algebra und Stochastik haben mir relativ viel Spaß gemacht.

Zudem frage ich mich was mit "Grundlagen der Informatik" oder "Theoretische Informatik" gemeint ist, könnte mir das jemand erläutern?

Hallo an alle,

Ich habe mal eine Frage:

Wie lang braucht eigentlich eine Nachricht um die Erde über das Internet(theoretisch)? Kann mir bitte jemand diese Frage beantworten, wenn möglich bitte auch mit Quelle(außer Wikipedia). Danke schon mal im Voraus.

Checke irgendwie nicht, wie ich überprüfen soll, mit dem pumping-Lemma, ob eine Sprache regulär ist oder nicht.

1. Ist eine platzbeschränkte Turing-Maschine immer zeitbeschränkt?
2. Ist eine zeitbeschränkte Turing-Maschine immer platzbeschränkt?

Beim P/NP-Problem geht es soweit ich weiß darum das ein effizienter Algorithmus für ein Problem zum Beispiel die Färbung von Graphen, die Existenz von effizienten Algorithmen für alle anderen Probleme der selben Komplexität impliziert, korrigiert mich gerne falls ich das falsch verstanden habe. Ich verstehe nur gerade nicht wie man die Komplexität eines Problems definiert wenn man nicht den effizientesden Algorithmus kennt? "Ein Problem ist K-schwer wenn sich alle anderen Probleme der Klasse K auf den Algorithmus zur diesem Problem zurückführen lassen", damit beißt sich die Katze aber in den Schwanz du definierst die Komplexität eines Problems K dadurch daß sich alle anderen Probleme der Klasse K auf den den selben Algorithmus zurückzuführen wie unseres Anfangsproblems lassen. Weiterhin stellt sich mir die Frage ob es unendlich viele Probleme einer Komplexitätsklassen oder allgemein unendlich viele Komplexitätsklassen gibt?

Habe folgende Aufgabe. Ich soll den Kürzesten Pfad in einem Labyrinth Rekursiv finden.

Bisher kenne ich mich nur mit Wave Propagation (Iterativ) und wallfollower etc aus.

Meine Idee ists nun, dass ich Rekursiv erstmal das Maze entdecke und jedem Schritt eine Distanz zu ordne (Rekursive tiefe).

Nachdem alle Zellen discovered sind gehe ich vom Ziel aus und Suche dort Rekursiv per Backtracking den Kürzesten weg.

Ist das der Richtige Ansatz um das Problem zu lösen?

Das Labyrinth kann auch keine Wände haben und sehr großen Freiraum. Siehe Beispiel:

new String[]{
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "S               D",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
}

Es wird per Aufgabe zugesichert, dass der Weg maximal 65535 schritte lang ist. Das springt sofort ins Auge, weil unsigned short so groß ist. Dies würde meine Theorie bestätigen wenn man eine unsigned short matrix nehmen würde zum tracken der besuchten Zellen.

Oder gibts da eine bessere Lösung? Hab noch nie wirklich rekursiv gearbeitet und mag Rekursion nicht wirklich bisher.

Hallo,
Ich würde gerne die Zahl - 21,25 im IEEE single Format darstellen. Dafür wird die Kommazahl ja erstmal in Binär umgewandelt. Jetzt weiß Ich jedoch nicht genau wie das geht. Ich weiß wie man negative ganze Zahlen im Einerkomplement, Zweierkomplement und Vorzeichendarstellung darstellt, Ich weiß auch wie man positive Kommazahlen darstellt, jedoch weiß Ich nicht wie man dies mit Kommazahlen macht. Mit Ek,Zk Vorzeichendarstellung?
Wäre super wenn mir jemand helfen könnte vielleicht auch mit einer beispielhaften Rechnung :)
Danke schonmal!

In dieser Aufgabe sollte ich den DEA zu einem Automaten zeichnen, der nur Wörter akzeptiert, die nicht "00" enthalten, wobei Σ = {0;1}. Wäre dieser Automat zulässig, bzw. was müsste ich verbessern ?

Ich habe bis :

hA(n) ist Turing Berechenbar genau dann wenn , eine Turing Maschine existiert die auf Input n eine 1 schreibt falls n element A und ansonsten unendlich läuft. Was Äquivalant dazu ist, dass A semi entscheidbar ist.

also ist die Menge ja gleichmächtig wie die Menge der semi entscheidbaren Sprachen ? oder nicht?

sind die Semi entscheidbaren Sprachen denn abzählbar unendlich ? wenn ja wie beweise ich das wenn nein wo ist mein Fehler ?

Gibt es eine maximale Speichergröße die in einem System vorhanden sein kann und hängt die damit zusammen wie viele bit ein System hat ? Die Frage ist nur theoretisch und hat für mich keinen praktischen Nutzen.

Meine Überlegung:

Wenn eine Speicheradresse maximal 64bit lang sein kann dann kann es doch auch nur nur begrenzte bit im ganzen System geben die korrekt angesteuert werden können ?

Bsp: Für 64bit binär gibt es dezimal 2^64 Möglichkeiten also doch auch 2^64 verschiedene Adressen. Aufgrund dessen das jede Speicheradresse 64bit enthält kommt ich auch ein ganzes von (2^64)*64bit womit ich auf ein totales von

(2^64)*8*(0,1^15) petabyte = 147.573 petabyte

Oder

147.573.952 GB

Das sind natürlich utopische Mengen, jedoch bei einem 32bit system wären es dann nur

17,18 GB

Also wo liegt mein Denkfehler ?

Meine Kenntnisse vom Aufbau eines Computers sind nicht überweltigend, jedoch will ich ja was lernen also wenn die Antwort mit Google-recherche zu verstehen ist bin ich zufrieden.

Vielen Dank schonmal vorab

Hallo, evtl. kennt sich jemand mit der Pumping-Zahl aus.

Diese ist nämlich jene minimale Zahl p, sodass gilt:

Jedes Wort w aus der Sprache L mit einer Länge von mind. p (also |w| = p) kann in w = xyz aufgespalten werden, derart, dass

1. |xy| <= p
2. y =/= e (leeres Wort)
3. x(y^i)z ist in L

------------------------

Ich hätte mich jetzt gefragt, was die Pumping-Zahl von 0001*, 1011 und ((011) u (1*0*) ist.

-----------------------

Beim Ersten hätte ich p = 4 vermutet. Begründung: x = 000, y = 1, z = e

Dann |xy| <= p, y =/= e, und xy^iz ist in L (weil 000111...11 in L) für jedes i aus IN.

----------------------

Beim Zweiten bin ich mir nicht sicher, ob es da überhaupt eine Pumping-Zahl gibt, weil ich 1011 eigentlich nicht aufpumpen kann. Vielleicht weiß da jemand mehr.

----------------------

Beim Dritten hätte ich eine Pumping-Zahl von 1 vermutet. Begründung: Setze x = e, y = 1 und z = e

Dann |xy| <= p, y =/= e und xy^iz ist in L (weil 111...11 in L) für jedes i aus IN.

---------------------

Stimmen meine Vermutungen? Was mache ich mit dem endlichen Ausdruck 1011?

Ich wollte mal eure meine dazu wissen, ob dieser endliche Automat deterministisch ist oder nichtdeterministisch ist?

Meiner Meinung nach ist dieser Automat nichtdeterministisch, weil es kein eindeutigen Startzustand gibt, da man mit b oder c das Wort anfangen kann.

Lg

Hallo , habe ich folgende Aufgabe richtig gelöst ? oder habe ich einen Denkfehler:

Ich habe gesagt es gibt genau 3 Äquivalenzklassen nämlich :

[Epsilon] ,[a] und [z] wobei z elemt von Sigma stern ist aber ohne die Wörter die mit a beginnen.

Jetzt habe ich noch gezeigt das diese alle unterschiedlich sind und das die 3 wirklich alle sind. Hier bin ich mir aber nicht sicher.

Kann mir das eventuell jemand erklären ?

Einen wunderschönen guten boungiorno an alle,

Gegeben sei ein Graph G mit negativen Kantengewichten w ∈ ℤ \ℕ. Sei k das kleinste Gewicht einer Kante. Wir verfolgen die folgende Strategie, um die negativen Gewichte in positive zu transformieren: Addiere |k| auf jedes Kantengewicht und führe den Dijkstra-Algorithmus aus.Führt unsere Strategie zu einer korrekten Bestimmung der kürzesten Wege in G? Begründe Deine Antwort anhand eines Beispielgraphen.

Ansatz: Ich bin mir nicht sicher ob ich die Aufgabe richtig verstanden habe. Wir haben hier jetzt einen Graphen, der ausschließlich aus negativen Kantengewichten besteht. Und jetzt sollen wir |k| also das größte negative Gewicht auf jede einzelne Kante addieren und prüfen, ob Dijkstra noch korrekt funktioniert. Und genau da liegt der Hund in der Petersilie begraben. Weil Djkstra arbeitet doch ohnehin schon nicht mehr 100 % korrekt mit negativen Kantangewichten. Wie soll ich dann prüfen, ob er unter dieser Modifikation ( |k| drauf addieren ), dann noch korrekt arbeitet, wenn schon mal die Voraussetzung für korrektes Arbeiten nicht mehr erfüllt ist.

In dem Hinweis steht jetzt „Begründe Deine Antwort anhand eines Beispielgraphen“.. das hört sich so an als würden die dann nach einem Gegenbeispiel fragen.

Aber es würde sich doch nichts an den Kürzesten Wegen ändrern. Angenommen wir haben jetzt einen Graphen mit den Kantengewichten k = -10, -9, -8, -7, -6, -5, -4, -3, -2, -1. Dann wäre das kleinste Gewicht k = - 10. Also ist |k| = 10. Also überall 10 addieren

-10 + 10 = 0

-9 + 10 = -1

-8 + 10 = - 2

-1 + 10 = 9

usw.

Dann sind die Kantengewichte halt alle um 10 größer. Ändert sich nichts dran.Die Wege die früher "-10" waren und die kürzesten wahren, sind jetzt halt die Wege die "0" heißen und die kürzesten sind. Diejenigen die früher die zweitkürzesten waren und "-9" hießen, heißen jetzt halt "-1" usw.. Selbes System. Oder hat jemand ein gutes Gegenbeispiel wo es nicht funktioniert? Bei positiven Kantengewichten würde mir jetzt sowart was einfallen, aber hier sollen die Gewichte ja nur negativ sein.

Danke und einen wunderschönen sonnigen Sonntag Nachmittag

Hallo, ich verstehe die Konzept auf Reduktion, und auch Turing machine. aber ich weiss nich wie man mit so Aufgaben umgehen muss.

Guten Abend

Ansatz:

Zunächst erst mal alle unnötig kompliziert gegebenen Funktionen so umschreiben, dass sie sich vergleichen lassen

a (n) = 13n³, kann man nicht mehr vereinfachen

b (n) = log_4 n³ ist nichts anderes als 1,5 log_2 n

c (n) = 9 log_3 n hätt ich jetzt auch nicht weiter vereinfachen können

d (n) = log_2 4 n^4/3 ist nichts anderes als log_2 (4) + log2 (n^3/4), also 2 + 3/4 log_2 n

e (n) = n^log_4 n^4 kann man umschreiben zu n^2 log_2 (n).

Ich hätte die Funktionen also sortiert (von langsam nach schnell):

c < d < b < a < e.

Problem: Mein Tutor meinte die richtige Reihenfolge wäre: d < b < c < e < a.

Ich versteh es nicht. c. hat ja log_3 (n) und das ist ja schon mal langsamer als alles mit log_2 (n). Bei d und b bin ich mir unsicher, weil die ja eigentlich asymptotisch gleich schnell wachsen sollten. b wächst vielleicht bissl schneller weil es mit 1,5 multipliziert wird, während d nur mit 3/4 multipliziert wird.

Großes Kopfzerbrechen bereitet mir die Tatsache, dass e langsamer wachen soll als a. Bei e (n) ist doch das "n" im Exponenten. Auch wenn man im TR z.B. für n = 17 die Funktion e (n) eingibt, also 17^log_4 (17)^4 ist das 2.9210^21, also eine tierisch hoche Zahl. Wärend n = 17 in die Funtkion a(n) eingesetzt, lediglich 1317³ = 63869 ergibt, also viel weniger wächst. Auf desmos kann man die Funktionen plotten, und dort ist e (n) [bzw. ich musste es hier f(n) nennen, weil das Programm den Buchstaben "e" direkt als Euler'sche Phi-Funktion interpretiert] auch viel stärker an der y-Achse dran, also müsste es doch eigentlich stärker wachsen, or?

Hallo

falls ihr das schon gemacht habt, ist das schwer? Bruacht man da viel aufwand?

Ich habe mal gehört dass sich da viele irgendwie die Zähne ausbeißen aber eigentlich ist das mit den Automaten ja ziemlich leicht.

Kann mih da wer aufklräen? Wie schwer ist das ca?

lg

Moin moin. Unszwar geht es darum, dass man die asymptotische Notation zeigen soll, also das log2 (n!) genau so schnell wächst wie (n log2 n), bei der Fakultätsfunktion n! = n* (n-1) * (n-2)...1.

Hierzu muss in Aufgabenteil a) gezeigt werden, dass log 2 (n!) höchstens so schnell wächst wie (n log2 n) und in Aufgabenteil b), dass es mindestens so schnell wächst

Mein Ansatz. Wenn man zwei Funktionen teilt und das Ergebnis gegen unendlich geht, gilt O (höchstens so schnell). Wenn das Ergebnis gegen 0 geht, gilt Ω. Wenn das Ergebnis der Division ein konstanter Faktor ist, gilt Θ. Man könnte also log 2n! durch (n log 2n) teilen und zeigen, dass ein konstanter Faktor rauskommt und daher Θ gilt.

Die Aufgabe zwingt einen jedoch dazu, sowohl O und dann Ω zu zeigen

Ich müsste also log2n! durch (n log2 n) teilen und zeigen, dass es gegen unendlich geht, um O zu zeigen. Aber dann müsste man auch zeigen, dass es gegen 0 geht. Der Ansatz funktioniert also nicht.

Eine andere Möglichkeit wäre

log2 n! <= c * (n log2 n) zu rechnen. Aber dann müsste man auch log 2 n! >= c * (n log 2n) zeigen. Und leider kann ich n! nicht wegkürzen. :(

Hey :)

ich hab hier eine Aufgabe zu endlichen Automaten und einen Lösungsansatz.

Aufgabe:
Es soll ein endlicher Automat gezeichnet werden, der eine gerade Anzahl an Nullen akzeptiert.

A = {0,1}

Meine Lösung:

Wir haben in Informatik momentan als Thema Sortierverfahren und jeder im Kurs soll eines vorstellen. Nun, ich habe den Quicksort zugeteilt bekommen und ich soll mich bei diesem ebenfalls mit der Laufzeit auseinandersetzen. Beim Quicksort beträgt die Laufzeit im worst-case O(n^2), was ich ja noch verstehe. Im average und im best-case beträgt diese aber O(n*log(n)) und ich weiß bei Leibe nicht was das heißen soll.

Ich hatte daraufhin mal auf Wikipedia nachgeschaut, aber da stand nur das es sich um ein super lineares Wachstum handelt und ich habe leider keine Ahnung, was das heißen soll...

Wäre nett, wenn das irgendwer zufällig wissen sollte. :)