Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

wiedermal Aufgaben bis Mittwoch
Gehe zu Seite 1, 2, 3  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> wiedermal Aufgaben bis Mittwoch
 
Autor Nachricht
Katha S.
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 12.05.2005
Beiträge: 16
Wohnort: Langen

BeitragVerfasst am: 27 Mai 2005 - 08:20:07    Titel: wiedermal Aufgaben bis Mittwoch

huhu =)

wir haben mal wieder bis Mittwoch Aufgaben zu lösen. Müssen uns aus dem Blatt immer 2 Aufgaben aussuchen.
In der Übungsstunde wurden wiedermal keine gescheiten Tipps oder Erklärungen gegeben, nu weiß ich echt nicht, was ich mit den Aufgaben anfangen soll.
Helft ihr mir nochmal dabei? Rolling Eyes Ich muss nämlich einiges an Punkten aufholen, da ich bei den ersten Übungsblätter kaum Punkte bekommen hab (Teilpunkte werden nicht gezählt. entweder Aufgabe ist ganz richtig oder man bekommt nichts *sniff*)
Könnt euch selbsverfreilich 2 der Aufgaben aussuchen und gucken, welche das geringste Übel sind.
Die Aufgaben findet ihr hier:

http://www.math.uni-frankfurt.de/~zahri/blatt6.pdf

Ich bin euch so dankbar, dass ihr bisher schon so viel geholfen habt, da ich mit den Aufgaben meistens nichts anfangen kann und dementsprechend verloren wäre, wenn ich die allein machen müsste.

LIeber Gruß
Katha
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 27 Mai 2005 - 12:51:06    Titel:

Ich würde an deiner Stelle die 1 und die 2 machen. Zu Aufgabe 2). Du mußt hier eine Touring-Maschine definieren, die eine polynomielle oberschranke für Laufzeitkomplexität hat. Und das geht für die gegebene Sprache nur dann, wenn das Alphabet endlich ist. Kurze Anmerkung zum Beweis: Das Programm läßt sich stets auf die Auswertung der Bedingung x_n = x_(i-n) zurückführen. Da die Touring-Maschine dazu mindestens einen Zustandsübergäng machen muß, nämlich "x_n ist ein Symbol a", gibt es zu jedem Zeichen (Element des Alphabets) mindestens einen Zustand. Ist die Menge der Zeichen unendlich, so gilt dies auch für die Menge der Zustände, womit ein Widerspruch zur Definition einer Touring maschine vorliegt.

Das Programm selbst ist einfach:

Definiere die Touring-Maschine mit folgenden Zuständen:

- Start
- Für jedes Zeichen a des Alphabets einen Zustand a_gelesen

Und die Zustandsübergangsfunktion:

- Ist man im Zustand Start und das Band ist leer, so stoppe
- Ist man im Zustand Start und das Band ist nichtleer lese das Zeichen a, lösche a, gehe an das Ende des Wortes und gehe in den Zustand a_gelesen über
- Ist man im Zustand a_gelesen für ein Zeichen a und das Band ist leer so stoppe
- Ist man im Zustand a_gelesen für ein Zeichen a und das Band ist nicht leer, so lese ein Zeichen. Falls dieses a ist, so lösche a, gehe an den Anfang des Wortes und gehe in den Zustand Start über. Sonst gehe in eine Endlosschleife (oder gib sonst irgendwie ein "nein" aus)

Beachte: "Gehe an den Anfang" usw. sind Teilprogoramme, die weiter ausgeführt werden können. "Das Band ist leer" bedeutet, daß man beim Lesen das "Leerzeichen" (muß separat definiert sein, das Zeichen mit dem das Band außerhalb der Eingabe gefüllt ist) liest.

Zum Komplexitätsbeweis:

Das Program läßt den Kopf hin und her zwischen dem Anfang und dem Ende des Wortes höchstens Länge des Wortes / 2 mal laufen. Dabei bewegt sich der Kopf zwei mal über das ganze Wort, welches mit jedem Durchlauf 2 Stellen kürzer wird. Somit ist O(n^2) eine Abschätzung für die Laufzeitkomplexität, welche Polynomiell ist.

