Algorithmen Projektarbeit - Versionsgeschichte

Akaibel: /* Themen für die Projektarbeit */

2022-03-01T07:34:54Z

Themen für die Projektarbeit

← Nächstältere Version		Version vom 1. März 2022, 07:34 Uhr
Zeile 61:		Zeile 61:
	## '''Risiko-Berater:'''<br/>''Wie viele Armeen bleiben übrig, wenn man z.B. mit 23 Armeen 20 Armeen des Gegners angreift?''		## '''Risiko-Berater:'''<br/>''Wie viele Armeen bleiben übrig, wenn man z.B. mit 23 Armeen 20 Armeen des Gegners angreift?''
	## ''VIELE andere Simulationen sind denkbar!!!'''		## ''VIELE andere Simulationen sind denkbar!!!'''
	# '''~~Wie schwimmt man am schnellsten quer durch den Rhein?~~'''~~<br/>''Das Problem ist, dass die Strömung in~~ der Mitte stärker wird, d.h. ab wann sollte man einfach "quer" schwimmen (und dann am Strand wieder zurücklaufen).<br/>Folgende Grundannahmen: Der Rhein ist 400m breit. Die Strömungsgeschwindigkeit (in m/s) wird durch folgende Funktion ~~gegeben:~~ f(x) = -(1/20000)x<sup>2</sup> + (1/50)x (D.h. in der Rheinmitte ist die Strömung dann 2m/s.) Der Schwimmer hat eine Geschwindigkeit von 1,5m/s (das schafft ein Leistungssportler auf 400m). Wenn er am Ufer zurücklaufen muss, ist seine Geschwindigkeit auch 1,5m/s.''		# '''Divide-And-Conquer Algorithmen'''
	~~# '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en~~)~~: Multi~~-~~Armed~~-~~Bandit]~~		## Nullstellenbestimmung der Funktion f(x) = sin(x) mit Divide-And-Conquer
	# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Insertion-Heuristik und Farthest-Insertion-Heuristik zum Lösen des TSP für viele (d.h. mehr als 20) Städte<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]		# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Insertion-Heuristik und Farthest-Insertion-Heuristik zum Lösen des TSP für viele (d.h. mehr als 20) Städte<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]
	# '''Fehler-Erkennungs-Algorithmen:'''<br/>zwei ausgewählte darstellen und an Beispielen testen.<br/>[https://de.wikipedia.org/wiki/Fehlerkorrekturverfahren Fehlerkorrekturverfahren(Wikipedia)]		# '''Fehler-Erkennungs-Algorithmen:'''<br/>zwei ausgewählte darstellen und an Beispielen testen.<br/>[https://de.wikipedia.org/wiki/Fehlerkorrekturverfahren Fehlerkorrekturverfahren(Wikipedia)]
Zeile 69:		Zeile 69:
	## '''Graphen so einfärben, dass benachbarte Knoten nicht die gleiche Farbe haben: Wie viele Farben braucht man dafür?'''<br/>[https://en.wikipedia.org/wiki/Graph_coloring Wikipedia (en): Graph Coloring]		## '''Graphen so einfärben, dass benachbarte Knoten nicht die gleiche Farbe haben: Wie viele Farben braucht man dafür?'''<br/>[https://en.wikipedia.org/wiki/Graph_coloring Wikipedia (en): Graph Coloring]
	## '''Springerproblem:'''<br/>Der Springer soll auf einem Schachbrett alle Felder ab-"springen", ohne dabei 2x auf dasselbe Feld zu kommen. [https://de.wikipedia.org/wiki/Springerproblem Springerproblem (Wikipedia)]		## '''Springerproblem:'''<br/>Der Springer soll auf einem Schachbrett alle Felder ab-"springen", ohne dabei 2x auf dasselbe Feld zu kommen. [https://de.wikipedia.org/wiki/Springerproblem Springerproblem (Wikipedia)]
			## '''Rucksackproblem:'''<br/>Vergleich der Laufzeit und der Genauigkeit eines Backtracking- und eines [https://en.wikipedia.org/wiki/Greedy_algorithm Greedy-Algorithmus]
			## '''Travelling-Salesman-Problem:'''<br/>Vergleich der Laufzeit und der Genauigkeit eines Backtracking- und eines [https://en.wikipedia.org/wiki/Greedy_algorithm Greedy-Algorithmus]
	# '''Konvexe Hülle:''' <br/>Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.		# '''Konvexe Hülle:''' <br/>Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.
	# '''Optimale Verkehrsplanung:''' <br>Maximale Flüsse<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo23.php Algorithmus der Woche]		# '''Optimale Verkehrsplanung:''' <br>Maximale Flüsse<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo23.php Algorithmus der Woche]
Zeile 76:		Zeile 78:
	# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]		# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]
	## '''Integrale näherungsweise berechnen mit Trapezen bzw. mit Rechtecken:'''<br/>Vergleich der Konvergenzgeschwindigkeit.		## '''Integrale näherungsweise berechnen mit Trapezen bzw. mit Rechtecken:'''<br/>Vergleich der Konvergenzgeschwindigkeit.
	## '''Pi (oder die Eulersche Zahl e) berechnen mit einem geeigneten Algorithmus:''' <br/>~~Einen geeigneten rekursiven Algorithmus~~ recherchieren, programmieren, Genauigkeit		## '''Pi (oder die Eulersche Zahl e) berechnen mit einem geeigneten Algorithmus:''' <br/>Zwei geeignete Algorithmen recherchieren, programmieren und auf Genauigkeit vergleichen.
	## '''Ternary Search: Die Suche nach einem Maximum in einer Funktion, die überall rechts gekrümmt ist.'''<br/>[https://en.wikipedia.org/wiki/Ternary_search Wikipedia (en): Ternary search]		## '''Ternary Search: Die Suche nach einem Maximum in einer Funktion, die überall rechts gekrümmt ist.'''<br/>[https://en.wikipedia.org/wiki/Ternary_search Wikipedia (en): Ternary search]
	## '''Welche Funktion erfüllt die Differentialgleichung f''(x) = - f(x) bzw. f'(x) = x + f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]<br>''Man kann das auch mit Excel angehen!''		## '''Welche Funktion erfüllt die Differentialgleichung f''(x) = - f(x) bzw. f'(x) = x + f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]<br>''Man kann das auch mit Excel angehen!''
