Grundlagen der Informatik II

at Karlsruher Institut für Technologie

Join course
739
Next exam
FEB 11
Discussion
Documents
Flashcards
Darf man die Bonusklausur schreiben, ohne die Übungen zu besuchen? Vielen Dank im Voraus
ja
Man erhält jedoch nur den Bonus, wenn man im Tut anwesend ist und die Bonusklausur besteht.
Hallo, ist Grundlagen der Informatik 2 machbar, ohne Grundlagen der Informatik 1 gehört zu haben? Oder baut es zu stark aufeinander auf? Danke schon mal
Es ist machbar auch ohne GDI 1. Es gibt sehr wenige Sachen und eher unwichtig die von GDI 1 vorkommen. Ich habe selber die Klausur geschrieben und bestanden ohne erstmal GDI 1 zu schreiben. Übe viel mit den zwei Übungsbücher die empfohlen werden. Das hilft sehr!
Alles klar, vielen Dank :)
Weiss jemand wann die Korrektur fertig ist?
View 2 more comments
Aber ohne Auswertung oder? Bei mir wird keine Note angezeigt
doch, die erreichten Punkte werden schon angezeigt, jedoch ohne bonus deswegen noch keine finale note
Wie fandet ihr die Klausur? Ich fand sie ganz gut, viele schema Aufgaben. Klar gabs auch 2-3 schwere
Hey, kann mir jemand erklären wieso wir im Tut 3, Aufgabe 2 schreiben, dass die Sprache L1 = a^m b^n c^n , m,n>=1; dass PPL erfüllt, wo wir doch in Aufgabe 1 gezeigt haben dass L= a^n b^n c^n, das nicht tut? Da nicht ausgeschlossen ist dass m und n gleich sein können muss L1 doch auch eine Schnittmenge mit L haben und dass PPL für beide nicht erfüllt sein? Oder sehe ich was falsch
View 2 more comments
Es könnten 2 Sachen sein die du meinst. 1) Die Definitionsbereiche der Potenzen "hoch n" sind in Aufgabe 1 und 2 unterschiedlich Definiert. Sie sind also 2 unterschiedliche Sprachen 2) Das wir in Aufgabe 1 gezeigt haben, dass das PPL nicht erfüllt ist, bedeutet nicht, dass die Sprache nicht regulär ist, da das PPL eine notwendige Bedingung jedoch nicht eine hinreichende Bedingung ist, sodass die Regularität (oder das Kontextfrei sein) einer Sprache widerlegt wird
@AnonymesRiesenrad Danke dir für die Antwort, kann es vielleicht auch einfach daran liegen dass wir das PPL für Kontextfreie Sprachen in 1 anwenden und das für reguläre in Aufgabe 2?
In den Altklausuren werden bei den Aufgaben über die Kellerautomaten häufig "nichtdeterministische" KA gefordert,in den Lösungen werden dann aber einfach deterministische gezeigt und es wird nicht weiter darauf eingegangen. Gibt es eine Regel die besagt, dass die deterministischen nur eine Untergruppe der nichtdeterministischen KA sind? Vielleicht weiß ja jemand von euch eher Bescheid.
könnte mir jemand kurz die NP Problematik erklären. Folgende Punkte erschließen sich mir nicht ganz: 1) Die Probleme in NP sind alle polynomiell lösbar, was ist mit den Problemen in NP-schwer und in entscheidbar, sind diese auch polynomiell lösbar? 2) Kann man nur Probleme z.B. aus NP polynomiell auf ein NP-schweres Problem reduzieren oder geht es auch anders herum (von NP schwer nach NP)?
1) - Alle Probleme in NP-vollständig (liegen sowohl in NP, als auch in NP-schwer) sind gegenseitig in Polynomialzeit aufeinander reduzierbar. - Kein NP-schweres Problem kann durch einen bekannten polynomialen Algorithmus gelöst werden - falls jemals ein polynomialer Algorithmus für ein NP-schweres Problem gefunden wird, erhält man automatisch polynomiale Algorithmen für alle Probleme in NP 2) Man reduziert immer ein "leichteres" Problem auf ein "schwereres". Nicht umgekehrt.
ok vielen Dank! Sind Probleme die in Entscheidbar liegen also polynomiell lösbar? oder nur manche davon?
Wann nimmt man beim PPL die zerlegung xyz und wann uvwxy ?
Die Partition von w in xyz -> reguläre Sprachen. Die Partition von z in uvwxy -> kontextfreie Sprachen.
Hey Leute War es nicht so, dass man immer s0 auf a und b prüft und die "mengen an Zustände" dann weiterverwendet, um einen NDA (nicht deterministischen Automaten) zu einen DA zu machen? Daher frage ich mich, woher die s0,s1 kommt, da wir im ersten Schritt ja eigentlich nur s0,s3 erzeugt haben, das wir verwenden können..
Kann es sein, dass die Reihenfolge der lösung einfach unlogisch ist, weil man ja erst in Zeile 3 auf s0,s3 kommt?
Die Reihenfolge ist nicht so wie wir es in der VL besprochen haben, aber es ändert ja absolut gar nichts.. Man hat dann nur andere Bezeichnungen von s1 oder s2 aber sonst ändert das absolut nichts und ist auch so richtig 😊 also kein stress
Wie macht man bei Chomsky den ersten Schritt also "lambda frei" machen
https://www.youtube.com/watch?v=7xL6JMaB5-A&t=308s Dieses Video ist Hammer nice. Er hat 3 Videos darrüber. Die Aufgaben in der Klausur sind sogar oft einfacher als was er zeigt. Formale Sprachen #31 #32, #33. Aber zu deiner Frage konkret. Du schaust, welches Nonterminal auf λ abbildet (z.B. A -> λ I aA). Mit dem λ könntest du das aA nehmen und zu a machen, indem du das A mit dem λ wegmachst. Da du es jetzt gelöscht hast, musst du es "substituieren" indem du eine neue Abiilding schaffst. A -> λ I a. Macht das Sinn?
Weiß jemand wie viele Punkte man braucht, um zu bestehen?
40,5 von 90
Hey Leute, ich komme einfach nicht auf die 0/1/2/Äquivalent. Kann das jemand erklären? Ich weiß, dass die 0 Äquivalenz ({Nichtendzustand };{Endzustand}) ist und das ganz unten in der Tabelle ohne Zahl immer : ({Alle einzeln};{Außer die 2x Äquivalenten/zusammegefassten}). Was ist aber die 1 und 2 Äquivalenz? Bzw. wie komm ich drauf für die Klausur?
Bei 1-Äquivalenz machst du dir ne Tabelle und schaust wo die einzelnen zB bei der Ausgabe von a bzw b hingelangen ... die die bspw. auf ein endzustand und einen nicht-endzustand kommen sind zsm in einer klammer Bei 2-Äquivalenz machst du das selbe mit aa, bb , ab , ba es geht bestimmt einfacher aber so mach ich es
"Na, Sie haben ja zuvor schon die Minimierungstabelle ausgefüllt. Dort steht jede Zelle für ein Zustandspaar. Wenn die Zelle leer ist, sind die Zustände äquivalent zueinander, das heißt k-äquivalent für alle k Wenn in der Zelle ×i steht, dann sind die beiden Zustände nicht i-äquivalent, aber i−1 -äquivalent zueinander. Das heißt also, Sie fangen mit einer Menge an, die alle Zustände enthält (diese können wir ja mal unformal −1-äquivalent nennen, damit die obige Beschreibung auch für den i=0-fall passt), und trennen diese immer weiter auf. Zuerst beginnen Sie also mit den Zellen, die ×0 enthalten. Das sind Zustandspaare, die zueinander nicht 0-äquivalent sind. Die entsprechenden Zustände werden also voneinander getrennt, was zu zwei Mengen führt (in diesem Fall die Menge der Endzustände und die Menge der Nicht-Endzustände, für i=0 braucht man die Tabelle also noch gar nicht). So erhalten Sie die erste Zeile der Tabelle Dann nehmen Sie sich genauso die ×1-Zellen vor und trennen die Zustände voneinander, die zwar noch 0-äquivalent waren, aber nicht mehr 1-äquivalent sind. Dann die ×2-Zellen usw. In der letzten Zeile sind die Zellen gerade so aufgeteilt, wie die Zustände äquivalent zueinander sind." Die Erklärung von Lukas König aus dem Info 2 Forum hat mir geholfen.
Wird die Klausur am Freitag aus Aufgaben bestehen die 1:1 im Pool sind? Oder ähnliche?
Weiß jemand wer die Nachklausur erstellt hat? Bzw. ob die Nachklausur auch vom Rettinger erstellt wurde oder nicht? Demnach könnte man nämlich auf die Kapitel, die zum auswendiglernen sind, verzichten.
View 2 more comments
Deine Aussage ist völlig falsch, weil rettinger in der 1. Vorlesung gesagt hat, dass die Aufgabenthemen ausgesucht werden aber die Auswahl an Aufgaben erfolgt rein automatisch aus einem Pool von Aufgaben.. - - > Theorie auswendiglern3n ist genau so wichtig wie in den Altklausuren, kann also drankommen
Seine Aussage war in den späteren Vorlesungen, dass er nicht viel von Aufgaben hält, bei denen man nichts anwenden muss und nur auswendig gelerntes wiedergeben muss.
Was meint ihr dazu? Fehler in der Lösung 2018/19 (Hauptklausur) ??
Nein, da nur die Zustände markiert werden bei denen einer ein Endzustand ist und einer nicht. In diesem Fall wären beides Endzustände.
Schaltnetze und Schaltwerke relevant?
View 1 more comment
Die Frage ist eher, sind CMOS und Schaltnetze/Werke nicht so nah zusammen, dass beides entfällt. In der Klausur 2018/19 kam eine Aufgabe zu CMOS/Schaltnetze als EINE Aufgabe
Es gibt genug Aufgaben, die nur Schaltnetze/-werke bearbeiten.
Lernt ihr die Theorie Themen auch, die wurden ja in der Hauptklausur dieses Jahr garnicht abgefragt
Auf jeden Fall.. Sind halt geschenkte Punkte in vielen Altklausuren
Meint ihr damit die letzteren 3-4 Vorlesungsskripte?
Sind CMOS Klausurrelevant?
View 1 more comment
Wieso denkst du das? In der Hauptklausur 2018 gab es die Aufgabe 6) CMOS / Schaltnetze (10 Punkte) .
Weil es im ILIAS steht
War jemand in den Übungen/hat Aufschriebe?
Wenn du die Lösungen von den Übungsblättern meinst, die gibt es im Ilias.
Die sind nicht immer sehr intuitiv, manchmal sind mitschreiben hilfreicher
Ist Hash-Organisation klausurrelevant? Es gibt keine Aufgabe dazu in den Aufgabenblätter.
Leuts reichen 2 Wochen für die Prüfung?
View 2 more comments
Reicht auch eine Woche oder garnicht erst probieren?
Also wenn du dich auf tuts/altklausuren stürzt sollte man bestehen 🤔 vieles ist halt nach fixem schema
Gibt es eine Stoffabgrenzung oder wurde etwas über nicht Klausurrelevante Themen erwähnt?
Tut 1 : Hab null Durchblick, muss man selbst auf die Regel kommen oder ist die vorgegeben??
View 3 more comments
Es gibt immer mehrere Lösungen.
Kann das jemand noch präziser erklären?
Hey Leute, habt ihr Tipps für die Prüfungsvorbereitung?
View 2 more comments
Ich habe mir die Aufzeichnungen angeschaut und parallel dazu Aufgaben vom Übungsbuch bearbeitet. Das hat auch gut funktioniert.
In der Hauptklausur war eine Aufgabe 1:1 wie in einer Altklausur. ;)
Moin, gibt es bei regulären ausdrücken nur die eine richtige Lösung oder gibt es auch verschiedene Varianten? :)
Wenn man nicht all zu gut vorbereitet ist, sollte man dennoch schreiben oder bei Info II eher vorsichtig mit Versuchen sein? Sind die Nachtermine i.d.R. schwerer? Bin grad ziemlich verzweifelt, würde mich über ne Antwort freuen! :)
View 1 more comment
Letztes Semester ist die Nachklausur deutlich besser ausgefallen als der Haupttermin. Also wenn man genug lernt, kann man dort auch eine gute Note schreiben.
Danke für eure Antworten! :)
Hey, könnte jemand mal erzählen, wie man sich am besten vorbereitet? sind die vl relevant oder reicht es wenn man die übungen gut kann? :) Danke
VL sind definitiv relevant und Übungen würde ich einfach rauf und runter rechnen
Gibt es das Buch "Theoretische Informatik - ganz praktisch", das in der Vorlesung empfohlen wurde irgendwo als "kostenloses" e book?
Ja gibt als ebook von der kit bib
Danke!
No area was marked for this question
r=1, s=1 führt bei RS zum ERROR :)
my bad, ist schon etwas älter die kurübersicht :)