Aufgabe: Aufwandsabschätzung

[inkydevil]

Hallöchen,

ich habe im Unterricht folgende Aufgabe zum Algorithmus "KleineEinMalEins" aufbekommen:

Aufwandsabschätzung "KleineEinMalEins" - was ist zu tun ?

1.)Beschreibung Eingabe (Struktur)
2.)Beschreibung Ausgabe (Struktur)
3.)Deutsch-Version des Algorithmus für die kleine Schwester ggf. Struktogramm
4.)Zentrale Anweisung auswählen / Auswahl begründen
5.)Formalisierung des Aufwandes
6.)Wachstumsklasse angeben

public class KleinesEinMalEins
{
	public static void main(String[] kommandoZeilenParameter)
	{
		int faktorEins = 1;
		int faktorZwei;
		
		while (faktorEins <= 10)
		{
			faktorZwei = 1;

			while (faktorZwei <= 10)
			{
				System.out.print(faktorEins * faktorZwei);
				System.out.print('\t');
				faktorZwei++;
			}
			
			System.out.println();
			faktorEins++;
		}
	}
}

Nun wollt' ich euch gerne um Rat fragen. Ihr müsst nicht unbedingt die Aufgaben komplett lösen, nur wüsste ich
gerne, wie ich an die Sache herantreten muss...
Ich will mich nicht auf euch ausruhen, um mich vor der Hausaufgabe
zu drücken, gerne würde ich eine solche Aufwandsabschätzung verstehen und ich hab' schon viel dafür gearbeitet,
doch kriegt's unserer Lehrer einfach nicht auf die Reihe, uns den Stoff vernünftig beizubringen.
Ist halt noch ein (zu) junger Bursche!

Ich bedanke mich schonmal im Vorraus.
Gruß Stefan

 

[AlArenal]

Ist dein Problem nun das Programm oder die Aufwandsabschätzung? *kopfkratz*

Aufwandsabschätzungen sind immer subjektiv und orientieren sich an Erfahrungen. Naturgemäß sind Aufwandsabschätzungen zunächst sehr grob und meist sehr falsch. Das bessert sich mit der Zeit und ändert sich wieder, sobald man sich in neues Terrain wagt. Zum Projektmanagement gehört aber eine Aufwandsabschätzung und auch der wahrheitsgemäße Vergleich mit dem tatsächlich ermittelten Aufwand unter Berücksichtigung der Gründe, etc. - sonst lernt man ja nicht sich besser einzuschätzen.

 

[funnyjanni]

Aufwandabschätzung für das Program oder aus Projektmanagementsicht? Von deinen Aussagen her würde ich eher Aufwand zur Ausführung des Programmes tippen?!

Da gibt's ja dann z.B. Abschätzung nach Groß - O: Hier O(n²), da du 2 geschachtelte Schleifen hast ...

Grüße,
Jan

 

[SnooP]

Tja... Wachstumsklasse? Ich kenne Komplexität von Programmen und Komplexitätsklassen... aber Wachstumsklassen?

die wäre im übrigen imho auch O(1)=Omega(1) - also konstant, da in den Schleifen lediglich Konstanten als Grenzen angegeben wurden und keine Variablen könnte man das ganze hintereinander runterschreiben und hätte dasselbe Programm. Also ist die Komplexität von keiner Größe n abhängig und somit auch nicht quadratisch wachsend oder ähnliches sondern lediglich abhängig von der Geschwindigkeit des Rechners.

 

[AlArenal]

Also linear...

 

[na-oma]

http://de.wikipedia.org/wiki/Landau-Symbole

Das ist jetz eine Definitionsfrage, ob man das Programm als O(1) (also konstant) betrachtet, weil beide Grenzen vorgegeben sind. (da kein n existiert, ist es auch nicht linear, linear wäre eine schleife 0...n)

Oder ob man die Grenzen als n (im Beispiel n = 10) betrachtet, dann wäre es ne polynominelle (quadratische) Komplexität O(n²), da die innersten Anweisungen:

4.)Zentrale Anweisung auswählen / Auswahl begründen

z.b. System.out.print(faktorEins * faktorZwei);

n*n=n² mal ausgeführt werden.

@thread-ersteller
Genauere Erklärungen kann ich vileicht mal später posten...der Grundgedanke ist eigentlich relativ einfach, wenn man es erstmal verstanden hat, was denn die Komplexität darstellt

 

[SnooP]