Zeile 89:		Zeile 91:
	## '''Der Miller-Rabin-Test'''<br/>findet Primzahlen mit mehr als 500 Stellen.		## '''Der Miller-Rabin-Test'''<br/>findet Primzahlen mit mehr als 500 Stellen.
	## '''Das Hubschrauber-Problem:'''<br/>Es gibt 500 weit verstreute Häuser. Wo sollte der Standort für einen Hubschrauber sein, damit jedes Haus möglichst schnell erreicht werden kann?<br/>''"Kleinster umschließender Kreis", vgl. "42. Algorithmus der Woche".''		## '''Das Hubschrauber-Problem:'''<br/>Es gibt 500 weit verstreute Häuser. Wo sollte der Standort für einen Hubschrauber sein, damit jedes Haus möglichst schnell erreicht werden kann?<br/>''"Kleinster umschließender Kreis", vgl. "42. Algorithmus der Woche".''
			# '''Wie schwimmt man am schnellsten quer durch den Rhein?'''<br/>''Das Problem ist, dass die Strömung in der Mitte stärker wird, d.h. ab wann sollte man einfach "quer" schwimmen (und dann am Strand wieder zurücklaufen).<br/>Folgende Grundannahmen: Der Rhein ist 400m breit. Die Strömungsgeschwindigkeit (in m/s) wird durch folgende Funktion gegeben: f(x) = -(1/20000)x<sup>2</sup> + (1/50)x (D.h. in der Rheinmitte ist die Strömung dann 2m/s.) Der Schwimmer hat eine Geschwindigkeit von 1,5m/s (das schafft ein Leistungssportler auf 400m). Wenn er am Ufer zurücklaufen muss, ist seine Geschwindigkeit auch 1,5m/s.''
			# '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit]
	# ''(Das folgende Problem ist ein rein theoretisches, d.h. hier wird gar nicht programmiert!)''<br/>'''P-NP-Problem am Beispiel: ''Lässt sich eine Landkarte mit 3 Farben einfärben?'''''<br>''Zur Klasse '''P''' gehören alle Entscheidungsprobleme, die in polynomieller Zeit '''gelöst''' werden können.<br>Zur Klasse '''NP''' gehören alle Entscheidungsprobleme, bei denen die Antwort "JA" in polynomieller Zeit '''verifiziert''' werden kann.'' <br>Es soll aufgezeigt werden, dass das 3-Farben-Problem nicht zur Klasse P, aber zur Klasse NP gehört. <br>Außerdem soll die Bedeutung von NP-vollständigen Problemen für die Algorithmik an diesem Beispiel erläutert werden.<br>''Das ist eine rein theoretische Arbeit!''<br>[https://de.wikipedia.org/wiki/Färbung_(Graphentheorie) Wikipedia: Färbung eines Graphen]<br>[http://www14.in.tum.de/lehre/2008WS/ea/EA-12.pdf Erläuterung von P und NP]<br>[https://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme Wikipedia: 21 NP-vollständige Probleme]		# ''(Das folgende Problem ist ein rein theoretisches, d.h. hier wird gar nicht programmiert!)''<br/>'''P-NP-Problem am Beispiel: ''Lässt sich eine Landkarte mit 3 Farben einfärben?'''''<br>''Zur Klasse '''P''' gehören alle Entscheidungsprobleme, die in polynomieller Zeit '''gelöst''' werden können.<br>Zur Klasse '''NP''' gehören alle Entscheidungsprobleme, bei denen die Antwort "JA" in polynomieller Zeit '''verifiziert''' werden kann.'' <br>Es soll aufgezeigt werden, dass das 3-Farben-Problem nicht zur Klasse P, aber zur Klasse NP gehört. <br>Außerdem soll die Bedeutung von NP-vollständigen Problemen für die Algorithmik an diesem Beispiel erläutert werden.<br>''Das ist eine rein theoretische Arbeit!''<br>[https://de.wikipedia.org/wiki/Färbung_(Graphentheorie) Wikipedia: Färbung eines Graphen]<br>[http://www14.in.tum.de/lehre/2008WS/ea/EA-12.pdf Erläuterung von P und NP]<br>[https://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme Wikipedia: 21 NP-vollständige Probleme]

Akaibel: /* Themen für die Projektarbeit */

2022-02-20T17:05:02Z

Themen für die Projektarbeit

← Nächstältere Version		Version vom 20. Februar 2022, 17:05 Uhr
Zeile 60:		Zeile 60:
	## '''Poker-Berater:'''<br/>''Welche Chancen hat man mit einem gegebenen Blatt, das Spiel gegen 3 weitere Spieler zu gewinnen?''		## '''Poker-Berater:'''<br/>''Welche Chancen hat man mit einem gegebenen Blatt, das Spiel gegen 3 weitere Spieler zu gewinnen?''
	## '''Risiko-Berater:'''<br/>''Wie viele Armeen bleiben übrig, wenn man z.B. mit 23 Armeen 20 Armeen des Gegners angreift?''		## '''Risiko-Berater:'''<br/>''Wie viele Armeen bleiben übrig, wenn man z.B. mit 23 Armeen 20 Armeen des Gegners angreift?''
	## '''Wie schwimmt man am schnellsten quer durch den Rhein?'''<br/>''Das Problem ist, dass die Strömung in der Mitte stärker wird, d.h. ab wann sollte man einfach "quer" schwimmen (und dann am Strand wieder zurücklaufen).<br/>Folgende Grundannahmen: Der Rhein ist 400m breit. Die Strömungsgeschwindigkeit (in m/s) wird durch folgende Funktion gegeben: f(x) = -(1/20000)x<sup>2</sup> + (1/50)x (D.h. in der Rheinmitte ist die Strömung dann 2m/s.) Der Schwimmer hat eine Geschwindigkeit von 1,5m/s (das schafft ein Leistungssportler auf 400m). Wenn er am Ufer zurücklaufen muss, ist seine Geschwindigkeit auch 1,5m/s.''
	## '''Stau an der Tankstelle:'''<br/>''Es gibt 4 Zapfsäulen, 1x Tanken dauert 5min. Es gibt n Autos. Jedes Auto muss im Schnitt alle 100 Stunden tanken (mal schneller, mal weniger schnell.)''<br/>''Wie viele Autos kann die Tankstelle bedienen, ohne dass es zu Stau kommt?''<br/>''Das kann man am elegantesten mit Multithreading lösen.''
	## '''Stau auf der Autobahn:'''<br/>''Zwei Spuren werden an einer Baustelle auf eine Spur zusammengeführt.''<br/>''Welche Auswirkungen hat das Fahrverhalten (insbesondere Geschwindigkeit und Abstand halten) auf die Staubildung?<br/>''Das kann man am elegantesten mit Multithreading lösen.''
	## ''VIELE andere Simulationen sind denkbar!!!'''		## ''VIELE andere Simulationen sind denkbar!!!'''
			# '''Wie schwimmt man am schnellsten quer durch den Rhein?'''<br/>''Das Problem ist, dass die Strömung in der Mitte stärker wird, d.h. ab wann sollte man einfach "quer" schwimmen (und dann am Strand wieder zurücklaufen).<br/>Folgende Grundannahmen: Der Rhein ist 400m breit. Die Strömungsgeschwindigkeit (in m/s) wird durch folgende Funktion gegeben: f(x) = -(1/20000)x<sup>2</sup> + (1/50)x (D.h. in der Rheinmitte ist die Strömung dann 2m/s.) Der Schwimmer hat eine Geschwindigkeit von 1,5m/s (das schafft ein Leistungssportler auf 400m). Wenn er am Ufer zurücklaufen muss, ist seine Geschwindigkeit auch 1,5m/s.''
	# '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit]		# '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit]
	# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Insertion-Heuristik und Farthest-Insertion-Heuristik zum Lösen des TSP für viele (d.h. mehr als 20) Städte<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]		# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Insertion-Heuristik und Farthest-Insertion-Heuristik zum Lösen des TSP für viele (d.h. mehr als 20) Städte<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]

Akaibel: /* Themen für die Projektarbeit */

2022-02-20T17:03:36Z

Themen für die Projektarbeit

← Nächstältere Version		Version vom 20. Februar 2022, 17:03 Uhr
Zeile 53:		Zeile 53:
	Als Ideengeber eignet sich u.a. die Seite '''[https://www-i1.informatik.rwth-aachen.de/~algorithmus/liste.php Algorithmus der Woche (RWTH Aachen)]'''.<br/>Einige der Algorithmen werden unten auch genannt.		Als Ideengeber eignet sich u.a. die Seite '''[https://www-i1.informatik.rwth-aachen.de/~algorithmus/liste.php Algorithmus der Woche (RWTH Aachen)]'''.<br/>Einige der Algorithmen werden unten auch genannt.

	# '''Scratch:'''<br/>Die folgenden Probleme lassen sich mit Scratch bearbeiten~~.<br/>''Den ersten Zugriff auf diese Probleme haben SchülerInnen~~, ~~die in der Q1 nicht mehr Informatik haben~~.''		# '''Scratch:'''<br/>Die folgenden Probleme lassen sich am besten mit Scratch bearbeiten, weil man eine grafische Oberfläche braucht.
	## '''Planetenbahnen zeichnen:'''<br/>''Aus den Gesetzen der Schwerkraft kann man Näherungen gewinnen, so dass man (näherungsweise) Schritt für Schritt eine Planetenbahn zeichnen kann.'' <br/>''[https://de.wikipedia.org/wiki/Newtonsches_Gravitationsgesetz Gravitationsgesetz(Wikipedia)]''		## '''Planetenbahnen zeichnen:'''<br/>''Aus den Gesetzen der Schwerkraft kann man Näherungen gewinnen, so dass man (näherungsweise) Schritt für Schritt eine Planetenbahn zeichnen kann.'' <br/>''[https://de.wikipedia.org/wiki/Newtonsches_Gravitationsgesetz Gravitationsgesetz(Wikipedia)]''
	## '''(SEHR SCHWER:) Eine Doppelfeder simulieren:''' <br/>''Aus physikalischen Gesetzen das Verhalten einer Doppelfeder näherungsweise darstellen.''		## '''(SEHR SCHWER:) Eine Doppelfeder simulieren:''' <br/>''Aus physikalischen Gesetzen das Verhalten einer Doppelfeder näherungsweise darstellen.''
	~~## '''Integrale näherungsweise berechnen mit der Trapezregel:'''<br/>Abschätzung der Genauigkeit mit mathematischen Mitteln.~~
	~~## '''Pi berechnen mit einem rekursiven Algorithmus:''' <br/>Einen geeigneten rekursiven Algorithmus recherchieren, seine Herleitung, Genauigkeit~~
	~~## '''Ausweg aus einem Labyrinth mit dem Pledge-Algorithmus.<br/>Vergleiche "6. Algorithmus der Woche."~~
	~~## '''Ternary Search: Die Suche nach einem Maximum in einer Funktion, die überall rechts gekrümmt ist.'''<br/>[https://en.wikipedia.org/wiki/Ternary_search Wikipedia (en): Ternary search]~~
	# '''Simulationen:'''<br/>''Bei Simulationen gehört zur Projektarbeit auch die Abschätzung der Güte der Simulation, das heißt z.B.: Wie groß ist das Konfidenzintervall (von 99%) für das tatsächliche Verhalten des simulierten Ereignisses? Oder: wie oft muss man simulieren, damit die Abweichung vom tatsächlichen Ergebnis (mit einer Wahrscheinlichkeit von 99%) maximal 0,1% beträgt?''<br/>''Dafür braucht man etwas Statistik, die in aller Kürze hier erklärt wird: [[Algorithmen:_Mathematik]].''		# '''Simulationen:'''<br/>''Bei Simulationen gehört zur Projektarbeit auch die Abschätzung der Güte der Simulation, das heißt z.B.: Wie groß ist das Konfidenzintervall (von 99%) für das tatsächliche Verhalten des simulierten Ereignisses? Oder: wie oft muss man simulieren, damit die Abweichung vom tatsächlichen Ergebnis (mit einer Wahrscheinlichkeit von 99%) maximal 0,1% beträgt?''<br/>''Dafür braucht man etwas Statistik, die in aller Kürze hier erklärt wird: [[Algorithmen:_Mathematik]].''
	## '''Kniffel-Berater:'''<br/>''Was ist eine optimale Strategie, wenn man nur den oberen Bereich (1-6) füllen will? Wie viele Punkte kann man im Schnitt erwarten?''		## '''Kniffel-Berater:'''<br/>''Was ist eine optimale Strategie, wenn man nur den oberen Bereich (1-6) füllen will? Wie viele Punkte kann man im Schnitt erwarten?''
Zeile 67:		Zeile 63:
	## '''Stau an der Tankstelle:'''<br/>''Es gibt 4 Zapfsäulen, 1x Tanken dauert 5min. Es gibt n Autos. Jedes Auto muss im Schnitt alle 100 Stunden tanken (mal schneller, mal weniger schnell.)''<br/>''Wie viele Autos kann die Tankstelle bedienen, ohne dass es zu Stau kommt?''<br/>''Das kann man am elegantesten mit Multithreading lösen.''		## '''Stau an der Tankstelle:'''<br/>''Es gibt 4 Zapfsäulen, 1x Tanken dauert 5min. Es gibt n Autos. Jedes Auto muss im Schnitt alle 100 Stunden tanken (mal schneller, mal weniger schnell.)''<br/>''Wie viele Autos kann die Tankstelle bedienen, ohne dass es zu Stau kommt?''<br/>''Das kann man am elegantesten mit Multithreading lösen.''
	## '''Stau auf der Autobahn:'''<br/>''Zwei Spuren werden an einer Baustelle auf eine Spur zusammengeführt.''<br/>''Welche Auswirkungen hat das Fahrverhalten (insbesondere Geschwindigkeit und Abstand halten) auf die Staubildung?<br/>''Das kann man am elegantesten mit Multithreading lösen.''		## '''Stau auf der Autobahn:'''<br/>''Zwei Spuren werden an einer Baustelle auf eine Spur zusammengeführt.''<br/>''Welche Auswirkungen hat das Fahrverhalten (insbesondere Geschwindigkeit und Abstand halten) auf die Staubildung?<br/>''Das kann man am elegantesten mit Multithreading lösen.''
	~~## '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit]~~
	## ''VIELE andere Simulationen sind denkbar!!!'''		## ''VIELE andere Simulationen sind denkbar!!!'''
			# '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit]
	# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Insertion-Heuristik und Farthest-Insertion-Heuristik zum Lösen des TSP für viele (d.h. mehr als 20) Städte<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]		# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Insertion-Heuristik und Farthest-Insertion-Heuristik zum Lösen des TSP für viele (d.h. mehr als 20) Städte<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]
	# '''Fehler-Erkennungs-Algorithmen:'''<br/>zwei ausgewählte darstellen und an Beispielen testen.<br/>[https://de.wikipedia.org/wiki/Fehlerkorrekturverfahren Fehlerkorrekturverfahren(Wikipedia)]		# '''Fehler-Erkennungs-Algorithmen:'''<br/>zwei ausgewählte darstellen und an Beispielen testen.<br/>[https://de.wikipedia.org/wiki/Fehlerkorrekturverfahren Fehlerkorrekturverfahren(Wikipedia)]
Zeile 80:		Zeile 76:
	# '''Ein Stromnetz optimal planen (Kruskal):'''<br/>'''Minimale Spannbäume berechnen mit dem Algorithmus von Kruskal'''<br/>[https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal Algorithmus-von-Kruskal-(Wikipedia)]		# '''Ein Stromnetz optimal planen (Kruskal):'''<br/>'''Minimale Spannbäume berechnen mit dem Algorithmus von Kruskal'''<br/>[https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal Algorithmus-von-Kruskal-(Wikipedia)]
	# '''Suchen in O(1):'''<br>Hashing <br>[https://de.wikipedia.org/wiki/Hashfunktion Wikipedia: Hash-Funktion] <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo34.php Algorithmus der Woche]		# '''Suchen in O(1):'''<br>Hashing <br>[https://de.wikipedia.org/wiki/Hashfunktion Wikipedia: Hash-Funktion] <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo34.php Algorithmus der Woche]
	# '''Projektwoche: Wie verteilt man die Schüler auf Projekte?'''<br/>1000 Schüler und 50 Projekte; an jedem Projekt dürfen max. 25 Schüler teilnehmen. Jeder Schüler hat 3 Wunschprojekte und 3 "geht-so"-Projekte angegeben.<br/>Wie verteilt man die Schüler, so dass möglichst viele in ein Wunschprojekt kommen?<br/>Wie gewährleistet man, dass die Verteilung fair ist?<br/>Anhand welcher Kriterien entscheidet man, ob eine Verteilung "gut" ist?
	# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]		# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]
			## '''Integrale näherungsweise berechnen mit Trapezen bzw. mit Rechtecken:'''<br/>Vergleich der Konvergenzgeschwindigkeit.
			## '''Pi (oder die Eulersche Zahl e) berechnen mit einem geeigneten Algorithmus:''' <br/>Einen geeigneten rekursiven Algorithmus recherchieren, programmieren, Genauigkeit
			## '''Ternary Search: Die Suche nach einem Maximum in einer Funktion, die überall rechts gekrümmt ist.'''<br/>[https://en.wikipedia.org/wiki/Ternary_search Wikipedia (en): Ternary search]
	## '''Welche Funktion erfüllt die Differentialgleichung f''(x) = - f(x) bzw. f'(x) = x + f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]<br>''Man kann das auch mit Excel angehen!''		## '''Welche Funktion erfüllt die Differentialgleichung f''(x) = - f(x) bzw. f'(x) = x + f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]<br>''Man kann das auch mit Excel angehen!''
	## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''		## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''
	## '''Die Fläche unter der Gaußschen Glockenkurve <math>f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}</math> näherungsweise bestimmen.'''<br/>''Auch Excel ist möglich''		## '''Die Fläche unter der Gaußschen Glockenkurve <math>f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}</math> näherungsweise bestimmen.'''<br/>''Auch Excel ist möglich''
	~~# '''Sortieren mit AVL-Bäumen'''~~
	# '''Bestimmung des kürzesten Weges von A nach B in einem Graph mit dem Algorithmus von Bellman-Ford:'''<br/>[https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus Wikipedia: Bellman-Ford-Algorithmus]		# '''Bestimmung des kürzesten Weges von A nach B in einem Graph mit dem Algorithmus von Bellman-Ford:'''<br/>[https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus Wikipedia: Bellman-Ford-Algorithmus]
	# '''Maximum Subarray Problem''': Aus einer Liste von Zahlen die Teilliste herausfinden, deren Summe maximal ist.'''<br/>[https://en.wikipedia.org/wiki/Maximum_subarray_problem Wikipedia (en): Maximum subarray problem]		# '''Maximum Subarray Problem''': Aus einer Liste von Zahlen die Teilliste herausfinden, deren Summe maximal ist.'''<br/>[https://en.wikipedia.org/wiki/Maximum_subarray_problem Wikipedia (en): Maximum subarray problem]

Akaibel: /* Themen für die Projektarbeit */

2019-02-24T17:05:58Z

Themen für die Projektarbeit

← Nächstältere Version		Version vom 24. Februar 2019, 17:05 Uhr
Zeile 82:		Zeile 82:
	# '''Projektwoche: Wie verteilt man die Schüler auf Projekte?'''<br/>1000 Schüler und 50 Projekte; an jedem Projekt dürfen max. 25 Schüler teilnehmen. Jeder Schüler hat 3 Wunschprojekte und 3 "geht-so"-Projekte angegeben.<br/>Wie verteilt man die Schüler, so dass möglichst viele in ein Wunschprojekt kommen?<br/>Wie gewährleistet man, dass die Verteilung fair ist?<br/>Anhand welcher Kriterien entscheidet man, ob eine Verteilung "gut" ist?		# '''Projektwoche: Wie verteilt man die Schüler auf Projekte?'''<br/>1000 Schüler und 50 Projekte; an jedem Projekt dürfen max. 25 Schüler teilnehmen. Jeder Schüler hat 3 Wunschprojekte und 3 "geht-so"-Projekte angegeben.<br/>Wie verteilt man die Schüler, so dass möglichst viele in ein Wunschprojekt kommen?<br/>Wie gewährleistet man, dass die Verteilung fair ist?<br/>Anhand welcher Kriterien entscheidet man, ob eine Verteilung "gut" ist?
	# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]		# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]
	## '''Welche Funktion erfüllt die Differentialgleichung f''(x) = f(x) bzw. f'(x) = x + f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]<br>''Man kann das auch mit Excel angehen!''		## '''Welche Funktion erfüllt die Differentialgleichung f''(x) = - f(x) bzw. f'(x) = x + f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]<br>''Man kann das auch mit Excel angehen!''
	## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''		## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''
	## '''Die Fläche unter der Gaußschen Glockenkurve <math>f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}</math> näherungsweise bestimmen.'''<br/>''Auch Excel ist möglich''		## '''Die Fläche unter der Gaußschen Glockenkurve <math>f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}</math> näherungsweise bestimmen.'''<br/>''Auch Excel ist möglich''

Akaibel: /* Themen für die Projektarbeit */

2019-02-24T17:00:50Z

Themen für die Projektarbeit

← Nächstältere Version		Version vom 24. Februar 2019, 17:00 Uhr
Zeile 82:		Zeile 82:
	# '''Projektwoche: Wie verteilt man die Schüler auf Projekte?'''<br/>1000 Schüler und 50 Projekte; an jedem Projekt dürfen max. 25 Schüler teilnehmen. Jeder Schüler hat 3 Wunschprojekte und 3 "geht-so"-Projekte angegeben.<br/>Wie verteilt man die Schüler, so dass möglichst viele in ein Wunschprojekt kommen?<br/>Wie gewährleistet man, dass die Verteilung fair ist?<br/>Anhand welcher Kriterien entscheidet man, ob eine Verteilung "gut" ist?		# '''Projektwoche: Wie verteilt man die Schüler auf Projekte?'''<br/>1000 Schüler und 50 Projekte; an jedem Projekt dürfen max. 25 Schüler teilnehmen. Jeder Schüler hat 3 Wunschprojekte und 3 "geht-so"-Projekte angegeben.<br/>Wie verteilt man die Schüler, so dass möglichst viele in ein Wunschprojekt kommen?<br/>Wie gewährleistet man, dass die Verteilung fair ist?<br/>Anhand welcher Kriterien entscheidet man, ob eine Verteilung "gut" ist?
	# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]		# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]
	## '''Welche Funktion erfüllt die Differentialgleichung f'(x) = x * f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]<br>''Man kann das auch mit Excel angehen!''		## '''Welche Funktion erfüllt die Differentialgleichung f''(x) = f(x) bzw. f'(x) = x + f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]<br>''Man kann das auch mit Excel angehen!''
	## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''		## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''
	## '''Die Fläche unter der Gaußschen Glockenkurve <math>f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}</math> näherungsweise bestimmen.'''<br/>''Auch Excel ist möglich''		## '''Die Fläche unter der Gaußschen Glockenkurve <math>f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}</math> näherungsweise bestimmen.'''<br/>''Auch Excel ist möglich''

Akaibel: /* Themen für die Projektarbeit */

2019-02-24T16:48:37Z

Themen für die Projektarbeit

← Nächstältere Version		Version vom 24. Februar 2019, 16:48 Uhr
Zeile 63:		Zeile 63:
	## '''Kniffel-Berater:'''<br/>''Was ist eine optimale Strategie, wenn man nur den oberen Bereich (1-6) füllen will? Wie viele Punkte kann man im Schnitt erwarten?''		## '''Kniffel-Berater:'''<br/>''Was ist eine optimale Strategie, wenn man nur den oberen Bereich (1-6) füllen will? Wie viele Punkte kann man im Schnitt erwarten?''
	## '''Poker-Berater:'''<br/>''Welche Chancen hat man mit einem gegebenen Blatt, das Spiel gegen 3 weitere Spieler zu gewinnen?''		## '''Poker-Berater:'''<br/>''Welche Chancen hat man mit einem gegebenen Blatt, das Spiel gegen 3 weitere Spieler zu gewinnen?''
	## '''Risiko-Berater:'''<br/>''Wie viele Armeen bleiben übrig, wenn man z.B. mit 23 Armeen 20 Armeen des Gegners angreift?'''		## '''Risiko-Berater:'''<br/>''Wie viele Armeen bleiben übrig, wenn man z.B. mit 23 Armeen 20 Armeen des Gegners angreift?''
	## '''Wie schwimmt man am schnellsten quer durch den Rhein?'''<br/>''Das Problem ist, dass die Strömung in der Mitte stärker wird, d.h. ab wann sollte man einfach "quer" schwimmen (und dann am Strand wieder zurücklaufen).<br/>Folgende Grundannahmen: Der Rhein ist 400m breit. Die Strömungsgeschwindigkeit (in m/s) wird durch folgende Funktion gegeben: f(x) = -(1/20000)x<sup>2</sup> + (1/50)x (D.h. in der Rheinmitte ist die Strömung dann 2m/s.) Der Schwimmer hat eine Geschwindigkeit von 1,5m/s (das schafft ein Leistungssportler auf 400m). Wenn er am Ufer zurücklaufen muss, ist seine Geschwindigkeit auch 1,5m/s.''		## '''Wie schwimmt man am schnellsten quer durch den Rhein?'''<br/>''Das Problem ist, dass die Strömung in der Mitte stärker wird, d.h. ab wann sollte man einfach "quer" schwimmen (und dann am Strand wieder zurücklaufen).<br/>Folgende Grundannahmen: Der Rhein ist 400m breit. Die Strömungsgeschwindigkeit (in m/s) wird durch folgende Funktion gegeben: f(x) = -(1/20000)x<sup>2</sup> + (1/50)x (D.h. in der Rheinmitte ist die Strömung dann 2m/s.) Der Schwimmer hat eine Geschwindigkeit von 1,5m/s (das schafft ein Leistungssportler auf 400m). Wenn er am Ufer zurücklaufen muss, ist seine Geschwindigkeit auch 1,5m/s.''
	## '''Stau an der Tankstelle:'''<br/>''Es gibt 4 Zapfsäulen, 1x Tanken dauert 5min. Es gibt n Autos. Jedes Auto muss im Schnitt alle 100 Stunden tanken (mal schneller, mal weniger schnell.)''<br/>''Wie viele Autos kann die Tankstelle bedienen, ohne dass es zu Stau kommt?''<br/>''Das kann man am elegantesten mit Multithreading lösen.''		## '''Stau an der Tankstelle:'''<br/>''Es gibt 4 Zapfsäulen, 1x Tanken dauert 5min. Es gibt n Autos. Jedes Auto muss im Schnitt alle 100 Stunden tanken (mal schneller, mal weniger schnell.)''<br/>''Wie viele Autos kann die Tankstelle bedienen, ohne dass es zu Stau kommt?''<br/>''Das kann man am elegantesten mit Multithreading lösen.''

Akaibel: /* Themen für die Projektarbeit */

2019-02-12T06:57:48Z

Themen für die Projektarbeit

Akaibel: /* Themen für die Projektarbeit */

2019-02-10T20:56:47Z

Themen für die Projektarbeit

Akaibel: /* Themen für die Projektarbeit */

2019-02-10T20:52:14Z

Themen für die Projektarbeit

← Nächstältere Version		Version vom 10. Februar 2019, 20:52 Uhr
Zeile 73:		Zeile 73:
	# '''Aus einer Liste von 1.000.000 Codes möglichst schnell den häufigsten finden.'''<br/>Dafür braucht man Hashmaps, d.h. das Hashing-Verfahren muss erklärt werden.		# '''Aus einer Liste von 1.000.000 Codes möglichst schnell den häufigsten finden.'''<br/>Dafür braucht man Hashmaps, d.h. das Hashing-Verfahren muss erklärt werden.
	# '''Backtracking:'''<br/>Backtracking ist eine Form des systematischen Ausprobierens. Vergleiche [[Backtracking]]		# '''Backtracking:'''<br/>Backtracking ist eine Form des systematischen Ausprobierens. Vergleiche [[Backtracking]]
	~~## '''Rucksackproblem:''' <br>Pareto-optimale Punkte nutzen<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo15.php Algorithmus der Woche]~~
	## '''Graphen so einfärben, dass benachbarte Knoten nicht die gleiche Farbe haben: Wie viele Farben braucht man dafür?'''<br/>[https://en.wikipedia.org/wiki/Graph_coloring Wikipedia (en): Graph Coloring]		## '''Graphen so einfärben, dass benachbarte Knoten nicht die gleiche Farbe haben: Wie viele Farben braucht man dafür?'''<br/>[https://en.wikipedia.org/wiki/Graph_coloring Wikipedia (en): Graph Coloring]
	## '''~~Magische 4x4 Quadrate berechnen~~:'''<br/>~~Systematisches Probieren z~~.B. ~~mit Backtracking~~		## '''Springerproblem:'''<br/>Der Springer soll auf einem Schachbrett alle Felder ab-"springen", ohne dabei 2x auf dasselbe Feld zu kommen. [https://de.wikipedia.org/wiki/Springerproblem Springerproblem (Wikipedia)]
	# '''Konvexe Hülle:''' <br/>Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.		# '''Konvexe Hülle:''' <br/>Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.

	# '''Optimale Verkehrsplanung:''' <br>Maximale Flüsse<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo23.php Algorithmus der Woche]		# '''Optimale Verkehrsplanung:''' <br>Maximale Flüsse<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo23.php Algorithmus der Woche]
	# '''Ein Stromnetz optimal planen (Prim):'''<br/>'''Minimale Spannbäume berechnen mit dem Algorithmus von Prim'''<br/>[https://de.wikipedia.org/wiki/Algorithmus_von_Prim Algorithmus-von-Prim-(Wikipedia)]		# '''Ein Stromnetz optimal planen (Prim):'''<br/>'''Minimale Spannbäume berechnen mit dem Algorithmus von Prim'''<br/>[https://de.wikipedia.org/wiki/Algorithmus_von_Prim Algorithmus-von-Prim-(Wikipedia)]

Akaibel: /* formale Anforderungen */

2019-02-10T20:47:41Z

formale Anforderungen

