FreitagsrundenWiki - Benutzerbeiträge [de]

Studieren und mehr

2017-10-11T12:48:37Z

Bastla: aktuelle Uni++ Slides

'''Uni++ Studieren und mehr -- Was kann man sonst noch so in der Uni machen?'''

... ist ein Vortrag, den die Freitagsrunde in der [[Einführungswoche|E-Woche]] hält. Wir stellen einige Aktivitäten vor, denen man als Student*in der Fak. IV an der Uni nachgehen kann und die über das Studium an sich hinausgehen.

Wenn ihr im Rahmen dieses Vortrages euer Projekt vorstellen wollt, dann beachtet die Hinweise am Ende.

== Aktuelle Folien ==

* [https://docs.freitagsrunde.org/E-Woche/2017/Vortraege/uniplusplus.pdf Folien von Oktober 2017 als PDF]

Achtung: Die folgenden Abschnitte geben grob den Inhalt wieder, aber in einer anderen Reihenfolge

=== Entspannungs- und Arbeitsräume ===
* Draußen sitzen
** Einsteinufer: grillen
** Südcampus: Volleyball Basketball und Tischtennis spielen
* Arbeitsräume
** [[Hauptgebäude|H]] 3062
** [[MAR|MAR]] Keller
** FH 310
** E 027 (neben dem [[Cafe_Shila|Shila]])
** [[Mathegebäude|MA]] - 5. - 7. Stock
** [[Mathegebäude|MA]] - Foyer
** [[Elektrotechnik-Neubau|EN]] - Foyer
** [[Elektrotechnik-Neubau|EN]] - 181-189
** EB - dritter Stock (EB 326, EB 317c)
** StudyCenter @ [[Mensa|TU-Mensa]] (15-18 Uhr)
* [[Rechnerraum|Rechnerräume]]
* studentische Cafés
** Vorteile:
*** Günstiger Kaffee
*** gemütliche Atmosphäre
*** nette Leute
*** Hilfe bei Problemen
** Beispiele:
*** TEL-Quel
*** [[Cafe_Shila|Shila]]
*** [[I-cafe|i-Café]]
*** Wiwi-Café [http://www.wiwicafe.de/]
* sonstige Cafés
** TEL-Cafeteria "Skyline"
** z.B. in Cafeteria am Eingang zum Mathegebäude ist das Arbeiten nicht erwünscht/gestattet
* Ini-Räume
* den eigenen Arbeitsplatz

=== Musik machen ===

* Collegium Musicum = FU + TU
** Großer Chor (Di 19-22 Uhr)
** Kammerchor (Do 19-22 Uhr)
** Sinfonieorchester (Mo 18:30-22 Uhr)
** Kleines Sinfonisches Orchester (Mi 18:30-22 Uhr)
** Uni Bigband Berlin (Di 19:30-22 Uhr)
** http://collegium-musicum-berlin.de/
** jedes Semester Konzerte

=== TU-Sport ===

* Informieren und Buchen über Website [http://www.tu-sport.de]
* Fitnessraum
** günstiger als normale Fitnessstudios
** es gibt Duschen
** Einführungstrainig unter Aufsicht nötig
* Sportkurse
** sehr breit gefächertes Angebot
*** von Aerobic
*** inkl. Qi Gong und Segeln
*** bis Yoga
** relativ günstig (16 Euro Badminton - 125 Euro Segeln)

=== Sprachkurse ===

* Sprach- und Kulturbörse (SKB) [http://www.skb.tu-berlin.de]
** Kurse meistens 1/Woche abends oder Intensivkurse während Semesterferien
** breites Angebot
*** Englisch, Französisch, Spanisch...
*** aber auch exotischere wie Arabisch, Mongolisch, Thailändisch, Hebräisch
** DAAD Sprachzeugnisse (zB falls Auslandssemester geplant)
** ACHTUNG: Werden nicht als Wahlpflichtkurse/Studium Generale anerkannt, da keine ECTS-Punkte
** nicht kostenlos, aber günstig: 51€/20h bis 149€/80h

* Zentraleinrichtung Moderne Sprachen (ZEMS) [http://www.zems.tu-berlin.de]
** nichtexotische Sprachen wie Deutsch, Englisch, Französisch, Spanisch
** spezialisiert auf Fachsprachen
** 24€ oder 48€/Semester
** "echte" LV/Module mit Prüfungen -> können als Studium Generale anerkannt werden, sofern nicht Zugangsvoraussetzung für den Studiengang (Keine Garantie!)
** Englisch ist Voraussetzung für Master
** Sonderkurs für Fak IV, kostenlos

=== Auslandsaufenthalt ===

* Erasmus
* DAAD
* TUB Fak IV: Double Degree Abkommen
* Praktikum AIESEC [http://www.aiesec.de]

=== Arbeiten ===

* für Bachelor: besser später (ab 3./4. Semester)
* an der Uni
** generell: 10,98€/Stunde - gesetzlicher Stundensatz für Studenten
** 40h/Monat, 60h/Monat oder maximal 80h/Monat
** mit Lehraufgaben (Tutor)
*** Tutorien halten
*** erst ab 4. Semester Bachelor oder mit Vordiplom
** ohne Lehraufgaben
*** Admin, Programmierer, administrative Aufgaben, Bibliothek...
*** einfach so bewerben
* Wo finden:
** Ausschreibungen Fak IV hängen aus (z.B. neben Verwaltung im FR 5. Etage)
** Onlineliste der Fakultät [http://cs.tu-berlin.de/Jobs/]
** Jobs-Mailingliste: <email>jobs@lists.freitagsrunde.org</email> [http://lists.freitagsrunde.org/mailman/listinfo/jobs]
** Seiten der TU zu Jobs und Karriere [http://www.tu-berlin.de/menue/service/job_karriere/]
* JunITer [http://www.juniter.de]
** studentische IT-Beratung
** Teil des Company Consulting Team (CCT)
** Verein für Studenten aller Fachrichtungen
** gemeinnützig, vermittelt IT-Projekte an Teams
** diese Teams arbeiten dann als GbR für Kunden
** Kernkompetenzen: Web- und Datenbankanwendungen
** Beispiel: meinprof.de
** Vernetzung der Mitglieder durch "Workends" und "Outside-Office-Events"
** betreiben außerdem eigene Infrastruktur
** Interesse? [http://www.juniter.de Bewerben!]
* in der freien Wirtschaft
** verlockend, da oft mehr Geld
** Praxiserfahrung für den Lebenslauf
** Vorsicht: viel Arbeit - Schaff ich das?

=== Studentische Aktivitäten ===

* AG Rechnersicherheit [http://www.agrs.tu-berlin.de/]
** hacken und gehackt werden
** Wettbewerbe (CTFs)
** jeden Dienstag 18 Uhr im EN 360
* DK0TU [http://dk0tu.de]
** Amateurfunkgruppe der TU-Berlin seit 1972
** Antennenabbau [...] ~2007 [...] mehrere Rückschläge seitdem
** Shack unter dem Dach des Hauptgebäudes
** Antennenbaumöglichkeiten auf dem Dach
** alle Afu-Bänder 160m bis 10GHz
** Schwerpunkte u.a. Meteorscatter (2m), EME (70cm)
** vorhandene Amateurfunkprüfung nicht notwendig
** Kontakt: <email>shack@dk0tu.de</email>
* Lötlabor [http://www.loetlabor.org]
** Raum: EN 444/445
** eigene Projekte mitbringen oder an vorhandenen mitarbeiten
** Betreuung durch bezahlte Tutoren
* Freitagsrunde
** [[Einführungswoche|E-Woche]] mitgestalten
** [[TechTalks]]
*** Projekte vorstellen
*** Vortrag ca 30-60 Minuten, in Einzelfällen auch länger möglich
*** auch in Verbindung mit Workshop
*** Letzte Themen:
**** Linux-Kernelprogrammierung (Chrysh's Diplomarbeit)
**** BitCoin (Jeffrey Paul, der den gleichen Talk auf auf dem Chaos Communication Camp gehalten hat)
**** 3D-Animation von Grund auf (Jakob, Mitglied der Freitagsrunde und VJ)
**** Tor (Erynn, Mitarbeiterin im Tor-Project)
** Party, [[Kickerturnier]]
*** Ihr könnt euch eins organisieren
*** 3. Uniwoche
*** Orgatreffen!
** [[LAN|LAN-Party]]
** [[Lip|Linux-Install-Party]]
** [[Java Kurs|Java-Kurs]]
*** MPGI 2: Java vorausgesetzt
*** Java vor Beginn des 2. Semesters lernen
*** eine Woche lang Vorträge und Übungen
*** sehr gutes Betreuungsverhältnis
** vor Wintersemester: wieder [[Ckurs|C-Kurs]]

=== Unipolitik ===

* Motivation:
** Ändern, was einen stört
* Uniweit
** Studenten wählen [[Studierendenparlament]] (StuPa) - im Juni erst wieder
** StuPa wählt den [[Allgemeiner Studierendenausschuss|Allgemeinen Studierendenausschuss]] (AstA) [http://asta.tu-berlin.de]
** AstA hat Referate, zu jedem gehört ein Arbeitskreis, in dem man sich beteiligen kann
*** Bildungspolitik
*** Sozialreferat
*** Umweltreferat
*** Ini-Koordination
*** Ausländer_innenreferat...
** Außerdem Service- und Beratungsangebot
*** Bafög/Soziales
*** Semesterticketbüro
*** Probleme mit Prüfungsamt
** EB 104 [http://eb104.tu-berlin.de/]
* Fakultätsweit
** Freitagsrunde
** Studenten wählen [[Fakultätsrat]] (FKR)
*** gewählte studentische Vertreter, derzeit
*** paritätisch besetzt, d.h. Studenten haben 2 Stimmen, außerdem noch Professoren, Wimis...
*** 2 Stimmen für 4 Studiengänge - das geht nur gemeinsam
** FKR benennt [[Ausbildungskommission]] (AK)
*** d.h. wir können einfach Leute mitnehmen
*** AK ändert z.B. Prüfungsordnung
** FKR benennt Prüfungsausschuss (PA)
** PA entscheidet z.B. Anerkennungsfragen

Siehe auch: [[Einführungswoche]]

== alte Folien ==

* [http://docs.freitagsrunde.org/E-Woche/2011/sonstso2011.pdf Folien aus WS 2011/12 als PDF] (13 MB)
* [http://docs.freitagsrunde.org/E-Woche/2008/Studieren_und_mehr_WS2008.pdf Folien aus WS2008 als PDF]
* [https://docs.freitagsrunde.org/E-Woche/2010/StudierenUndMehr/sonstso2010.pdf Folien zum 2010'er Vortrag "Studieren und mehr: Was man sonst noch so in der Uni machen kann"] (achtung, groß, 15MB)
* [http://docs.freitagsrunde.org/E-Woche/2012/uniplusplus.pdf Folien von Oktober 2012] (Achtung, 27 MB groß)
* [http://docs.freitagsrunde.org/E-Woche/2015/uniplusplus.pdf Folien von Oktober 2015 als PDF] (Achtung, 30 MB groß)
* [https://docs.freitagsrunde.org/E-Woche/2016/Vortraege/uniplusplus.pdf Folien von Oktober 2016 als PDF]

= Hinweise zur Aufnahme von Inhalten =

'''Bedingung:''' Ihr seid eine Berliner Hochschulgruppe oder steht in klarem Bezug zur TU Berlin.

Schickt uns bis '''eine Woche vor Beginn''' der [http://www.eecs.tu-berlin.de/menue/studium_und_lehre/start_ins_studium/semesterbeginn/ Einführungswoche der Fak IV] Inhalte im Umfang von '''1-3 Folien''' für '''1-3min Vorstellungszeit.''' Formate:

* '''Stichpunkt''' und '''Bilder'''
* oder alternativ die fertigen Folien als PDF '''ohne''' Seitenzahlen, Inhaltsverzeichnis etc. (wir betten diese dann wie Bilder bei uns ein)

Wir pflegen eine gemeinsame Präsentation, damit man nicht mit USB-Sticks und/oder Foliensätzen rotieren muss. Außerdem sind wir flexibler, ob Leute auftauchen oder auch nicht und können das auch selbst vorstellen.

Zu dem Zeitansatz - bevor Fragen kommen: Zu mehr sind die Studis nicht aufnahmefähig - der Vortrag soll einen Überblick bieten und einen Anreiz sich weiterzuinformieren, wenn einen etwas interessiert. Für die Gruppen, die mehr Zeit als eine kurze Vorstellung benötigen, gibt es im Anschluss einen frei gehaltenen Slot an unseren Vortrag. Ihr könnt dann gern den Raum bewerben in dem die Einführung in euer Thema stattfindet - bei der Raumbuchung unterstützt euch bei Bedarf die Fakultätsverwaltung.

Meldet euch bitte direkt bei den Verantwortlichen um den Informationsfluss zu verbessern:

<code>
Magdalena Rätz <maggyrz ät freitagsrunde.org>
Sebastian Lange <bastla ät freitagsrunde.org>
</code>

[[Kategorie:Studium]]

Studieren und mehr

2016-10-15T11:30:28Z

Bastla: Aktuelle Folien verlinkt

'''Uni++ Studieren und mehr -- Was kann man sonst noch so in der Uni machen?'''

... ist ein Vortrag, den die Freitagsrunde in der [[Einführungswoche|E-Woche]] hält. Wir stellen einige Aktivitäten vor, denen man als Student*in der Fak. IV an der Uni nachgehen kann und die über das Studium an sich hinausgehen.

Wenn ihr im Rahmen dieses Vortrages euer Projekt vorstellen wollt, dann beachtet die Hinweise am Ende.

== Aktuelle Folien ==

* [https://docs.freitagsrunde.org/E-Woche/2016/Vortraege/uniplusplus.pdf Folien von Oktober 2016 als PDF]

Achtung: Die folgenden Abschnitte geben grob den Inhalt wieder, aber in einer anderen Reihenfolge

=== Entspannungs- und Arbeitsräume ===
* Draußen sitzen
** Einsteinufer: grillen
** Südcampus: Volleyball Basketball und Tischtennis spielen
* Arbeitsräume
** [[Hauptgebäude|H]] 3062
** [[MAR|MAR]] Keller
** FH 310
** E 027 (neben dem [[Cafe_Shila|Shila]])
** [[Mathegebäude|MA]] - 5. - 7. Stock
** [[Mathegebäude|MA]] - Foyer
** [[Elektrotechnik-Neubau|EN]] - Foyer
** [[Elektrotechnik-Neubau|EN]] - 181-189
** EB - dritter Stock (EB 326, EB 317c)
** StudyCenter @ [[Mensa|TU-Mensa]] (15-18 Uhr)
* [[Rechnerraum|Rechnerräume]]
* studentische Cafés
** Vorteile:
*** Günstiger Kaffee
*** gemütliche Atmosphäre
*** nette Leute
*** Hilfe bei Problemen
** Beispiele:
*** TEL-Quel
*** [[Cafe_Shila|Shila]]
*** [[I-cafe|i-Café]]
*** Wiwi-Café [http://www.wiwicafe.de/]
* sonstige Cafés
** TEL-Cafeteria "Skyline"
** z.B. in Cafeteria am Eingang zum Mathegebäude ist das Arbeiten nicht erwünscht/gestattet
* Ini-Räume
* den eigenen Arbeitsplatz

=== Musik machen ===

* Collegium Musicum = FU + TU
** Großer Chor (Di 19-22 Uhr)
** Kammerchor (Do 19-22 Uhr)
** Sinfonieorchester (Mo 18:30-22 Uhr)
** Kleines Sinfonisches Orchester (Mi 18:30-22 Uhr)
** Uni Bigband Berlin (Di 19:30-22 Uhr)
** http://collegium-musicum-berlin.de/
** jedes Semester Konzerte

=== TU-Sport ===

* Informieren und Buchen über Website [http://www.tu-sport.de]
* Fitnessraum
** günstiger als normale Fitnessstudios
** es gibt Duschen
** Einführungstrainig unter Aufsicht nötig
* Sportkurse
** sehr breit gefächertes Angebot
*** von Aerobic
*** inkl. Qi Gong und Segeln
*** bis Yoga
** relativ günstig (16 Euro Badminton - 125 Euro Segeln)

=== Sprachkurse ===

* Sprach- und Kulturbörse (SKB) [http://www.skb.tu-berlin.de]
** Kurse meistens 1/Woche abends oder Intensivkurse während Semesterferien
** breites Angebot
*** Englisch, Französisch, Spanisch...
*** aber auch exotischere wie Arabisch, Mongolisch, Thailändisch, Hebräisch
** DAAD Sprachzeugnisse (zB falls Auslandssemester geplant)
** ACHTUNG: Werden nicht als Wahlpflichtkurse/Studium Generale anerkannt, da keine ECTS-Punkte
** nicht kostenlos, aber günstig: 51€/20h bis 149€/80h

* Zentraleinrichtung Moderne Sprachen (ZEMS) [http://www.zems.tu-berlin.de]
** nichtexotische Sprachen wie Deutsch, Englisch, Französisch, Spanisch
** spezialisiert auf Fachsprachen
** 24€ oder 48€/Semester
** "echte" LV/Module mit Prüfungen -> können als Studium Generale anerkannt werden, sofern nicht Zugangsvoraussetzung für den Studiengang (Keine Garantie!)
** Englisch ist Voraussetzung für Master
** Sonderkurs für Fak IV, kostenlos

=== Auslandsaufenthalt ===

* Erasmus
* DAAD
* TUB Fak IV: Double Degree Abkommen
* Praktikum AIESEC [http://www.aiesec.de]

=== Arbeiten ===

* für Bachelor: besser später (ab 3./4. Semester)
* an der Uni
** generell: 10,98€/Stunde - gesetzlicher Stundensatz für Studenten
** 40h/Monat, 60h/Monat oder maximal 80h/Monat
** mit Lehraufgaben (Tutor)
*** Tutorien halten
*** erst ab 4. Semester Bachelor oder mit Vordiplom
** ohne Lehraufgaben
*** Admin, Programmierer, administrative Aufgaben, Bibliothek...
*** einfach so bewerben
* Wo finden:
** Ausschreibungen Fak IV hängen aus (z.B. neben Verwaltung im FR 5. Etage)
** Onlineliste der Fakultät [http://cs.tu-berlin.de/Jobs/]
** Jobs-Mailingliste: <email>jobs@lists.freitagsrunde.org</email> [http://lists.freitagsrunde.org/mailman/listinfo/jobs]
** Seiten der TU zu Jobs und Karriere [http://www.tu-berlin.de/menue/service/job_karriere/]
* JunITer [http://www.juniter.de]
** studentische IT-Beratung
** Teil des Company Consulting Team (CCT)
** Verein für Studenten aller Fachrichtungen
** gemeinnützig, vermittelt IT-Projekte an Teams
** diese Teams arbeiten dann als GbR für Kunden
** Kernkompetenzen: Web- und Datenbankanwendungen
** Beispiel: meinprof.de
** Vernetzung der Mitglieder durch "Workends" und "Outside-Office-Events"
** betreiben außerdem eigene Infrastruktur
** Interesse? [http://www.juniter.de Bewerben!]
* in der freien Wirtschaft
** verlockend, da oft mehr Geld
** Praxiserfahrung für den Lebenslauf
** Vorsicht: viel Arbeit - Schaff ich das?

=== Studentische Aktivitäten ===

* AG Rechnersicherheit [http://www.agrs.tu-berlin.de/]
** hacken und gehackt werden
** Wettbewerbe (CTFs)
** jeden Dienstag 18 Uhr im EN 360
* DK0TU [http://dk0tu.de]
** Amateurfunkgruppe der TU-Berlin seit 1972
** Antennenabbau [...] ~2007 [...] mehrere Rückschläge seitdem
** Shack unter dem Dach des Hauptgebäudes
** Antennenbaumöglichkeiten auf dem Dach
** alle Afu-Bänder 160m bis 10GHz
** Schwerpunkte u.a. Meteorscatter (2m), EME (70cm)
** vorhandene Amateurfunkprüfung nicht notwendig
** Kontakt: <email>shack@dk0tu.de</email>
* Lötlabor [http://www.loetlabor.org]
** Raum: EN 444/445
** eigene Projekte mitbringen oder an vorhandenen mitarbeiten
** Betreuung durch bezahlte Tutoren
* Freitagsrunde
** [[Einführungswoche|E-Woche]] mitgestalten
** [[TechTalks]]
*** Projekte vorstellen
*** Vortrag ca 30-60 Minuten, in Einzelfällen auch länger möglich
*** auch in Verbindung mit Workshop
*** Letzte Themen:
**** Linux-Kernelprogrammierung (Chrysh's Diplomarbeit)
**** BitCoin (Jeffrey Paul, der den gleichen Talk auf auf dem Chaos Communication Camp gehalten hat)
**** 3D-Animation von Grund auf (Jakob, Mitglied der Freitagsrunde und VJ)
**** Tor (Erynn, Mitarbeiterin im Tor-Project)
** Party, [[Kickerturnier]]
*** Ihr könnt euch eins organisieren
*** 3. Uniwoche
*** Orgatreffen!
** [[LAN|LAN-Party]]
** [[Lip|Linux-Install-Party]]
** [[Java Kurs|Java-Kurs]]
*** MPGI 2: Java vorausgesetzt
*** Java vor Beginn des 2. Semesters lernen
*** eine Woche lang Vorträge und Übungen
*** sehr gutes Betreuungsverhältnis
** vor Wintersemester: wieder [[Ckurs|C-Kurs]]

=== Unipolitik ===

* Motivation:
** Ändern, was einen stört
* Uniweit
** Studenten wählen [[Studierendenparlament]] (StuPa) - im Juni erst wieder
** StuPa wählt den [[Allgemeiner Studierendenausschuss|Allgemeinen Studierendenausschuss]] (AstA) [http://asta.tu-berlin.de]
** AstA hat Referate, zu jedem gehört ein Arbeitskreis, in dem man sich beteiligen kann
*** Bildungspolitik
*** Sozialreferat
*** Umweltreferat
*** Ini-Koordination
*** Ausländer_innenreferat...
** Außerdem Service- und Beratungsangebot
*** Bafög/Soziales
*** Semesterticketbüro
*** Probleme mit Prüfungsamt
** EB 104 [http://eb104.tu-berlin.de/]
* Fakultätsweit
** Freitagsrunde
** Studenten wählen [[Fakultätsrat]] (FKR)
*** gewählte studentische Vertreter, derzeit
*** paritätisch besetzt, d.h. Studenten haben 2 Stimmen, außerdem noch Professoren, Wimis...
*** 2 Stimmen für 4 Studiengänge - das geht nur gemeinsam
** FKR benennt [[Ausbildungskommission]] (AK)
*** d.h. wir können einfach Leute mitnehmen
*** AK ändert z.B. Prüfungsordnung
** FKR benennt Prüfungsausschuss (PA)
** PA entscheidet z.B. Anerkennungsfragen

Siehe auch: [[Einführungswoche]]

== alte Folien ==

* [http://docs.freitagsrunde.org/E-Woche/2011/sonstso2011.pdf Folien aus WS 2011/12 als PDF] (13 MB)
* [http://docs.freitagsrunde.org/E-Woche/2008/Studieren_und_mehr_WS2008.pdf Folien aus WS2008 als PDF]
* [https://docs.freitagsrunde.org/E-Woche/2010/StudierenUndMehr/sonstso2010.pdf Folien zum 2010'er Vortrag "Studieren und mehr: Was man sonst noch so in der Uni machen kann"] (achtung, groß, 15MB)
* [http://docs.freitagsrunde.org/E-Woche/2012/uniplusplus.pdf Folien von Oktober 2012] (Achtung, 27 MB groß)
* [http://docs.freitagsrunde.org/E-Woche/2015/uniplusplus.pdf Folien von Oktober 2015 als PDF] (Achtung, 30 MB groß)

= Hinweise zur Aufnahme von Inhalten =

'''Bedingung:''' Ihr seid eine Berliner Hochschulgruppe oder steht in klarem Bezug zur TU Berlin.

Schickt uns bis '''eine Woche vor Beginn''' der [http://www.eecs.tu-berlin.de/menue/studium_und_lehre/start_ins_studium/semesterbeginn/ Einführungswoche der Fak IV] Inhalte im Umfang von '''1-3 Folien''' für '''1-3min Vorstellungszeit.''' Formate:

* '''Stichpunkt''' und '''Bilder'''
* oder alternativ die fertigen Folien als PDF '''ohne''' Seitenzahlen, Inhaltsverzeichnis etc. (wir betten diese dann wie Bilder bei uns ein)

Wir pflegen eine gemeinsame Präsentation, damit man nicht mit USB-Sticks und/oder Foliensätzen rotieren muss. Außerdem sind wir flexibler, ob Leute auftauchen oder auch nicht und können das auch selbst vorstellen.

Zu dem Zeitansatz - bevor Fragen kommen: Zu mehr sind die Studis nicht aufnahmefähig - der Vortrag soll einen Überblick bieten und einen Anreiz sich weiterzuinformieren, wenn einen etwas interessiert. Für die Gruppen, die mehr Zeit als eine kurze Vorstellung benötigen, gibt es im Anschluss einen frei gehaltenen Slot an unseren Vortrag. Ihr könnt dann gern den Raum bewerben in dem die Einführung in euer Thema stattfindet - bei der Raumbuchung unterstützt euch bei Bedarf die Fakultätsverwaltung.

Meldet euch bitte direkt bei den Verantwortlichen um den Informationsfluss zu verbessern:

<code>
Magdalena Rätz <maggyrz ät freitagsrunde.org>
Sebastian Lange <bastla ät freitagsrunde.org>
</code>

[[Kategorie:Studium]]

Studieren und mehr

2016-10-10T09:35:48Z

Bastla: Hinweis

'''Uni++ Studieren und mehr -- Was kann man sonst noch so in der Uni machen?'''

... ist ein Vortrag, den die Freitagsrunde in der [[Einführungswoche|E-Woche]] hält. Wir stellen einige Aktivitäten vor, denen man als Student*in der Fak. IV an der Uni nachgehen kann und die über das Studium an sich hinausgehen.

Wenn ihr im Rahmen dieses Vortrages euer Projekt vorstellen wollt, dann beachtet die Hinweise am Ende.

== Aktuelle Folien ==
* [http://docs.freitagsrunde.org/E-Woche/2015/uniplusplus.pdf Folien von Oktober 2015 als PDF] (Achtung, 30 MB groß)

Achtung: Die folgenden Abschnitte geben etwa den Inhalt wieder, aber in einer anderen Reihenfolge

=== Entspannungs- und Arbeitsräume ===
* Draußen sitzen
** Einsteinufer: grillen
** Südcampus: Volleyball Basketball und Tischtennis spielen
* Arbeitsräume
** [[Hauptgebäude|H]] 3062
** [[MAR|MAR]] Keller
** FH 310
** E 027 (neben dem [[Cafe_Shila|Shila]])
** [[Mathegebäude|MA]] - 5. - 7. Stock
** [[Mathegebäude|MA]] - Foyer
** [[Elektrotechnik-Neubau|EN]] - Foyer
** [[Elektrotechnik-Neubau|EN]] - 181-189
** EB - dritter Stock (EB 326, EB 317c)
** StudyCenter @ [[Mensa|TU-Mensa]] (15-18 Uhr)
* [[Rechnerraum|Rechnerräume]]
* studentische Cafés
** Vorteile:
*** Günstiger Kaffee
*** gemütliche Atmosphäre
*** nette Leute
*** Hilfe bei Problemen
** Beispiele:
*** TEL-Quel
*** [[Cafe_Shila|Shila]]
*** [[I-cafe|i-Café]]
*** Wiwi-Café [http://www.wiwicafe.de/]
* sonstige Cafés
** TEL-Cafeteria "Skyline"
** z.B. in Cafeteria am Eingang zum Mathegebäude ist das Arbeiten nicht erwünscht/gestattet
* Ini-Räume
* den eigenen Arbeitsplatz

=== Musik machen ===

* Collegium Musicum = FU + TU
** Großer Chor (Di 19-22 Uhr)
** Kammerchor (Do 19-22 Uhr)
** Sinfonieorchester (Mo 18:30-22 Uhr)
** Kleines Sinfonisches Orchester (Mi 18:30-22 Uhr)
** Uni Bigband Berlin (Di 19:30-22 Uhr)
** http://collegium-musicum-berlin.de/
** jedes Semester Konzerte

=== TU-Sport ===

* Informieren und Buchen über Website [http://www.tu-sport.de]
* Fitnessraum
** günstiger als normale Fitnessstudios
** es gibt Duschen
** Einführungstrainig unter Aufsicht nötig
* Sportkurse
** sehr breit gefächertes Angebot
*** von Aerobic
*** inkl. Qi Gong und Segeln
*** bis Yoga
** relativ günstig (16 Euro Badminton - 125 Euro Segeln)

=== Sprachkurse ===

* Sprach- und Kulturbörse (SKB) [http://www.skb.tu-berlin.de]
** Kurse meistens 1/Woche abends oder Intensivkurse während Semesterferien
** breites Angebot
*** Englisch, Französisch, Spanisch...
*** aber auch exotischere wie Arabisch, Mongolisch, Thailändisch, Hebräisch
** DAAD Sprachzeugnisse (zB falls Auslandssemester geplant)
** ACHTUNG: Werden nicht als Wahlpflichtkurse/Studium Generale anerkannt, da keine ECTS-Punkte
** nicht kostenlos, aber günstig: 51€/20h bis 149€/80h

* Zentraleinrichtung Moderne Sprachen (ZEMS) [http://www.zems.tu-berlin.de]
** nichtexotische Sprachen wie Deutsch, Englisch, Französisch, Spanisch
** spezialisiert auf Fachsprachen
** 24€ oder 48€/Semester
** "echte" LV/Module mit Prüfungen -> können als Studium Generale anerkannt werden, sofern nicht Zugangsvoraussetzung für den Studiengang (Keine Garantie!)
** Englisch ist Voraussetzung für Master
** Sonderkurs für Fak IV, kostenlos

=== Auslandsaufenthalt ===

* Erasmus
* DAAD
* TUB Fak IV: Double Degree Abkommen
* Praktikum AIESEC [http://www.aiesec.de]

=== Arbeiten ===

* für Bachelor: besser später (ab 3./4. Semester)
* an der Uni
** generell: 10,98€/Stunde - gesetzlicher Stundensatz für Studenten
** 40h/Monat, 60h/Monat oder maximal 80h/Monat
** mit Lehraufgaben (Tutor)
*** Tutorien halten
*** erst ab 4. Semester Bachelor oder mit Vordiplom
** ohne Lehraufgaben
*** Admin, Programmierer, administrative Aufgaben, Bibliothek...
*** einfach so bewerben
* Wo finden:
** Ausschreibungen Fak IV hängen aus (z.B. neben Verwaltung im FR 5. Etage)
** Onlineliste der Fakultät [http://cs.tu-berlin.de/Jobs/]
** Jobs-Mailingliste: <email>jobs@lists.freitagsrunde.org</email> [http://lists.freitagsrunde.org/mailman/listinfo/jobs]
** Seiten der TU zu Jobs und Karriere [http://www.tu-berlin.de/menue/service/job_karriere/]
* JunITer [http://www.juniter.de]
** studentische IT-Beratung
** Teil des Company Consulting Team (CCT)
** Verein für Studenten aller Fachrichtungen
** gemeinnützig, vermittelt IT-Projekte an Teams
** diese Teams arbeiten dann als GbR für Kunden
** Kernkompetenzen: Web- und Datenbankanwendungen
** Beispiel: meinprof.de
** Vernetzung der Mitglieder durch "Workends" und "Outside-Office-Events"
** betreiben außerdem eigene Infrastruktur
** Interesse? [http://www.juniter.de Bewerben!]
* in der freien Wirtschaft
** verlockend, da oft mehr Geld
** Praxiserfahrung für den Lebenslauf
** Vorsicht: viel Arbeit - Schaff ich das?

=== Studentische Aktivitäten ===

* AG Rechnersicherheit [http://www.agrs.tu-berlin.de/]
** hacken und gehackt werden
** Wettbewerbe (CTFs)
** jeden Dienstag 18 Uhr im EN 360
* DK0TU [http://dk0tu.de]
** Amateurfunkgruppe der TU-Berlin seit 1972
** Antennenabbau [...] ~2007 [...] mehrere Rückschläge seitdem
** Shack unter dem Dach des Hauptgebäudes
** Antennenbaumöglichkeiten auf dem Dach
** alle Afu-Bänder 160m bis 10GHz
** Schwerpunkte u.a. Meteorscatter (2m), EME (70cm)
** vorhandene Amateurfunkprüfung nicht notwendig
** Kontakt: <email>shack@dk0tu.de</email>
* Lötlabor [http://www.loetlabor.org]
** Raum: EN 444/445
** eigene Projekte mitbringen oder an vorhandenen mitarbeiten
** Betreuung durch bezahlte Tutoren
* Freitagsrunde
** [[Einführungswoche|E-Woche]] mitgestalten
** [[TechTalks]]
*** Projekte vorstellen
*** Vortrag ca 30-60 Minuten, in Einzelfällen auch länger möglich
*** auch in Verbindung mit Workshop
*** Letzte Themen:
**** Linux-Kernelprogrammierung (Chrysh's Diplomarbeit)
**** BitCoin (Jeffrey Paul, der den gleichen Talk auf auf dem Chaos Communication Camp gehalten hat)
**** 3D-Animation von Grund auf (Jakob, Mitglied der Freitagsrunde und VJ)
**** Tor (Erynn, Mitarbeiterin im Tor-Project)
** Party, [[Kickerturnier]]
*** Ihr könnt euch eins organisieren
*** 3. Uniwoche
*** Orgatreffen!
** [[LAN|LAN-Party]]
** [[Lip|Linux-Install-Party]]
** [[Java Kurs|Java-Kurs]]
*** MPGI 2: Java vorausgesetzt
*** Java vor Beginn des 2. Semesters lernen
*** eine Woche lang Vorträge und Übungen
*** sehr gutes Betreuungsverhältnis
** vor Wintersemester: wieder [[Ckurs|C-Kurs]]

=== Unipolitik ===

* Motivation:
** Ändern, was einen stört
* Uniweit
** Studenten wählen [[Studierendenparlament]] (StuPa) - im Juni erst wieder
** StuPa wählt den [[Allgemeiner Studierendenausschuss|Allgemeinen Studierendenausschuss]] (AstA) [http://asta.tu-berlin.de]
** AstA hat Referate, zu jedem gehört ein Arbeitskreis, in dem man sich beteiligen kann
*** Bildungspolitik
*** Sozialreferat
*** Umweltreferat
*** Ini-Koordination
*** Ausländer_innenreferat...
** Außerdem Service- und Beratungsangebot
*** Bafög/Soziales
*** Semesterticketbüro
*** Probleme mit Prüfungsamt
** EB 104 [http://eb104.tu-berlin.de/]
* Fakultätsweit
** Freitagsrunde
** Studenten wählen [[Fakultätsrat]] (FKR)
*** gewählte studentische Vertreter, derzeit
*** paritätisch besetzt, d.h. Studenten haben 2 Stimmen, außerdem noch Professoren, Wimis...
*** 2 Stimmen für 4 Studiengänge - das geht nur gemeinsam
** FKR benennt [[Ausbildungskommission]] (AK)
*** d.h. wir können einfach Leute mitnehmen
*** AK ändert z.B. Prüfungsordnung
** FKR benennt Prüfungsausschuss (PA)
** PA entscheidet z.B. Anerkennungsfragen

Siehe auch: [[Einführungswoche]]

== alte Folien ==

* [http://docs.freitagsrunde.org/E-Woche/2011/sonstso2011.pdf Folien aus WS 2011/12 als PDF] (13 MB)
* [http://docs.freitagsrunde.org/E-Woche/2008/Studieren_und_mehr_WS2008.pdf Folien aus WS2008 als PDF]
* [https://docs.freitagsrunde.org/E-Woche/2010/StudierenUndMehr/sonstso2010.pdf Folien zum 2010'er Vortrag "Studieren und mehr: Was man sonst noch so in der Uni machen kann"] (achtung, groß, 15MB)

= Hinweise zur Aufnahme von Inhalten =

'''Bedingung:''' Ihr seid eine Berliner Hochschulgruppe oder steht in klarem Bezug zur TU Berlin.

Schickt uns bis '''eine Woche vor Beginn''' der [http://www.eecs.tu-berlin.de/menue/studium_und_lehre/start_ins_studium/semesterbeginn/ Einführungswoche der Fak IV] '''Stichpunkte''' und '''Bilder''' für '''1-3 Folien''' mit '''1-3min Vorstellungszeit.''' Wir pflegen eine gemeinsame Präsentation, damit man nicht mit USB-Sticks und/oder Foliensätzen rotieren muss. Außerdem sind wir flexibler, ob Leute auftauchen oder auch nicht und können das auch selbst vorstellen.

Zu dem Zeitansatz - bevor Fragen kommen: Zu mehr sind die Studis nicht aufnahmefähig - der Vortrag soll einen Überblick bieten und einen Anreiz sich weiterzuinformieren, wenn einen etwas interessiert. Für die Gruppen, die mehr Zeit als eine kurze Vorstellung benötigen, gibt es im Anschluss einen frei gehaltenen Slot an unseren Vortrag. Ihr könnt dann gern den Raum bewerben in dem die Einführung in euer Thema stattfindet - bei der Raumbuchung unterstützt euch bei Bedarf die Fakultätsverwaltung.

Meldet euch bitte direkt bei den Verantwortlichen um den Informationsfluss zu verbessern:

<code>
Magdalena Rätz <maggyrz ät freitagsrunde.org>
Sebastian Lange <bastla ät freitagsrunde.org>
</code>

[[Kategorie:Studium]]

Studieren und mehr

2016-10-10T09:32:23Z

Bastla: Vorstellungsdauer

''' Studieren und mehr -- Was kann man sonst noch so in der Uni machen? ''' 
... ist ein Vortrag, den die Freitagsrunde in der [[Einführungswoche|E-Woche]] hält.
Wir stellen einige Aktivitäten vor, denen man als Student*in der Fak.IV an der Uni nachgehen kann und die über das Studium an sich hinausgehen.

== Aktuelle Folien ==
* [http://docs.freitagsrunde.org/E-Woche/2015/uniplusplus.pdf Folien von Oktober 2015 als PDF] (Achtung, 30 MB groß)

Achtung: Die folgenden Abschnitte geben etwa den Inhalt wieder, aber in einer anderen Reihenfolge

=== Entspannungs- und Arbeitsräume ===
* Draußen sitzen
** Einsteinufer: grillen
** Südcampus: Volleyball Basketball und Tischtennis spielen
* Arbeitsräume
** [[Hauptgebäude|H]] 3062
** [[MAR|MAR]] Keller
** FH 310
** E 027 (neben dem [[Cafe_Shila|Shila]])
** [[Mathegebäude|MA]] - 5. - 7. Stock
** [[Mathegebäude|MA]] - Foyer
** [[Elektrotechnik-Neubau|EN]] - Foyer
** [[Elektrotechnik-Neubau|EN]] - 181-189
** EB - dritter Stock (EB 326, EB 317c)
** StudyCenter @ [[Mensa|TU-Mensa]] (15-18 Uhr)
* [[Rechnerraum|Rechnerräume]]
* studentische Cafés
** Vorteile:
*** Günstiger Kaffee
*** gemütliche Atmosphäre
*** nette Leute
*** Hilfe bei Problemen
** Beispiele:
*** TEL-Quel
*** [[Cafe_Shila|Shila]]
*** [[I-cafe|i-Café]]
*** Wiwi-Café [http://www.wiwicafe.de/]
* sonstige Cafés
** TEL-Cafeteria "Skyline"
** z.B. in Cafeteria am Eingang zum Mathegebäude ist das Arbeiten nicht erwünscht/gestattet
* Ini-Räume
* den eigenen Arbeitsplatz

=== Musik machen ===

* Collegium Musicum = FU + TU
** Großer Chor (Di 19-22 Uhr)
** Kammerchor (Do 19-22 Uhr)
** Sinfonieorchester (Mo 18:30-22 Uhr)
** Kleines Sinfonisches Orchester (Mi 18:30-22 Uhr)
** Uni Bigband Berlin (Di 19:30-22 Uhr)
** http://collegium-musicum-berlin.de/
** jedes Semester Konzerte

=== TU-Sport ===

* Informieren und Buchen über Website [http://www.tu-sport.de]
* Fitnessraum
** günstiger als normale Fitnessstudios
** es gibt Duschen
** Einführungstrainig unter Aufsicht nötig
* Sportkurse
** sehr breit gefächertes Angebot
*** von Aerobic
*** inkl. Qi Gong und Segeln
*** bis Yoga
** relativ günstig (16 Euro Badminton - 125 Euro Segeln)

=== Sprachkurse ===

* Sprach- und Kulturbörse (SKB) [http://www.skb.tu-berlin.de]
** Kurse meistens 1/Woche abends oder Intensivkurse während Semesterferien
** breites Angebot
*** Englisch, Französisch, Spanisch...
*** aber auch exotischere wie Arabisch, Mongolisch, Thailändisch, Hebräisch
** DAAD Sprachzeugnisse (zB falls Auslandssemester geplant)
** ACHTUNG: Werden nicht als Wahlpflichtkurse/Studium Generale anerkannt, da keine ECTS-Punkte
** nicht kostenlos, aber günstig: 51€/20h bis 149€/80h

* Zentraleinrichtung Moderne Sprachen (ZEMS) [http://www.zems.tu-berlin.de]
** nichtexotische Sprachen wie Deutsch, Englisch, Französisch, Spanisch
** spezialisiert auf Fachsprachen
** 24€ oder 48€/Semester
** "echte" LV/Module mit Prüfungen -> können als Studium Generale anerkannt werden, sofern nicht Zugangsvoraussetzung für den Studiengang (Keine Garantie!)
** Englisch ist Voraussetzung für Master
** Sonderkurs für Fak IV, kostenlos

=== Auslandsaufenthalt ===

* Erasmus
* DAAD
* TUB Fak IV: Double Degree Abkommen
* Praktikum AIESEC [http://www.aiesec.de]

=== Arbeiten ===

* für Bachelor: besser später (ab 3./4. Semester)
* an der Uni
** generell: 10,98€/Stunde - gesetzlicher Stundensatz für Studenten
** 40h/Monat, 60h/Monat oder maximal 80h/Monat
** mit Lehraufgaben (Tutor)
*** Tutorien halten
*** erst ab 4. Semester Bachelor oder mit Vordiplom
** ohne Lehraufgaben
*** Admin, Programmierer, administrative Aufgaben, Bibliothek...
*** einfach so bewerben
* Wo finden:
** Ausschreibungen Fak IV hängen aus (z.B. neben Verwaltung im FR 5. Etage)
** Onlineliste der Fakultät [http://cs.tu-berlin.de/Jobs/]
** Jobs-Mailingliste: <email>jobs@lists.freitagsrunde.org</email> [http://lists.freitagsrunde.org/mailman/listinfo/jobs]
** Seiten der TU zu Jobs und Karriere [http://www.tu-berlin.de/menue/service/job_karriere/]
* JunITer [http://www.juniter.de]
** studentische IT-Beratung
** Teil des Company Consulting Team (CCT)
** Verein für Studenten aller Fachrichtungen
** gemeinnützig, vermittelt IT-Projekte an Teams
** diese Teams arbeiten dann als GbR für Kunden
** Kernkompetenzen: Web- und Datenbankanwendungen
** Beispiel: meinprof.de
** Vernetzung der Mitglieder durch "Workends" und "Outside-Office-Events"
** betreiben außerdem eigene Infrastruktur
** Interesse? [http://www.juniter.de Bewerben!]
* in der freien Wirtschaft
** verlockend, da oft mehr Geld
** Praxiserfahrung für den Lebenslauf
** Vorsicht: viel Arbeit - Schaff ich das?

=== Studentische Aktivitäten ===

* AG Rechnersicherheit [http://www.agrs.tu-berlin.de/]
** hacken und gehackt werden
** Wettbewerbe (CTFs)
** jeden Dienstag 18 Uhr im EN 360
* DK0TU [http://dk0tu.de]
** Amateurfunkgruppe der TU-Berlin seit 1972
** Antennenabbau [...] ~2007 [...] mehrere Rückschläge seitdem
** Shack unter dem Dach des Hauptgebäudes
** Antennenbaumöglichkeiten auf dem Dach
** alle Afu-Bänder 160m bis 10GHz
** Schwerpunkte u.a. Meteorscatter (2m), EME (70cm)
** vorhandene Amateurfunkprüfung nicht notwendig
** Kontakt: <email>shack@dk0tu.de</email>
* Lötlabor [http://www.loetlabor.org]
** Raum: EN 444/445
** eigene Projekte mitbringen oder an vorhandenen mitarbeiten
** Betreuung durch bezahlte Tutoren
* Freitagsrunde
** [[Einführungswoche|E-Woche]] mitgestalten
** [[TechTalks]]
*** Projekte vorstellen
*** Vortrag ca 30-60 Minuten, in Einzelfällen auch länger möglich
*** auch in Verbindung mit Workshop
*** Letzte Themen:
**** Linux-Kernelprogrammierung (Chrysh's Diplomarbeit)
**** BitCoin (Jeffrey Paul, der den gleichen Talk auf auf dem Chaos Communication Camp gehalten hat)
**** 3D-Animation von Grund auf (Jakob, Mitglied der Freitagsrunde und VJ)
**** Tor (Erynn, Mitarbeiterin im Tor-Project)
** Party, [[Kickerturnier]]
*** Ihr könnt euch eins organisieren
*** 3. Uniwoche
*** Orgatreffen!
** [[LAN|LAN-Party]]
** [[Lip|Linux-Install-Party]]
** [[Java Kurs|Java-Kurs]]
*** MPGI 2: Java vorausgesetzt
*** Java vor Beginn des 2. Semesters lernen
*** eine Woche lang Vorträge und Übungen
*** sehr gutes Betreuungsverhältnis
** vor Wintersemester: wieder [[Ckurs|C-Kurs]]

=== Unipolitik ===

* Motivation:
** Ändern, was einen stört
* Uniweit
** Studenten wählen [[Studierendenparlament]] (StuPa) - im Juni erst wieder
** StuPa wählt den [[Allgemeiner Studierendenausschuss|Allgemeinen Studierendenausschuss]] (AstA) [http://asta.tu-berlin.de]
** AstA hat Referate, zu jedem gehört ein Arbeitskreis, in dem man sich beteiligen kann
*** Bildungspolitik
*** Sozialreferat
*** Umweltreferat
*** Ini-Koordination
*** Ausländer_innenreferat...
** Außerdem Service- und Beratungsangebot
*** Bafög/Soziales
*** Semesterticketbüro
*** Probleme mit Prüfungsamt
** EB 104 [http://eb104.tu-berlin.de/]
* Fakultätsweit
** Freitagsrunde
** Studenten wählen [[Fakultätsrat]] (FKR)
*** gewählte studentische Vertreter, derzeit
*** paritätisch besetzt, d.h. Studenten haben 2 Stimmen, außerdem noch Professoren, Wimis...
*** 2 Stimmen für 4 Studiengänge - das geht nur gemeinsam
** FKR benennt [[Ausbildungskommission]] (AK)
*** d.h. wir können einfach Leute mitnehmen
*** AK ändert z.B. Prüfungsordnung
** FKR benennt Prüfungsausschuss (PA)
** PA entscheidet z.B. Anerkennungsfragen

Siehe auch: [[Einführungswoche]]

== alte Folien ==

* [http://docs.freitagsrunde.org/E-Woche/2011/sonstso2011.pdf Folien aus WS 2011/12 als PDF] (13 MB)
* [http://docs.freitagsrunde.org/E-Woche/2008/Studieren_und_mehr_WS2008.pdf Folien aus WS2008 als PDF]
* [https://docs.freitagsrunde.org/E-Woche/2010/StudierenUndMehr/sonstso2010.pdf Folien zum 2010'er Vortrag "Studieren und mehr: Was man sonst noch so in der Uni machen kann"] (achtung, groß, 15MB)

= Hinweise zur Aufnahme von Inhalten =

'''Bedingung:''' Ihr seid eine Berliner Hochschulgruppe oder steht in klarem Bezug zur TU Berlin.

Schickt uns bis '''eine Woche vor Beginn''' der [http://www.eecs.tu-berlin.de/menue/studium_und_lehre/start_ins_studium/semesterbeginn/ Einführungswoche der Fak IV] '''Stichpunkte''' und '''Bilder''' für '''1-3 Folien''' mit '''1-3min Vorstellungszeit.''' Wir pflegen eine gemeinsame Präsentation, damit man nicht mit USB-Sticks und/oder Foliensätzen rotieren muss. Außerdem sind wir flexibler, ob Leute auftauchen oder auch nicht und können das auch selbst vorstellen.

Zu dem Zeitansatz - bevor Fragen kommen: Zu mehr sind die Studis nicht aufnahmefähig - der Vortrag soll einen Überblick bieten und einen Anreiz sich weiterzuinformieren, wenn einen etwas interessiert. Für die Gruppen, die mehr Zeit als eine kurze Vorstellung benötigen, gibt es im Anschluss einen frei gehaltenen Slot an unseren Vortrag. Ihr könnt dann gern den Raum bewerben in dem die Einführung in euer Thema stattfindet - bei der Raumbuchung unterstützt euch bei Bedarf die Fakultätsverwaltung.

Meldet euch bitte direkt bei den Verantwortlichen um den Informationsfluss zu verbessern:

<code>
Magdalena Rätz <maggyrz ät freitagsrunde.org>
Sebastian Lange <bastla ät freitagsrunde.org>
</code>

[[Kategorie:Studium]]

Studieren und mehr

2016-10-07T14:09:15Z

Bastla: FAQ Aufnahme von Inhalten

''' Studieren und mehr -- Was kann man sonst noch so in der Uni machen? ''' 
... ist ein Vortrag, den die Freitagsrunde in der [[Einführungswoche|E-Woche]] hält.
Wir stellen einige Aktivitäten vor, denen man als Student*in der Fak.IV an der Uni nachgehen kann und die über das Studium an sich hinausgehen.

== Aktuelle Folien ==
* [http://docs.freitagsrunde.org/E-Woche/2015/uniplusplus.pdf Folien von Oktober 2015 als PDF] (Achtung, 30 MB groß)

Achtung: Die folgenden Abschnitte geben etwa den Inhalt wieder, aber in einer anderen Reihenfolge

=== Entspannungs- und Arbeitsräume ===
* Draußen sitzen
** Einsteinufer: grillen
** Südcampus: Volleyball Basketball und Tischtennis spielen
* Arbeitsräume
** [[Hauptgebäude|H]] 3062
** [[MAR|MAR]] Keller
** FH 310
** E 027 (neben dem [[Cafe_Shila|Shila]])
** [[Mathegebäude|MA]] - 5. - 7. Stock
** [[Mathegebäude|MA]] - Foyer
** [[Elektrotechnik-Neubau|EN]] - Foyer
** [[Elektrotechnik-Neubau|EN]] - 181-189
** EB - dritter Stock (EB 326, EB 317c)
** StudyCenter @ [[Mensa|TU-Mensa]] (15-18 Uhr)
* [[Rechnerraum|Rechnerräume]]
* studentische Cafés
** Vorteile:
*** Günstiger Kaffee
*** gemütliche Atmosphäre
*** nette Leute
*** Hilfe bei Problemen
** Beispiele:
*** TEL-Quel
*** [[Cafe_Shila|Shila]]
*** [[I-cafe|i-Café]]
*** Wiwi-Café [http://www.wiwicafe.de/]
* sonstige Cafés
** TEL-Cafeteria "Skyline"
** z.B. in Cafeteria am Eingang zum Mathegebäude ist das Arbeiten nicht erwünscht/gestattet
* Ini-Räume
* den eigenen Arbeitsplatz

=== Musik machen ===

* Collegium Musicum = FU + TU
** Großer Chor (Di 19-22 Uhr)
** Kammerchor (Do 19-22 Uhr)
** Sinfonieorchester (Mo 18:30-22 Uhr)
** Kleines Sinfonisches Orchester (Mi 18:30-22 Uhr)
** Uni Bigband Berlin (Di 19:30-22 Uhr)
** http://collegium-musicum-berlin.de/
** jedes Semester Konzerte

=== TU-Sport ===

* Informieren und Buchen über Website [http://www.tu-sport.de]
* Fitnessraum
** günstiger als normale Fitnessstudios
** es gibt Duschen
** Einführungstrainig unter Aufsicht nötig
* Sportkurse
** sehr breit gefächertes Angebot
*** von Aerobic
*** inkl. Qi Gong und Segeln
*** bis Yoga
** relativ günstig (16 Euro Badminton - 125 Euro Segeln)

=== Sprachkurse ===

* Sprach- und Kulturbörse (SKB) [http://www.skb.tu-berlin.de]
** Kurse meistens 1/Woche abends oder Intensivkurse während Semesterferien
** breites Angebot
*** Englisch, Französisch, Spanisch...
*** aber auch exotischere wie Arabisch, Mongolisch, Thailändisch, Hebräisch
** DAAD Sprachzeugnisse (zB falls Auslandssemester geplant)
** ACHTUNG: Werden nicht als Wahlpflichtkurse/Studium Generale anerkannt, da keine ECTS-Punkte
** nicht kostenlos, aber günstig: 51€/20h bis 149€/80h

* Zentraleinrichtung Moderne Sprachen (ZEMS) [http://www.zems.tu-berlin.de]
** nichtexotische Sprachen wie Deutsch, Englisch, Französisch, Spanisch
** spezialisiert auf Fachsprachen
** 24€ oder 48€/Semester
** "echte" LV/Module mit Prüfungen -> können als Studium Generale anerkannt werden, sofern nicht Zugangsvoraussetzung für den Studiengang (Keine Garantie!)
** Englisch ist Voraussetzung für Master
** Sonderkurs für Fak IV, kostenlos

=== Auslandsaufenthalt ===

* Erasmus
* DAAD
* TUB Fak IV: Double Degree Abkommen
* Praktikum AIESEC [http://www.aiesec.de]

=== Arbeiten ===

* für Bachelor: besser später (ab 3./4. Semester)
* an der Uni
** generell: 10,98€/Stunde - gesetzlicher Stundensatz für Studenten
** 40h/Monat, 60h/Monat oder maximal 80h/Monat
** mit Lehraufgaben (Tutor)
*** Tutorien halten
*** erst ab 4. Semester Bachelor oder mit Vordiplom
** ohne Lehraufgaben
*** Admin, Programmierer, administrative Aufgaben, Bibliothek...
*** einfach so bewerben
* Wo finden:
** Ausschreibungen Fak IV hängen aus (z.B. neben Verwaltung im FR 5. Etage)
** Onlineliste der Fakultät [http://cs.tu-berlin.de/Jobs/]
** Jobs-Mailingliste: <email>jobs@lists.freitagsrunde.org</email> [http://lists.freitagsrunde.org/mailman/listinfo/jobs]
** Seiten der TU zu Jobs und Karriere [http://www.tu-berlin.de/menue/service/job_karriere/]
* JunITer [http://www.juniter.de]
** studentische IT-Beratung
** Teil des Company Consulting Team (CCT)
** Verein für Studenten aller Fachrichtungen
** gemeinnützig, vermittelt IT-Projekte an Teams
** diese Teams arbeiten dann als GbR für Kunden
** Kernkompetenzen: Web- und Datenbankanwendungen
** Beispiel: meinprof.de
** Vernetzung der Mitglieder durch "Workends" und "Outside-Office-Events"
** betreiben außerdem eigene Infrastruktur
** Interesse? [http://www.juniter.de Bewerben!]
* in der freien Wirtschaft
** verlockend, da oft mehr Geld
** Praxiserfahrung für den Lebenslauf
** Vorsicht: viel Arbeit - Schaff ich das?

=== Studentische Aktivitäten ===

* AG Rechnersicherheit [http://www.agrs.tu-berlin.de/]
** hacken und gehackt werden
** Wettbewerbe (CTFs)
** jeden Dienstag 18 Uhr im EN 360
* DK0TU [http://dk0tu.de]
** Amateurfunkgruppe der TU-Berlin seit 1972
** Antennenabbau [...] ~2007 [...] mehrere Rückschläge seitdem
** Shack unter dem Dach des Hauptgebäudes
** Antennenbaumöglichkeiten auf dem Dach
** alle Afu-Bänder 160m bis 10GHz
** Schwerpunkte u.a. Meteorscatter (2m), EME (70cm)
** vorhandene Amateurfunkprüfung nicht notwendig
** Kontakt: <email>shack@dk0tu.de</email>
* Lötlabor [http://www.loetlabor.org]
** Raum: EN 444/445
** eigene Projekte mitbringen oder an vorhandenen mitarbeiten
** Betreuung durch bezahlte Tutoren
* Freitagsrunde
** [[Einführungswoche|E-Woche]] mitgestalten
** [[TechTalks]]
*** Projekte vorstellen
*** Vortrag ca 30-60 Minuten, in Einzelfällen auch länger möglich
*** auch in Verbindung mit Workshop
*** Letzte Themen:
**** Linux-Kernelprogrammierung (Chrysh's Diplomarbeit)
**** BitCoin (Jeffrey Paul, der den gleichen Talk auf auf dem Chaos Communication Camp gehalten hat)
**** 3D-Animation von Grund auf (Jakob, Mitglied der Freitagsrunde und VJ)
**** Tor (Erynn, Mitarbeiterin im Tor-Project)
** Party, [[Kickerturnier]]
*** Ihr könnt euch eins organisieren
*** 3. Uniwoche
*** Orgatreffen!
** [[LAN|LAN-Party]]
** [[Lip|Linux-Install-Party]]
** [[Java Kurs|Java-Kurs]]
*** MPGI 2: Java vorausgesetzt
*** Java vor Beginn des 2. Semesters lernen
*** eine Woche lang Vorträge und Übungen
*** sehr gutes Betreuungsverhältnis
** vor Wintersemester: wieder [[Ckurs|C-Kurs]]

=== Unipolitik ===

* Motivation:
** Ändern, was einen stört
* Uniweit
** Studenten wählen [[Studierendenparlament]] (StuPa) - im Juni erst wieder
** StuPa wählt den [[Allgemeiner Studierendenausschuss|Allgemeinen Studierendenausschuss]] (AstA) [http://asta.tu-berlin.de]
** AstA hat Referate, zu jedem gehört ein Arbeitskreis, in dem man sich beteiligen kann
*** Bildungspolitik
*** Sozialreferat
*** Umweltreferat
*** Ini-Koordination
*** Ausländer_innenreferat...
** Außerdem Service- und Beratungsangebot
*** Bafög/Soziales
*** Semesterticketbüro
*** Probleme mit Prüfungsamt
** EB 104 [http://eb104.tu-berlin.de/]
* Fakultätsweit
** Freitagsrunde
** Studenten wählen [[Fakultätsrat]] (FKR)
*** gewählte studentische Vertreter, derzeit
*** paritätisch besetzt, d.h. Studenten haben 2 Stimmen, außerdem noch Professoren, Wimis...
*** 2 Stimmen für 4 Studiengänge - das geht nur gemeinsam
** FKR benennt [[Ausbildungskommission]] (AK)
*** d.h. wir können einfach Leute mitnehmen
*** AK ändert z.B. Prüfungsordnung
** FKR benennt Prüfungsausschuss (PA)
** PA entscheidet z.B. Anerkennungsfragen

Siehe auch: [[Einführungswoche]]

== alte Folien ==

* [http://docs.freitagsrunde.org/E-Woche/2011/sonstso2011.pdf Folien aus WS 2011/12 als PDF] (13 MB)
* [http://docs.freitagsrunde.org/E-Woche/2008/Studieren_und_mehr_WS2008.pdf Folien aus WS2008 als PDF]
* [https://docs.freitagsrunde.org/E-Woche/2010/StudierenUndMehr/sonstso2010.pdf Folien zum 2010'er Vortrag "Studieren und mehr: Was man sonst noch so in der Uni machen kann"] (achtung, groß, 15MB)

= Hinweise zur Aufnahme von Inhalten =

'''Bedingung:''' Ihr seid eine Berliner Hochschulgruppe oder steht in klarem Bezug zur TU Berlin.

Schickt uns bis '''eine Woche vor Beginn''' der [http://www.eecs.tu-berlin.de/menue/studium_und_lehre/start_ins_studium/semesterbeginn/ewoche/ Einführungswoche der Fak IV] '''Stichpunkte''' und '''Bilder''' für '''1-3 Folien''' mit '''1-3min Vorstellungszeit.''' Wir pflegen eine gemeinsame Präsentation, damit man nicht mit USB-Sticks und/oder Foliensätzen rotieren muss. Außerdem sind wir flexibler, ob Leute auftauchen oder auch nicht und können das auch selbst vorstellen. Zu dem Zeitansatz - bevor Fragen kommen: Zu mehr sind die Studis eh nicht aufnahmefähig - der Vortrag soll einen Überblick bieten und einen Anreiz sich weiterzuinformieren, wenn einen etwas interessiert.

Meldet euch bitte direkt bei den Verantwortlichen um den Informationsfluss zu verbessern:

<code>
Magdalena Rätz <maggyrz ät freitagsrunde.org>
Sebastian Lange <bastla ät freitagsrunde.org>
</code>

[[Kategorie:Studium]]

DK0TU

2013-12-05T14:00:21Z

Bastla: + DK0TU

#REDIRECT [[AFUTUB]]

AFUTUB

2013-12-05T13:59:52Z

Bastla: + AFUTUB

'''AFUTUB''' steht für die ''Amateurfunkgruppe der TU Berlin'' und ist eine registrierte Vereinigung dieser. Die Funkstation unter dem Dach des Hauptgebäudes arbeitet unter dem Rufzeichen ''DK0TU'' und bietet für Studierende, Mitarbeiterinnen und Mitarbeiter Berliner und Brandenburger Hochschulen u.a. kostenlose Kurse zur Erlangung der Amateurfunk-Lizenz.

Weitere Informationen unter http://www.dk0tu.de

Diskussion:Ewoche/seidaktiv

2012-10-29T13:29:05Z

Bastla: /* Guten Tag */

Wenn ihr im Uninetz seid oder mit eurem Account am Wiki angemeldet seid, seht ihr unter der Navigationszeile oben ein paar Links. Bitte drückt jetzt dort auf das Plus, damit ihr einen neuen Kommentar hinterlasst. Damit wir wissen, wer diesen Kommentar geschrieben hat, schreibt bitte den Text eures Kommentars gleich auch auf eure Abgabe. Wenn dort kein unterstrichenes + zu sehen ist, seid ihr nicht angemeldet oder nicht im Uninetz.

== Ewoche Unirallye ==

Pudding

== Unirallye like a pro ==

Wie prangern an, dass die Tastaturen in Unixpool so komisch funktionieren und das die Aufgabe 11 total strange ist!

== Rallye. ==

strich. punkt. komma.

== Guten Tag ==

Wo ist die Kletterausrüstung versteckt, um aufs Dach des Hauptgebäudes zu kommen?

: Die war nicht notwendig. Es ging um darum was an der Tür zum Aufgang steht. ;-) --[[Benutzer:Bastla|bastla]] 14:29, 29. Okt. 2012 (CET)

== Campus-Rallye ==

Weil wir so schön sind, so schlau sind, so schlank und rank.
Gewinnen wir die Campus-Rallye! =)

== Freitagsrunde ==

Liebe Gruesse Freitagsrunde,
Tilo, Ruben und Dennis.

== Unirallye ==

Hallö
schöne grüße von Flori, Kamil, Dorothea

== Unixpool unter wasser! ==

Wir wissen jetzt, wieviel Wasser in den Unixpool reinpasst.
Aber nicht, wie wir es wieder rauskriegen!! sry

== Finde ich richtig gut ==

Ich finde die Idee der Unirallye wirklich gut.

Gruß an die Frunde.

== Unirallye ==

Die Rechner im PC-Pool sind lahm! :P

Grüße Robin,Hannes,Colin

== Runter vom Dach!!! ==

Alles Gute von Jordi, Christian und Stefan!!!

== Uni-Rally vorbei - Sieger festgelegt! [nicht offiziell] ==

1. Platz : Max Oehme, Thomas Havekost, Marian Stenzel

neuer Kommentar

== Betreff ==

gez. Julian, Patrick Vincent

== hier ist ein text ==

kann sein das wir auf unserem blatt nichts hingeschrieben haben

== Aktivität ==

Wir waren aktiv: Sören, Kaufi, Jeli.

Diskussion:Analysis II für Ingenieurwissenschaften

2012-10-02T14:02:52Z

Bastla: Linkliste kürzen

Der Übersicht halber würde ich die Links zu den Klausurensammlungen im Wesentlichen auf das Apache dir reduzieren. Ich denke keiner will per Hand dauerhaft das Wiki mit der Sammlung syncen. Wenn kein Widerspruch kommt, dann werd ich das mal tun. --[[Benutzer:Bastla|bastla]] 16:02, 2. Okt. 2012 (CEST)

Ana1

2012-10-02T13:12:39Z

Bastla: ana1 redirect

#REDIRECT [[Analysis I für Ingenieure]]

Ana2

2012-10-02T13:11:54Z

Bastla: ana2 redirect

#REDIRECT [[Analysis II für Ingenieure]]

ITPDG für Ingenieure

2012-07-14T14:53:47Z

Bastla: Spiegel-Artikel Link

{{Vorlage:KlausurBox|titel=|klausurliste=


[http://docs.freitagsrunde.org/klausuren/ITPDG_fuer_Ingenieure/?N=D Klausuren 2002-2010]

}}

'''Integraltransformationen und partielle Differentialgleichungen für Ingenieure''' ist eine Service-Veranstaltung der Fakultät II (Mathematik und Naturwissenschaften). Sie ist Pflichtfach im dritten Semester des [[Lehrveranstaltungen Technische Informatik|Studiengangs Technische Informatik]] und besteht aus 2 SWS [[Vorlesung]] und 2 SWS [[Übung]] und entspricht 6 [[ECTS]]-Leistungspunkten.

==Inhalt==
* Überblick gewöhnliche Differentialgleichungen
* Fourier-/Laplacetransformation
* Partielle Differentialgleichungen, Bessel- und Legendregleichung

== Tipps und nützliche Infos ==

* Die Veranstaltung wird sowohl im Sommer- wie im Wintersemester angeboten.
* Es gibt jeweils zwei Klausuren im Semester (Februar/April und Juli/Oktober).
* Dozent: versch. der Fakultät II
* Voraussetzung: [[Lineare Algebra für Ingenieure]] / [[Analysis I für Ingenieure]]
* Skript: PDF-Skript in versch. Formaten zum Ausdrucken
* Prüfung: 2x60min Klausur (Rechen- und Verständnisteil)
* Homepage: http://www.moses.tu-berlin.de/Mathematik/

== Persönliche Kommentare ==

Die Veranstaltung sollte man in Hinsicht auf [[Signale und Systeme]] besuchen, da hier die nötigen mathematischen Grundlagen sehr ausführlich behandelt werden.
Meist ähnelt die Klausur sehr wenig den Altklausuren, die zweite Klausur jedoch stark der ersten. Die Altklausuren sind als Übung aber definitiv zu empfehlen!

Der Physiker und Informatiker ''[http://www.spiegel.de/unispiegel/studium/mathe-professor-loviscach-vorlesung-bei-youtube-a-843076.html Jörn Loviscach]'' bietet in seinem [https://www.youtube.com/user/JoernLoviscach YouTube-Channel] sehr gute Mitschnitte seiner Vorlesungen unter CC-Lizenz an. Viele Themen aus ITPDG findet ihr folglich gut erklärt, wenn ihr dort ein wenig stöbert. Ansonsten ist [http://www.wolframalpha.com/ Wolfram Alpha] natürlich auch hier ein gutes Tool, um seine Lösungen zu überprüfen. --[[Benutzer:bastla|bastla]]

[[Kategorie:Lehrveranstaltungen]]
__NOTOC__

Signale und Systeme (Bachelor)

2012-07-13T08:51:33Z

Bastla:

{{Vorlage:KlausurBox|titel=|klausurliste=

[http://www.isis.tu-berlin.de (aktueller ISIS Kurs) 1998-today] 
[http://docs.freitagsrunde.org/Klausuren/Signale%20und%20Systeme/ docs.freitagsrunde Klausuren-Mirror]
}}

''Hinweis: Eine Übersicht zum ehemaligen Diplom-Modul befindet sich im Wiki-Artikel [[Signale und Systeme (StuPO90)]].''

----

''Signale und Systeme'' ist eine Veranstaltung aus dem Fachbereich von Prof. Sikora [[http://www.nue.tu-berlin.de/ FG Nachrichtenübertragung]]. Die Lehrveranstaltung legt die theoretischen Grundlagen für die Nachrichtenübertragung, allderings auch für Regelungstechnik. Hier wird ''die Information'' oder ''das Signal'' im Zeitbereich, Frequenzbereich, bezüglich des Signaltyps betrachtet, es wird durch ''Systeme'' geleitet und man beschäftigt sich mit den verschiedenen Möglichkeiten aus einem Signal mit Hilfe eines Systems ein anderes zu machen.

[[Kategorie:Lehrveranstaltungen]]
[[Kategorie:Fakultäts-ABC]]

''Signale und Systeme'' ist Pflichtveranstaltung für [[Lehrveranstaltungen Elektrotechnik Bachelor/Master | Grundstudium]] im vierten Semester. Die Veranstaltung besteht aus 2 SWS [[Vorlesung]], 2 SWS [[Übung]] und entspricht 6 [[ECTS]]-Leistungspunkten. Es werden seit Sommersemester 2010 freiwillige Hausaufgaben angeboten, die wöchentlich von jedem Studenten auf der ISIS Plattform bearbeitet werden können. Wer am Ende des Semesters eine gewisse Prozentzahl an Hausaufgaben richtig gelöst hat, erhält bis zu 3 Bonuspunkte für die Klausur.

== Inhalt ==
* kontinuierliche Signale im Zeitbereich
* wert- und zeitdiskrete Signale
* Laplace- und Fourier-Transformation
* diskrete und zeitdiskrete Fourier-Transformation
* Abtastung
* Z-Transformation

== Tipps und nützliche Infos ==

* Die Veranstaltung wird im Sommersemester angeboten.
* Es gibt jeweils zwei Klausuren im Semester (Juli und Oktober).
* Dozent: Prof. Sikora
* Voraussetzung: Grundlagen der Mathematik, insbesondere ITPDG
* Skript: in gedruckter gebundener Form im Raum 340 zu kaufen
* Es gibt eine online-Plattform auf der ISIS-Seite, die die Lehre von SUS unterstützen soll.
* Prüfung: 90min, mit einem '''einseitig''' handbeschriebenen A4-Blatt als Hilfsmittel ''(es wird Kontrolliert!)''
* Homepage: [http://www.nue.tu-berlin.de/menue/studium_und_lehre/sommersemester/signale_und_systeme/ SuS Website des Fachgebietes],[[ISIS|ISIS]]

== Literatur ==

== Persönliche Kommentare ==
Die Vorlesung ist sehr stark mathematikorientiert, praktische Beilspiele werden eher selten verwendet. Allerdings ist Prof. Sikora ein wirklich guter Dozent, der auch trockenen Stoff anschaulich vermitteln kann. Bei der Wahl der Übungsgruppe sollte man aufpassen, da nicht alle WiMis eine gute Übung machen!
Mit dem A4-Blatt ist man für die Klausur gut gerüstet. Es ist sehr empfehlenswert die alten Klausuren alle durchzurechnen.

[[Kategorie: Lehrveranstaltungen]]
__NOTOC__

Signale und Systeme (StuPO90)

2012-07-13T08:45:15Z

Bastla: Links sind Case Sensitive...

{{Vorlage:KlausurBox|titel=|klausurliste=


SS 2005
* [http://docs.freitagsrunde.org/LV-Material/Signale_und_Systeme/sign+sys-Mitschriften-Ue_SoSe05.rar (''handschriftl., ~10MB'')]

}}

''Hinweis: Das Modul ist veraltet. Die Neuerung befindet sich unter [[Signale und Systeme (Bachelor)]].''

----

==Wissenswertes==
* Lehrform: 2 SWS VL / 2 SWS UE
* Bemerkungen: nur im SS
* Dozent: Prof. Sikora
* Voraussetzung: Integraltransformationen und partielle Differentialgleichungen
* Skript: "Signale und Systeme" von Prof. Noll, erhältlich in der ersten Veranstaltung
* Anrechnung: Pflichveranstaltung für TI
* Prüfung: 120min Klausur für TI
* Homepage: http://www.nue.tu-berlin.de/lehre/sns/

==Inhalt==
* Fourier/Laplace/Z-Transformation und ihre Eigenschaften
* Lineare Systeme im Zeit/Frequenzbereich
* Abtastung/Diskretisierung von Signalen
* Basiswissen Digitaler Signalverarbeitung
* Filterentwurf

==Eindrücke==
Die Vorlesung wird leider nicht mehr von Prof. Noll gehalten, sondern von Prof. Sikora fortgeführt. Ich habe noch bei Prof. Noll gehört und war jedes Mal aufs neue von seiner Kompetenz und den didaktischen Fähigkeit beeindruckt, was in Kombination nicht so häufig anzutreffen ist. Trotz multimedialer Möglichkeiten war seine Präsentation der Inhalte mit Tafel und OH-Projektor klar und eindeutig. Die Veranstaltung ist sehr gut strukturiert und orientiert sich ausschliesslich am Skript. Dieses ist meiner Meinung nach sehr gut und völlig ausreichend um die Veranstaltung zu meistern. Es sind Übungsaufgaben inklusive Lösungen enthalten. Fehler oder Änderungen im Skript sind auf der Web-Seite des Fachbereiches dokumentiert. Die Grossübung reduziert sich auf Vorrechnen der im Skript markierten Aufgaben. Die Lösungswege wurden vom Tutor als pdf zur Verfügung gestellt.

[[Kategorie:Lehrveranstaltungen]]

Signale und Systeme (Bachelor)

2012-07-13T08:43:50Z

Bastla:

{{Vorlage:KlausurBox|titel=|klausurliste=

[http://www.isis.tu-berlin.de (aktueller ISIS Kurs) 1998-today] 
[http://docs.freitagsrunde.org/Klausuren/Signale%20und%20Systeme/ docs.freitagsrunde Klausuren-Mirror]
}}

''Hinweis: Eine Übersicht zum ehemaligen Diplom-Modul [[Signale und Systeme (StuPO90)]] befindet sich in einem anderen Wiki-Artikel.''

----

''Signale und Systeme'' ist eine Veranstaltung aus dem Fachbereich von Prof. Sikora [[http://www.nue.tu-berlin.de/ FG Nachrichtenübertragung]]. Die Lehrveranstaltung legt die theoretischen Grundlagen für die Nachrichtenübertragung, allderings auch für Regelungstechnik. Hier wird ''die Information'' oder ''das Signal'' im Zeitbereich, Frequenzbereich, bezüglich des Signaltyps betrachtet, es wird durch ''Systeme'' geleitet und man beschäftigt sich mit den verschiedenen Möglichkeiten aus einem Signal mit Hilfe eines Systems ein anderes zu machen.

[[Kategorie:Lehrveranstaltungen]]
[[Kategorie:Fakultäts-ABC]]

''Signale und Systeme'' ist Pflichtveranstaltung für [[Lehrveranstaltungen Elektrotechnik Bachelor/Master | Grundstudium]] im vierten Semester. Die Veranstaltung besteht aus 2 SWS [[Vorlesung]], 2 SWS [[Übung]] und entspricht 6 [[ECTS]]-Leistungspunkten. Es werden seit Sommersemester 2010 freiwillige Hausaufgaben angeboten, die wöchentlich von jedem Studenten auf der ISIS Plattform bearbeitet werden können. Wer am Ende des Semesters eine gewisse Prozentzahl an Hausaufgaben richtig gelöst hat, erhält bis zu 3 Bonuspunkte für die Klausur.

== Inhalt ==
* kontinuierliche Signale im Zeitbereich
* wert- und zeitdiskrete Signale
* Laplace- und Fourier-Transformation
* diskrete und zeitdiskrete Fourier-Transformation
* Abtastung
* Z-Transformation

== Tipps und nützliche Infos ==

* Die Veranstaltung wird im Sommersemester angeboten.
* Es gibt jeweils zwei Klausuren im Semester (Juli und Oktober).
* Dozent: Prof. Sikora
* Voraussetzung: Grundlagen der Mathematik, insbesondere ITPDG
* Skript: in gedruckter gebundener Form im Raum 340 zu kaufen
* Es gibt eine online-Plattform auf der ISIS-Seite, die die Lehre von SUS unterstützen soll.
* Prüfung: 90min, mit einem '''einseitig''' handbeschriebenen A4-Blatt als Hilfsmittel ''(es wird Kontrolliert!)''
* Homepage: [http://www.nue.tu-berlin.de/menue/studium_und_lehre/sommersemester/signale_und_systeme/ SuS Website des Fachgebietes],[[ISIS|ISIS]]

== Literatur ==

== Persönliche Kommentare ==
Die Vorlesung ist sehr stark mathematikorientiert, praktische Beilspiele werden eher selten verwendet. Allerdings ist Prof. Sikora ein wirklich guter Dozent, der auch trockenen Stoff anschaulich vermitteln kann. Bei der Wahl der Übungsgruppe sollte man aufpassen, da nicht alle WiMis eine gute Übung machen!
Mit dem A4-Blatt ist man für die Klausur gut gerüstet. Es ist sehr empfehlenswert die alten Klausuren alle durchzurechnen.

[[Kategorie: Lehrveranstaltungen]]
__NOTOC__

Signale und Systeme

2012-07-13T08:40:50Z

Bastla: Redirect zu aktuellem Bachelor-Modul

#REDIRECT [[Signale und Systeme (Bachelor)]]

Signale und Systeme (StuPO90)

2012-07-13T08:39:53Z

Bastla: Hinweis auf neues Bachelor Modul

{{Vorlage:KlausurBox|titel=|klausurliste=


SS 2005
* [http://docs.freitagsrunde.org/lv-material/Singale_und_Systeme/sign%2bsys-Mitschriften-Ue_SoSe05.rar Mitschriften der Übung (''handschriftl., ~10MB'')]

}}

''Hinweis: Das Modul ist veraltet. Die Neuerung befindet sich unter [[Signale und Systeme (Bachelor)]].''

----

==Wissenswertes==
* Lehrform: 2 SWS VL / 2 SWS UE
* Bemerkungen: nur im SS
* Dozent: Prof. Sikora
* Voraussetzung: Integraltransformationen und partielle Differentialgleichungen
* Skript: "Signale und Systeme" von Prof. Noll, erhältlich in der ersten Veranstaltung
* Anrechnung: Pflichveranstaltung für TI
* Prüfung: 120min Klausur für TI
* Homepage: http://www.nue.tu-berlin.de/lehre/sns/

==Inhalt==
* Fourier/Laplace/Z-Transformation und ihre Eigenschaften
* Lineare Systeme im Zeit/Frequenzbereich
* Abtastung/Diskretisierung von Signalen
* Basiswissen Digitaler Signalverarbeitung
* Filterentwurf

==Eindrücke==
Die Vorlesung wird leider nicht mehr von Prof. Noll gehalten, sondern von Prof. Sikora fortgeführt. Ich habe noch bei Prof. Noll gehört und war jedes Mal aufs neue von seiner Kompetenz und den didaktischen Fähigkeit beeindruckt, was in Kombination nicht so häufig anzutreffen ist. Trotz multimedialer Möglichkeiten war seine Präsentation der Inhalte mit Tafel und OH-Projektor klar und eindeutig. Die Veranstaltung ist sehr gut strukturiert und orientiert sich ausschliesslich am Skript. Dieses ist meiner Meinung nach sehr gut und völlig ausreichend um die Veranstaltung zu meistern. Es sind Übungsaufgaben inklusive Lösungen enthalten. Fehler oder Änderungen im Skript sind auf der Web-Seite des Fachbereiches dokumentiert. Die Grossübung reduziert sich auf Vorrechnen der im Skript markierten Aufgaben. Die Lösungswege wurden vom Tutor als pdf zur Verfügung gestellt.

[[Kategorie:Lehrveranstaltungen]]

Signale und Systeme (Bachelor)

2012-07-13T08:38:07Z

Bastla: Hinweis auf alte StuPO

{{Vorlage:KlausurBox|titel=|klausurliste=

[http://www.isis.tu-berlin.de (aktueller ISIS Kurs) 1998-today] 
[http://docs.freitagsrunde.org/Klausuren/Signale%20und%20Systeme/ docs.freitagsrunde Klausuren-Mirror]
}}

''Hinweis: Das alte Modul [[Signale und Systeme (StuPO90)]] befindet sich in einem anderen Wiki-Artikel.''

----

''Signale und Systeme'' ist eine Veranstaltung aus dem Fachbereich von Prof. Sikora [[http://www.nue.tu-berlin.de/ FG Nachrichtenübertragung]]. Die Lehrveranstaltung legt die theoretischen Grundlagen für die Nachrichtenübertragung, allderings auch für Regelungstechnik. Hier wird ''die Information'' oder ''das Signal'' im Zeitbereich, Frequenzbereich, bezüglich des Signaltyps betrachtet, es wird durch ''Systeme'' geleitet und man beschäftigt sich mit den verschiedenen Möglichkeiten aus einem Signal mit Hilfe eines Systems ein anderes zu machen.

[[Kategorie:Lehrveranstaltungen]]
[[Kategorie:Fakultäts-ABC]]

''Signale und Systeme'' ist Pflichtveranstaltung für [[Lehrveranstaltungen Elektrotechnik Bachelor/Master | Grundstudium]] im vierten Semester. Die Veranstaltung besteht aus 2 SWS [[Vorlesung]], 2 SWS [[Übung]] und entspricht 6 [[ECTS]]-Leistungspunkten. Es werden seit Sommersemester 2010 freiwillige Hausaufgaben angeboten, die wöchentlich von jedem Studenten auf der ISIS Plattform bearbeitet werden können. Wer am Ende des Semesters eine gewisse Prozentzahl an Hausaufgaben richtig gelöst hat, erhält bis zu 3 Bonuspunkte für die Klausur.

== Inhalt ==
* kontinuierliche Signale im Zeitbereich
* wert- und zeitdiskrete Signale
* Laplace- und Fourier-Transformation
* diskrete und zeitdiskrete Fourier-Transformation
* Abtastung
* Z-Transformation

== Tipps und nützliche Infos ==

* Die Veranstaltung wird im Sommersemester angeboten.
* Es gibt jeweils zwei Klausuren im Semester (Juli und Oktober).
* Dozent: Prof. Sikora
* Voraussetzung: Grundlagen der Mathematik, insbesondere ITPDG
* Skript: in gedruckter gebundener Form im Raum 340 zu kaufen
* Es gibt eine online-Plattform auf der ISIS-Seite, die die Lehre von SUS unterstützen soll.
* Prüfung: 90min, mit einem '''einseitig''' handbeschriebenen A4-Blatt als Hilfsmittel ''(es wird Kontrolliert!)''
* Homepage: [http://www.nue.tu-berlin.de/menue/studium_und_lehre/sommersemester/signale_und_systeme/ SuS Website des Fachgebietes],[[ISIS|ISIS]]

== Literatur ==

== Persönliche Kommentare ==
Die Vorlesung ist sehr stark mathematikorientiert, praktische Beilspiele werden eher selten verwendet. Allerdings ist Prof. Sikora ein wirklich guter Dozent, der auch trockenen Stoff anschaulich vermitteln kann. Bei der Wahl der Übungsgruppe sollte man aufpassen, da nicht alle WiMis eine gute Übung machen!
Mit dem A4-Blatt ist man für die Klausur gut gerüstet. Es ist sehr empfehlenswert die alten Klausuren alle durchzurechnen.

[[Kategorie: Lehrveranstaltungen]]
__NOTOC__

Checkliste zur ersten Uniwoche

2012-06-22T11:12:09Z

Bastla: 0TU link

'''Was sollte ich in der ersten Woche an der TU-Berlin machen?'''

Die erste Woche:
# Gehe zum [http://lsf2.tubit.tu-berlin.de/ Vorlesungsverzeichnis] und suche dir die Zeiten zu deinen Kursen.
# Gehe auf [https://www.moseskonto.tu-berlin.de/moseskonto/ Moses], melde dich zu deinen Kursen an.
# Mentor aussuchen auf [https://www.moseskonto.tu-berlin.de/moseskonto/ Moses]
# [http://www.pruefungen.tu-berlin.de/menue/qisposonlineanmeldungen/e-tub/zulassungsantrag/ Mantelbogen] beim Prüfungsamt erstellen lassen (in [https://www.tu-berlin.de/login_pw qispos] Forumlar ausfüllen, ausdrucken und zum Prüfungsamt bringen.)
# Gehe auf [https://www.isis.tu-berlin.de/login/index.php Isis] und melde dich zu deinen Kursen an
# Melde dich für ''eecs-Studium'' auf Isis an.
# Nimm an einer [http://www.ub.tu-berlin.de/index.php?id=135 Einführung in die Bibliothek] teil
# Mache dich nochmal mit deiner Studien- und Prüfungsordnung vertraut! Sie stehen in deinem [http://www.eecs.tu-berlin.de/fileadmin/f4/fkIVdokumente/StF/StuF-TI-BSc.pdf Studienführer]. Zu finden auf [http://www.eecs.tu-berlin.de/menue/studium_und_lehre/ Studium und Lehre], wenn du dich in deinen Studiengang einklickst und auf die rechte Seite achtest!
# Mache dich mit den Modulbeschreibungen vertraut. Diese sind durch Klicken im [http://www.eecs.tu-berlin.de/menue/studium_und_lehre/studiengaenge/technische_informatik/bachelor/bachelor_-_studienverlaufsplan/ Studienverlaufsplan] einsehbar oder im [http://www.eecs.tu-berlin.de/fileadmin/f4/fkIVdokumente/Module/bachelor/TI/BSc-TI.pdf Modulhandbuch]
# im TEL in den obersten Stock fahren, 'nen Kaffe trinken und die Aussicht über den Campus genießen
# Namen/Emailadresse mit sympathischen Komilitonen und Komilitoninnen aus den Kleingruppen austauschen
# zur [[Freitagsrunde]] gehen

Das erste Semester:
# Unisportkurse aussuchen http://www.tu-sport.de/
# sich über [http://www.skb.tu-berlin.de/ Sprachkurse] informieren
# sich Gedanken über [[Auslandssemester]] machen
# sich für die Uni engagieren: Freitagsrunde, studentische Cafés, Lötlabor, [http://www.dk0tu.de DK0TU], Unirad, FasTUB, Grillen organisieren, ...

Im dritten Semester:
# für [[Auslandssemester]] bewerben
# sich über Fachstudium Gedanken machen

to be continued

== Vorschläge ==

# print@campus einrichten
# mailbox.tu-berlin.de einrichten

[[Kategorie:Studium]]

Benutzer:Bastla

2012-05-30T22:28:59Z

Bastla:

[[Bild:Bastla.freifunk.jpg|thumb|200px|bastla über den Dächern der Landeshauptstadt Potsdam 2008, Foto: [http://potsdam.freifunk.net Freifunk-Potsdam P)))]]]

* Realname: Sebastian Lange
* Studi der ''Technischen Informatik'' an der TU-Berlin
* mail: bastla -at- bastla -dot- net
** Wenn möglich, bitte GPG-Verschlüsselt (als PGP/MIME, nicht inline):
:: Public Key ID: 4F980AB6 2007-12-12
:: Key fingerprint = A986 44DF 1A1A 32FC 6F9C 84C4 3AE9 3DF2 4F98 0AB6
* IRC: user bastla @ irc://irc.freenode.net/freitagsrunde
** Hobby: Poweridlen
:: Lösung: Highlight auf "bastla", Beispiel: "< foo> bastla: [...]"

'''Ansonsten'''

* http://www.bastla.net
* Amateurfunk
** an der TU-Berlin http://www.dk0tu.de
** Notfunk http://www.darc.de/referate/notfunk/
* Freifunk Potsdam http://www.freifunk-potsdam.de
* THW http://www.ov-potsdam.thw.de
** Weitverkehrstrupp (WVTr) http://wvtr.thw-potsdam.de
* Linux User Group Potsdam (upLUG) http://www.uplug.de
* Brandenburger Linux-Info-Tag http://www.blit.org

'''Aktuelles'''

* <s>[[Benutzer:Bastla/Geb2009]]</s>

ITPDG

2012-04-02T13:46:32Z

Bastla: ITPDG Redirect

#REDIRECT [[ITPDG für Ingenieure]]

ITPDG für Ingenieure

2012-04-02T13:43:29Z

Bastla: Link renamed

{{Vorlage:KlausurBox|titel=|klausurliste=


[http://docs.freitagsrunde.org/klausuren/ITPDG_fuer_Ingenieure/?N=D Klausuren 2002-2010]

}}

'''Integraltransformationen und partielle Differentialgleichungen für Ingenieure''' ist eine Service-Veranstaltung der Fakultät II (Mathematik und Naturwissenschaften). Sie ist Pflichtfach im dritten Semester des [[Lehrveranstaltungen Technische Informatik|Studiengangs Technische Informatik]] und besteht aus 2 SWS [[Vorlesung]] und 2 SWS [[Übung]] und entspricht 6 [[ECTS]]-Leistungspunkten.

==Inhalt==
* Überblick gewöhnliche Differentialgleichungen
* Fourier-/Laplacetransformation
* Partielle Differentialgleichungen, Bessel- und Legendregleichung

== Tipps und nützliche Infos ==

* Die Veranstaltung wird sowohl im Sommer- wie im Wintersemester angeboten.
* Es gibt jeweils zwei Klausuren im Semester (Februar/April und Juli/Oktober).
* Dozent: versch. der Fakultät II
* Voraussetzung: [[Lineare Algebra für Ingenieure]] / [[Analysis I für Ingenieure]]
* Skript: PDF-Skript in versch. Formaten zum Ausdrucken
* Prüfung: 2x60min Klausur (Rechen- und Verständnisteil)
* Homepage: http://www.moses.tu-berlin.de/Mathematik/

== Persönliche Kommentare ==

Die Veranstaltung sollte man in Hinsicht auf [[Signale und Systeme]] besuchen, da hier die nötigen mathematischen Grundlagen sehr ausführlich behandelt werden.
Meist ähnelt die Klausur sehr wenig den Altklausuren, die zweite Klausur jedoch stark der ersten. Die Altklausuren sind als Übung aber definitiv zu empfehlen!

Der Physiker und Informatiker ''Jörn Loviscach'' bietet in seinem [https://www.youtube.com/user/JoernLoviscach YouTube-Channel] sehr gute Mitschnitte seiner Vorlesungen unter CC-Lizenz an. Viele Themen aus ITPDG findet ihr folglich gut erklärt, wenn ihr dort ein wenig stöbert. Ansonsten ist [http://www.wolframalpha.com/ Wolfram Alpha] natürlich auch hier ein gutes Tool, um seine Lösungen zu überprüfen. --[[Benutzer:bastla|bastla]]

[[Kategorie:Lehrveranstaltungen]]
__NOTOC__

Diskussion:ITPDG für Ingenieure

2012-02-18T22:51:42Z

Bastla: old Request done

Die Veranstaltung heißt nicht (mehr) ITPDGL sondern nur noch ITPDG. Außerdem wurde die Z-Transformation mittlerweile zu Analysis III für Ingenieure verlegt. Vielleicht kann das mal einer ändern :)

: Ist jetzt endgültig erledigt. --[[Benutzer:Bastla|bastla]] 23:51, 18. Feb. 2012 (CET)

ITPDG für Ingenieure

2012-02-18T21:41:47Z

Bastla: /* Persönliche Kommentare */

{{Vorlage:KlausurBox|titel=|klausurliste=


[http://docs.freitagsrunde.org/klausuren/ITPDGL_fuer_Ingenieure/?N=D Klausuren 2002-2010]

}}

'''Integraltransformationen und partielle Differentialgleichungen für Ingenieure''' ist eine Service-Veranstaltung der Fakultät II (Mathematik und Naturwissenschaften). Sie ist Pflichtfach im dritten Semester des [[Lehrveranstaltungen Technische Informatik|Studiengangs Technische Informatik]] und besteht aus 2 SWS [[Vorlesung]] und 2 SWS [[Übung]] und entspricht 6 [[ECTS]]-Leistungspunkten.

==Inhalt==
* Überblick gewöhnliche Differentialgleichungen
* Fourier-/Laplacetransformation
* Partielle Differentialgleichungen, Bessel- und Legendregleichung

== Tipps und nützliche Infos ==

* Die Veranstaltung wird sowohl im Sommer- wie im Wintersemester angeboten.
* Es gibt jeweils zwei Klausuren im Semester (Februar/April und Juli/Oktober).
* Dozent: versch. der Fakultät II
* Voraussetzung: [[Lineare Algebra für Ingenieure]] / [[Analysis I für Ingenieure]]
* Skript: PDF-Skript in versch. Formaten zum Ausdrucken
* Prüfung: 2x60min Klausur (Rechen- und Verständnisteil)
* Homepage: http://www.moses.tu-berlin.de/Mathematik/

== Persönliche Kommentare ==

Die Veranstaltung sollte man in Hinsicht auf [[Signale und Systeme]] besuchen, da hier die nötigen mathematischen Grundlagen sehr ausführlich behandelt werden.
Meist ähnelt die Klausur sehr wenig den Altklausuren, die zweite Klausur jedoch stark der ersten. Die Altklausuren sind als Übung aber definitiv zu empfehlen!

Der Physiker und Informatiker ''Jörn Loviscach'' bietet in seinem [https://www.youtube.com/user/JoernLoviscach YouTube-Channel] sehr gute Mitschnitte seiner Vorlesungen unter CC-Lizenz an. Viele Themen aus ITPDG findet ihr folglich gut erklärt, wenn ihr dort ein wenig stöbert. Ansonsten ist [http://www.wolframalpha.com/ Wolfram Alpha] natürlich auch hier ein gutes Tool, um seine Lösungen zu überprüfen. --[[Benutzer:bastla|bastla]]

[[Kategorie:Lehrveranstaltungen]]
__NOTOC__

Diskussion:ITPDG für Ingenieure

2012-02-18T21:26:18Z

Bastla: hat „Diskussion:ITPDGL für Ingenieure“ nach „Diskussion:ITPDG für Ingenieure“ verschoben: Veranstaltung wurde umbenannt

Die Veranstaltung heißt nicht (mehr) ITPDGL sondern nur noch ITPDG. Außerdem wurde die Z-Transformation mittlerweile zu Analysis III für Ingenieure verlegt. Vielleicht kann das mal einer ändern :)

edit: Anscheinend hat keiner so recht Lust dazu...LOS! BEWEGUNG!!!

Diskussion:ITPDGL für Ingenieure

2012-02-18T21:26:18Z

Bastla: hat „Diskussion:ITPDGL für Ingenieure“ nach „Diskussion:ITPDG für Ingenieure“ verschoben: Veranstaltung wurde umbenannt

#WEITERLEITUNG [[Diskussion:ITPDG für Ingenieure]]

ITPDGL für Ingenieure

2012-02-18T21:26:17Z

Bastla: hat „ITPDGL für Ingenieure“ nach „ITPDG für Ingenieure“ verschoben: Veranstaltung wurde umbenannt

#WEITERLEITUNG [[ITPDG für Ingenieure]]

ITPDG für Ingenieure

2012-02-18T21:26:16Z

Bastla: hat „ITPDGL für Ingenieure“ nach „ITPDG für Ingenieure“ verschoben: Veranstaltung wurde umbenannt

Java

2012-02-02T13:54:07Z

Bastla: Anleitung von Info1

[[WikiPedia:Java|Java]] ist eine [[WikiPedia:Objektorientierte Programmierung|objekt-orientierte]] Programmiersprache, die bei uns an der Fakultät vom 2. Semester an benutzt wird. Insbesondere die Vorlesungen [[Informatik 2]], [[Informatik 3]] und [[Informatik 4]] (bzw. [[MPGI_2_(Bachelor)]]) verwenden [[WikiPedia:Java|Java]] für praktische Beispiele und den Übungsbetrieb.

== Java installieren ==
Damit ihr in MPGI, Inftech oder auch woanders Java programmieren könnt, müsst ihr euch das Java-Development-Kit installieren. Wie ihr Java installiert, hängt von eurem aktuellen Betriebssystem ab.

=== Ubuntu 11.10 ===
Wenn ihr das von Sun entwickelte Java benutzen wollt, nutzt folgende Quellen:
<pre>
sudo add-apt-repository ppa:ferramroberto/java
sudo apt-get update
sudo apt-get install sun-java6-jdk
</pre>
Hinweis: Die installation aus Fremdquellen kann gefährlich sein.

=== alte Javainstallationsanleitung ===

Bis wir im Wiki unsere Anleitungen eingepflegt haben hier eine schöne Übersicht der Veranstaltung "Einführung in die Informatik 1": https://www.freitagsrunde.org/~andy/Java-Installationsanleitung.pdf

=== Wechsel zwischen den Java Versionen ===
Um zwischen den Javaversionen (OpenJDK und Sun Java) zu wechseln benutzt einfach folgenden Befehl:
<pre>
sudo update-alternatives --config java
</pre>

Checkliste zur ersten Uniwoche

2011-10-21T12:44:48Z

Bastla: ss -> ß ;)

Was sollte ich in der ersten Woche an der TU-Berlin machen?

Die erste Woche:
# Gehe zum [http://lsf2.tubit.tu-berlin.de/ Vorlesungsverzeichnis] und suche dir die Zeiten zu deinen Kursen.
# Gehe auf [https://www.moseskonto.tu-berlin.de/moseskonto/ Moses], melde dich zu deinen Kursen an.
# Mentor aussuchen auf [https://www.moseskonto.tu-berlin.de/moseskonto/ Moses]
# Gehe auf [https://www.isis.tu-berlin.de/login/index.php isis] und melde dich in deinen Kursen an
# Melde dich für eecs-Studium auf isis an.
# [http://www.pruefungen.tu-berlin.de/menue/qisposonlineanmeldungen/e-tub/zulassungsantrag/ Mantelbogen] beim Prüfungsamt erstellen lassen (in [https://www.tu-berlin.de/login_pw qispos] Forumlar ausfüllen, ausdrucken und zum Prüfungsamt bringen.)
# Nimm an einer [http://www.ub.tu-berlin.de/index.php?id=135 Einführung] in die Bibliothek teil
# Mache dich nochmal mit deiner Studien- und Prüfungsordnung vertraut! Sie stehen in deinem [http://www.eecs.tu-berlin.de/fileadmin/f4/fkIVdokumente/StF/StuF-TI-BSc.pdf Studienführer]. Zu finden auf [http://www.eecs.tu-berlin.de/menue/studium_und_lehre/ Studium und Lehre], wenn du dich in deinen Studiengang einklickst und auf die rechte Seite achtest!
# Mache dich mit den Modulbeschreibungen vertraut. Diese sind durch Klicken im [http://www.eecs.tu-berlin.de/menue/studium_und_lehre/studiengaenge/technische_informatik/bachelor/bachelor_-_studienverlaufsplan/ Studienverlaufsplan] einsehbar oder im [http://www.eecs.tu-berlin.de/fileadmin/f4/fkIVdokumente/Module/bachelor/TI/BSc-TI.pdf Modulhandbuch]
# im TEL in den obersten Stock fahren, nen Kaffe trinken und die Aussicht über den Campus 'genießen'
# zur Freitagsrunde gehen
# Namen/Emailadresse mit sympatischen Komilitonen und Komilitoninnen aus den Kleingruppen austauschen

Das erste Semester:
# Unisportkurse aussuchen http://www.tu-sport.de/
# sich über [http://www.skb.tu-berlin.de/franzosisch/mittefrz.html Sprachkurse] informieren
# sich Gedanken über Auslandssemester machen
# sich für die Uni engagieren: Freitagsrunde, studentische Cafés, Lötlabor, Dk0TU, Unirad, FasTUB, Grillen organisieren, ...

Im dritten Semester:
# für Auslandssemester bewerben
# sich über Fachstudium Gedanken machen

to be continued

== Vorschläge ==

# print@campus einrichten
# mailbox.tu-berlin.de einrichten

Lehrveranstaltungen Technische Informatik Bachelor/Master (StuPO 2006)

2010-02-22T02:14:18Z

Bastla: ch BSPrak

== Empfohlener Studienverlauf für den Bachelor der Technischen Informatik ==

[[BachelorMasterFAQ|FAQ zu den Bachelor- und Masterstudiengängen]]

'''Modulbeschreibungen bei der Ausbildungskommission: http://iv.tu-berlin.de/comm/ak/modul_dateien/TI.html
'''
{| class="wikitable"
! Semester
! colspan=5 | Studienfächer
|-
| style="text-align: center; padding: 0.7em" | 1
| bgcolor="#dff2ed" style="text-align: center; padding: 0.7em" | [[TechGI 1 (Bachelor) | TechGI 1]]
| bgcolor="#f4e4ce" style="text-align: center; padding: 0.7em" colspan=2 | [[MPGI 1 (Bachelor) | MPGI 1]]
| bgcolor="#eeeaef" style="text-align: center; padding: 0.7em" | [[Grundlagen der Elektrotechnik (Bachelor) | Grundlagen der Elektrotechnik ]]
| bgcolor="#FFE4B5" style="text-align: center; padding: 0.7em" | [[Lineare Algebra für Ingenieure]]
|-
| style="text-align: center; padding: 0.7em" | 2
| bgcolor="#dff2ed" style="text-align: center; padding: 0.7em" | [[TechGI 2 für TI (Bachelor) | TechGI 2 für TI]]
| bgcolor="#f4e4ce" style="text-align: center; padding: 0.7em" colspan=2 | [[MPGI 2 (Bachelor) | MPGI 2]]
| bgcolor="#eeeaef" style="text-align: center; padding: 0.7em" | [[Elektrische Netzwerke (Bachelor) | Elektrische Netzwerke]]
| bgcolor="#FFE4B5" style="text-align: center; padding: 0.7em" | [[Analysis I für Ingenieure]]
|-
| style="text-align: center; padding: 0.7em" | 3
| bgcolor="#dff2ed" style="text-align: center; padding: 0.7em" | [[TechGI 3 (Bachelor) | TechGI 3]]
| bgcolor="#f4e4ce" style="text-align: center; padding: 0.7em" | [[MPGI 3 für TI (Bachelor) | MPGI 3 für TI]]
| bgcolor="#eeeaef" style="text-align: center; padding: 0.7em" | [[Halbleiterbauelemente (Bachelor) | Halbleiterbauelemente]]
| bgcolor="#FFE4B5" style="text-align: center; padding: 0.7em" | [[Analysis II für Ingenieure]]
| bgcolor="#FFE4B5" style="text-align: center; padding: 0.7em" | [[ITPDGL für Ingenieure]]
|-
| style="text-align: center; padding: 0.7em" | 4
| bgcolor="#dff2ed" style="text-align: center; padding: 0.7em" | [[TechGI 4 (Bachelor) | TechGI 4]]
| bgcolor="#eeeaef" style="text-align: center; padding: 0.7em" | [[Signale und Systeme (Bachelor) | Signale und Systeme]]
| bgcolor="#eeeaef" style="text-align: center; padding: 0.7em" | [[Theoretische Elektrotechnik I (Bachelor) | Theoretische Elektrotechnik I ]]
| bgcolor="#eadaee" style="text-align: center; padding: 0.7em" | [[Physik für TI (Bachelor)|Physik für TI]]
| bgcolor="#eeeaef" style="text-align: center; padding: 0.7em" | [[Schaltungstechnik (Bachelor) | Schaltungstechnik]]
|-
| style="text-align: center; padding: 0.7em" | 5
| bgcolor="#eaf6fc" style="text-align: center; padding: 0.7em" | [[TheGI für TI (Bachelor) | TheGI für TI]]
| bgcolor="#EEE8AA" style="text-align: center; padding: 0.7em" | [[Betriebssystempraktikum (Bachelor) | Betriebssystempraktikum]]
| bgcolor="#FFFFE0" style="text-align: center; padding: 0.7em" rowspan=2 | [[Module Elektrotechnik (Bachelor) | Module Elektrotechnik]]
| bgcolor="#FFFFE0" style="text-align: center; padding: 0.7em" rowspan=2 | [[Module Informatik (Bachelor) | Module Informatik]]
| bgcolor="#eeeaef" style="text-align: center; padding: 0.7em" | [[Grundlagen der Messtechnik (Bachelor) | Grundlagen der Messtechnik]]
|-
| style="text-align: center; padding: 0.7em" | 6
| bgcolor="#f5f3f3" style="text-align: center; padding: 0.7em" rowspan=2 | [[Fachübergreifendes Studium (Bachelor) | Fachübergreifendes Studium]]
| bgcolor="#EEE8AA" style="text-align: center; padding: 0.7em" | [[Hardwarepraktikum (Bachelor) | Hardwarepraktikum]]
| bgcolor="#FFFFE0" style="text-align: center; padding: 0.7em" rowspan=2 | [[Module Technische Informatik (Bachelor) | Module Technische Informatik]]
|-
| style="text-align: center; padding: 0.7em" | 7
| bgcolor="#e1dfd7" style="text-align: center; padding: 0.7em" colspan=2 | [[Bachelorarbeit]]
| bgcolor="#EEE8AA" style="text-align: center; padding: 0.7em" | [[Berufspraktische Tätigkeit]]
|}

== Empfohlener Studienverlauf für den Master der Technischen Informatik ==

{| class="wikitable"
! Semester
! colspan=4 | Studienfächer
|-
| style="text-align: center; padding: 0.7em" | 1
| bgcolor="#f5f3f3" style="text-align: center; padding: 0.7em" rowspan=2 | [[Schwerpunktfach (Master) | Schwerpunktfach]]
| bgcolor="#FFFFE0" style="text-align: center; padding: 0.7em" rowspan=2 | [[Hauptfach (Master) | Hauptfach]]
| bgcolor="#FFFFE0" style="text-align: center; padding: 0.7em" rowspan=2 | [[Hauptfach (Master) | Hauptfach]]
| bgcolor="#eeeaef" style="text-align: center; padding: 0.7em" rowspan=2 | [[Studium Generale]]
|-
| style="text-align: center; padding: 0.7em" | 2
|-
| style="text-align: center; padding: 0.7em" | 3
| bgcolor="#e1dfd7" style="text-align: center; padding: 0.7em" colspan=4 | [[Masterarbeit]]
|}

----
[[Studiengänge|Zurück zu den Studiengängen]]
[[Kategorie:Fakultäts-ABC]]

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-11T02:10:08Z

Bastla: format + typo

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''abx'' | x ∈ Σ*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und es folgen beliebig viele ''a'' oder ''ba''}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeformt werden muss. D.h. man muss einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====

L1 = {x aus E* : in x kommt a mind. einmal vor}
L2 = {x aus E* : x fängt mit a oder endet mit b}
L3 = {x aus {aa, bb}*}
= {x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4 = {x aus (ab)*}
= {x : x ist die Iteration des Strings ab oder das leere Wort}
L5 = {ε}

====9====
F1 = E*(aab)E*
= (a*b*)*aab(a*b*)*
F2 = (aab)E*
= aab(a*b*)*
F3 = (aab)+ (Iteration setzt mindestens das einmalige Vorkommen voraus)

====10====

(1) R+S = S+R (Richtig, braucht keinen Nachweis)

(2) RS = SR (Falsch, braucht keinen Nachweis)

(3) (RS)* = (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)* -
Mit (RS)* lässt sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(4) (R+S)* = (R*+S*)* (Richtig)
Direkter Beweis: (R+S)* = (R*S*)*
= ((R*)*(S*)*)*
= (R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===

Von oben nach unten einzutragen:

* Typ-0: allgemeine Sprachen
* Typ-1: kontextsensitive Sprachen
* Typ-2: kontextfreie Sprachen
* Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===

#
#* Die Sprache L2 ist komplementär zur Sprache L1
#* L1 ist das spezielle Halteproblem für Turingmaschinen
#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von Mω
#
#* Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
#* Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-11T02:07:50Z

Bastla: format

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''abx'' | x ∈ Σ*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und es folgen beliebig viele ''a'' oder ''ba''}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeformt werden muss. D.h. man muss einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====

L1 = {x aus E* : in x kommt a mind. einmal vor}
L2 = {x aus E* : x fängt mit a oder endet mit b}
L3 = {x aus {aa, bb}*}
= {x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4 = {x aus (ab)*}
= {x : x ist die Iteration des Strings ab oder das leere Wort}
L5 = {ε}

====9====
F1 = E*(aab)E*
= (a*b*)*aab(a*b*)*
F2 = (aab)E*
= aab(a*b*)*
F3 = (aab)+ (Iteration setzt mindestens das einmalige Vorkommen voraus)

====10====

R+S = S+R (Richtig, braucht keines Nachweises)

RS = SR (Falsch, braucht keines Nachweises)

(RS)* = (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)* -
Mit (RS)* lässt sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(R+S)* = (R*+S*)* (Richtig)
Direkter Beweis: (R+S)* = (R*S*)*
= ((R*)*(S*)*)*
= (R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===

Von oben nach unten einzutragen:

* Typ-0: allgemeine Sprachen
* Typ-1: kontextsensitive Sprachen
* Typ-2: kontextfreie Sprachen
* Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===

#
#* Die Sprache L2 ist komplementär zur Sprache L1
#* L1 ist das spezielle Halteproblem für Turingmaschinen
#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von Mω
#
#* Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
#* Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-11T01:58:52Z

Bastla: typo

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''abx'' | x ∈ Σ*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und es folgen beliebig viele ''a'' oder ''ba''}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeformt werden muss. D.h. man muss einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====

L1 = {x aus E* : in x kommt a mind. einmal vor}
L2 = {x aus E* : x fängt mit a oder endet mit b}
L3 = {x aus {aa, bb}*}
= {x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4 = {x aus (ab)*}
= {x : x ist die Iteration des Strings ab oder das leere Wort}
L5 = {ε}

====9====
F1 = E*(aab)E*
= (a*b*)*aab(a*b*)*
F2 = (aab)E*
= aab(a*b*)*
F3 = (aab)+ (Iteration setzt mindestens das einmalige Vorkommen voraus)

====10====
R+S=S+R (Richtig, braucht keines Nachweises)

RS=SR (Falsch, braucht keines Nachweises)

(RS)*= (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)*, mit (RS)* laesst sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(R+S)*=(R*+S*)* (Richtig)
Direkter Beweis: (R+S)*=(R*S*)*=((R*)*(S*)*)*=(R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===

Von oben nach unten einzutragen:

* Typ-0: allgemeine Sprachen
* Typ-1: kontextsensitive Sprachen
* Typ-2: kontextfreie Sprachen
* Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===

#
#* Die Sprache L2 ist komplementär zur Sprache L1
#* L1 ist das spezielle Halteproblem für Turingmaschinen
#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von Mω
#
#* Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
#* Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-11T01:57:26Z

Bastla: hübscher

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''abx'' | x ∈ Σ*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und es folgen beliebig viele ''a'' oder ''ba''}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeformt werden muss. D.h. man muss einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====

L1 = {x aus E* : in x kommt a mind. einmal vor}
L2 = {x aus E* : x fängt mit a oder endet mit b}
L3 = {x aus {aa, bb}*}
= {x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4 = {x aus (ab)*}
= {x : x ist die Iteration des Strings ab oder das leere Wort}
L5 = {ε}

====9====
F1 = E*(aab)E*
= (a*b*)*aab(a*b*)*
F2 = (aab)E*
= aab(a*b*)*
F3 = (aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)

====10====
R+S=S+R (Richtig, braucht keines Nachweises)

RS=SR (Falsch, braucht keines Nachweises)

(RS)*= (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)*, mit (RS)* laesst sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(R+S)*=(R*+S*)* (Richtig)
Direkter Beweis: (R+S)*=(R*S*)*=((R*)*(S*)*)*=(R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===

Von oben nach unten einzutragen:

* Typ-0: allgemeine Sprachen
* Typ-1: kontextsensitive Sprachen
* Typ-2: kontextfreie Sprachen
* Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===

#
#* Die Sprache L2 ist komplementär zur Sprache L1
#* L1 ist das spezielle Halteproblem für Turingmaschinen
#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von Mω
#
#* Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
#* Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-11T01:47:45Z

Bastla: format

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''abx'' | x ∈ Σ*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und es folgen beliebig viele ''a'' oder ''ba''}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeformt werden muss. D.h. man muss einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====

L1 = {x aus E* : in x kommt a mind. einmal vor}
L2 = {x aus E* : x fängt mit a oder endet mit b}
L3 = {x aus {aa, bb}*}
= {x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4 = {x aus (ab)*}
= {x : x ist die Iteration des Strings ab oder das leere Wort}
L5 = {ε}

====9====
F1=E*(aab)E*=(a*b*)*aab(a*b*)*
F2=aabE*=aab(a*b*)*
F3=(aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)

====10====
R+S=S+R (Richtig, braucht keines Nachweises)

RS=SR (Falsch, braucht keines Nachweises)

(RS)*= (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)*, mit (RS)* laesst sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(R+S)*=(R*+S*)* (Richtig)
Direkter Beweis: (R+S)*=(R*S*)*=((R*)*(S*)*)*=(R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===

Von oben nach unten einzutragen:

* Typ-0: allgemeine Sprachen
* Typ-1: kontextsensitive Sprachen
* Typ-2: kontextfreie Sprachen
* Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===

#
#* Die Sprache L2 ist komplementär zur Sprache L1
#* L1 ist das spezielle Halteproblem für Turingmaschinen
#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von Mω
#
#* Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
#* Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-11T01:16:30Z

Bastla: Ergänzung + typos

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''abx'' | x ∈ Σ*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und es folgen beliebig viele ''a'' oder ''ba''}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeformt werden muss. D.h. man muss einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====
L1={x aus E* : in x kommt a mind. einmal vor}
L2={x aus E* : x fängt mit a oder endet mit b}
L3={x aus {aa, bb}*}={x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4={x aus (ab)*}={x : x ist die Iteration des Strings ab oder das leere Wort}
L5={e}

====9====
F1=E*(aab)E*=(a*b*)*aab(a*b*)*
F2=aabE*=aab(a*b*)*
F3=(aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)

====10====
R+S=S+R (Richtig, braucht keines Nachweises)

RS=SR (Falsch, braucht keines Nachweises)

(RS)*= (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)*, mit (RS)* laesst sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(R+S)*=(R*+S*)* (Richtig)
Direkter Beweis: (R+S)*=(R*S*)*=((R*)*(S*)*)*=(R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===

Von oben nach unten einzutragen:

* Typ-0: allgemeine Sprachen
* Typ-1: kontextsensitive Sprachen
* Typ-2: kontextfreie Sprachen
* Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===

#
#* Die Sprache L2 ist komplementär zur Sprache L1
#* L1 ist das spezielle Halteproblem für Turingmaschinen
#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von Mω
#
#* Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
#* Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-11T00:53:21Z

Bastla: ja, kann man

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''abx'' | x ∈ Σ*} = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====
L1={x aus E* : in x kommt a mind. einmal vor}
L2={x aus E* : x fängt mit a oder endet mit b}
L3={x aus {aa, bb}*}={x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4={x aus (ab)*}={x : x ist die Iteration des Strings ab oder das leere Wort}
L5={e}

====9====
F1=E*(aab)E*=(a*b*)*aab(a*b*)*
F2=aabE*=aab(a*b*)*
F3=(aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)

====10====
R+S=S+R (Richtig, braucht keines Nachweises)

RS=SR (Falsch, braucht keines Nachweises)

(RS)*= (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)*, mit (RS)* laesst sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(R+S)*=(R*+S*)* (Richtig)
Direkter Beweis: (R+S)*=(R*S*)*=((R*)*(S*)*)*=(R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===

Von oben nach unten einzutragen:

* Typ-0: allgemeine Sprachen
* Typ-1: kontextsensitive Sprachen
* Typ-2: kontextfreie Sprachen
* Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===

#
#* Die Sprache L2 ist komplementär zur Sprache L1
#* L1 ist das spezielle Halteproblem für Turingmaschinen
#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von Mω
#
#* Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
#* Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-11T00:10:34Z

Bastla: typos und Formulierung angepasst

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
kann man eigentlich auch
''L2'' = {''abx'' | x ∈ Σ*}
schreiben?

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====
L1={x aus E* : in x kommt a mind. einmal vor}
L2={x aus E* : x fängt mit a oder endet mit b}
L3={x aus {aa, bb}*}={x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4={x aus (ab)*}={x : x ist die Iteration des Strings ab oder das leere Wort}
L5={e}

====9====
F1=E*(aab)E*=(a*b*)*aab(a*b*)*
F2=aabE*=aab(a*b*)*
F3=(aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)

====10====
R+S=S+R (Richtig, braucht keines Nachweises)

RS=SR (Falsch, braucht keines Nachweises)

(RS)*= (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)*, mit (RS)* laesst sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(R+S)*=(R*+S*)* (Richtig)
Direkter Beweis: (R+S)*=(R*S*)*=((R*)*(S*)*)*=(R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===

Von oben nach unten einzutragen:

* Typ-0: allgemeine Sprachen
* Typ-1: kontextsensitive Sprachen
* Typ-2: kontextfreie Sprachen
* Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===

#
#* Die Sprache L2 ist komplementär zur Sprache L1
#* L1 ist das spezielle Halteproblem für Turingmaschinen
#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von Mω
#
#* Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
#* Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-10T22:27:19Z

Bastla: Struktur und kleine Umformulierung

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
kann man eigentlich auch
''L2'' = {''abx'' | x ∈ Σ*}
schreiben?

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====
L1={x aus E* : in x kommt a mind. einmal vor}
L2={x aus E* : x fängt mit a oder endet mit b}
L3={x aus {aa, bb}*}={x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4={x aus (ab)*}={x : x ist die Iteration des Strings ab oder das leere Wort}
L5={e}

====9====
F1=E*(aab)E*=(a*b*)*aab(a*b*)*
F2=aabE*=aab(a*b*)*
F3=(aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)

====10====
R+S=S+R (Richtig, braucht keines Nachweises)

RS=SR (Falsch, braucht keines Nachweises)

(RS)*= (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)*, mit (RS)* laesst sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(R+S)*=(R*+S*)* (Richtig)
Direkter Beweis: (R+S)*=(R*S*)*=((R*)*(S*)*)*=(R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===

Von oben nach unten einzutragen:

* Typ-0: allgemeine Sprachen
* Typ-1: kontextsensitive Sprachen
* Typ-2: kontextfreie Sprachen
* Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===
#
#* Die Sprache L2 ist komplementär zur Sprache L1
#* L1 ist das spezielle Halteproblem für Turingmaschinen
#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von Mω
#
#* Eine Sprache ist entscheidbar, wenn wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
#* Eine Sprache ist semi-entscheidbar, wenn ein Automat für diese Sprache terminiert für Wörter aus der Sprache, sein Zustand für Wörter die nicht aus der Sprache sind aber undefiniert ist, er möglicherweise also nicht terminiert für Wörter die nicht aus der Sprache sind.
#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält.
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-10T15:07:16Z

Bastla: /* Aufgabe 15 */

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
kann man eigentlich auch
''L2'' = {''abx'' | x ∈ Σ*}
schreiben?

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====
L1={x aus E* : in x kommt a mind. einmal vor}
L2={x aus E* : x fängt mit a oder endet mit b}
L3={x aus {aa, bb}*}={x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4={x aus (ab)*}={x : x ist die Iteration des Strings ab oder das leere Wort}
L5={e}

====9====
F1=E*(aab)E*=(a*b*)*aab(a*b*)*
F2=aabE*=aab(a*b*)*
F3=(aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)

====10====
R+S=S+R (Richtig, braucht keines Nachweises)

RS=SR (Falsch, braucht keines Nachweises)

(RS)*= (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)*, mit (RS)* laesst sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(R+S)*=(R*+S*)* (Richtig)
Direkter Beweis: (R+S)*=(R*S*)*=((R*)*(S*)*)*=(R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===

Von oben nach unten einzutragen:

* Typ-0: allgemeine Sprachen
* Typ-1: kontextsensitive Sprachen
* Typ-2: kontextfreie Sprachen
* Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===
# Die Sprache L2 ist komplementär zur Sprache L1 L1 ist das spezielle Halteproblem für Turingmaschinen Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist die codierung von Mω
# - Eine Sprache ist entscheidbar, wenn wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht. - Eine Sprache ist semi-entscheidbar, wenn ein Automat für diese Sprache terminiert für Wörter aus der Sprache, sein Zustand für Wörter die nicht aus der Sprache sind aber undefiniert ist, er möglicherweise also nicht terminiert für Wörter die nicht aus der Sprache sind. - Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält.
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Lösungen TheGI TI Probeklausur vom 19.01.06

2010-02-10T14:49:02Z

Bastla: /* Aufgabe 3 */

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} auch: {''axb'' : ''x'' ∈ Σ*}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q0
|-
|q1
|q1
|q1
|}

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
kann man eigentlich auch
''L2'' = {''abx'' | x ∈ Σ*}
schreiben?

:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = a(a+ba)*}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8, 9, 10===

Es gilt allgemein: E*=(a*b*)*=(a+b)*.
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache. Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

====8====
L1={x aus E* : in x kommt a mind. einmal vor}
L2={x aus E* : x fängt mit a oder endet mit b}
L3={x aus {aa, bb}*}={x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
L4={x aus (ab)*}={x : x ist die Iteration des Strings ab oder das leere Wort}
L5={e}

====9====
F1=E*(aab)E*=(a*b*)*aab(a*b*)*
F2=aabE*=aab(a*b*)*
F3=(aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)

====10====
R+S=S+R (Richtig, braucht keines Nachweises)

RS=SR (Falsch, braucht keines Nachweises)

(RS)*= (R*S*)* (Falsch)
Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)*, mit (RS)* laesst sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

(R+S)*=(R*+S*)* (Richtig)
Direkter Beweis: (R+S)*=(R*S*)*=((R*)*(S*)*)*=(R*+S*)*

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' ≤ ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===
:von oben nach unten
:*Typ-0; allgemeine
:*Typ-1; kontext-sensitive
:*Typ-2; kontext-freie
:*Typ-3; reguläre

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|nein
|nein
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

===Aufgabe 18===
# Die Sprache L2 ist komplementär zur Sprache L1 L1 ist das spezielle Halteproblem für Turingmaschinen Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist die codierung von Mω
# - Eine Sprache ist entscheidbar, wenn wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht. - Eine Sprache ist semi-entscheidbar, wenn ein Automat für diese Sprache terminiert für Wörter aus der Sprache, sein Zustand für Wörter die nicht aus der Sprache sind aber undefiniert ist, er möglicherweise also nicht terminiert für Wörter die nicht aus der Sprache sind. - Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält.
#
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
|
|x
|-
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
|x
|
|-
|Das spezielle Halteproblem ist nicht entscheidbar.
|x
|
|-
|Das spezielle Halteproblem ist semi-entscheidbar.
|x
|
|-
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
|x
|
|}

===Aufgabe 19===
1.
: - SAT ∈ NP
: - Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.
2.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!wahr
!falsch
|-
|Die Klasse P enthält nur entscheidbare Sprachen.
|x
|
|-
|Die Klasse NP enthält nur entscheidbare Sprachen.
|x
|
|-
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
|x
|
|-
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|
|x
|-
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
|x
|
|}
3.
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!Aussage
!bekannt
!unbekannt
|-
|Die Klasse P ist Teilklasse der Klasse NP.
|x
|
|-
|Die Klasse NP ist Teilklasse der Klasse P.
|
|x
|-
|Die Klasse P ist gleich der Klasse NP.
|
|x
|-
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
|
|x
|}

:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

TheGI TI (StuPO90)

2010-02-10T12:34:56Z

Bastla: überisichtlicher

<div id="Dokumente" style="float:right; width:20%; margin:10px; padding:10px; background-color:#efefef;">
WS 2005
* [http://docs.freitagsrunde.org/LV-Material/TheGI_TI/tgi_mitschriften_ws05.rar Mitschriften der VL (''handschriftl., ~100MB'')]

</div>

== Theoretische Grundlagen der Informatik (für Technische Informatiker) ==

Die Inhalte von [[TheGI 1]], [[TheGI 2]], [[TheGI 3]] in sehr komprimierter Form.
"Damit sie wissen, wie ein Informatiker denkt" - so einst (WS05) Prof. Mahr.
Pflichtveranstaltung im Hauptstudium Technische Informatik.

==Klausuren==

Die Prüfung findet im WS 05/06 erstmals in Form einer Klausur statt. Am 19.01. und 09.02.2006 fand dazu das Vorrechnen einer Probeklausur statt.

* [http://docs.freitagsrunde.org/Klausuren/TheGI_TI/klausur_ti_probe_ws0506.ps Probeklausur WS2005/2006] ([[Lösungen TheGI TI Probeklausur vom 19.01.06]])

==Weblinks==

* http://flp.cs.tu-berlin.de/lv/wise-0708-thegiti.html

[[Kategorie:Lehrveranstaltungen]]

Datei:Bastla.freifunk.jpg

2009-07-14T08:36:20Z

Bastla: hat eine neue Version von „Datei:Bastla.freifunk.jpg“ hochgeladen: smaller Version