und solange man keine Schleifeninvarianten finden muss ... - ich würde aber wie oben sagen konstant, wenn der Lehrer schon son Quelltext vorgibt. Von n abhängig kann es ja nur sein, wenn n tatsächlich dasteht - sprich, wenn ich ne Konstante irgendwohindefiniere, dann hab ich auch keine Abhängigkeit von einem n mehr, sondern nur ne Abhängigkeit von der Konstante und dann kann ich das Ding auch in ne Schaltung mit fertigen Gattern gießen

 

[inkydevil]

So, hab' mich erst einmal schlau gemacht.
Schon mal danke für eure Beteiligung.
Zunächst nochmal kurze Klarstellungen:

Mein Problem geht aus der Aufgabenstellung soweit heraus, dass ich nicht so recht etwas
mit der Aufwandsabschätzung anfangen kann, mein Problem ist also die Aufwandsabschätzung für das Programm, das Programm verstehe ich ganz gut.

Nun zu den Aufgaben:

1.)Beschreibung Eingabe (Struktur)

Die Eingabemenge betrifft die Int-Werte "faktorEins" und "faktorZwei", die jeweils mit der Zahl 1 fest deklariert werden. Mit dem "faktorEins" wird in der ersten While-Schleife gearbeitet, in der dem "faktorZwei" zunächst die Zahl 1 zugewiesen wird. In der zweiten While-Schleife wird dann der "faktorZwei" gebraucht.

2.)Beschreibung Ausgabe (Struktur)

Die Ausgabemenge beschreibt die Ausgabe der Multiplikation zwischen den Werten "faktorEins" und "faktorZwei" bis zum Wert 100.
--> Nur was bedeutet

System.out.print('\t');

// Neue Zeile?

3.)Deutsch-Version des Algorithmus für die kleine Schwester ggf. Struktogramm

Es gibt zwei Werte "faktorEins" und "faktorZwei".
"faktorEins" hat den Wert 1.
Nun sollst du, solange "faktorEins" kleiner als oder gleich 10 ist folgendes tun:
Du gibst "faktorZwei" ebenfalls den Wert 1.
Solange dieser kleiner als oder gleich 10 ist fährst du folgendermaßen fort:
Du multiplizierst "faktorEins" und "faktorZwei" miteinander und nennst mir die Ergebnisse. Dabei solltest du auf die Werte 1 bis 10 kommen, wenn du "faktorZwei" nach jedem Schritt immer mit 1 addierst.
Da "faktorZwei" nun 10 ist, verfällt diese Bedingung und du addierst "faktorEins" mit der Zahl 1.
Nun gehst du alle oben genannten Arbeitsschritte mit erneuter Berücksichtigung der Bedingung "faktorZwei" kleiner als oder gleich 10 solange durch, bis "faktorEins" gleich 10 ist.
Nun multiplizierst du also "faktorEins", der gleich 2 ist, und "faktorZwei", der gleich 1 ist, miteinander und kommst, wenn du wieder "faktorZwei" um 1 addierst, auf die Werte 2-20, wobei immer nur jede zweite Zahl auftaucht.
Wie schon gesagt, tust du das nun solange, bis "faktorEins" gleich 10 ist und kommst dabei auf Ergebnisse von 1 bis 100.
Die Ergebnis-Reihe ist immer äquivalent zum "faktorEins".
So erhälst du beim Wert 4 für "faktorEins" die Ergebnisse 4,8,12,16,20,14,28,32,36,40.
Beim Faktor 7 entprechend: 7,14,21,28,35,42,49,56,63,70

4.)Zentrale Anweisung auswählen / Auswahl begründen

Die zentralen Anweisungen sind "faktorZwei++;" und "faktorEins++;", da an der Stelle jeweils die zugewiesenen Integer-Werte "faktorEins" und "faktorZwei" um eins aufgerechnet werden.
Es handelt sich also um einen Kopiervorgang.

5.)Formalisierung des Aufwandes

k(a)=2a + 1 ???? ---> Für mich nicht einsehbar, daher habe ich einfach mal 'ne lineare Funktion herausgesucht, die wahrscheinlich nicht relevant ist, aber das Konstante angeben soll.

6.)Wachstumsklasse angeben

linear~konstant ???


Soviel dazu. Man sieht, was der Lehrer bisher erreicht hat.
Ich merke nämlich jedes Mal, dass das total simple Aufgaben sind, aber er erklärt nie etwas
und redet immer von Selbststudium. Schön...aber wie und wo Selbststudium, wenn er uns nichts brauchbares zu lesen gibt bzw. empfiehlt!?

Naja, ich hoffe ihr könnt mir bei der ein oder anderen Sache nochmal ein paar Ergäntzungen bieten.