← Nächstältere Version		Version vom 10. Februar 2019, 20:47 Uhr
Zeile 34:		Zeile 34:
	Für die Projektarbeit gelten dieselben formalen Anforderungen wie für eine Facharbeit.		Für die Projektarbeit gelten dieselben formalen Anforderungen wie für eine Facharbeit.

	Die formalen Anforderungen finden sich hier: [http://sibi-honnef.de/~~index.php~~/oberstufe~~/facharbeit.html~~ SIBI-Homepage: ~~Facharbeit~~]		Die formalen Anforderungen finden sich hier: [http://www.sibi-honnef.de/die-schule/oberstufe SIBI-Homepage: Oberstufe]

	''Außerdem gibt es auf dieser Seite auch Vorlagen für die Formatierung einer Arbeit! (Sowohl MS-Word als auch LibreOffice-Writer.) Am einfachsten lädt man sich die Vorlage runter und schreibt darin seine Arbeit - dann ist die Formatierung "automatisch" richtig.''		''Außerdem gibt es auf dieser Seite auch Vorlagen für die Formatierung einer Arbeit! (Sowohl MS-Word als auch LibreOffice-Writer.) Am einfachsten lädt man sich die Vorlage runter und schreibt darin seine Arbeit - dann ist die Formatierung "automatisch" richtig.''

	==Teamarbeit?!==		==Teamarbeit?!==

← Nächstältere Version		Version vom 12. Februar 2019, 06:57 Uhr
Zeile 69:		Zeile 69:
	## '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit]		## '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit]
	## ''VIELE andere Simulationen sind denkbar!!!'''		## ''VIELE andere Simulationen sind denkbar!!!'''
	# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-~~Neighbor~~-Heuristik zum Lösen des TSP für ~~n>18~~<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]		# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Insertion-Heuristik und Farthest-Insertion-Heuristik zum Lösen des TSP für viele (d.h. mehr als 20) Städte<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]
	# '''Fehler-Erkennungs-Algorithmen:'''<br/>zwei ausgewählte darstellen und an Beispielen testen.<br/>[https://de.wikipedia.org/wiki/Fehlerkorrekturverfahren Fehlerkorrekturverfahren(Wikipedia)]		# '''Fehler-Erkennungs-Algorithmen:'''<br/>zwei ausgewählte darstellen und an Beispielen testen.<br/>[https://de.wikipedia.org/wiki/Fehlerkorrekturverfahren Fehlerkorrekturverfahren(Wikipedia)]
	# '''Aus einer Liste von 1.000.000 Codes möglichst schnell den häufigsten finden.'''<br/>Dafür braucht man Hashmaps, d.h. das Hashing-Verfahren muss erklärt werden.		# '''Aus einer Liste von 1.000.000 Codes möglichst schnell den häufigsten finden.'''<br/>Dafür braucht man Hashmaps, d.h. das Hashing-Verfahren muss erklärt werden.
Zeile 76:		Zeile 76:
	## '''Springerproblem:'''<br/>Der Springer soll auf einem Schachbrett alle Felder ab-"springen", ohne dabei 2x auf dasselbe Feld zu kommen. [https://de.wikipedia.org/wiki/Springerproblem Springerproblem (Wikipedia)]		## '''Springerproblem:'''<br/>Der Springer soll auf einem Schachbrett alle Felder ab-"springen", ohne dabei 2x auf dasselbe Feld zu kommen. [https://de.wikipedia.org/wiki/Springerproblem Springerproblem (Wikipedia)]
	# '''Konvexe Hülle:''' <br/>Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.		# '''Konvexe Hülle:''' <br/>Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.

	# '''Optimale Verkehrsplanung:''' <br>Maximale Flüsse<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo23.php Algorithmus der Woche]		# '''Optimale Verkehrsplanung:''' <br>Maximale Flüsse<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo23.php Algorithmus der Woche]
	# '''Ein Stromnetz optimal planen (Prim):'''<br/>'''Minimale Spannbäume berechnen mit dem Algorithmus von Prim'''<br/>[https://de.wikipedia.org/wiki/Algorithmus_von_Prim Algorithmus-von-Prim-(Wikipedia)]		# '''Ein Stromnetz optimal planen (Prim):'''<br/>'''Minimale Spannbäume berechnen mit dem Algorithmus von Prim'''<br/>[https://de.wikipedia.org/wiki/Algorithmus_von_Prim Algorithmus-von-Prim-(Wikipedia)]
Zeile 83:		Zeile 82:
	# '''Projektwoche: Wie verteilt man die Schüler auf Projekte?'''<br/>1000 Schüler und 50 Projekte; an jedem Projekt dürfen max. 25 Schüler teilnehmen. Jeder Schüler hat 3 Wunschprojekte und 3 "geht-so"-Projekte angegeben.<br/>Wie verteilt man die Schüler, so dass möglichst viele in ein Wunschprojekt kommen?<br/>Wie gewährleistet man, dass die Verteilung fair ist?<br/>Anhand welcher Kriterien entscheidet man, ob eine Verteilung "gut" ist?		# '''Projektwoche: Wie verteilt man die Schüler auf Projekte?'''<br/>1000 Schüler und 50 Projekte; an jedem Projekt dürfen max. 25 Schüler teilnehmen. Jeder Schüler hat 3 Wunschprojekte und 3 "geht-so"-Projekte angegeben.<br/>Wie verteilt man die Schüler, so dass möglichst viele in ein Wunschprojekt kommen?<br/>Wie gewährleistet man, dass die Verteilung fair ist?<br/>Anhand welcher Kriterien entscheidet man, ob eine Verteilung "gut" ist?
	# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]		# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]
	## '''Welche Funktion erfüllt die Differentialgleichung f'(x) = x * f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]		## '''Welche Funktion erfüllt die Differentialgleichung f'(x) = x * f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]<br>''Man kann das auch mit Excel angehen!''
	## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''		## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''
			## '''Die Fläche unter der Gaußschen Glockenkurve <math>f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}</math> näherungsweise bestimmen.'''<br/>''Auch Excel ist möglich''
	# '''Sortieren mit AVL-Bäumen'''		# '''Sortieren mit AVL-Bäumen'''
	# '''Bestimmung des kürzesten Weges von A nach B in einem Graph mit dem Algorithmus von Bellman-Ford:'''<br/>[https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus Wikipedia: Bellman-Ford-Algorithmus]		# '''Bestimmung des kürzesten Weges von A nach B in einem Graph mit dem Algorithmus von Bellman-Ford:'''<br/>[https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus Wikipedia: Bellman-Ford-Algorithmus]

← Nächstältere Version		Version vom 10. Februar 2019, 20:56 Uhr
Zeile 85:		Zeile 85:
	## '''Welche Funktion erfüllt die Differentialgleichung f'(x) = x * f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]		## '''Welche Funktion erfüllt die Differentialgleichung f'(x) = x * f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]
	## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''		## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''
	# '''P-NP-Problem am Beispiel: ''Lässt sich eine Landkarte mit 3 Farben einfärben?'''''<br>''Zur Klasse '''P''' gehören alle Entscheidungsprobleme, die in polynomieller Zeit '''gelöst''' werden können.<br>Zur Klasse '''NP''' gehören alle Entscheidungsprobleme, bei denen die Antwort "JA" in polynomieller Zeit '''verifiziert''' werden kann.'' <br>Es soll aufgezeigt werden, dass das 3-Farben-Problem nicht zur Klasse P, aber zur Klasse NP gehört. <br>Außerdem soll die Bedeutung von NP-vollständigen Problemen für die Algorithmik an diesem Beispiel erläutert werden.<br>''Das ist eine rein theoretische Arbeit!''<br>[https://de.wikipedia.org/wiki/Färbung_(Graphentheorie) Wikipedia: Färbung eines Graphen]<br>[http://www14.in.tum.de/lehre/2008WS/ea/EA-12.pdf Erläuterung von P und NP]<br>[https://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme Wikipedia: 21 NP-vollständige Probleme]
	# '''Sortieren mit AVL-Bäumen'''		# '''Sortieren mit AVL-Bäumen'''
	# '''Bestimmung des kürzesten Weges von A nach B in einem Graph mit dem Algorithmus von Bellman-Ford:'''<br/>[https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus Wikipedia: Bellman-Ford-Algorithmus]		# '''Bestimmung des kürzesten Weges von A nach B in einem Graph mit dem Algorithmus von Bellman-Ford:'''<br/>[https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus Wikipedia: Bellman-Ford-Algorithmus]
	# '''Maximum Subarray Problem''': Aus einer Liste von Zahlen die Teilliste herausfinden, deren Summe maximal ist.'''<br/>[https://en.wikipedia.org/wiki/Maximum_subarray_problem Wikipedia (en): Maximum subarray problem]		# '''Maximum Subarray Problem''': Aus einer Liste von Zahlen die Teilliste herausfinden, deren Summe maximal ist.'''<br/>[https://en.wikipedia.org/wiki/Maximum_subarray_problem Wikipedia (en): Maximum subarray problem]
	# '''Longest common subsequence: Gegeben sind zwei Listen von Wörtern. Finde die längste Teilliste, die in beiden Listen (in der entsprechenden Reihenfolge enthalten ist!'''<br/>[https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Example Wikipedia (en): longest common subsequence problem]		# '''Longest common subsequence:'''<br/>Gegeben sind zwei Listen von Wörtern. Finde die längste Teilliste, die in beiden Listen (in der entsprechenden Reihenfolge enthalten ist!'''<br/>[https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Example Wikipedia (en): longest common subsequence problem]
	# '''Zuordnungsproblem: 90 Taxis sind über eine Stadt verteilt. Jetzt bestellen 90 Kunden ein Taxi. Welches Taxi fährt zu welchem Kunden, so dass die Kunden insgesamt am kürzesten warten müssen?<br/>[https://de.wikipedia.org/wiki/Zuordnungsproblem Wikipedia: Zuordnungsproblem]		# '''Zuordnungsproblem:'''<br/>90 Taxis sind über eine Stadt verteilt. Jetzt bestellen 90 Kunden ein Taxi. Welches Taxi fährt zu welchem Kunden, so dass die Kunden insgesamt am kürzesten warten müssen?<br/>[https://de.wikipedia.org/wiki/Zuordnungsproblem Wikipedia: Zuordnungsproblem]
	# '''Vergleichbasiertes Ranking:<br>~~'''~~ Gegeben sind z.B. 100 Marken. Die Nutzer sollen immer 2 von ihnen vergleichen. Wie kann daraus eine Bewertung der Marken erstellen?<br/>Man braucht dafür den Algorithmus der ELO-Punkte im Schach.<br/>Marc Zuckerberg verwendete diesen Algorithmus für seine (skandalträchtige) Software ''Facemash''.		# '''Vergleichbasiertes Ranking:'''<br> Gegeben sind z.B. 100 Marken. Die Nutzer sollen immer 2 von ihnen vergleichen. Wie kann daraus eine Bewertung der Marken erstellen?<br/>Man braucht dafür den Algorithmus der ELO-Punkte im Schach.<br/>Marc Zuckerberg verwendete diesen Algorithmus für seine (skandalträchtige) Software ''Facemash''.
	# '''Monte-Carlo- und Las-Vegas-Algorithmen:'''<br/>Das sind Algorithmen, die Zufall nutzen, um eine beste oder näherungsweise beste Lösung zu finden.		# '''Monte-Carlo- und Las-Vegas-Algorithmen:'''<br/>Das sind Algorithmen, die Zufall nutzen, um eine beste oder näherungsweise beste Lösung zu finden.
	## '''Der Miller-Rabin-Test'''<br/>findet Primzahlen mit mehr als 500 Stellen.		## '''Der Miller-Rabin-Test'''<br/>findet Primzahlen mit mehr als 500 Stellen.
	## '''Das Hubschrauber-Problem:'''<br/>Es gibt 500 weit verstreute Häuser. Wo sollte der Standort für einen Hubschrauber sein, damit jedes Haus möglichst schnell erreicht werden kann?<br/>''"Kleinster umschließender Kreis", vgl. "42. Algorithmus der Woche".''		## '''Das Hubschrauber-Problem:'''<br/>Es gibt 500 weit verstreute Häuser. Wo sollte der Standort für einen Hubschrauber sein, damit jedes Haus möglichst schnell erreicht werden kann?<br/>''"Kleinster umschließender Kreis", vgl. "42. Algorithmus der Woche".''
			# ''(Das folgende Problem ist ein rein theoretisches, d.h. hier wird gar nicht programmiert!)''<br/>'''P-NP-Problem am Beispiel: ''Lässt sich eine Landkarte mit 3 Farben einfärben?'''''<br>''Zur Klasse '''P''' gehören alle Entscheidungsprobleme, die in polynomieller Zeit '''gelöst''' werden können.<br>Zur Klasse '''NP''' gehören alle Entscheidungsprobleme, bei denen die Antwort "JA" in polynomieller Zeit '''verifiziert''' werden kann.'' <br>Es soll aufgezeigt werden, dass das 3-Farben-Problem nicht zur Klasse P, aber zur Klasse NP gehört. <br>Außerdem soll die Bedeutung von NP-vollständigen Problemen für die Algorithmik an diesem Beispiel erläutert werden.<br>''Das ist eine rein theoretische Arbeit!''<br>[https://de.wikipedia.org/wiki/Färbung_(Graphentheorie) Wikipedia: Färbung eines Graphen]<br>[http://www14.in.tum.de/lehre/2008WS/ea/EA-12.pdf Erläuterung von P und NP]<br>[https://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme Wikipedia: 21 NP-vollständige Probleme]