P.S: Und wiederrum beweist uns der Kollege mit dem komischen Name äußerste Schlampigkeit. Scheißt doch euren Übnungsleiter zusammen. Ein Dozent, der nicht in der Lage ist, die Angabe in einer vernünftigen äußeren Form darzustellen, ist auch wahrscheinlich nicht in der Lage Inhalte zu vermitteln.
Katha S.
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 12.05.2005
Beiträge: 16
Wohnort: Langen

BeitragVerfasst am: 30 Mai 2005 - 15:32:13    Titel:

danke =)

nur wie mach ich die 1 am besten? Wie kann ich das verstehen mit den Schaltkreisen über x1...? wisst ihr wo ich sowas nachlesen kann?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 30 Mai 2005 - 22:41:13    Titel:

Zitat:
nur wie mach ich die 1 am besten? Wie kann ich das verstehen mit den Schaltkreisen über x1...? wisst ihr wo ich sowas nachlesen kann?


Nachlesen kannst Du im Skript zur Vorlesung (link ist im letzten Thread von vor einer Woche). Ich versuche mich mal an die Lösungen, kann aber die Richtigkeit nicht garantieren, da die Aufgabenstellung nicht präzise ist.

Die Frage bei 1a) ist im Wesentlichen nach der Anzahl boolscher Funktionen, die aus den Eingaben x_1,nicht(x_1),...,x_n,nicht(x_n) usw. dargestellt werden können. Ich habe leider jetzt keine Zeit um mir das Skript durchzulesen. Ich nehme an, daß es darum geht, daß eine boolsche Funktion realisiert wird, die die Form

f : B^k -> B

hat, wobei B = {T,F} ist.

Dann ist die Antwort auf 1a) 2n (da man eben einfach ein der Signale ausgibt).

Bei 1b) kann man ein der Signale ausgeben, oder zwei der Signale mit einem der 2 Gatter verbinden. D.h. 2n + (2n over 2) (da man 2 Signale aus 2n auswählt und "und" und "oder" Gatter symmetrisch sind). Nun ist aber nicht klar, ob man logische Äquivalenzklassen von Schaltkreisen betrachten soll (also Vergleichskriterium Funktion) oder die Schaltkreise selber. Ich nehme an, daß er wirklich Schaltkreise meint. Sonst müsste man noch die Anzahl solcher Schaltkreise abziehen, die konstante F Funktion (x1 und nicht x1) bzw. T (beim oder Gatter) realisieren (davon gibt es ja n). Darfst Du Dir aussuchen, bzw. da können Wir noch reden. So ergibt sich insgesamt: 2n + (2n over 2) - n = n + (2n over 2)

1c) Also wählen wir eine Glied-Art. Semantisch kann man aufgrund der Transitivität von und bzw. oder die Schaltung als ein großes und bzw. oder mit l-1 Eingängen ansehen. Dann ist die Anzahl der Äquivalenzklassen von Schaltkreisen mit gleicher boolscher Funktion 2n + (2n over (l-1)) - t. Nun muß man noch die konstanten T bzw. F -Funktionen t abziehen. Davon gibt es (glaube ich) n (2n-2 over (l-3)), da man zuerst 2 benachbarte x_k und nicht(x_k) auswählt (n Mgk) und die restlichen (l-3) unter den verbleibenden 2n-2 Signalen. Was die Schaltkreise anbetrifft, so ist es deutlich komplizierter: Für ein Gatter gibt es 3 Mgk. Entweder es liegt an einem der Signale mit einem seiner Anschlüsse, oder es liegt an einem der Gatter-Ausgänge. Ich kann leider auf die Schnelle den Lösungsweg dazu nicht überblicken.

