-
Notifications
You must be signed in to change notification settings - Fork 0
/
input-clean.txt
1 lines (1 loc) · 61.9 KB
/
input-clean.txt
1
pdflatex=q/xelatex-8bit-shell-escape-synctex=1%O%S/\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\setlength{\parindent}{0in}\newcommand{\uebungsGruppe}{1}\newcommand{\zettelNummer}{1}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle\begin{aufgabe}SeiG:=(V,E)einzusammenhngender,ungerichteterGraphmitexakteinemPfadproKnotenpaarundnicht-leerer,endlicherKnotenmenge.Zuzeigen:\sum_{v\inV}deg(v)=2(|V|-1)AlleberdenBeweisbetrachtetenGraphenhabendiebeschriebenenEigenschaften.BeweisberInduktion,berdieAnzahlderKnoten|V|:\textbf{I.A.}\\SeiG:=(V,E)mit|V|=1.\\AlsoE=\emptysetausdenEigenschaften.\\Also\forallv\inV,\deg(v)=0.\\Also\sum_{v\inV}deg(v)=0=2(|V|-1).\\\textbf{I.V.}\\Sein\in\mathbb{N}^+.\\\forallG:=(V,E)mit|V|=ngilt:\sum_{v\inV}deg(v)=2(n-1)\textbf{I.S.}\\SeiG:=(V,E)mit|V|=n+1.\\AusdenEigenschaftenvonGfolgt:\\EsgibteinenKnotenv_{Blatt}mitdeg(v_{Blatt})=1.\\WirbetrachtendeninduziertenTeilgraphG':=(V',E')mitV'=V\backslash\{v_{Blatt}\}.\\FrG'giltausI.V.\sum_{v\inV'}deg_{G'}(v)=2(n-1)E\backslashE'=\{v_{Blatt},v_{Parent}\}\forallv\inV:deg_G(v)=\begin{aligned}\begin{cases}1&\text{wenn}v=v_{Blatt}\\deg_{G'}(v)+1&\text{wenn}v=v_{Parent}\\deg_{G'}(v)&\text{sonst}\end{cases}\end{aligned}Also:\sum_{v\inV}deg_{G}(v)=2(n-1)+22(n-1)+2=2((n+1)-1)=2(|V|-1)\qed\end{aufgabe}\begin{aufgabe}Zuzeigen:\foralln\in\mathbb{N}:\sum_{i=1}^{n}i^3=\frac{n^2\cdot(n+1)^2}{4}BeweisberInduktion,berdien.\textbf{I.A.}\\n=1.\\Also\sum_{i=1}^{1}i^3=1^3=1.\\\frac{1^2\cdot(1+1)^2}{4}=1.\\\textbf{I.V.}\\Sein\in\mathbb{N}.\\Esgilt:\sum_{i=1}^{n}i^3=\frac{n^2\cdot(n+1)^2}{4}\textbf{I.S.}\\Zuzeigen:\sum_{i=1}^{n+1}i^3=\frac{(n+1)^2\cdot((n+1)+1)^2}{4}\begin{aligned}\sum_{i=1}^{n+1}i^3&=(n+1)^3+\sum_{i=1}^{n}i^3\\&\overset{I.V.}{=}(n+1)^3+\frac{n^2\cdot(n+1)^2}{4}\\&=\frac{4\cdot(n+1)^3}{4}+\frac{n^2\cdot(n+1)^2}{4}\\&=\frac{4\cdot(n+1)^3+n^2\cdot(n+1)^2}{4}\\&=\frac{(4\cdot(n+1)+n^2)\cdot(n+1)^2}{4}\\&=\frac{(n^2+2\cdot2\cdotn+2^2)\cdot(n+1)^2}{4}\\&=\frac{(n+2)^2\cdot(n+1)^2}{4}\\&=\frac{((n+1)+1)^2\cdot(n+1)^2}{4}\\&=\frac{(n+1)^2\cdot((n+1)+1)^2}{4}\\\end{aligned}\qed\end{aufgabe}\begin{aufgabe}\begin{teilaufgabe}LineareSucheinPseudocode:\begin{algorithm}[H]\caption{\textsc{LinSearch}(A[1,\dots,n],v)}\begin{algorithmic}[1]\For{i\gets1\ton}\If{A[i]=v}\State\textbf{Return}i\label{return:i}\EndIf\EndFor\State\textbf{Return}\textsc{Nil}\label{return:nil}\end{algorithmic}\end{algorithm}\end{teilaufgabe}\begin{teilaufgabe}SchleifeninvarianteI(i):\forallj\in[1,i):A[j]\neqv\textbf{Initialisierung}i=1\implies[1,i)=\emptyset\implies\forallj\in\emptyset:A[j]\neqv=:I(1)\textbf{Erhaltung}AngenommenI(i).WennA[i]=vdannbrechenwirabunddasEndedesSchleifendurchlaufswirdnichterreicht(sieheTermination).Sonst,wennA[i]\neqvdann:(I(i):=\forallj\in[1,i):A[j]\neqv)\landA[i]\neqv\iff\forallj\in[1,i+1):A[j]\neqv=:I(i+1)AlsogiltI(i+1)amEndedesSchleifendurchlaufs.\textbf{Terminierung}DieSchleifekannaus2Grndenbeendetwerden:\begin{enumerate}\item\textbf{Return}i(Zeile\ref{return:i})wennA[i]=v.I(i)giltgenauwieamAnfangdesSchleifendurchlaufs,wieinErhaltungbeschrieben,dawederinochAnachdererfrhtenTerminationverndertwurde.\label{return:i:description}\item\textbf{Return}\textsc{Nil}(Zeile\ref{return:nil})wenni=n+1(bestimmteModellevon\textbf{for}Endenmiti=n;dieselbeArgumentationgilt,aberdieKorrektheitmussmhseligerbegrndetwerden).I(n+1):=\forallj\in[1,n+1):A[j]\neqv\iff\forallj\in[1,n]:A[j]\neqvI(n+1)gilt,dasonstTerminationsfall\ref{return:i:description}erreichtwrde.Also:vistnichtinAenthalten,alsowird\textsc{Nil}zurckgegeben.\label{return:nil:description}\end{enumerate}DerTerminationsfall\ref{return:i:description}korrespondierenzumFall,dassimitx_i=vzurckgegebenwird.DerTerminationsfall\ref{return:nil:description}korrespondierenzumFall,dass\textbf{Nil}mit\not\existsi\in[1,n]:x_i=vzurckgegebenwird.DamiterflltderAlgorithmusdasgewnschteVerhalten.\qed\end{teilaufgabe}\begin{teilaufgabe}Laufzeitbestimmung\begin{algorithm}[H]\caption{\textsc{LinSearch}(A[1,\dots,n],v)}\begin{algorithmic}[1]\For{i\gets1\ton}\Comment{\sum_{i=1}^nT(I)}\If{A[i]=v}\Comment{O(1)}\State\textbf{Return}i\Comment{O(1)}\EndIf\EndFor\State\textbf{Return}\textsc{Nil}\Comment{O(1)}\end{algorithmic}\end{algorithm}Laufzeit:\sum_{i=1}^n(O(1)+O(1))+O(1)=O(n)\end{teilaufgabe}\end{aufgabe}\end{document}\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\setlength{\parindent}{0in}\newcommand{\uebungsGruppe}{1}\newcommand{\zettelNummer}{2}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle%Aufgabe1\begin{aufgabe}%Teilaufgabea)\begin{teilaufgabe}f(n)\subseteq\Omega(g(n))\\\Leftrightarrowg(n)\subseteq\mathcal{O}(f(n))\\\Leftrightarrow\existsc,n_0>0,sodass\foralln\gen_0:g(n)\leqc\cdotf(n)\leqc\cdotf(n)^4\\\Leftrightarrowg(n)\subseteq\mathcal{O}(f(n)^4)\\\\(c\cdotf(n)\leqc\cdotf(n)^4gilt,daf(n)strengmonotonwachsendundpositivist,frallen\gen_0)\end{teilaufgabe}%Teilaufgabeb)\begin{teilaufgabe}ZuZeigen:\mathcal{O}(f(n)+g(n))\subseteq\mathcal{O}(f(n))fallsg(n)\subseteq\mathcal{O}(f(n))\\\\Seih:N\toNweiteremonotoneFunktionmith(n)\subseteq{O}(f(n)+g(n))\\\\Esgilt:\\\\g(n)\subseteq\mathcal{O}(f(n))\\\\\Leftrightarrow\existsc_1,n_1>0sodass\foralln\gen_1:g(n)\leqc_1\cdotf(n)\\\\h(n)\subseteq\mathcal{O}(f(n)+g(n))\\\\\Leftrightarrow\existsc_2,n_2>0sodass\foralln\gen_2:h(n)\leqc_2\cdot(f(n)+g(n))\\\\\rightarrow\existsc_0,n_0>0sodass\foralln\gen_0:h(n)\leqc_2\cdot(f(n)+c_2\cdot(g(n)\leqc_2\cdotf(n)+c_2\cdotc_1\cdotf(n)=c_0\cdotf(n)mitc_0=(c_2\cdotc_1+c_2)undn_0=max\{n_1,n_2\}\\\\\Leftrightarrowh(n)\subseteq\mathcal{O}(f(n))\end{teilaufgabe}\end{aufgabe}%Aufgabe2\begin{aufgabe}WirhabendenfolgendenAlgorithmusentworfen:\begin{algorithm}[H]\renewcommand{\thealgorithm}{}\caption{FindeLngsteAbsteigendeFolge(A[1,\dots,n])}\begin{algorithmic}[1]\StatecurrentRun\gets1\Comment{O(1)}\StatelongestRun\gets1\Comment{O(1)}\For{i\gets1\ton-1}\Comment{\sum_{i=1}^{n-1}T(I)}\If{A[i]>A[i+1]}\StatecurrentRun\getscurrentRun+1\label{increment:currentRun}\Comment{O(1)}\If{currentRun>longestRun}\StatelongestRun\getscurrentRun\label{set:currentRun}\Comment{O(1)}\EndIf\Else\StatecurrentRun\gets1\label{reset:currentRun}\Comment{O(1)}\EndIf\EndFor\State\textbf{Return}longestRun\Comment{O(1)}\end{algorithmic}\end{algorithm}\textbf{Laufzeitanalyse:}O(1)+\sum_{i=1}^{n-1}O(1)=O(1)+O(n)=O(n)AlleOperationeninderSchleifebentigen\mathcal{O}(1).DieSchleifewirdnmalausgefhrt,weshalbdieAsymptotischeWorst-CaseLaufzeit\mathcal{O}(n)betrgt.\\\textbf{Korrektheit:}Hilfsdefinitionen:\begin{aligned}¤tRun_{right}\\&:=\max\left(\left\{right-left\left|\begin{aligned}&left\in[1,right)\\&\forallj\in[left,right]:A[j]>A[j+1]\\\end{aligned}\right.\right\}\cup\left\{1\right\}\right)\\&=\text{maximaleLngeeinesbeiA[right]endendemTeilintervallsmitabsteigendenZahlen}\end{aligned}\begin{aligned}&longestRun_i\\&:=\max\left(\left\{currentRun_{right}\left|\begin{aligned}&right\in(1,i]\\\end{aligned}\right.\right\}\cup\left\{1\right\}\right)\\&=\text{maximaleLngeeinesTeilintervallsmitabsteigendenZahlenvonA[1]bisA[i]}\end{aligned}Invariante:\begin{aligned}I(i)&:=\\&longestRun=longestRun_i\\\land\\¤tRun=currentRun_i\\\end{aligned}\textbf{Initialisierung:}currentRun=1\\longestRun=1\\i=1\begin{aligned}I(1)&:=\\&longestRun=1=\max(\emptyset\cup\{1\})=longestRun_i\\\land\\¤tRun=1=\max(\emptyset\cup\{1\})=currentRun_i\\\end{aligned}\textbf{Erhaltung:}AngenommenI(i).\\FallsA[i]>A[i+1],soexistierteinbeiA[i+1]endendesTeilintervallmitabsteigendenZahlen,dessenLngeum1lngerist,alsdasTeilintervallmitabsteigendenZahlen,dassbeiA[i]endet.DamitsetztZeile\ref{increment:currentRun}currentRunaufcurrentRun_{i+1}.FallscurrentRunnungreristalslongestRun,sosetztZeile\ref{reset:currentRun}longestRunaufcurrentRun.AlsowirdlongestRunauflongestRun_{i+1}gesetzt(Aussagenber\maxzubeweisenwirddemLeserberlassen).FallsnichtA[i]>A[i+1],soexistiertkeinbeiA[i+1]endendesTeilintervallmitabsteigendenZahlen,dessenLngeum1lngerist,alsdasTeilintervallmitabsteigendenZahlen,dassbeiA[i]endet.DasTeilintervall,mitabsteigendenZahlen,dassbeiA[i+1]endethatalsoLnge1.DamitsetztZeile\ref{reset:currentRun}currentRunaufcurrentRun_{i+1}.IndiesemFallknnenwirauchfestellen,dasslongestRun_i=longestRun_{i+1}=longestRun.(Aussagenber\maxzubeweisenwirddemLeserberlassen)AlsogiltnachdemSchleifendurchlaufI(i+1).\textbf{Termination:}DieSchleifeendetnachn-1Durchlufen.DanachgiltI((n-1)+1)=I(n).DamitistlongestRun=longestRun_n,waszurckgegebenwird.\qed\end{aufgabe}%Aufgabe3\begin{aufgabe}FrdieseBeweisenehmeichandasLogBaseeist.\\1.3^{n\cdot\log(n^{3})}=3^{3\cdotn\cdot\log(n)}=(3^3)^{n\cdot\log(n)}=27^{n\cdot\log(n)}=e^{log(27^{n\cdot\log(n)})}\\\\=e^{n\cdotlog(n)\cdotlog(27)}\subseteq\mathcal{O}(e^{n\cdotlog(n)log(27)})\\\\2.101010\subseteq\mathcal{O}(1),da101010<101011\cdot1\\\\3.\sqrt[3]{n}^{\logn}=n^{\frac{1}{3}log(n)}=e^{log(n^{\frac{1}{3}log(n)})}=e^{\frac{1}{3}log(n)log(n)}=e^{\frac{1}{3}log^2(n)}\subseteq\mathcal{O}(e^{log^2(n)})\\\\4.2^{20}n^{15}\subseteq\mathcal{O}(n^{15}),da2^{20}n^{15}<2^{42}n^{15}\\\\5.5^{n-1}=\frac{1}{5}5^{n}\subseteq\mathcal{O}(5^{n})\leftrightarrow\mathcal{O}(e^{nlog(5)}),da\foralln\frac{1}{5}5^{n}<5^{n}\\\\\rightarrowOrdnungderFunktionen:2,4,3,5,1,da\mathcal{O}(1)\subseteq\mathcal{O}(n^{15})\subseteq\mathcal{O}(e^{log^2(n)})\subseteq\mathcal{O}(e^{n\cdotlog(5)})\subseteq\mathcal{O}(e^{n\cdotlog(n)log(27)})\end{aufgabe}%Aufgabe4\begin{aufgabe}%Teilaufgabea\begin{teilaufgabe}DerAlgorithmusbeginntbeidemletztenElementimArrayundverschiebtesimmerweiternachvorne,biskeinElementweitervorneimArraygreristalsdasaktuelleElement.DieswirdmitjedemElementwiederholt.\end{teilaufgabe}%Teilaufgabeb)\begin{teilaufgabe}InvarianteinnereSchleife:I_1(i):A[n-i]istdaskleinsteElementimArray(n-i,n]\\Beweis:\begin{enumerate}\itemIntialisierung:I(1)=A[n-1]istkleinstesElementin(n-1,n],wahr,dadieMengeeinelementigist.\itemErhaltung:SeidieBedingungenimSchleifendurchlaufkorrekt\\Z.z.:Invarianteistimk+1Schleifendurchlaufkorrekt\\Fallunterscheidung:\\Fall1:A[n-(k+1)]<A[n-k]\landA[n-k]istkleinstesElementinA(n-k,n]\\\RightarrowA[n-(k+1)]istkleinstesElementinA(n-(k+1),n]=:I(k+1)\\Fall2:A[n-(k+1)]>A[n-k]\\\RightarrowA[n-(k+1)]\leftrightarrowA[n-k]\\\RightarrowA[n-(k+1)]istkleinstesElementinA(n-(k+1),n]=:I(k+1)\\\rightarrowDieBedingungistimk+1Schleifendurchlaufkorrekt.\itemTerminierung:DieSchleifeterminiert,wennj=i\\\RightarrowA[i]istkleinstesElementinA(i-k,n]\end{enumerate}InvarianteuereSchleife:I_2[l]:=[1,\dots,l]istaufsteigendsortiert\\\LeftrightarrowA[m]istdaskleinsteElementvonA[m,\dots,a]\foralla\in[1,l)\begin{enumerate}\itemInitialisierung:l=1\rightarrowA[m]istdaskleinsteElementvonA[m,\dots,a]\forallk\in[1,1)istwahr.\itemErhaltung:DieSchleifeninvarianteistzuBeginndesiSchleifendurchlaufskorrekt\\Z.z.:Invarianteistimi+1Schleifendurchlaufkorrekt\\\\Esgilt:A[m]istdaskleinsteElementvonA[m,\dots,a]\foralla\in[1,i)\\(nachInduktionsbehauptung.)\landA[m]istdaskleinsteElementvonA[m,\dots,i](folgtausderinnerenSchleifeninvariante.)\\\\\rightarrowA[m]istdaskleinsteElementvonA[m,\dots,a]\foralla\in[1,i]=:I_2[i+1]\\\RightarrowDieSchleifeninvarianteistzuBeginnderi+1-Schleifedurchlaufskorrekt.\itemTerminierung:\\i=n-1\\A[m]istdaskleinsteElementvonA[m,\dots,a]\foralla\in[1,n-1)\land\\A[m]istdaskleinsteElementinA[m,\dots,n]\rightarrowA[m]istdaskleinsteElementvonA[m,\dots,a]\foralla\in[1,n)\Leftrightarrow[1,\dots,n]istaufsteigendsortiert\end{enumerate}\end{teilaufgabe}%Teilaufgabec)\begin{teilaufgabe}\begin{algorithm}[H]\renewcommand{\thealgorithm}{}\caption{Sort(A[1\dotsn])}\begin{algorithmic}[1]\For{i\gets1tolength(A)-1}\Comment{\sum_{i=1}^{n-1}T(I)}\For{j\getslength(A)downtoi+1}\Comment{\sum^{j=n}_{i+1}T(J)}\If{A[j]<A[j-1]}\Comment{1xCompare:\Theta(1)}\StateA[j-1]\leftrightarrowA[j]\Comment{1xSwap:\Theta(1)}\EndIf\EndFor\EndFor\end{algorithmic}\end{algorithm}T(J):=\Theta(1)+\Theta(1)=\Theta(1)\begin{aligned}&\sum_{i=1}^{n-1}\sum^{j=n}_{i+1}1\\=&(n-1)+(n-2)+\dots+2+1\\\\=&\frac{\begin{aligned}&(n-&1&)+(n-&2&)+\dots+&2&+&1&\\+&&1&+&2&+\dots+(n-&2&)+(n-&1&)\\\end{aligned}}{2}\\=&\frac{\overbrace{n+n+\dots+n+n}^{n-1}}{2}\\=&\frac{n\cdot(n-1)}{2}\end{aligned}Eswerdenalso\frac{n\cdot(n-1)}{2}SwapsunddieselbeAnzahlvonVergleichenbentigt.\Theta\left(\frac{n\cdot(n-1)}{2}\right)=\Theta\left(n^2\right)\end{teilaufgabe}\end{aufgabe}\end{document}defeli_pow(x,n):result=1whilen>0:ifn%2==1:result=result*xx=x*xn=(n-(n%2))/2rechtsshiftreturnresultI(n):=result*(x_var^n_var)=x_0^n^0x_i,n_i,result_ix_{i+1}=x_i\cdotx_in_{i+1}=\lfloorn_i/2\rfloorresult_{i+1}=result_i\cdotx^{n_i\mod2}result_i\cdotx^{n_i\mod2}\cdotx_i\cdotx_i\cdot\lfloorn_i/2\rfloordefdavid_pow(x,n):result=1whilen>1:ifn%2==1:result=result*xx=x*xn=n//2returnresult*xprintvaluesforpow(3,n)fornto10forninrange(0,11):print(Real:+str(pow(3,n)))print(Eli:+str(eli_pow(3,n)))print(David:+str(david_pow(3,n)))\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}\usepackage{graphicx}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\setlength{\parindent}{0in}\newcommand{\uebungsGruppe}{1}\newcommand{\zettelNummer}{1}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle\begin{aufgabe}PowinlinearerZeit:\begin{algorithm}[H]\caption{\textsc{PowLin}(x,n)}\begin{algorithmic}[1]\Stateresult\gets1\Comment{O(1)}\While{n>0}\Comment{\sigma_{i=1}^kT(I)}\If{n\mod2=1}\Comment{O(1)}\Stateresult\getsresult\cdotx\Comment{O(1)}\EndIf\Statex\getsx\cdotx\Comment{O(1)}\Staten\gets(n-(n\mod2))/2\Comment{O(1)}\EndWhile\State\textbf{Return}result\Comment{O(1)}\end{algorithmic}\end{algorithm}\textbf{Schleifeninvariante:}I(n):=result_n\cdot(x_n)^{n}=(x_{orig})^{n_{orig}}\textbf{Korrektheit:}\textbf{Initialisierung:}n=n_{orig}\\x=x_{orig}\\result=1result\cdotx^n=(x_{orig})^{n_{orig}}\textbf{Erhaltung:}Gegebenseifrdiei-teIteration:I(n_i):=result_{n_i}\cdot(x_{n_i})^{n_{n_i}}=(x_{orig})^{n_{orig}}Esgilt:I(n_i).Nunistzuzeigen:I(n_{i+1})=result_{n_{i+1}}\cdot(x_{n_{i+1}})^{n_{n_{i+1}}}=(x_{orig})^{n_{orig}}Durchfhrung:result_{n_{i+1}}=\begin{cases}result_{n_{i+1}}&\text{falls}n_{n_{i+1}}\mod2=0\\result_{n_{i+1}}\cdotx_{n_{i+1}}&\text{falls}n_{n_{i+1}}\mod2=1\\\end{cases}=result_{n_i}\cdotx^{n_{n_i}\mod2}x_{n_{i+1}}=x_{n_i}\cdotx_{n_i}=x_{n_i}^{2}n_{n_{i+1}}=\frac{(n_{n_i}-(n_{n_i}\mod2))}{2}\begin{aligned}LHS&=result_{n_{i+1}}\cdot(x_{n_{i+1}})^{n_{n_{i+1}}}\\&=(result_{n_i}\cdotx^{n_{n_i}\mod2})\cdot(x_{n_i}^{2})^{\frac{(n_{n_i}-(n_{n_i}\mod2))}{2}}\\&=result_{n_i}\cdotx^{n_{n_i}\mod2}\cdot((x_{n_i}^{2})^{\frac12})^{(n_{n_i}-(n_{n_i}\mod2))}\\&=result_{n_i}\cdotx^{(n_{n_i}\mod2)}\cdotx_{n_i}^{n_{n_i}-(n_{n_i}\mod2)}\\&=result_{n_i}\cdot(x_{n_i})^{n_{n_i}}\\&\overset{Annahme}{=}(x_{orig})^{n_{orig}}\end{aligned}\textbf{Laufzeit:}Potentialfunktion:\Psi(n)=\log(n)\\Wirbrechenab,wennn\not>0also,wenn\log(n)\not>1\\Dan_{i+1}=\frac{(n_{i}-(n_{i}\mod2))}{2}:\\\Psi(n_{i+1})\leq\Psi(n_i)-1Damit:k\inO(\frac{\Psi(n)}{1})=O(\log(n))\\O(1)+O(\log(n))+O(1)=O(\log(n))\\DamithatderAlgorithmusdieLaufzeitO(\log(n))\end{aufgabe}\begin{aufgabe}\begin{teilaufgabe}\begin{algorithm}\caption{\textsc{NonRecMergeSort}(A[1,\dots,2^k])}\begin{algorithmic}\For{i\gets1uptok}\For{j\gets0upto2^{k-i}-1}\StateMerge(A,2^i\cdotj+1,2^i\cdotj+(2^{i-1})+1,2^i\cdot(j+1))\EndFor\EndFor\end{algorithmic}\end{algorithm}\end{teilaufgabe}\begin{teilaufgabe}Hilfsdefinitionen:Sorted(A[n,\dots,m]):=\foralli\in[n,m):A[i]\leqA[i+1]Invarianten:I(i,j):=\foralll\in[0:2^{k-i}-1-j):Sorted(A[2^{i}\cdotl,\dots,2^{i}\cdot(l+1)-1])I(i):=\forallm\in[1:i):\forallj\in[0:2^{k-i}-1]:Sorted(A[2^{i}\cdotj,\dots,2^{i}\cdot(j+1)-1])\end{teilaufgabe}\end{aufgabe}\begin{aufgabe}%Image2022-04-29-DuA_3.JPG\noindent\makebox[\textwidth]{\includegraphics[width=\textwidth]{2022-04-29-DuA_3.JPG}}\end{aufgabe}\end{document}\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}\usepackage{stmaryrd}\usepackage{graphicx}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\setlength{\parindent}{0in}\newcommand{\uebungsGruppe}{110}\newcommand{\zettelNummer}{4}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}%Loadthesetspacepackage\usepackage{setspace}\doublespacing\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle\begin{aufgabe}HerleitungdergeschlossenenFormelT(n):\\Angenommenn=4^{k}\begin{aligned}T(n)&=T\left(4^{k}\right)\\&=4T\left(\frac{4^{k}}{4}\right)+\sqrt{4^{k}}\cdotc_2\\&=4\cdotT\left(4^{k-1}\right)+2^{k}\cdotc_2\\&=4\left(4\cdotT\left(4^{k-2}\right)+2^{k-1}\cdotc_2\right)+2^{k}\cdotc_2\\&=4^{2}\underbrace{T\left(4^{k-2}\right)}_\text{sukzessivesEinsetzen}+2^{k+1}\cdotc_2+2^{k}\cdotc_2\\&=4^{k}c_1+\left(\sum_{j=0}^{k-1}2^{k+i}\right)c_2\\&=4^{k}c_1+\left(2^{k}\cdot\sum_{j=0}^{k-1}2^{i}\right)c_2&|\text{geometrischeSumme}\\&=4^{k}c_1+2^{k}\left(\frac{1-2^{k}}{1-2}\right)c_2\\&=4^{k}c_1+2^{k}\left(2^{k}-1\right)c_2\\&=4^{k}\left(c_1+c_2\right)-2^{k}c_2\end{aligned}KorrektheitsbeweisderFormeldurchvollstndigeInduktion:\\Beh.:T(n)=T(4^{k})=4^{k}(c_1+c_2)-2^{k}c_2I.A.:n=1T(1)=T(4^{0})=c_1=4^{0}(c_1+c_2)-2^{0}c_2I.V.:Esgilt:T(4^{k-1})=4^{k-1}(c_1+c_2)-2^{k-1}c_2I.S.:ZuZeigen:T(n)=T(4^{k})=4^{k}(c_1+c_2)-2^{k}c_2NachDefinitionvonT(n)gilt(dan>1ist):\begin{aligned}T(n)&=T(4^{k})\\&=4T(\frac{4^{k}}{4})+\sqrt{4^{k}}\cdotc_2\\&=4\cdotT(4^{k-1})+2^{k}\cdotc_2\\&\stackrel{IV}{=}4\cdot(4^{k-1}(c_1+c_2)-2^{k-1}c_2)+\sqrt{4^{k}}\cdotc_2\\&=4^{k}(c_1+c_2)-2^{k+1}c_2+2^{k}\cdotc_2\\&=4^{k}(c_1+c_2)-2^{k}c_2\\\end{aligned}\qed\end{aufgabe}\begin{aufgabe}AusderRekursionsgleichungfolgt:a=2,b=2undf(n)=n\logn\\\Rightarrown^{\log_b(a)}=n^{\log_2(2)}=n^1\\f(n)=n\logn=n^{\log_n(n\log_2n)}=n^{\log_n(n)+\log_n\log_2(n)}=n^{1+\log_n\log_2(n)}\\DasMastertheoremkannnurangewendetwerden,\\fallsf(n)\in\mathcal{O}(n^{1-\varepsilon})\lorf(n)\in\Theta(n)\lor(f(n)\in\Omega(n^{1+\varepsilon})\landa\cdotf(\frac{n}{b})\leqc\cdotf(n))Esgilttrivialerweise:\begin{aligned}n^{1+\log_n\log_2(n)}&\not\in\mathcal{O}(n)\\\Rightarrown^{1+\log_n\log_2(n)}&\not\in\mathcal{O}(n^{1-\varepsilon})\\\text{und\quad}n^{1+\log_n\log_2(n)}&\not\in\Theta(n)\end{aligned}Istf(n)\in\Omega(n^{1+\varepsilon})?\\\iff\existsc,n_0>0,sodass\foralln\geqn_0:n^{1+\log_n\log_2(n)}\geqc\cdotn^{1+\varepsilon}\\Diesfrc=1und\varepsilon=\frac{1}{10}erfllt\\\Rightarrowf(n)\in\Omega(n^{1+\varepsilon}),aberdiezweiteBedingungistnichterfllt\\2\cdot\frac{n}{2}\log(\frac{n}{2})\leqc\cdotn\cdot\log(n)\\n\cdot\log(\frac{n}{2})\leqc\cdotn\cdot\log(n)\\DieseBedingungwirdnurvonc=1erfllt,da\displaystyle\lim_{n\rightarrow\infty}\frac{n\cdot\log(\frac{n}{2})}{n\cdotlog(n)}\\=\displaystyle\lim_{n\rightarrow\infty}\frac{\log(\frac{n}{2})}{\log(n)}\\Da\displaystyle\lim_{n\rightarrow\infty}\log(\frac{n}{2})=\infty\land\displaystyle\lim_{n\rightarrow\infty}\log(n)=\inftygilt,\\kanndieRegelvomKrankenhausangewendetwerden:)\\\displaystyle\lim_{n\rightarrow\infty}\frac{\log(\frac{n}{2})}{\log(n)}=\displaystyle\lim_{n\rightarrow\infty}\frac{\frac{\mathrm{d}}{\mathrm{d}n}\log(\frac{n}{2})}{\frac{\mathrm{d}}{\mathrm{d}n}log(n)}=\displaystyle\lim_{n\rightarrow\infty}\frac{\frac{\mathrm{d}}{\mathrm{d}n}\log(n)-\log(2)}{\frac{\mathrm{d}}{\mathrm{d}n}log(n)}\\\displaystyle\lim_{n\rightarrow\infty}\frac{\frac{1}{n}}{\frac{1}{n}}=\displaystyle\lim_{n\rightarrow\infty}1=1\quad\left[\text{d.h.siesindasympt.quiv.}\right]\\\Rightarrowc=1\lightningc<1\\\RightarrowDieRekursionsgleichungkannnichtmitdemallgemeinenMaster-Theoremanalysiertwerden\end{aufgabe}\begin{aufgabe}\begin{teilaufgabe}\begin{algorithm}[H]\caption{\textsc{3Sort}(A,i,j)}\begin{algorithmic}[1]\If{j\leqi+1}\If{A[i]>A[j]}\StateA[i]\leftrightarrowA[j]\EndIf\Statereturn\EndIf\Statek\gets\left\lfloor\frac{j-i+1}{3}\right\rfloor\State3Sort(A,i,j-k)\label{3Sort:1}\State3Sort(A,i+k,j)\label{3Sort:2}\State3Sort(A,i,j-k)\label{3Sort:3}\end{algorithmic}\end{algorithm}\end{teilaufgabe}\begin{teilaufgabe}Sein:=len(A).BeweisberInduktionbern:\\\textbf{Basisfall:}\\n=0:Trivial\\n=1:Trivial\\n=2:Mita>b:A\gets[a,b];\mathrm{3Sort}(A,0,1)\impliesA=[b,a]\\A\gets[b,a];\mathrm{3Sort}(A,0,1)\impliesA=[b,a]NunInduktion:Sein\in\mathbb{N}Angenommen3Sort(A,i,j)sortiertAwennj-i+1\leqnZuzeigenist:3Sort(A,i,j)sortiertAwennj-i+1=n+1WirbetrachteneineAusfhrungvon3Sortmitj-i+1=n+1:3SortinZeile\ref{3Sort:1}sortiertA[i:j-k],da((j-k)-i+1)=\left(\left(j-\left\lfloor\frac{j-i+1}{3}\right\rfloor\right)-i+1\right)=\left\lceil\frac{2}{3}\cdot(j-i+1)\right\rceil\leqnA=(a|b|c)wobeia,b,cdiedrittelvonAsind.DaA[i:j-k]nunsortiertist,istbekannt,dassdaszweite\frac13vonA(b)greralsdaserste\frac13vonA(a)ist.DajedesElementausanunmindestens\frac13\cdot(n+1)Elementebersichhatmitwissenwir,dasskeinElementderobersten\frac13vonA(c)imersten\frac13vonA(a)ist.AlleElemente,dieamEndeincseinsollensindnunin(b|c).NachderAusfhrungvon3SortinZeile\ref{3Sort:2}istdamitckorrektpopuliert.AlleElementevona,bbefindensichin(a|b)undchatkeineElementevonaundb.NachderAusfhrungvon3SortinZeile\ref{3Sort:3}istdamita,bkorrektpopuliert.cwurdenichtgendertundistimmernochkorrektpopuliert.NunistA=(a|b|c)sortiert.\end{teilaufgabe}\begin{teilaufgabe}T(n)=\begin{cases}1&\text{falls}n=1\\3\cdotT(\frac{2}{3}n)+1&\text{falls}n\geq2\\\end{cases}NachMastertheorem:a=3;b=\frac{3}{2};c=1Daa>b:T(n)\in\Theta(n^{\log_{}\frac{3}{2}(3)})\end{teilaufgabe}\end{aufgabe}\end{document}\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}\usepackage{graphics}\usepackage{stmaryrd}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\usepackage{graphicx}\usepackage{pdfpages}\graphicspath{{./images/}}\setlength{\parindent}{0in}\newcommand{\uebungsGruppe}{110}\newcommand{\zettelNummer}{5}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle%Aufgabe1\begin{aufgabe}\begin{teilaufgabe}Esgilt:n=4^{k}\\NachRekursionsgleichung:\\a=b=3(\impliesn^{\log_b{a}}=n^{\log_3{3}}=n)\\undf(n)=\frac{n}{4}=4^{k-1}\\n\neq3^{k}\\\impliesallgemeinesMastertheoremmussangewendetwerden.\\\\UntersuchungderLaufzeitderRekursionsgleichgungdurchdasallgemeineMastertheorem:\\\\Liegtf(n)\in\Theta(n)?\\\\f(n)\in\Theta(n)\\\iff\existsc_1,c_2,n_0>0sodass\foralln\gen_0:c_1\cdotn\leqf(n)\leqc_2\cdotn\\Diesistfrc_1=\frac{1}{8},c_2=1undn_0=42069erfllt.\\\impliesNachdemMastertheoremhatT(n)\in\mathcal{O}(n\cdotlog(n))\end{teilaufgabe}\begin{teilaufgabe}Esgilt:n=2^{k}\\NachRekursionsgleichung:\\a=8b=2(\impliesn^{\log_b{a}}=n^{\log_2{8}}=n^{3})\\undf(n)=n^{4}\cdot\log(n)\\Dan=2{k}=b^{k},aberf(n)nichtkonstantist,kanndasvereinfachteMastertheoremnichtangewendetwerden.\\UntersuchungderLaufzeitderRekursionsgleichungdurchdasallgemeineMastertheorem:\\Offentsichtlicherweisegiltf(n)\notin\Theta(n^3)\\Liegtf(n)\in\mathcal{O}(n^{3-\epsilon})?\\\\Offensichtlicherweisegiltf(n)\notin\mathcal{O}(n^{3})\\\impliesf(n)\notin\mathcal{O}(n^{3-\epsilon})\\Liegtf(n)\in\Omega(n^{3+\epsilon})?\\\\f(n)\in\Omega(n^{3+\epsilon})\\\iff\existsc,n_0>0,sodass\foralln\geqn_0:n^{4}\cdot\log(n)\geqc\cdotn^{3+\varepsilon}\\Diesistfrc=1und\epsilon=1erfllt\\Nunistnochzuberprfen,oba\cdotf(\frac{n}{b})\leqc\cdotf(n)\\\\a\cdotf(\frac{n}{b})\leqc\cdotf(n)=8\cdotf(\frac{n}{2})\leqc\cdotf(n)\\=8\cdot(\frac{n}{2})^{4}\cdot\log(\frac{n}{2})\leqc\cdotn^{4}\cdot\log(n)\\=2^{3}\cdot\frac{n^{4}}{2^{4}}\cdot\log(\frac{n}{2})\leqc\cdotn^{4}\cdot\log(n)\\=\frac{n^{4}}{2}\cdot(\log(n)-\log(2))\leqc\cdotn^{4}\cdot\log(n)\\DieseUngleichungistz.B.frc=\frac{2}{3}erfllt.\\\impliesNachdemMastertheoremgilt:f(n)\in\Theta(n^{4}\cdot\log(n),da\existsc<1\end{teilaufgabe}\end{aufgabe}%Aufgabe2\begin{aufgabe}\begin{teilaufgabe}BeweisdurchWiederspruch:o.B.d.AdaskleinsteElementkommtnichtdoppeltimHeapvor.AngenommendaskleinsteElement:=wwrekeinBlatt.\\\overset{Form-Invariante}\implieswhatkinder\overset{Heap-Invariante}\impliesdieKinderhabeneinenkleinerenWertalsw:\lightningwistkleinstesElementdesHeaps.\qed\end{teilaufgabe}\begin{teilaufgabe}Gegenbeispiel\\\includegraphics[scale=0.5]{2022-05-13-H52b.JPG}\\\end{teilaufgabe}\begin{teilaufgabe}\end{teilaufgabe}\end{aufgabe}%Aufgabe3\begin{aufgabe}Eswirdeinn-elementigerMin-Heapbetrachtet:\begin{teilaufgabe}Z.Z.:DieHhe(derWurzel)betrgt\lfloor\log(n)\rfloor\\Beweis:\\Fallunterscheidung:\\Fall1:Sei\log(n)\in\mathbb{N}.\\\overset{Form-Invariante}\impliesMinheapisteinvollstndigerBinrbaum.DadieseraufjederEbenemitdermaximalenAnzahlanKnotenbestcktist.\\\impliesInjederEbenewirddieAnzahlderKnotenverdoppelt.Diesistmaximal\log(n)malmglich.\\\implies\forallBlattknoten\existsPhadderLnge\log(n)zurWurzeldesBaumes.\\\impliesDieHhedesBaumesist\log(n)\\\\Fall2:Sei\log(n)\notin\mathbb{N}.\\\overset{Form-Invariante}\impliesMinheapisteinvollstndigerBinrbaum,bisaufdieuntersteEbene.\\\impliesInjederEbenewirddieAnzahlderWurzelnverdoppelt.Diesistmaximal\log(n-1)malmglich.DiebrigenKontensindBltterinderunterstenEbene.\\\implies\forallBlattknoteninderuntersten\existsPhadderLnge\lfloor\log(n)\rfloorzurWurzeldesBaumes.\\\impliesDieHheistBaumesist\lfloor\log(n)\rfloor\\\\\impliesAussage\qed\end{teilaufgabe}\begin{teilaufgabe}Z.Z.Esgibthchstens\lceil\frac{n}{2^{h+1}}\rceilKnotenmitderhheh\\\\BeweisdurchvollstndigeInduktionberdieHhedesBaumes:\\Seik_h:=DiemaximalAnzahlderKnotenaufHheh\\IA:h=0:DerBaumbestehtauseinemBlatt\iffn=1\\\impliesk_0=1=\lceil\frac{1}{2^{0+1}}\rceil\\IV:Esgeltefreinbeliebiges,aberfestesi:h=ik_i=\lceil\frac{n}{2^{i+1}}\rceil\\IS:Z.Z.Frh=i+1gilt:k_{i+1}=\lceil\frac{n}{2^{(i+1)+1}}\rceil=\lceil\frac{n}{2^{i+2}}\rceil\\%%Nachagilt:DieHhe(derWurzel)betrgt\lfloor\log(n)\rfloor\\%%\impliesi+1=\log(k)\landi=\lfloor\log(k+1)\rfloormitk\in\mathbb{N}\\Form-Invariante:DerBaumisteinvollstndigerBinrbaumbisaufdieunterstenEbene\\\iffk_{i+1}=\frac{1}{2}\cdotk_i\overset{I.V.}=\frac{1}{2}\cdot(\lceil\frac{n}{2^{i+1}}\rceil)=\lceil\frac{n}{2^{(i+2)}}\rceil\\(DieoberenGausklammernsindhiernotwendig,daderBaumaufderunterstenEbenenichtumbedingtvollstndigist.\\NachdemInduktionsprinzipgiltfrh=i:k_i=\lceil\frac{n}{2^{i+1}}\rceil\foralli\in\mathbb{N}\qed\end{teilaufgabe}\begin{teilaufgabe}Z.ZDieworst-caseLaufzeitvonHeapifyist\Omega(\log(n))\\Beweis:\includepdf[pages=-]{2022-05-13-DuA-beiProfGharibian-Heimblatt-05.pdf}\end{teilaufgabe}\end{aufgabe}\end{document}\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}\usepackage{graphics}\usepackage{stmaryrd}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\usepackage{graphicx}\usepackage{pdfpages}\graphicspath{{./images/}}\setlength{\parindent}{0in}\newcommand{\uebungsGruppe}{110}\newcommand{\zettelNummer}{5}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle%Aufgabe1\begin{aufgabe}%Angenommen,dieFunktionPartitonteiltTeilarraysderGrennimmerinzweiTeilarraysauf,%vondeneneines(1)nElementeunddasanderenElementeenthlt,mit1%2<1.Geben%SiedieRekursionsgleichungfurdieLaufzeitvonQuicksortunterdieserAnnahmeanundleiten%Sie(ohneVerwendungdesMasterTheorems)einegeschlosseneFormher.GebenSiezusatzlich%dieLaufzeitimO-KalklinAbhangigkeitvonundnan.\begin{algorithm}[H]\caption{\textsc{Quicksort}(A[1...n],l,r)O(f(n))}\begin{algorithmic}[1]\If{p<r}\Comment{O(1)}\Stateq\getsPartition(A,p,r)\Comment{O(n)}\StateQuicksort(A,p,q-1)\Comment{O(f(n\cdot(1-\alpha)))}\StateQuicksort(A,q+1,r)\Comment{O(f(n\cdot\alpha))}\EndIf\end{algorithmic}\end{algorithm}f(n)=n+f(n\cdot\alpha)+f(n\cdot(1-\alpha))DadieRekursionstiefefr\alpha>\frac12nichtFestistknnenwirkeineexakteGeschlosseneFormelangeben.AbereineAnalyseimO-Kalkhlistmglich:\begin{aligned}O(f(n))&=O(n+f(n\cdot(1-\alpha))+f(n\cdot\alpha))\\&=O(n+2\cdotf(n\cdot\alpha))\quad\text{da}n\cdot(1-\alpha)\leqn\cdot\alpha\\&=O(n+2\cdotn\cdot\alpha+\dots+2^{k-1}\cdotn\cdot\alpha^{k-1}+2^k\cdotf(n\cdot\alpha^k))\\&\text{fr}k=\log_{\frac{1}{\alpha}}(n)\\&=O(n+2\cdotn\cdot\alpha+\dots+2^{k-1}\cdotn\cdot\alpha^{k-1})\\&=O(n)+O(2\cdotn\cdotalpha)+\dots+O(2^{k-1}\cdotn\cdotalpha^{k-1})\\&=O(n)+\underbrace{O(n)+\dots+O(n)}_{\text{k-mal}}\\&=O(k\cdotn)\\&=O(n\cdot\log_{\frac{1}{\alpha}}(n))\end{aligned}\end{aufgabe}\begin{aufgabe}%embed2022-05-19-Blatt-6-Aufgabe-2.pdf\includepdf[pages=-]{2022-05-19-Blatt-6-Aufgabe-2.pdf}\end{aufgabe}\begin{aufgabe}\includepdf[pages=-]{2022-05-19-Blatt-6-Aufgabe-3.pdf}\end{aufgabe}\end{document}\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}\usepackage{graphics}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\usepackage{graphicx}\usepackage{pdfpages}\usepackage{tikz}\setlength{\parindent}{0in}\newcommand{\zettelNummer}{10}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle%Aufgabe1\begin{aufgabe}FrdieAdjazenzlistendarstellung:SeiG_{new}einneuerleererGraphinAdjazenzlistendarstellung.ErwirdimLaufedesAlgorithmusmitdenEintrgendesTransponiertenGraphenG^Terweitert.FrjedenKnotenvausV(G):(|V|mal)WirfgenvzuG_{new}hinzu.(O(1))FrjedenKnotenvausV(G):(|V|mal)WiriterierenberdieursprnglicheAdjazenzlisteA(v)mitv_{adj}adjazentzuv:(|A(v)|mal)WirfgenzurAdjazenzlistevonv_{adj}denKnotenvhinzu.(O(1))NunistG_{new}eineAdjazenzlistendarstellungvonG^T.Bemerkung:|V|\cdot|A(v)|=O(|E|)DasheitwirbenO(|V|+|E|)ElementareOperationenaus.DerAlgorithmusistkorrekt,weileralleundnurdieseKantenausG^TdemGraphenG_{new}hinzufgt.\rule{\textwidth}{0.5pt}FrdieAdjazenzmatrixdarstellung:SeiG_{new}einneuerkantenloserGraphinAdjazenzmatrixdarstellungberdieselbenKnotenVausG.NunseiAdieAdjazenzmatrixvonGundA_{new}dieAdjazenzmatrixvonG_{new}.Nunfr1\leqi\leq|V|:(O(|V|))Und1\leqj\leq|V|:(O(|V|))A_{new}(j,i)=A(i,j)(O(1))NunistA_{new}=A^TundG_{new}eineAdjazenzmatrixdarstellungvonG^T.DerAlgorithmusbtO(|V|^2)ElementareOperationenaus.DieKorrektheitdesAlgorithmuslsstsichausderVertauschungderIndizesiundjbegrnden.\end{aufgabe}%Aufgabe2\begin{aufgabe}DerAlgorithmus\textsc{Bipartite-Check-Breadth-First-Search}nimmteinenGraphenGundeinenStartknotens\inV.\begin{algorithm}[H]\caption{\textsc{Bipartite-Check-Breadth-First-Search}(G,s)}\begin{algorithmic}[1]\For{jedenKnotenuinV\backslash\{s\}}\Statecolor[u]\getsWHITE\State\pi[u]\getsNIL\EndFor\Statecolor[s]\getsGRAY\State\pi[s]\getsNIL\StateQ\gets\{\}\StateEnqueue(Q,s)\While{Q\neq\emptyset}\Stateu\getsDequeue(Q)\If{color[u]=GRAY}\StateotherColor\getsBLACK\Else\StateotherColor\getsGRAY\EndIf\For{jedenKnotenvinA(u)}\Comment{A(u):Nachbarnvonu}\If{color[v]=WHITE}\Statecolor[v]\getsotherColor\State\pi[v]\getsu\StateEnqueue(Q,v)\ElsIf{color[v]\neqotherColor}\State\textbf{return}\textsc{false}\EndIf\EndFor\EndWhile\State\textbf{Return}\textsc{true}\end{algorithmic}\end{algorithm}WirreduzierendasProblemderBipartitheitsprfungaufdender2-Frbbarkeit.MithilfederBreitensucheknennwirdie2-FrbungaufGversuchenundbeieinemKonfliktabbrechen.EinGraphistgenaudann2-Frbbar,wennerbipartitist.UnserAlgorithmusistdamitkorrekt,weiltruerckgibt,genaudannwennderGraph2-Frbbarist.Undweilerfalserckgibt,wennderGraphnicht2-Frbbarist.DieLaufzeiteinerBreitensucheistausderVorlesungmitO(|V|+|E|)ElementarenOperationenbekanntundwurdehierbeinurdurchElementareOperationenErweitert,weswegendieserweiterhininO(|V|+|E|)liegt.\end{aufgabe}\begin{aufgabe}DervorgeschlageneAlgorithmusbestehtaus3Phasen:1.Phase:AufteilenderKantenmitGewichtungw\neq1inw-KantenmitGewichtung1.ManfgtzustzlicheKnotenhinzuundballertdadurchzustzlicheKantenrein.Laufzeit:O(|E|\cdotk)(daw\in[1,k])2.Phase:BreitensucheLaufzeit:O((|V|+|E|)\cdotk)dawirKnotenundKantenhinzugefgthaben.3.Phase:VergessenderneuhinzugefgtenKnoten+Kanten.WirvergessendieneuhinzugefgtenKnotenundKantenindengefundenenkrzestenPfaden.Laufzeit:O(|V|\cdotk)(dawirnurErgebnissefrjedenKnotenspeichernundmaximalkKnoten+KantenproKnotenvergessen)DieGesamtlaufzeitistdamitO(|V|+|E|\cdotk)\end{aufgabe}\end{document}\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}\usepackage{graphics}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\usepackage{graphicx}\setlength{\parindent}{0in}\newcommand{\uebungsGruppe}{1}\newcommand{\zettelNummer}{7}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle%Aufgabe1\begin{aufgabe}DamitPrev(x)undSucc(x)in\mathcal{O}(1)liegen,mussmaneinezustzlicheEigenschaftfralleKnotenimBaumdefinieren.\\JederKnotenximBaumerhltzustzlicheineVerweisaufdieAdresseseinesNachfolgersundVorgngersmitN_x:=dieAdressedesNachvolgersvonxundV_x:=dieAdressedesVorgngersvonx\\DamitdiesEigenschaftaufrechterhaltenwirdmssendieEinfgen-undLschenfunktionabgendertwerden.\begin{algorithm}[H]\caption{EinfgenNeu(T,z)}\begin{algorithmic}[1]\Statey\getsnil\Statex\getsroot[T]\While{x\neqnil}1\Statey\getsx\If{key[z]<key[x]}\Statex\getslc[x]\Else\Statex\getsrc[x]\EndIf\EndWhile\Statep[z]\getsy\If{y=nil}\Stateroot[t]\getsz\StateV[z]\getsnil\StateN[z]\getsnil\Else\If{key[z]<key[y]}\Statelc[y]\getsz\StateN_{V_y}\getsz\StateV_z\getsV_y\StateV_y\getsz\StateN_z\getsy\Else\Staterc[y]\getsz\StateV_{N_y}\getsz\StateN_z\getsN_y\StateN_y\getsz\StateV_z\getsy\EndIf\EndIf\end{algorithmic}\end{algorithm}\begin{algorithm}[H]\caption{LschenNeu(T,z)}\begin{algorithmic}[1]\If{lc[z]=nil\lorrc[z]=nil}\Statey\getsz\Else\Statey\getsN_z\EndIf\If{V_y\neqnil}\StateN_{V_y}\getsN_z\EndIf\If{N_y\neqnil}\StateV_{N_y}\getsV_z\EndIf\If{V_z\neqnil}\StateN_{V_z}\getsN_z\EndIf\If{N_z\neqnil}\StateV_{N_z}\getsV_z\EndIf\If{lc[y]\neqnil}\Statex\getslc[y]\Else\Statex\getsrc[y]\EndIf\If{x\neqnil}\Statep[x]\getsp[y]\EndIf\If{p[y]=nil}\Stateroot[T]\getsx\Else\If{y=lc[p[y]]}\Statelc[p[y]]\getsx\Else\Staterc[p[y]]\getsx\EndIf\EndIf\If{y\neqz}\Statekey[y]\getskey[z]\EndIf\State\textbf{Return}y\end{algorithmic}\end{algorithm}\begin{algorithm}[H]\caption{Pred(x)}\begin{algorithmic}[1]\State\textbf{Return}key[V_x]\end{algorithmic}\end{algorithm}\begin{algorithm}[H]\caption{Succ(x)}\begin{algorithmic}[1]\State\textbf{Return}key[N_x]\end{algorithmic}\end{algorithm}\end{aufgabe}%Aufgabe2\begin{aufgabe}\includegraphics[width=\textwidth]{2022-05-28-Blatt-7-DuA7_2.JPG}\end{aufgabe}%Aufgabe3\begin{aufgabe}\begin{teilaufgabe}EswirdInorder-Tree-Walk(x),mitVertauschungvonlc[x]mitrc[x]undstatteinerAusgabewirdlist-insert(L,x)aufgerufen.\\DadurchwirdeineabsteigendeSortierungderSchlsselanlist-insertbergebenwodurcheineaufsteigendsortierteLink-listentsteht.ZumBeginndesAlgorithmuswirdxaufroot[T]gesetztunddieListeListleer.\\\begin{algorithm}[H]\caption{bin-Search-to-linked-list(T,L,x)}\begin{algorithmic}[1]\If{x\neqnil}\Statebin-Search-to-linked-list(T,L,rc[x])\StateList-Insert(L,x)\Statebin-Search-to-linked-list(T,L,lc[x])\EndIf\end{algorithmic}\end{algorithm}\end{teilaufgabe}\begin{teilaufgabe}Z.zDerAlgorithmusistKorrekt\LongleftrightarrowDieElementeinLsindaufsteigendsortiert.\\o.B.d.AIstdiesderFall,fallsList-insertdieAdressenderElementedesBaumesunddieElementeineinerabsteigendensortiertenReihenfolgebertragenwerden.\\\RightarrowEsistnurnochzuzeigen,dassdieElementedesBaumesineinerabsteigendensortiertenReihenfolgeanList-Insertbertragenwerden.(DasdieAdressendieserbertragenwerdengiltnachZeile3).\\BeweisdurchVollstndigeInduktionberdieAnzahlderElementeinesBaumesmitHilfederSuchbaumeigenschaft.\\SeiT_{n}:=einbeliebigerbinrerSuchbaummitnElementen\\IA:n=0:Trivial\\n=1:Trivial\\n=2:Trivial\\%%n=3:\\%%Seix:=dasrechtesteBlattvonT_{3}%%DerAlgorithmuswirdber:\\%%bin-Search-to-linked-list(T_{3},L,(root[T_{3}]))aufgerufen.\\%%NunwirdZeile2,solangerekursivausgefhrtbisxerreichtist.\\%%DiesesistnachderbinrenSuchbaumeigenschaftdasgrteElementvonT_{3}.\\%%DieseswirdnachZeile3anList-Insertbertragen.\\%%DannachZeile4ausgefrhrt,bisderVorgngervonxerreichtist.\\%%DiesesistnachderbinrenSuchbaumeigenschaftdaszweitgrteElementvonT_{3}.Dieseswirdbertragen.\\%%DannachwirdderAlgorithmussolangeRekursivausgefhrt,bisderVorgngervomVorgngervonxerreichtist.\\%%DiesesistnachderbinrenSuchbaumeigenschaftdasdrittgrteElementvonT_{3}.Dieseswirdbertragen.\\%%NunwurdenalleElementeaufgerufenundderAlgorithmusterminiert.\\IV:Esgelte:DerAlgorithmusbertrgtdieElementeeinesBaumesT_{n-1}ineinerabsteigendensortiertenReihenfolgekorrekt.\\IS:Z.ZDerAlgorithmusbertrgtdieElementeeinesBaumesT_{n}ineinerabsteigendensortiertenReihenfolgekorrekt.\\Esgilt:T_{n}=T_{n-1}+Einfgen(T_{n-1},n)\\NachIVgiltbereitsdasalleElementeohnenKorrektausgegebenwerden.\\FolglichistnurnochzuZeigen,dasnanderrichtigenStelleausgebenwird.\\Diesist,abertrivialerweisederFall,dabeimEinfgendieSuchbaumeigenschafterhaltenbleibt.\\\RightarrownwirdanderrichtigenStelleausgeben.NachdemInduktionsprinzipgilt,dassfreinenBaummitnelementen,dieElementedesBaumesineinerabsteigendensortiertenReihenfolgeanList-Insertbertragenwerden.\\\RightarrowDerAlgorthmusistKorrekt.\qed\end{teilaufgabe}\begin{teilaufgabe}bin-Search-to-linked-lististeineabgenderteVariantedesausderVorlesungbekanntenAlgo.Inoder-Tree-Walk.\\EsgibtzweiUnterschiedezwischenbin-Search-to-linked-listundInoder-Tree-Walk,welcheaberkeinenEinflussaufdieLaufzeithaben.\\Zumeinenwurderc[x]durchlc[x]ausgetauscht.(DieshattrivialerweisekeinenEinflussaufdieLaufzeit.)Zumanderenwurdereturnkey[x]durchList-Insert(L,x)ausgetauscht.DiesehabenbeideeineLaufzeitvon\mathcal{O}(1)(NachLemma10.10)FolglichbleibtdieLaufzeiterhalten.\\DaInoder-Tree-Walk(x)nachFolie45eineLaufzeitvon\theta(n),hatbin-Search-to-linked-listfolglichaucheineLaufzeit\theta(n)\\\end{teilaufgabe}\end{aufgabe}\end{document}\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}\usepackage{graphics}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\usepackage{graphicx}\setlength{\parindent}{0in}\newcommand{\zettelNummer}{7}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle%Aufgabe1\begin{aufgabe}\begin{teilaufgabe}Esgibt2Mglichkeitendieszuimplementieren:\\Mglichkeit1:\\Push=Enqueue.O(1)\\Pop:Enqueue(Q,Dequeue(Q))n-1-Mal,dannreturnDequeue(Q).O(n)\\Mglichkeit2:\\Pop=Dequeue.O(1)\\Push:Enqueue(Q,x),dannEnqueue(Dequeue(Q),x)n-1-Mal.O(n)\\hnlichwiebeic).\end{teilaufgabe}\begin{teilaufgabe}nistdieAnzahlderSpeicherpltzeimArray.aistdieAnzahlderElementeimStackA.bistdieAnzahlderElementeimStackB.\\\includegraphics[width=\textwidth]{2022-05-28-Blatt-8-1-b.png}\\Awchstnachrechts,Bwchstnachlinks.\\\end{teilaufgabe}\begin{teilaufgabe}ImallgemeinenistesMglichalleObjekteeinerQeueineinemderStackszuspeichern.DerzweiteStackwirdhierbeinurjeweilsbentigt,umeinederBeidenQueueoperationenDequeueoderEnqueuezurealiesieren.\\FolglichgibteszweiMglichkeitendiesbeidenzuimplementieren:\\SeiS_1derStackindemdieElementederQueuegespeichertsind.\\Mglichkeit1:DequeueistindiesemFallidentischzuPopundhatsomiteineLaufzeitvon\mathcal{O}(1)\\FrEnqueuemussderganzeStackmitPopundPushOperationenindenzweitenStackbertragenwerden.HierbeiwirddieReihenfolgederElementeinvertiert.NunwirddasneueObjektmiteinerPushOperationhinzugefgt.DannachwerdenwiederalleObjekteinStack1bertragenunddieOperationistbeendet.\\DajedePushundPopoperationeineLaufzeitvon\mathcal{O}(1)hatliegtEnqueuein\mathcal{O}(n)\\Mglichkeit2:EnqueueistindiesemFallidentischzuPushundhatsomiteineLaufzeitvon\mathcal{O}(1)\\FrDequeuemussderganzeStackmitPopundPushOperationenindenzweitenStackbertragenwerden.HierbeiwirddieReihenfolgederElementeinvertiert.NunwirddasneueObjektmiteinerPop-Operationhinzugefgt.DannachwerdenwiederalleObjekteinStack1bertragenunddieOperationistbeendet.\\DajedePushundPopoperationeineLaufzeitvon\mathcal{O}(1)hatliegtDequeuein\mathcal{O}(n)\\\end{teilaufgabe}\end{aufgabe}%Aufgabe2\begin{aufgabe}\begin{teilaufgabe}DieLogikbeimVorgehenbeieinerRechtsrotationistidentisch.\\\begin{algorithm}[H]\caption{Linksrotation(T,x)}\begin{algorithmic}[1]\Statey\getsrc[x]\Staterc[x]\getslc[x]\State\If{lc[y]\neqnil}\Statep[y]\getsp[x]\EndIf\If{p[x]=nil}\Stateroot[T]\getsy\ElsIf{x=lc[p[x]]}\Statelc[p[x]]\getsy\Else\Staterc[p[x]]\getsy\EndIf\Statelc[y]\getsx\Staterc[x]\getsy\Stateh[x]\gets1+max\{h[lc[x]],h[rc[x]]\}\Stateh[y]\gets1+max\{h[lc[y]],h[rc[y]]\}\Statesize[x]\gets1+size[lc[x]]+size[rc[x]]\Statesize[y]\gets1+size[lc[y]]+size[rc[y]]\end{algorithmic}\end{algorithm}Wobeisize[nil]=0.\begin{algorithm}\caption{SizeOf(T,x)}\begin{algorithmic}[1]\State\textbf{Return}size[x]\end{algorithmic}\end{algorithm}\end{teilaufgabe}\begin{teilaufgabe}DerAlgortihmuswirdmitderWurzeldesBaumesaufgerufen.\\\begin{algorithm}[H]\caption{k-median(T,x,k)}\begin{algorithmic}[1]\If{SizeOf(rc[x])-SizeOf(x)=k\lorlc[x]=rc[x]=Nil}\Statereturnx\EndIf\If{SizeOf(lc[x])>k-1}\Statereturnk-median(T,rc[x],SizeOf(x)-(SizeOf(rc[x]+1))\Else\Statereturnk-median(T,lc[x],k)\EndIf\end{algorithmic}\end{algorithm}BudgetLaufzeitanalyse:\\DerAlgorithmusistrekursivundruftsichselberwiederberdaslinkeoderrechteKinddesaktuellenElements.DademAlgorithmuszuBeginndieWurzelvomBaumbergebenwird,kommtesimworstcasezuhRekursionsaufrufen(,wobeihdiehhedesBaumesist)unddieLaufzeitproAufrufistkostant.FolglichhatderAlgorithmuseineLaufzeitvon\mathcal{O}(h)).DaderBetrachteteBaumeinAVL-Baumist,istnachSatz12.2gilth=\Theta(log(n)).AlsohatderAlgorithmuseineLaufzeitvon\mathcal{O}(log(n))\end{teilaufgabe}\end{aufgabe}%Aufgabe3\begin{aufgabe}JederKnotenimBaumhateinezustzlicheVariablesize,wiein2\\AuchistjederKnotenannotiertmitminundmax,welchedasMinimumunddasMaximumsdesTeilbaumsdesKnotenenthlt.\\Erstaufrufmitx=root[T]\\\begin{algorithm}[H]\caption{Schnittmengensuche(T,x,a,b)}\begin{algorithmic}[1]\If{a>b}\State\textbf{Return}0\label{terminate:a>b}\EndIf\If{x=nil}\State\textbf{Return}0\label{terminate:x=nil}\EndIf\If{key[x]<a}\State\textbf{Return}Schnittmengensuche(T,rc[x],a,b)\label{recurse:key[x]<a}\ElsIf{key[x]>b}\State\textbf{Return}Schnittmengensuche(T,lc[x],a,b)\label{recurse:key[x]>b}\Else\Statemin\getsMinimumSuche(x)\Statemax\getsMaximumSuche(x)\If{key[min]\leqa\landb\leqkey[max]}\State\textbf{Return}size[x]\label{terminate:key}\Else\Stateresult\gets1\label{result}\Stateresult\getsresult+Schnittmengensuche(T,lc[x],a,b)\Stateresult\getsresult+Schnittmengensuche(T,rc[x],a,b)\State\textbf{Return}result\EndIf\EndIf\end{algorithmic}\end{algorithm}DieIdeeist,dasswirdieSchnittmengensuchemithilfederAnnotiertenVariablensize,min,maxfrhstmglichbeendenknnen.UnddamitnurdenBaumsotiefablaufen,bisdasErgebnisKlarist.\\UnsereLaufzeitistdurchTeilbumebegrenzt,dessenEltern-KnotennichtimIntervallliegen.DaderAVLBaumbalanciertundeinBinrerSuchbaumist,befindensichdieseTeilbumemaximalaufderHhe\leq\log(n).\\Damitrekursierenwirunsmaximal\log(n)mal.\\MiteinerAdditionvonLaufzeitO(1)proEbeneistdieLaufzeit\mathcal{O}(log(n)).\\DerAlgorithmusistkorrekt,daerabZeile\ref{result}dieAnzahlderSchnittmengenklassischBerechnet,miteinerregulrenTerminationinZeile\ref{terminate:a>b}undinZeile\ref{terminate:x=nil}.DieRekursioninZeile\ref{recurse:key[x]<a}undinZeile\ref{recurse:key[x]>b}istkorrekt,dadieSchnittmengennurindenTeilbumenliegendielinksoderrechtssind.DieTerminationmitSizeinZeile\ref{terminate:key}istkorrekt,dadiedergesamtTeilbaumimgesuchtenIntervallliegt.\end{aufgabe}\end{document}\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}\usepackage{graphics}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\usepackage{graphicx}\usepackage{pdfpages}\usepackage{tikz}\setlength{\parindent}{0in}\newcommand{\zettelNummer}{9}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle%Aufgabe1\begin{aufgabe}\begin{teilaufgabe}\includepdf[pages=-]{2022-06-10-Blatt-9-Aufgabe-1-1.pdf}\end{teilaufgabe}\end{aufgabe}\begin{aufgabe}BekanntsindHashtablellenmitderBacking-Struktur``Liste''.WirersetzendieBacking-StrukturmiteinemAVL-Baum.%\textbf{Insert(T,x):}%Fallskey[x]nochnichtinBaumT[h(key[x])]vorhanden,fgexinBaumT[h(key[x])]ein.\begin{algorithm}[H]\caption{\textsc{Insert}(T,x)}\begin{algorithmic}[1]\State\textbf{Insert-AVL(T[h(key[x])],x)}\end{algorithmic}\end{algorithm}%\textbf{Delete(T,x):}%Fallskey[x]inBaumT[h(key[x])]vorhanden,entfernexausBaumT[h(key[x])].\begin{algorithm}[H]\caption{\textsc{Delete}(T,x)}\begin{algorithmic}[1]\State\textbf{Delete-AVL(T[h(key[x])],x)}\end{algorithmic}\end{algorithm}%\textbf{Search(T,x):}%Fallskey[x]inBaumT[h(key[x])]vorhanden,lieferetrue,sonstfalse.\begin{algorithm}[H]\caption{\textsc{Search}(T,x)}\begin{algorithmic}[1]\State\textbf{Search-AVL(T[h(key[x])],x)}\end{algorithmic}\end{algorithm}DieKorrektheitistdurchdiefunktionalidentischeSemantikzuHashtablellenmitBacking-Listegegeben.DurchErsetzungderBacking-Strukturder``Liste''miteinemAVL-BaumersetzenwirdiezuvorbekanntenOperationenmitWorst-CaseLaufzeitenO(n)durchO(logn).\end{aufgabe}\begin{aufgabe}\begin{teilaufgabe}BeweisdurchvollstndigeInduktionberdieKreislnge:=n:WirverwendendieKreisnotation(x_1,x_2,\cdots,x_n)freinenKreisbereinenGraphenG.\begin{tikzpicture}[nodePath/.style={circle,fill=yellow40}]\node[nodePath](n1)at(0,0){x_1};\node[nodePath](n2)at(1,1){x_2};\node[nodePath](nn)at(2,0){x_n};\foreach\from/\toin{n1/n2,nn/n1}\draw[->](\from)--(\to)node[midway,auto](){};\foreach\from/\toin{n2/nn}%dottedline\draw[dashed,->](\from)--(\to)node[midway,auto](){};\end{tikzpicture}\textbf{I.A.:}n=1:trivialn=2:WirbetrachtendieMglichenKreiseK_1=(x_1,x_2)K_2=(x_1,x_1).K_1isteineinfacherKreis.K_2isteinkomplexerKreis.K_2kannindieeinfachenKreise(x_1)und(x_1)aufgeteiltwerden.\rule{\textwidth}{0.5pt}Sein\in\mathbb{N}.\textbf{I.V.:}JederkomplexeKreismitbiszun-1KnotenkannineinfacheKreiseaufgeteiltwerden.\textbf{I.S.:}SeiK_n=(x_1,x_2,\cdots,x_{i-1},x_i,\cdots,x_{j-1},x_j\cdots,x_n)einkomplexerKreis.Existierenkein1\leqi\neqj\leqn:x_i=x_jsoistderKreiseinfach.Alsoexistieren1\leqi\leqn:x_i=x_j.NunsindK_a=(x_1,x_2,\cdots,x_{i-1},x_j,\cdots,x_n)undK_b=(x_i,x_j,\cdots,x_{j-1})Kreise.SindK_aundK_beinfach,sosindwirfertig.Sindsiekomplex,soknnenwirsienach\textbf{I.V.}ineinfacheKreiseK_a=K_{a_1}+K_{a_2}+\cdots+K_{a_k},K_b=K_{b_1}+K_{b_2}+\cdots+K_{b_l}aufteilen.NunsindistK_{a_1},K_{a_2},\cdots,K_{a_k},K_{b_1},K_{b_2},\cdots,K_{b_l}eineAufteilungvonK_nineinfacheKreise.\qed\end{teilaufgabe}\begin{teilaufgabe}``\implies'':SeiGeinGraphmiteinemEulerkreisE=(x_1,x_2,\cdots,x_{i-1},x_i,x_{i+1},\cdots,x_n).SeixeinKnoteninGundi\in\{i_1,\cdots,i_k\}diek-VorkommnissevonximEulerkreissind.Danun(x_{i-1},x_i)eineEingangskantevonxist,diemaximal1-malfreinivorkommt,istindeg(x)=k.Danun(x_i,x_{i+1})eineAusgangskantevonxist,diemaximal1-malfreinivorkommt,istoutdeg(x)=k.Damitindeg(x)=outdeg(x).\rule{\textwidth}{0.5pt}``\impliedby'':berInduktionberdieKantenanzahln.\textbf{I.A.:}n=1:trivial,daindeg\neqoutdegnichtvorkommt.\rule{\textwidth}{0.5pt}Sein\in\mathbb{N}.\textbf{I.V.:}JederGraphmitindeg(v)=outdeg(v)undmaximaln-1KantenhateinenEulerkreis.\textbf{I.S.:}SeiG=(E,V)einGraphmitindeg(v)=outdeg(v)undnKanten.Bekanntist,dasseinKreisKinGexistiert.DerKreisKgehtberdieKantenmengeE(K).DerInduzierteTeilgraphvonE\backslashE(K):G_\text{ind}hatimmernochindeg(v)=outdeg(v),daKiminduzierteTeilgraphvonE(K)einEulerkreisist.Nach\textbf{I.V.}hatG_\text{ind}einenEulerkreis,wirnennenihnK_\text{ind}.WirbetrachteneinenKnotenv\inV(K).WirstellenK_\text{ind}alsK_\text{ind}=(v_1,v_2,\cdots,v_{i-1},v_i,v_{i+1},\cdots,v_k)dar,wobeiv=v_i.WirstellenKalsK=(x_1,x_2,\cdots,x_{j-1},x_j,x_{j+1},\cdots,x_l)dar,wobeiv_i=v=x=x_j.Nunist(v,v_{i+1},\cdots,v_k,v_1,\cdots,v_{i-1},v,x_{j+1},\cdots,x_l,x_1,\cdots,x_{j-1})einEulerkreisinG.\end{teilaufgabe}\end{aufgabe}\end{document}binarytreeinpythonclassNode:def__init__(self,value):self.value=valueself.left=Noneself.right=Noneself.parent=Noneforprintdef__repr__(self):return(N:+str(self.value)+)classBinarySearchTreeWithPreviousAndNext:We'llmaintainadict`prev`and`next`def__init__(self):self.root=Noneself.prev={}self.next={}definsert(self,value):node_x=self.rootnode_y=Nonenode_z=Node(value)whilenode_x=None:node_y=node_xifvalue<node_x.value:node_x=node_x.leftelse:node_x=node_x.rightnode_z.parent=node_yifnode_y==None:self.root=node_zself.prev[node_z]=Noneself.next[node_z]=Noneelse:ifnode_z.value<node_y.value:node_y.left=node_zself.next[self.prev[node_y]]=node_zself.prev[node_z]=self.prev[node_y]self.prev[node_y]=node_zself.next[node_z]=node_yelse:node_y.right=node_zself.prev[self.next[node_y]]=node_zself.next[node_z]=self.next[node_y]self.next[node_y]=node_zself.prev[node_z]=node_ydefsearch(self,value):node_x=self.rootwhilenode_x=None:ifvalue==node_x.value:returnnode_xifvalue<node_x.value:node_x=node_x.leftelse:node_x=node_x.rightreturnNonedefdelete(self,node_z):node_zisthenodetodeleteifnode_z.left==Noneornode_z.right==None:node_y=node_zelse:node_y=self.next[node_z]ifself.prev[node_y]=None:self.next[self.prev[node_y]]=self.next[node_z]ifself.next[node_y]=None:self.prev[self.next[node_y]]=self.prev[node_z]ifself.prev[node_z]=None:self.next[self.prev[node_z]]=self.next[node_z]ifself.next[node_z]=None:self.prev[self.next[node_z]]=self.prev[node_z]ifnode_y.left=None:node_x=node_y.leftelse:node_x=node_y.rightnode_xisthechildofnode_yandtakesnode_y'splaceifnode_x=None:node_x.parent=node_y.parentparentofnode_yisnowparentofnode_xifnode_y.parent==None:self.root=node_xifnode_ywasroot,node_xisnowrootelse:sinceitwasn'taroot,ithadaparentifnode_y==node_y.parent.left:node_y.parent.left=node_xelse:node_y.parent.right=node_xnode_xisnowthechildofnode_y'sparentifnode_y=node_z:node_z.value=node_y.valuenode_zisnownode_yreturnnode_ydefoutput_in_order(self):usesself.nextstartsatleftmostvalueoutput=[]node_x=self.rootwhilenode_x.left=None:ifnode_x.left=None:node_x=node_x.leftwhilenode_x=None:output.append(node_x.value)node_x=self.next[node_x]returnoutputimportrandomif__name__==__main__:values=[5,3,7,2,4,6,8]values=[1,2,1]valuesis10randomvaluesvalues=[random.randint(0,1000)foriinrange(40)]print(values)bst=BinarySearchTreeWithPreviousAndNext()forvalueinvalues:bst.insert(value)first_value=values[0]deleteinlistandtreevalues.remove(first_value)bst.delete(bst.search(first_value))output=bst.output_in_order()print(output)values.sort()print(values)printifbothareequalprint(output==values)\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amssymb}\usepackage{amsmath}\usepackage{graphics}\usepackage{stmaryrd}%Pseudocode\usepackage{algorithm}\usepackage[noend]{algpseudocode}\usepackage{graphicx}\usepackage{pdfpages}\usepackage{tikz}\setlength{\parindent}{0in}\newcommand{\zettelNummer}{11}\newcommand{\studierenderEins}{EliKogan-Wang(7251030)}\newcommand{\studierenderZwei}{DavidNoahStamm(7249709)}\newcommand{\studierenderDrei}{DanielHeins(7213874)}\newcommand{\studierenderVier}{TimWolf(7269381)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\newcommand{\qed}{\hfill\square}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}\\\studierenderVier{}}\maketitle%Aufgabe1\begin{aufgabe}SeiG=(V,E)einungerichteterGraph.\textbf{Zuzeigen}:NachDFS(G,s)freins\inVistjedevonserreichbareKanktee\inE_{\text{connected}s}eineBaumkantedesDFS-Baums,eineRckwrts/Vorwrtskante.\textbf{Beweis}:Seie\inE_{\text{connected}s}einevonserreichbareKante.Dasheit,dassfre={v_1,v_2}mitv_1\neqv_2,derStartknotenv_1imDFS-Baumliegt,unddaderBaumbzgl.derZusammenhangskomponentevonsvollstndigist,auchv_2imDFS-Baumliegt.NunlsstsicheineFallunterscheidungdurchfhren:WenneimDFS-Baumliegt,dannisteeineBaumkante.WennenichtimDFS-Baumliegt,dannisteeineRckwrts/Vorwrtskante.DaezweiKnotenausdemDFS-Baumverbindet.Betrachtetmanealsgerichtet,sokannmanbetrachten,obv_1vorodernachv_2indertopologischenSortierungdesBaumesvorkommt.\end{aufgabe}\begin{aufgabe}WirbeginnenmitdemErgebnisdesAlgorithmusTran:E^*.O(|V|^2+|V|\cdot|E|)InO(|V|^2)reduzierenwirE^*zuE^{*\prime}=\{(u,v)|\text{EsexistierteinWeginGvonunachvundvonvnachu}\}.UndreduzierendannE^{*\prime}zurungerichtetenunterliegendenKantenmengeE^{*\prime\prime}=\{\{u,v\}|\text{EsexistierteinWeginGvonunachvundvonvnachu}\}auchinO(|V|^2).NunfhrenwirSuchen(TiefenoderBreitensuche)maximal|V|malinG''=(V,E^{*\prime\prime})durch,umdieeinzelnenZusammenhangskomponentenzuentfernen.|V|mal,daesmaximal|V|Zusammenhangskomponenten(einefrjedenKnoten)gibt.DasgeschiehtineinerLaufzeitvonO((|V|+|E|)\cdot|V|)=O(|V|^2+|V|\cdot|E|).DerAlgorithmusberuhtaufderKorrektheitvonTranundextrahiertmithilfevonkorrektenSuchenstarkeZusammenhangskomponentenauf.DieStarkenzusammenhangskomponentenbildeninnerhalbderdoppelttransitivenungerichtetenHlledieregulrenstarkenZusammenhangskomponenten,dieklassischmitSuchenentdecktwerdenknnen.\end{aufgabe}\begin{aufgabe}\begin{teilaufgabe}DerAlgorithmusfunktioniertwiezuvor.Sei(u,v)eineKantemitGewichtung0.NachdemuausdemHeapentferntwurdeundzurMengeSderentdecktenKnotenhinzugefgtwurde,wirdd(v)aufd(u)+0gesetztundvdarauffolgendentfernt(mitKnotenmitderselbenDistanz).DamitwirdvZeitlichrichtigimAlgorithmusentfernet.\end{teilaufgabe}\begin{teilaufgabe}WirbetrachtendiesenGraphen:\\\includegraphics[scale=1]{2022-06-26-Blatt-11-3-b.png}Dijkstravonaaus:\vspace{0.5cm}S=\{a\}\vspace{0.5cm}\begin{tabular}{l|l|l}V\backslashS&b&c\\d(a)&1&\infty\\\pi(a)&a&\infty\end{tabular}\vspace{1cm}S=\{a,b\}d(b)=1\vspace{0.5cm}\begin{tabular}{l|l|}V\backslashS&c\\d(a)&2\\\pi(a)&b\end{tabular}\vspace{1cm}NachDijkstraistderkrzesteWeg:a\rightarrowb\rightarrowcmitGesamtlnge3.\lightningkrzesterWegista\rightarrowb\rightarrowb\dotsb\rightarrowcmitGesamtlnge-\infty.\end{teilaufgabe}\end{aufgabe}\end{document}\documentclass{article}\usepackage[utf8]{inputenc}\usepackage[ngerman]{babel}\usepackage{amsmath}%Pseudocode\usepackage{algorithm}\usepackage{algpseudocode}\setlength{\parindent}{0in}\newcommand{\uebungsGruppe}{1}\newcommand{\zettelNummer}{1}\newcommand{\studierenderEins}{MartinaMusterfrau(1234567)}\newcommand{\studierenderZwei}{MaxMustermann(7654321)}\newcommand{\studierenderDrei}{ManuelMustermann(1234765)}\newcounter{AufgabenCounter}\setcounter{AufgabenCounter}{1}\newcounter{TeilaufgabenCounter}\newenvironment{aufgabe}{\section*{Aufgabe\theAufgabenCounter}\setcounter{TeilaufgabenCounter}{1}}{\stepcounter{AufgabenCounter}}\newenvironment{teilaufgabe}{\paragraph*{\alph{TeilaufgabenCounter})}}{\stepcounter{TeilaufgabenCounter}}\renewcommand{\to}{\textnormal{to}}\newcommand{\bigO}{\mathcal{O}}\begin{document}\title{DatenstrukturenundAlgorithmen\\Heimbung\zettelNummer{}}\author{\studierenderEins{}\\\studierenderZwei{}\\\studierenderDrei{}}\maketitle%Aufgabe1\begin{aufgabe}%Teilaufgabea)\begin{teilaufgabe}WirhabendenfolgendenAlgorithmusentworfen:\begin{algorithm}[H]\caption{FindeGrtesElementFor(A[1,\dots,n])}\begin{algorithmic}[1]\StateErgebnis\gets0\For{i\gets1\ton}\If{A[i]\geqErgebnis}\StateErgebnis\getsA[i]\EndIf\EndFor\State\textbf{Return}Ergebnis\end{algorithmic}\end{algorithm}AlternativhabenwirdenfolgendenquivalentenAlgorithmusentworfen:\begin{algorithm}[H]\caption{FindeGrtesElementFor(A[1,\dots,n])}\begin{algorithmic}[1]\StateErgebnis\gets0\Statei\gets1\While{i\leqn}\If{A[i]\geqErgebnis}\StateErgebnis\getsA[i]\EndIf\Statei\getsi+1\EndWhile\State\textbf{Return}Ergebnis\end{algorithmic}\end{algorithm}\end{teilaufgabe}%Teilaufgabeb)\begin{teilaufgabe}ImerstenAlgorithmushabenwireineZuweisunginZeile1undinZeilen3-4derFor-SchleifeeinenVergleichundeineZuweisung.DieFor-Schleifewirdnmaldurchlaufen.DamitergibtsicheineGesamtlaufzeitvon\bigO(n).DerzweiteAlgorithmushat2ZuweisungenauerhalbderWhile-Schleifeund2Zuweisungen,einenVergleichundeineAdditioninnerhalbderWhile-SchleifeinZeilen4-7.DaauchdieWhile-Schleifemaximalnmaldurchlaufenwird,ergibtsicheineLaufzeitvon\bigO(n).\end{teilaufgabe}\end{aufgabe}%Aufgabe2\begin{aufgabe}%Teilaufgabea)\begin{teilaufgabe}Esgilt...\end{teilaufgabe}%Teilaufgabeb)\begin{teilaufgabe}HierknnenwirdasinderVorlesunggezeigteTheoremanwendenunderhalten...\end{teilaufgabe}%Teilaufgabec)\begin{teilaufgabe}EinGegenbeispielkonstruiertsichwiefolgt....\end{teilaufgabe}\end{aufgabe}%Aufgabe3\begin{aufgabe}FrSortierenhabenwirgelernt,dass...\end{aufgabe}\end{document}Letxbe$