diff options
| -rw-r--r-- | .gitignore | 11 | ||||
| -rw-r--r-- | ECM 7.tex | 260 |
2 files changed, 271 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..765cf1b --- /dev/null +++ b/.gitignore @@ -0,0 +1,11 @@ +*.lock +*.db +*.aux +*.bbl +*.fdb_latexmk +*.fls +*.log +*.out +*.pdf +*.synctex.gz +*.toc
\ No newline at end of file diff --git a/ECM 7.tex b/ECM 7.tex new file mode 100644 index 0000000..3a2d0d5 --- /dev/null +++ b/ECM 7.tex @@ -0,0 +1,260 @@ +\documentclass[12pt]{article} + +% try removing packages if errors happen. package may need to be installed to your Tex Distribution manually. + + +% Encoding and language +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +\usepackage[ngerman]{babel} + +% Math +\usepackage{mathtools} +\usepackage{amsmath} +\usepackage{amssymb} +\usepackage{amsfonts} +\usepackage{amsthm} + +\newcommand{\lt}{<} +\newcommand{\gt}{>} +\newtheoremstyle{customtheorem} + {}{}{}{}{\bfseries}{:}{ }{} +\theoremstyle{customtheorem} +\newtheorem*{lemma}{Lemma} +\newtheorem*{theorem}{Satz} +\renewenvironment{proof}{{\\ \bfseries Beweis:\pushQED{\qed}}}{\popQED\\} + +% Graphics +\usepackage{epsfig} +\usepackage{graphicx} + +% URLs and hyperlinks +\usepackage{hyperref} +\usepackage{url} + +% Colors +\usepackage{xcolor} + +% Page geometry +\usepackage[a4paper, margin=2.5cm]{geometry} + +% Better tables +\usepackage{array} +\usepackage{booktabs} + +% Nicer lists +\usepackage{enumitem} + +% For nicer captions (optional) +\usepackage{caption} + +% For code listings (optional) +\usepackage{listings} +\lstset{ + literate={→}{$\rightarrow$}1 {←}{$\leftarrow$}1, + basicstyle=\ttfamily +} + + + +%footer and header +\usepackage{fancyhdr} +% +\pagestyle{fancy} +\fancyhf{} % clear defaults + +% +\fancyhead[L]{ \small{Linnea Gräf \& Lexi Naatz}} +\fancyhead[R]{\small{ Einführung in die computerorientierte Mathematik }} +\renewcommand{\footrulewidth}{0.4pt} +\fancyfoot[L]{\small{ Goethe Universität Frankfurt am Main}} + + +\title{Einführung in die computerorientierte Mathematik} +\author{ Linnea Gräf \& Lexi Naatz \\ Tutorium Gruppe 3 } +\date{\today} + +\begin{document} +\begin{titlepage} + \Huge + \maketitle +\end{titlepage} +\tableofcontents\pagebreak + +\section{Übung 7} +Weitere Aufgaben hier als \verb|\subsection{}|. +\subsection{Fibonacci-Zahlen} +\begin{lemma} + $\forall m,n \in \mathbb N : ggT(m, m+n) = ggT(m,n)$. + \begin{proof} + \begin{align*} + ggT(m,m+n) &= ggT((m + n) \mod m, m) \\ + &= ggT(((m \mod m) + (n \mod m)) \mod m, m) \\ + &= ggT((0 + (n \mod m)) \mod m, m) \\ + &= ggT(n \mod m, m) \\ + &= ggT(m, n) + \end{align*} + \end{proof} +\end{lemma} + +\begin{theorem} + Zwei auffeinanderfolgende Fibonacci-Zahlen sind teilerfremd. + \begin{proof} + Zwei Zahlen $a,b$ sind teilerfremd, genau dann wenn $ggT(a,b) = 1$. + Es ist also zu zeigen, dass $ggT(f_a, f_{a+1}) = 1$. Wir benutzen eine Induktion über die natürlichen Zahlen. + + \textbf{Induktionsanfang}. $ggT(f_0, f_1) = ggT(0, 1) = 1$. + + \textbf{Induktionsschritt}. Wir wissen, dass $a > 0$, also ist es für uns möglich $f_{a+1}$ über die rekursive Definition umzuformen. $ggT(f_a, f_{a+1}) = ggT(f_a, f_a + f_{a-1}) = ggT(f_a, f_{a-1})$. Aus der Induktionsvorraussetzung wissen wir, dass $ggT(f_a, f_{a-1}) = 1$. + + + \end{proof} +\end{theorem} + +Anbei ist eine \href{https://live.lean-lang.org//#codez=HYewLghmCWLABAIkKiEj4F4B88ByUBQ+AJgKYBm8Z0ARvAFzzLyBJhI/PvJwD7wAMG2Xh27wAjALHD4PBAGp4AJgkAKKrWABKePNU14yuWI0bCYABYkQAJxIBbSjQD6ALxJWQ9fbtq8t6Plp0/lZkADb45pY29mqOcCSeyt5GGClB8CHhkdZ2DtSOYADuII4ADqEArgDO+ggMyCacDElqtbIKfvqtmtpdegayosbG9MFhphY59gDmAMZEjlUkoWSOEEQLVtDTZmD69nWMjZ54YAB0c0Tw9sr28j3+pxfz1/B1/tQAnsJWhfAA2k9Lo4bLMADS4KDPBazEC2WwQp7rBa2EBEMFSTiQ86ohZLFaIqGudxrDaEnFoxy4jFYrFA+aOWHwiGABMJsdCQSRZgBdCZRXLA2JVCqzWaOEgARziwASBk8DWEDHpV2SPWSAyGnXE6S+wmgwCIIpgcDe8EK0HMwh4xI8WExvwBsRt5I5NscoXIYAhsXivJEwtF8FK8DMAntf3+sSKJXK1RdyMZcJurVKWkcNNpdKhwPxqwTWx2XvZwKZCJDvIAxLMLLMANbwQVOANiyXShKiXhAA}{Formalisierung des oberen Beweises in Lean4} (mit minimaler Nutzung der Standardbibliothek, außer da wo ich zu faul wurde Aussagen über den ggT zu beweisen.) +\begin{lstlisting} +def fib : Nat → Nat + | 0 => 0 + | 1 => 1 + | n + 2 => (fib n) + (fib (n + 1)) + +theorem fib_zero : ((fib 0) = 0) := rfl +theorem fib_one : ((fib 1) = 1) := rfl +theorem fib_two_plus (n : Nat) + : ((fib (n+2) = (fib n) + (fib (n+1)))) := rfl + +theorem gcd_self_add_right (m n : Nat) + : Nat.gcd m (m + n) = Nat.gcd m n := by + rw [Nat.gcd_rec, Nat.gcd_comm, Nat.add_mod, + Nat.mod_self, Nat.zero_add, Nat.mod_mod, + Nat.gcd_comm, ← Nat.gcd_rec] + +theorem gcd_fib_succ_eq_one (n : Nat) + : Nat.gcd (fib n) (fib (n+1)) = 1 := by + induction n with + | zero => + rw [fib_zero, Nat.gcd_zero_left, fib_one] + | succ p h => + rw [fib_two_plus, Nat.add_comm (fib p) _, + Nat.gcd_self_add_right, Nat.gcd_comm, h] +\end{lstlisting} + +\subsection{Lineare Differenzgleichung} +Finden Sie für die folgenden linearen Differenzengleichungen eine Lösung: +\begin{itemize} +\item $a_n = 7 a_{n-1} - 10 a_{n-2}$ mit $a_0 = 2, a_1 = 3$ +\item $a_n = 6 a_{n-1} - 11 a_{n-2} + 6 a_{n-3}$ mit $a_0 = 3, a_1 = 6, a_2 = 14$ +\end{itemize} + +\subsubsection*{Lösung (a): $a_n = 7 a_{n-1} - 10 a_{n-2}$} + +Das charakteristische Polynom $\lambda^2 - 7\lambda + 10 = 0$ hat Nullstellen $\lambda_1 = 5$ und $\lambda_2 = 2$. + +Die allgemeine Lösung ist $a_n = c_1 \cdot 5^n + c_2 \cdot 2^n$. + +Mit den Anfangsbedingungen ergibt sich das Gleichungssystem: +\begin{align*} + c_1 + c_2 &= 2 \\ + 5c_1 + 2c_2 &= 3 +\end{align*} + +Lösung: $c_1 = -\frac{1}{3}$, $c_2 = \frac{7}{3}$. + +$$ + \boxed{a_n = -\frac{1}{3} \cdot 5^n + \frac{7}{3} \cdot 2^n} +$$ + +\subsubsection*{Lösung (b): $a_n = 6 a_{n-1} - 11 a_{n-2} + 6 a_{n-3}$} + +Das charakteristische Polynom $\lambda^3 - 6\lambda^2 + 11\lambda - 6 = 0$ hat Nullstellen $\lambda_1 = 1$, $\lambda_2 = 2$, und $\lambda_3 = 3$. + +Die allgemeine Lösung ist $a_n = c_1 + c_2 \cdot 2^n + c_3 \cdot 3^n$. + +Mit den Anfangsbedingungen ergibt sich das Gleichungssystem: +\begin{align*} + c_1 + c_2 + c_3 &= 3 \\ + c_1 + 2c_2 + 3c_3 &= 6 \\ + c_1 + 4c_2 + 9c_3 &= 14 +\end{align*} + +Lösung: $c_1 = 1$, $c_2 = 1$, $c_3 = 1$. + +$$ + \boxed{a_n = 1 + 2^n + 3^n} +$$ + +\subsubsection*{Berechnung mit SymPy} + +\begin{lstlisting}[language=Python] +import sympy as sp + +# Problem (a): a_n = 7*a_{n-1} - 10*a_{n-2} +lam = sp.Symbol('lambda') +char_poly_a = lam**2 - 7*lam + 10 +roots_a = sp.solve(char_poly_a, lam) # [2, 5] + +# Solve linear system for coefficients +c1, c2 = sp.symbols('c1 c2') +eq1 = sp.Eq(c1 + c2, 2) # a_0 = 2 +eq2 = sp.Eq(5*c1 + 2*c2, 3) # a_1 = 3 +sol_a = sp.solve([eq1, eq2], [c1, c2]) +# sol_a = {c1: -1/3, c2: 7/3} + +n = sp.Symbol('n', integer=True, positive=True) +a_n = sol_a[c1] * 5**n + sol_a[c2] * 2**n +# a_n = 7*2**n/3 - 5**n/3 + +# Problem (b): a_n = 6*a_{n-1} - 11*a_{n-2} + 6*a_{n-3} +char_poly_b = lam**3 - 6*lam**2 + 11*lam - 6 +roots_b = sp.solve(char_poly_b, lam) # [1, 2, 3] + +# Solve linear system for coefficients +c1, c2, c3 = sp.symbols('c1 c2 c3') +eq1 = sp.Eq(c1 + c2 + c3, 3) # a_0 = 3 +eq2 = sp.Eq(c1 + 2*c2 + 3*c3, 6) # a_1 = 6 +eq3 = sp.Eq(c1 + 4*c2 + 9*c3, 14) # a_2 = 14 +sol_b = sp.solve([eq1, eq2, eq3], [c1, c2, c3]) +# sol_b = {c1: 1, c2: 1, c3: 1} + +b_n = sol_b[c1] + sol_b[c2] * 2**n + sol_b[c3] * 3**n +# b_n = 2**n + 3**n + 1 +\end{lstlisting} + +\subsection{\LaTeX. I} + +\begin{theorem} + Die Folge + $$ + x_n := \sum_{k=1}^{N}\frac{1}{k^2} + $$ + ist eine Cauchy-Folge. + \begin{proof} + Zu zeigen ist: $\forall \varepsilon \gt 0 \exists N \in \mathbb N$ + mit $\left|x_n - x_m\right|\lt\varepsilon, \forall m,n \gt N$. + + Also + \begin{align} + \left|x_n - x_m\right| + &= \left|\sum_{k=1}^{n}\frac{1}{k^2} - \sum_{k=1}^{m}\frac{1}{k^2}\right| \\ + &= \sum_{k=m+1}^{n}\frac{1}{k^2} \\ + &\lt \sum_{k=m+1}^{n}\frac{1}{k(k-1)} \\ + &= \sum_{k=m+1}^{N}(\frac{1}{k-1} - \frac{1}{k}) \\ + &= \frac{1}{m} - \frac{1}{n} \stackrel{!}{\lt} \varepsilon + \end{align} + \dots + \end{proof} + % {\tiny\textsubscript{i know that there is no \qed in the template but i cant be fucked changing my proof env just for this}} +\end{theorem} + +\subsection{\LaTeX. II} + +Ist dieses ganze Dokument \cite{1}. + +\pagebreak +\addcontentsline{toc}{section}{Literatur} +\begin{thebibliography}{1} + \bibitem{1} Donald E. Knuth. \textit{The art of Computer Programming.} Addison-Wesley, 1968-. + \bibitem{2} Thorsten Theobald und Saidk Iliman. \textit{Einführung in die computerorientierte Mathematik mit Sage.} Springer-Verlag, 2016. +\end{thebibliography} + +\end{document} |