Entschuldige also für's Delirium, aber ich versuche wenigstens irgendwie zu helfen. Lies mal das Skript durch, da steht sicher mehr drin. Ich kann leider jetzt mich nicht damit befassen. Habe ehe schon 30 minuten das Zeg geschrieben. Hoffe wenigstens ein wenig Dich vorangebracht zu haben.
Katha S.
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 12.05.2005
Beiträge: 16
Wohnort: Langen

BeitragVerfasst am: 31 Mai 2005 - 00:11:07    Titel:

ja, vielen Dank Wink

Werde mich morgen mittag mit ner Freundin treffen und mit ihr zusammen das Übungsblatt bearbeiten. Jetzt weiß ich wenigstens schonmal etwas =)

danke vielmals!


Wink
Katha S.
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 12.05.2005
Beiträge: 16
Wohnort: Langen

BeitragVerfasst am: 31 Mai 2005 - 14:52:24    Titel:

huhu nochmal =)


also hab mir deine Erklärung durchgelesen und versucht soe komplett zu verstehen. Bin aber leider Gottes häufiger mal hängen geblieben, weil ich was nicht so recht verstehe.

bei der 1b hast du geschrieben, dass es nicht klar sei, ob man sich die Schaltkreise oder die Äquivalenzklassen betrachten soll. Würde ich jetzt nur die Schaltkreise angucken, würde doch der erste Teil völlig ausreichen, oder? (also das: "Bei 1b) kann man ein der Signale ausgeben, oder zwei der Signale mit einem der 2 Gatter verbinden. D.h. 2n + (2n over 2) (da man 2 Signale aus 2n auswählt und "und" und "oder" Gatter symmetrisch sind). "
Denn das mit den Äquivalenzklassen versteh ich net so recht und die haben wir bisher auch meines Wissens nach nicht behalndelt.

bei der c steig ich leider vollständig aus =( Was ist beispielsweise ne Transitivität? Und was Mgk?


Ich finde es sowas von deprimierend, dass ich echt nicht versteh, was mein Professor von uns will. Wir sitzen echt in der Vorlesung und verstehen nichts. Und das wiederum versteht er nicht. Bisher war es immer so, dass ich mich in fast jeden Mathestoff einarbeiten konnte, aber die diskrete Mathematik ist knüppelhart find ich. Ich bekomm´s einfach nicht hin *sniff* da komm ich mir schon doof vor zu fragen, da es wahrscheinlich gar net so schwer ist. :/

aber nun gut, ich versuch mal weiter zu verstehen ^^
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 31 Mai 2005 - 16:31:04    Titel:

Zitat:
Würde ich jetzt nur die Schaltkreise angucken, würde doch der erste Teil völlig ausreichen, oder? (also das: "Bei 1b) kann man ein der Signale ausgeben, oder zwei der Signale mit einem der 2 Gatter verbinden. D.h. 2n + (2n over 2) (da man 2 Signale aus 2n auswählt und "und" und "oder" Gatter symmetrisch sind).


Genau. Was die Äquivalenzklassen anbetrifft hast Du das Problem, ob Du die "Schaltkreise", also Graphen aus Kanten (Verbindungen) und Knoten (Gattern bzw. Ein und Ausgängen) betrachtest oder die dadurch repräsentierte boolsche Funktion. So realisieren die Schaltkreise:

Code:

          -----
x1 ----->|    |
x2 ----->|  & |------->|----|
          -----        |    |
x3 ------------------->| &  | -----------> Ausgabe
                       -----


und

Code:

          -----
x3 ----->|    |
x2 ----->|  & |------->|----|
          -----        |    |
x1 ------------------->| &  | -----------> Ausgabe
                       -----


Die selbe boolsche Funktion x3 and x3 and x1 sind aber verschiedene Schaltkreise als Graphen. Die Relation ~ mit "zwei Schaltkreise stehen in ~" genau dann, wenn die die selbe Funktion realisieren ist Reflexiv, Transitiv und Symmetrisch. Eine Relation mit diesen Eigenschaften nennt man eine Äquivalenzrelation. Solche Relationen unterscheiden sich dadurch von anderen, daß die Mengen A_f = { Schaltkreis a | a realisiert eine Funktion f } eine Partition (eine vollständige Zerlegung in nichtleere paarweise disjunkte Mengen) darstellen (diese nennt man Äquivalenzklassen). Es macht also durchaus Sinn diese anstatt der Schaltkreise zu zählen und man kann ebenfalls durchaus Schaltkreise mit entsprechenden Klassen identifizieren. Ich vermute, daß er das hier nicht haben will.

Transitivität bedeutet Aus A ~ B und B ~ C folgz A ~ C (so, wie bei A=B und B = C => A =C). Ich habe mich natürlich aber oben verschrieben und meine die Assoziativität (A und B) und C = C und (A und B) Smile. Mgk. ist einfach eine Abkürzung für Möglichkeit.

Tut mir Leid für die Fehler, ich habe gestern den ganzen Tag bis 2:00 Analysis I korrigiert bäwääh Sad) --o-o%&' ( )-T. Heute mach ich nichts. Ich schaue mir das Skript kurz mal durch und werde mal für 1c) was besseres liefern. Bleib also, wenn Du die Lösung haben willst am Netz. Dann wird das ganze produktiver.

Was die Vorlesung anbetrifft, so hat das, was ihr macht nur marginal mit diskreter Mathe zu tun. Das ist so eine Mischung aus Komplexitätstheorie, Kombinatorik und Rechnerstrukturen. Naja. Ich finde die Aufgaben, vor allem wegen der Bewertung, als nicht leicht, obwohl ich bei der Aufwandseinschätzung zum deutlichen Untertreiben neige. Also keine Sorge.
Katha S.
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 12.05.2005
Beiträge: 16
Wohnort: Langen

BeitragVerfasst am: 31 Mai 2005 - 18:28:06    Titel:

was machst du beruflich eigentlich, wenn ich fragen darf? Denn kannst das ja schon gut erklären ^^


jetzt langsam kommt mir das ganze auch bisschen bekannter vor. Nicht mehr ganz so als völlig absurd.
Auch wenn es noch nicht ganz sitzt Wink aber ich bin auf dem Weg dahin Wink

Und zu der Bewertung: Unser toller Tutor gibt entweder volle Punktzahl oder gar keine Punkte...zumindest hat er es bisher so gemacht. Deshalb bekomm ich langsam auch echt Angst, dass ich das Semester in Mathe nicht hinbekomm Sad
intenso
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 31.05.2005
Beiträge: 1

BeitragVerfasst am: 31 Mai 2005 - 18:56:47    Titel:

alle die hier mitlesen und auch an der vorlesung "diskrete Mathematik" teilnehmen danken dem "algebrafreak"´und natürlich auch "Katha S." dafür: Idea Exclamation
Katha S.
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 12.05.2005
Beiträge: 16
Wohnort: Langen

BeitragVerfasst am: 01 Jun 2005 - 00:38:57    Titel:

*hehe* daher also die viele Ahnung Wink

naja, es ist auf jeden Fall mal gut zu wissen, dass die Aufgaben net gescheit formuliert sind etc., denn das wusste ich bis du es gesagt hast auch nicht wirklich. Hab immer nur gedacht, ich würd´s einfach net verstehen. Aber da müssen wir echt was machen. Der Prof ist ja schließlich kein Unmensch und möchte eigentlich nicht, dass wir die Aufgaben nicht lösen können. (hat er uns zumindst am Anfang gesagt) Deshalb hat er auch all seine alten Übungen und sein altes Skript extra für uns überarbeitet, dass es verständlicher ist (man sieht ja was draus geworden ist^^).


Soo, ich geh jetzt aber auch mal schlafen.

Danke wie gesagt, dass du dir so viel Mühe gegeben hast Smile

Gute Nacht
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> wiedermal Aufgaben bis Mittwoch
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2, 3  Weiter
Seite 1 von 3

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum