Induktion

[julia123]

hi,

bereite mich grade für eine Klausur vor, und hänge bei der Induktion.
Hier die Aufgabenstellung:

Aufgabe 1
Die Menge der Zeichenketten kann induktiv definiert werden:
Basis: Die leere Zeichenkette ist eine Zeichenkette.
Induktion: ist s eine Zeichenkette, und c ein beliebiges Zeichen, dann ist auch c -
s (s mit davor gesetztem c) eine
Zeichenkette.

Definieren Sie einen Algorithmus in Pseudocode der die Länge einer Zeichenkette berechnet und dabei nach dem Prinzip
Reduziere-und-Herrsche rekursiv über die Struktur der Zeichenkette definiert ist. Implementieren Sie diesen Algorithmus
in Java.

Aufgabe 2
Die Menge der Zeichenketten kann etwas anders induktiv definiert werden:
Basis: Die leere Zeichenkette ist eine Zeichenkette.
Induktion: ist s eine Zeichenkette, und c ein beliebiges Zeichen, dann ist auch s
- c (s mit angehängtem c) eine Zeichenkette.

Definieren Sie einen Algorithmus in Pseudocode der die Länge einer Zeichenkette berechnet und dabei nach dem Prinzip
Reduziere-und-Herrsche rekursiv über diese Struktur der Zeichenkette definiert ist. Implementieren Sie diesen
Algorithmus in Java.

Aufgabe 3
Die Menge G der Zeichenketten, die eine positive ganze Zahl darstellen, kann induktiv definiert werden:
Basis: Jede der Ziffer ist ein Element von G.
Induktion: Ist g element in G und g ungleich 0 dann ist auch g
* z element in G wobei z eine beliebige Ziffer ist.

Sind nach dieser Definition führende Nullen erlaubt?
Definieren Sie einen Algorithmus in Pseudocode der den Wert einer Zeichenkette aus G berechnet und dabei nach dem
Prinzip Teile-und-Herrsche rekursiv über die Struktur der Zeichenkette definiert ist.

Also ich hab den unterscheid der ersten und der zewiten Aufgabe nicht verstanden. Ist ads die gleiche Aufgabe oder übersehe ich da etwas?

Ansonsten fehlt mir echt jedeform an so etwas ran zugehen. Hab das Skrip schon durch gelesen.
Bei Aufgabe 3 ist keine führende Null erlaubt bei weil die Basis aus Postiven ganzen Zahlen besteht vermute ich mal.

liebe grüße

 

[sheel]

Hi

Der Unterschied zwischen Aufgabe 1 und 2 ist doch ziemlich eindeutig.

A1

stringlaenge(string s)
{
    wenn s leer ist return 0
    return 1 + stringlaenge(s_ohne_erstem_buchstaben);
}

A2

stringlaenge(string s)
{
    wenn s leer ist return 0
    return 1 + stringlaenge(s_ohne_letztem_buchstaben);
}

Das Ergebnis wird bei beiden das Selbe sein, nur die Reihenfolge,
wie die Buchstaben abgearbeitet werden...

Und die ersten zwei Aufgaben sind schon irgendwie seltsam,
aber die Frage bei A3 macht überhaupt keinen Sinn mehr.
Unbeantwortbar, falls ich richtig denke.

 

[julia123]

vielen dank hab die ersten beiden verstanden, hier mein quellcode zurüberprüfung:


Die 1 Aufgabe: (seh ich das richtig dass das ein top-Down Algoritmus ist)

public static int topdown(String s){
		if(s.isEmpty())
			return 0;
			else
			return 1 + topdown(s.substring(1));

	}

Die 2 Aufagbe

public static int bottomup(String s){
		if(s.isEmpty())
			return 0;
			else
			return 1 +  bottomup(s.substring(0, s.length()-1);

	}

Zur Aufgabe 3 hab so eine ähnliche Aufgabe aus einer Altklausur gefunden gehabt (Wollte mir die Aufgabe aufsparren um mich zu testen, Zeitdruck ... Aber wenn ich bei Aufgabe 3 hänge werde ich dass, denke ich bei dieser hier auch tun. Die ist glaube ich dran angelehnt) :

Die Menge G der Zeichenketten, die eine positive ganze Zahl darstellen, kann induktiv definiert werden:
Basis: Jede Ziffer ist ein Element von G.
Induktion: Ist g element in G und g ungleich 0 dann ist auch g - z element in G (g mit angehängtem z) wobei z eine beliebige Ziffer ist.
1. Sind nach dieser Definition führende Nullen erlaubt?
2. Definieren Sie einen Reduziere-und-Herrsche–Algorithmus in Pseudocode der den Zahlwert einer Zeichenkette
aus G berechnet und auf dieser induktiven Definition beruht. (Der Zahlwert der Zeichenkette ‘‘123’’ ist
die Zahl 123.)
3. Implementieren Sie diesen Algorithmus top–down (rekursiv) in Java.
4. Implementieren Sie diesen Algorithmus bottom–up (iterativ) in Java.
5. Kann die Technik der dynamischen Programmierung hier sinnvoll angewendet werden? Wenn ja: wie? Wenn
nein: warum nicht?

 

[HonniCilest]

Ich habe lange über die 3. Aufgabe nachgedacht und möchte Sheel zustimmen, dass diese in der Tat sehr merkwürdig ist!

aber fangen wir mal hinten an:

Definieren Sie einen Algorithmus in Pseudocode der den Wert einer Zeichenkette aus G berechnet und dabei nach dem Prinzip Teile-und-Herrsche rekursiv über die Struktur der Zeichenkette definiert ist.

Wir haben eine Zeichenkette, welche aus Ziffern besteht und der Wert soll berechnet werden. Heißt für mich beispielsweise: str --> int
Für die Implementierung würde man denke ich die einzelnen Ziffern durchlaufen und multipliziert Zehnerpotenzen addieren. Beim Durchlauf wäre die aktuelle Ziffer z und die Zehnerpotenz g, da diese nach Definition auch in G liegt. Die Zehnerpotenz ist zu keinem Zeitpunkt 0.

Nehmen wir nun das Beispiel "1" ohne führende Null und "01" mit der führenden Null.
foo("1") = z * g = 1 * 10^0 = 1 * 1 = 1
foo("01") = z1 * g1 + z0 * g0 = 0 * 10^1 + 1 * 10^0 = 0 * 10 + 1 * 1 = 0 + 1 = 1
Entsprechend würde ich behauptet die führende 0 ist erlaubt.

Aber wer weiß, vielleicht denke ich auch völlig falsch, echt verwirrend!

 

[julia123]

vielen dank ihr beiden ******

Hab das jetzt in Java so gelöst:
Das ist doch jetzt reduziere und Herrsche und nicht teile und Herrsche?

public static int wert(String s){
		if(s.isEmpty())
			return 0;
			else
			return Integer.parseInt(s.substring(1))*((int)Math.pow(10,s.length()-1))+wert(s.substring(1));
			
		
	}

Hab aber noch paar offe Fragen.

Wie geht man Taktisch klug bei diesen Induktionsaufgaben vor? Hat jemand ein Tipp( manchmal sind es die Einfachen sachen die ihr als selbstversändlich erachtet die mir jedoch sehr weiter helfen)

Ich hab echt viel über Induktion gelesen und kenn das auch aus der Mathematik aber ich seh in der Informatik jetzt kein richtigen unterscheid zur Rekusion?
Kann mir jemand vielleicht in eigenen Worten mal Induiton definieren.( Das Skript ist echt ********, im bezug auf Induktion obwhol das ein wichtiges Thema ist)

 

[just_]

Hi,
also ich muss wohl die gleiche klausur schreiben... vielleicht kann ich dir helfen. Reduziere und Hersche ist eine besondere form von Teile und hersche(so steht es in den folien), also schließe ich daraus das RH teilmenge von TH ist und somit TH ist.
Zu induktion: Du kannst dir es so vorstellen. Eine induktion ist immer ein teil der gesamtheit. So habe ich das verstanden. Wie in der aufgabe zu sehen ist, du hast einen kopletten string und diesen "splittest" (teilst) es aufs minimale und baust es durch die einzelne teile zum gesamten, zumindest habe ich das so verstanden. Ich hoffe ich konnte dir ein wenig helfen.

 

[julia123]

Sorry, der Algoritmus oben funktioniert doch nicht kann mir bitte jemand mein fehler nennen******
Komm nicht weiter hab schon diverses probiert :

	public static int wert(String s) {
		if (s.isEmpty())
			return 0;
//		else if (s.length() - 1 == 0)
//			return Integer.parseInt(s.substring(0))
//					* ((int) Math.pow(10, s.length()-1));
		else
			return s.charAt(0) - '0'
					* ((int) Math.pow(10, s.length() - 1))
					+ wert(s.substring(1));

	}

 

[just_]

Die zweite lösung stimmt fast. Das problem ist das dein wert bei "s.charAt(0)-'0'" falsch berechnet wird. Ersetze dies durch diesen ausdruck "Integer.parseInt((String.valueOf(s.charAt(0))))" und es wird funktionieren.
viel spass weiter hin, es wird nicht leichter....