Uni: Logik?
Hey Leute,
Ich bin ein neuer Student im Informatik und habe die Vorlesungen der Logik gesehen und jetzt sollen wir ein paar Aufgaben lösen.
Ich habe aber keine Ahnung wie man diese lösen kann. Könnte mir jemanden helfen?
2 Antworten
Bei Teil b) ist nach einer Funktion gefragt, die den größten gemeinsamen Teiler (ggT) für zwei Zahlen, a und b, berechnet. Also eine Abbildung, die zwei Zahlen auf eine andere Zahl abbildet:
Jetzt brauchen wir noch eine genaue Abbildungsvorschrift. Dazu rufen wir uns die mathematische Definition des ggT ins Gedächtnis:
Zu zwei natürlichen Zahlen a und b ist der ggT d die größte Zahl, sodass gilt: d teilt a und d teilt b.
Die Menge aller Zahlen, die a und b teilen, lässt sich formell so aufschreiben:
Jetzt musst Du noch kennzeichnen, dass Du das größte Element dieser Menge meinst. Dazu kann man eine bestimmte Funktion benutzen... Danach hast Du Deine gesuchte Abbildungsvorschrift.
Zur c): Damit der Algorithmus korrekt ist, muss Alg(a,b) für alle natürlichen a und b mit ggT(a,b) übereinstimmen. Also lautet der Satz:
Hier, als Beispiel das Teilermengen-Verfahren:
int Teilermengen_ggT(int a, int b)
{
int retval = 1;
for (int i = 2; i <= a && i <= b; i++)
{
if (a % i == 0 && b % i == 0)
{
retval = i;
}
}
return retval;
}
Nun, das Teilermengen Verfahren ist ja recht simpel und einfach:
Teile jede der beiden Zahlen durch alle Zahlen mit 1 beginnend incl. sich selbst ohne Rest. Jetzt finde die größte Zahl, die in beiden Mengen vorkommt.
Ja das habe ich im Internet gefunden, aber wieso das nicht in der VL erklärt wurde ist das Problem
Das Problem ich muss das nicht mit Programmiersprache beweisen sondern durch reine Mathematik. In der Vorlesung wurde uns nur Beweismitteln und sowas vorgestellt.