kap10.tex

\documentclass[main.tex]{subfiles}
\begin{document}

\chapter{Algorithmik}
\chapterauthor{Rémy}

\section{Algorithmen und Programmierung}
\begin{Definition}
	Algorithmen besitzen die folgenden charakteristischen Eigenschaften:
	\begin{itemize}
		\item Eindeutigkeit: ein Algorithmus darf keine widersprüchliche Beschreibung haben. Diese muss eindeutig sein.
		\item Ausführbarkeit: jeder Einzelschritt muss ausführbar sein.
		\item Finitheit (= Endlichkeit): die Beschreibung des Algorithmus muss endlich sein.
		\item Terminierung: nach endlich vielen Schritten muss der Algorithmus enden und ein Ergebnis liefern.
		\item Determiniertheit: der Algorithmus muss bei gleichen Voraussetzungen stets das gleiche Ergebnis liefern.
		\item   Determinismus: zu jedem Zeitpunkt der Ausführung besteht höchstens eine Möglichkeit der Fortsetzung. Der Folgeschritt ist also eindeutig bestimmt.
	\end{itemize}
\end{Definition}

Diese Eigenschaften können in der Mathematik genutzt werden, um Probleme zu lösen. Hierfür bedarf es einer einheitlichen Schreibweise.

Insbesondere vor dem Abitur stehen den Schülern mehrere Möglichkeiten zur Verfügung, die im Folgenden behandelt werden.

\subsection{Pseudocode}
Pseudocode ist ein Programmcode, der nicht zur maschinellen Interpretation, sondern lediglich zur Veranschaulichung eines Algorithmus dient. Meistens ähnelt er höheren Programmiersprachen, gemischt mit natürlicher Sprache und mathematischer Notation. Er ist leichter verständlich als realer Programmcode aber klarer und weniger missverständlich als eine Beschreibung in natürlicher Sprache.
\begin{Beispiel}
	Ein Beispiel erübrigt sich.
\end{Beispiel}

\subsection{Python}
Programmiersprache, bekannt durch ihre einfach verständliche Syntax, sie gilt als höhere Sprache, was sie zu einer auf die (gesprochene) Sprache angepasste Sprache macht. Sie ist somit gerade für Einsteiger interessant und eignet sich dennoch für größere Projekte. Ein weiterer Vorteil ist die mitlerweile allgegenwärtige Präsenz der Sprache, denn sie wird auch für Apps und Web-Entwicklung verwendet.

\subsubsection{Syntax}
Folgendes macht die Syntax Pythons aus:

\begin{itemize}
\item gute Lesbarkeit des Quellcodes
\item englische Schlüsselwörter
\item wenig syntaktische Konstruktionen
\end{itemize}

\subsubsection{Funktionsweise}
Python verwendet Schleifen und Verzweigungen.

\begin{lstlisting}[language=Python]
	#Schleifen:
	for: #(Wiederholung ueber Elemente einer Sequenz (Zahl, Liste, Zeit...))
		#Inhalt der Schleife
	while: #(Wiederholung, solange ein logischer Ausdruck wahr ist)
		#Inhalt der Schleife

	#Verzweigungen:
	if: #(prueft,ob ein logischer Ausdruck wahr ist)
		#Inhalt der Verzweigung
	elif: #(prueft,ob ein anderer logischer Ausdruck wahr ist)
		#Inhalt der Verzweigung
	else: #(letzter Fall, tritt ein, wenn keine der obigen Bedingungen erfuellt wurde)
		#Inhalt der Verzweigung
\end{lstlisting}
\begin{Beispiel}
	Man nehme den Algorithmus, der die Fibonacci-Sequenz bis zum $n$-ten Glied generiert:
	
	\begin{lstlisting}[language=Python]
		a = 0
		b = 1
		n = 10
		for iteration in range(n):
			print(a)
			a = a+b
			b = a-b
	\end{lstlisting}
\end{Beispiel}


\section{Algorithmen und mathematische Anwendungen}
\subsection{Iterationsverfahren}

Unter Iteration versteht man ein Verfahren zur schrittweisen Annäherung an die Lösung einer Gleichung unter Anwendung eines sich wiederholenden Rechengangs. Das bedeutet, (wenn es möglich ist) aus einer Näherungslösung durch Anwenden eines Algorithmus zu einer besseren Näherungslösung zu kommen und die Lösung beliebig gut an die exakte Lösung heranzuführen. Man sagt dann, dass die Iteration konvergiert.

Beispiele für Verfahren dieser Art werden im Folgenden behandelt.


\subsubsection{Newton-Rhapson Verfahren}
Das Newton-Rhapson Verfahren, auch bekannt als Newtonmethode dient der Nullstellenbestimmung komplexer Polynome und allgemein jeder differenzierbaren Funktion.

Die Grundidee ist, die Nullstelle der Tangente an der Stelle $x_0$ von $f$ zu nehmen und den Vorgang mit $f($NS$_T)$ zu wiederholen.

Eine mögliche Umsetzung in Python wäre:

\begin{lstlisting}[language=Python]
	def fx(x):
		return 3*x**3+5x**2+3					#beliebige Funktion (muss angegeben werden)

	def f_strich(x):
		return 9*x**2+10*x						#muss auch manuell angegeben werden

	def NS_Tangente(x):
		NS_T = x - fx(x)/f_strich(x)
		return NS_T

	Startwert=1
	altwert = NS_Tangente(Startwert)
	Genauigkeit = 0.00001

	while abs(altwert-NS_Tangente(altwert))>Genauigkeit:
		altwert=NS_Tangente(altwert)
	print(altwert)

\end{lstlisting}

\subsubsection{Heron-Verfahren}
Es handelt sich hierbei um eine vereinfachte Version des Newton-Rhapson Verfahrens, da es zur Berechnung einer Näherung der Quadratwurzel einer reellen Zahl $a>0$ dient.

Man erhält das gewünschte Ergebnis durch die Berechnung der Nullstelle einer Funktion $f(x)=x^{2}-a$. Es gilt also: $f'(x)=2x$.

Durch die Verwendung des Newton-Rhapson Verfahrens erhält man die Iterationsvorschrift:

$x_{n+1}=x_{n}-\dfrac{f(x_{n})}{f'(x_{n})}$

$\Leftrightarrow x_{n+1}=x_{n}-\dfrac{x_{n}^{2}-a}{2x_{n}}=\dfrac{x_{n}^{2}+a}{2x_{n}}=\dfrac{1}{2}\left (x_{n}+\dfrac{a}{x_{n}}\right )$

Als kluger, ungefähr zutreffender Startwert gilt $x_0=\dfrac{a+1}{2}$

Eine mögliche Umsetzung in Python wäre:

\begin{lstlisting}[language=Python]
	a=2															#Muss manuell angegeben werden
	def fx(x):
		return x**2-a

	def f_strich(x):
		return 2*x

	def next_val(wert):
		return 0.5*(wert+(a/wert))

	Startwert=(a+1)/2
	altwert = next_val(Startwert)
	Genauigkeit = 0.00001

	while abs(altwert-next_val(altwert))>Genauigkeit:
		altwert=next_val(altwert)
	print(altwert)
\end{lstlisting}

\end{document}