% ad-20230316.pdf - Lecture Slides on Algorithms and Data Structures in C/C++
% Copyright (C) 2018, 2019, 2020, 2021, 2022, 2023  Peter Gerwinski
%
% This document is free software: you can redistribute it and/or
% modify it either under the terms of the Creative Commons
% Attribution-ShareAlike 3.0 License, or under the terms of the
% GNU General Public License as published by the Free Software
% Foundation, either version 3 of the License, or (at your option)
% any later version.
%
% This document is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.
%
% You should have received a copy of the GNU General Public License
% along with this document.  If not, see <http://www.gnu.org/licenses/>.
%
% You should have received a copy of the Creative Commons
% Attribution-ShareAlike 3.0 Unported License along with this
% document.  If not, see <http://creativecommons.org/licenses/>.

% README: Einführung

\documentclass[10pt,t]{beamer}

\usepackage{pgslides}
\usepackage{tikz}
%\usepackage{rotating}

\newcommand{\underconstruction}{%
  \begin{picture}(0,0)
    \color{black}
    \put(6,-2.2){\makebox(0,0)[b]{\includegraphics[width=1.5cm]{Zeichen_123.pdf}}}
    \put(6,-2.5){\makebox(0,0)[t]{\shortstack{Änderungen\\vorbehalten}}}
  \end{picture}}

\title{Algorithmen und Datenstrukturen in C/C++}
\author{Prof.\ Dr.\ rer.\ nat.\ Peter Gerwinski}
\date{16.\ März 2023}

\begin{document}

\maketitleframe

% \sectionnonumber{Vorab: Online-Werkzeuge}
% 
% \begin{frame}
% 
%   \showsectionnonumber
%   \begin{itemize}
%     \item
%       \textbf{Mumble}: Seminarraum 2\\
%       Fragen: Mikrophon einschalten oder über den Chat\\
%       Umfragen: über den Chat
%     \smallskip
%     \item
%       \textbf{VNC}: Kanal 6, Passwort: \lstinline[style=cmd]{testcvh}\\
%       Eigenen Bildschirm freigeben: per VNC-Server oder Web-Interface\\
%       Kamerabild übertragen: Link zu Web-Interface auf Anfrage
%     \smallskip
%     \item
%       Allgemeine Informationen:
%       \url{https://www.cvh-server.de/online-werkzeuge/}
%     \smallskip
%     \item
%       Notfall-Schnellzugang: \url{https://www.cvh-server.de/virtuelle-raeume/}\\
%       Seminarraum 2, VNC-Passwort: \lstinline[style=cmd]{testcvh}
%     \smallskip
%     \item
%       Bei Problemen: bitte notieren:\\
%       Art des Problems, genaue Uhrzeit, JavaScript-Fehlermeldungen (F12)
%     \bigskip
%     \item
%       GitLab: \url{https://gitlab.cvh-server.de/pgerwinski/ad}\\
%       Links auf die Datei klicken, nicht mittig auf den Kommentar.
%   \end{itemize}
% 
% \end{frame}

\nosectionnonumber{Hardwarenahe Programmierung}

\begin{frame}

  \shownosectionnonumber

  \begin{itemize}
    \item[\textbf{1}] \textbf{Einführung}
      \hfill\makebox(0,0)[br]{\raisebox{2.25ex}{\url{https://gitlab.cvh-server.de/pgerwinski/hp.git}}}
    \item[\textbf{2}] \textbf{Einführung in C}
    \item[\textbf{3}] \textbf{Bibliotheken}
    \item[\textbf{4}] \textbf{Hardwarenahe Programmierung}
    \item[\textbf{5}] \textbf{\color{black}Algorithmen}
      \begin{itemize}
        \color{medgreen}
        \item[5.1] Differentialgleichungen
        \item[5.2] Rekursion
        \item[5.3] Aufwandsabschätzungen
      \end{itemize}
    \item[\textbf{6}] \textbf{Objektorientierte Programmierung}
    \item[\textbf{7}] \textbf{\color{black}Datenstrukturen}
      \begin{itemize}
        \color{medgreen}
        \item[7.1] Stack und FIFO
        \item[7.2] Verkettete Listen
        \item[7.3] Bäume
      \end{itemize}
  \end{itemize}
  \vspace*{-1cm}

\end{frame}

\begin{frame}

  \shownosectionnonumber

  \begin{itemize}
    \color{gray}
    \item[\textbf{1}] \textbf{Einführung}
      \hfill\makebox(0,0)[br]{\raisebox{2.25ex}{\url{https://gitlab.cvh-server.de/pgerwinski/hp.git}}}
    \item[\textbf{2}] \textbf{Einführung in C}
    \item[\textbf{3}] \textbf{Bibliotheken}
    \item[\textbf{4}] \textbf{Hardwarenahe Programmierung}
    \item[\textbf{5}] \textbf{\color{black}Algorithmen}
      \begin{itemize}
        \color{medgreen}
        \item[5.1] Differentialgleichungen
        \item[5.2] Rekursion
        \item[5.3] Aufwandsabschätzungen
      \end{itemize}
    \item[\textbf{6}] \textbf{Objektorientierte Programmierung}
    \item[\textbf{7}] \textbf{\color{black}Datenstrukturen}
      \begin{itemize}
        \color{medgreen}
        \item[7.1] Stack und FIFO
        \item[7.2] Verkettete Listen
        \item[7.3] Bäume
      \end{itemize}
  \end{itemize}
  \vspace*{-1cm}

\end{frame}

\nosectionnonumber{Algorithmen}

\begin{frame}

  \shownosectionnonumber

  {\color{medgreen}\textbf{Differentialgleichungen}}
  \begin{itemize}
    \item Pendel
    \item Planetenbahnen
  \end{itemize}

  {\color{medgreen}\textbf{Rekursion}}
  \begin{itemize}
    \item Türme von Hanoi
  \end{itemize}

  \smallskip

  \textarrow\ \emph{Wie rechnet man das überhaupt aus?}

  \bigskip

  {\color{medgreen}\textbf{Aufwandsabschätzungen}}
  \begin{itemize}
    \item Selectionsort
    \item Bubblesort
    \item Quicksort
  \end{itemize}

  \smallskip

  \textarrow\ \emph{Wie rechnet man das möglichst effizient aus?}
  \begin{itemize}
    \item[\textbf{?}] möglichst schnell
    \item[\textbf{?}] mit möglichst wenig Speicherplatzverbrauch
    \item[\textbf{?}] unter Berücksichtigung gegebener Randbedingungen
  \end{itemize}

\end{frame}

\nosectionnonumber{Datenstrukturen}

\begin{frame}

  \shownosectionnonumber

  \addvspace{-3pt}

  \begin{visibleenv}<2->
    \textbf{Structs und Objekte}
    \begin{itemize}
      \item zusammengehörige Daten gemeinsam speichern
    \end{itemize}
  \end{visibleenv}

  {\color{medgreen}\textbf{Stack und FIFO}}\only<2->{\textbf{ -- Arrays}}
  \begin{itemize}
    \item effizientes Anfügen und Entfernen vorne und hinten
    \item effizienter direkter Zugriff auf Elemente in der Mitte
    \item ineffizientes Einfügen und Entfernen in der Mitte
  \end{itemize}

  {\color{medgreen}\textbf{Verkettete Listen}}\only<2->{\textbf{ -- Structs mit Pointern}}
  \begin{itemize}
    \item effizientes Einfügen und Entfernen in der Mitte
    \item ineffizienter direkter Zugriff auf Elemente in der Mitte
  \end{itemize}

  {\color{medgreen}\textbf{Bäume}}\only<2->{\textbf{ -- Structs mit Pointern}}
  \begin{itemize}
    \item Kompromiß
  \end{itemize}

  \smallskip

  \textarrow\ \emph{Wie speichert man das möglichst effizient?}
  \begin{itemize}
    \item[\textbf{?}] möglichst schnell
    \item[\textbf{?}] mit möglichst wenig Speicherplatzverbrauch
    \item[\textbf{?}] unter Berücksichtigung gegebener Randbedingungen
  \end{itemize}

\end{frame}

\nosectionnonumber{Aufwandsabschätzungen \protect\color{gray}-- Komplexitätsanalyse}

\begin{frame}[fragile]

%  \newcommand{\w}{\hspace*{0.75pt}}

  \shownosectionnonumber

  \begin{picture}(0,0)
    \put(7.6,-0.5){%
      \begin{minipage}[t]{5.3cm}
%        \vspace*{-1.0cm}\includegraphics{landau-symbols.pdf}
        \alt<3->{\vspace*{-0.93cm}\includegraphics{landau-symbols-3.pdf}}%
                {\vspace*{-1.00cm}\includegraphics{landau-symbols.pdf}}
        \small%\vspace*{-1.0cm}
        \begin{description}\itemsep0pt\leftskip-0.5cm
          \item[$n$:] Eingabedaten
          \item[$g(n)$:] Rechenzeit
        \end{description}
      \end{minipage}}
  \end{picture}

  \vspace*{-\bigskipamount}

  Wann ist ein Programm "`schnell"'?

  \medskip

  \begin{onlyenv}<1>
      Türme von Hanoi: $\mathcal{O}(2^n)$
      \par\medskip
      Für jede zusätzliche Scheibe\\verdoppelt sich die Rechenzeit!
      \begin{itemize}
        \arrowitem
          $\frac{30,672\,\text{s}\,\cdot\,2^{32}}{3600\,\cdot\,24\,\cdot\,365,25} \approx 4174$
          Jahre\\[\smallskipamount]
          für 64 Scheiben
      \end{itemize}

      \bigskip
  \end{onlyenv}

  \begin{onlyenv}<1->
    Faustregel:\\Schachtelung der Schleifen zählen\\
    $k$ Schleifen ineinander \textarrow\ $\mathcal{O}(n^k)$

    \bigskip
  \end{onlyenv}

  \begin{onlyenv}<2>
    \textbf{Beispiel: Sortieralgorithmen}

    \smallskip

    Anzahl der Vergleiche bei $n$ Strings
    \begin{itemize}
      \item
        Maximum suchen mit Schummeln: $\mathcal{O}(1)$
%      \pause
      \item
        Maximum suchen: $\mathcal{O}(n)$
%      \pause
      \item
        Selection-Sort: $\mathcal{O}(n^2)$
%      \pause
      \item
        Bubble-Sort: $\mathcal{O}(n)$ bis $\mathcal{O}(n^2)$
%      \pause
      \item
        Quicksort: $\mathcal{O}(n\log n)$ bis $\mathcal{O}(n^2)$
    \end{itemize}

  \end{onlyenv}

%   \begin{onlyenv}<3>
%     \textbf{Wie schnell ist RSA-Verschlüsselung?}
% 
%     \smallskip
% 
%     \begin{math}
%       c = m^e\,\%\,N
%     \end{math}
%     \quad
%     ("`$\%$"' = "`modulo"')
% 
%     \medskip
% 
%     \begin{lstlisting}[gobble=6,xleftmargin=2em]
%       int c = 1;
%       for (int i = 0; i < e; i++)
%         c = (c * m) % N;
%     \end{lstlisting}
% 
%     \smallskip
% 
%     \begin{itemize}
%       \item
%         $\mathcal{O}(e)$ Iterationen
% %      \item
% %        wenn $n$ die Anzahl der Binärziffern (Bits) von $e$ ist:
% %        $\mathcal{O}(2^n)$ Iterationen
%       \item
%         mit Trick:
%         $\mathcal{O}(\log e)$ Iterationen ($\log e$ = Anzahl der Ziffern von $e$)
%     \end{itemize}
% 
%     \smallskip
% 
%     Jede Iteration enthält eine Multiplikation und eine Division.\\
%     Aufwand dafür: $\mathcal{O}(\log e)$\\
%     \textarrow\ Gesamtaufwand: $\mathcal{O}\bigl((\log e)^2\bigr)$
% 
%   \end{onlyenv}

  \begin{onlyenv}<3->

    \textbf{Wie schnell ist RSA?}\\

    \smallskip

    ($n$ = typische beteiligte Zahl, z.\,B. $e,p,q$)

    \begin{itemize}
      \item
        Ver- und Entschlüsselung (Exponentiation):\\
        \strut\hbox to 3.5cm{\color{red}$\mathcal{O}\!\left((\log n)^2\right)$\hss}
        \only<3->{{\color{magenta}$\mathcal{O}(n^2)$}}
      \item
        Schlüsselerzeugung (Berechnung von $d$):\\
        \strut\hbox to 3.5cm{\color{red}$\mathcal{O}\!\left((\log n)^2\right)$\hss}
        \only<3->{{\color{magenta}$\mathcal{O}(n^2)$}}
      \item
        Verschlüsselung brechen (Primfaktorzerlegung):\\
        \strut\hbox to 3.5cm{\color{red}$\mathcal{O}\bigl(2^{\sqrt{\log n\,\cdot\,\log\log n}}\bigr)$\hss}
        \only<3->{{\color{magenta}$\mathcal{O}\bigl(2^{\sqrt{n\log n}}\bigr)$}}
    \end{itemize}

    \smallskip
%    \vspace{0cm plus 1filll}

    \textbf{Die Sicherheit von RSA beruht darauf,
    daß das Brechen der Verschlüsselung aufwendiger ist als
    \boldmath$\mathcal{O}\bigl((\log n)^k\bigr)$ (für beliebiges $k$).}

%    \vspace*{0.65cm}

  \end{onlyenv}

\end{frame}

\nosectionnonumber{\inserttitle}

\begin{frame}

  \shownosectionnonumber

  \begin{itemize}
    \item[\textbf{1}] \textbf{Einführung}
      \hfill\makebox(0,0)[br]{\raisebox{2.25ex}{\url{https://gitlab.cvh-server.de/pgerwinski/ad.git}}}
    \item[\textbf{2}] \textbf{\dots}
  \end{itemize}

  \begin{picture}(0,0)(-2,-0.5)
    \put(0.5,-1.0){\mbox{\Large$\mathcal{O}(n\log n)$}}
    \put(0.6,-2.7){\mbox{\large\bf B-Baum}}
    \put(-1.3,-3.4){\mbox{\small\it verkettete Liste}}
    \put(1.5,-4.0){\mbox{\large Datenbanken}}
    \put(-1.0,-1.9){\mbox{\large\tt struct}}
    \put(3.0,-2.0){\mbox{\large Wegfindung}}
    \put(4.0,-3.0){\mbox{Verschlüsseln}}
    \put(5.7,-4.2){\mbox{\it Datenkompression}}
    \put(6.0,-1.5){\mbox{CORDIC}}
    \put(8.5,-2.0){\mbox{\small\bf FFT}}
    \put(7.5,-2.9){\mbox{\small\tt pointer}}
    \put(3.5,-0.5){\mbox{\it Rasterung}}
    \put(7.7,-0.7){\mbox{\tt array}}
    \put(-0.5,-5.0){\mbox{digitale Signatur}}
    \put(3.5,-5.2){\mbox{\large Hash-Tabelle}}
    \put(0.0,-6.3){\mbox{\small\bf kryptographische Hash-Funktion}}
    \put(6.5,-6.0){\mbox{\it Prüfsumme}}
%    \pause
%    \put(4.0,-2.7){\begin{rotate}{18}
%                     \makebox(0,0){\LARGE\color{red}\shortstack{%
%                       Online-Werkzeuge für Home Office, Lehre\\
%                       und Kommunikation mit Unterdrückten}}
%                   \end{rotate}}
  \end{picture}

\end{frame}

\begin{frame}

  \shownosectionnonumber

  \begin{itemize}
    \item[\textbf{1}] \textbf{Einführung}
      \underconstruction
      \hfill\makebox(0,0)[br]{\raisebox{2.25ex}{\url{https://gitlab.cvh-server.de/pgerwinski/ad.git}}}
%    \item[\textbf{\color{red}i}] {\color{red}Online-Werkzeuge für Home Office, Lehre\\
%                                             und Kommunikation mit Unterdrückten}
    \item[\textbf{2}] \textbf{Datenorganisation}
    \item[\textbf{3}] \textbf{Optimierung}
    \item[\textbf{4}] \textbf{Hardwarenahe Algorithmen}
    \item[\textbf{5}] \textbf{Datenkodierung}
    \color{gray}
    \item[\textbf{6}] \textbf{Numerik}
  \end{itemize}

\end{frame}

\subsectionnonumber{C: Arrays und Zeiger für Fortgeschrittene}

\begin{frame}[fragile]
  \showsubsectionnonumber

  \begin{minipage}[t]{6cm}
    Array:
    \smallskip
    \begin{lstlisting}[gobble=6]
      char a[] = "Test";
    \end{lstlisting}
  \end{minipage}\hfill
  \begin{minipage}[t]{6cm}
    Zeiger:
    \smallskip
    \begin{lstlisting}[gobble=6]
      char *p = "Test";
    \end{lstlisting}
  \end{minipage}

  \bigskip

  \begin{itemize}
    \item
      In beiden Fällen wird ein Array von ganzen Zahlen\\
      (5 \lstinline{char}-Variable mit den Werten 84, 101, 115, 116 und 0)\\
      im Speicher angelegt.
    \medskip
    \item
      Links heißt das Array \lstinline{a};
      rechts ist es "`anonym"'.
    \item
      Rechts wird zusätzlich ein Zeiger \lstinline{p} im Speicher angelegt,\\
      der auf das (anonyme) Array zeigt.
    \medskip
    \item
      \lstinline{&a} ist dasselbe wie \lstinline{a},
      nämlich die Adresse des Arrays.
    \item
      \lstinline{&p} ist die Adresse des Zeigers.
    \item
      \lstinline{p} ist der Wert des Zeigers,\\
      momentan also die Adresse des (anonymen) Arrays.
  \end{itemize}

\end{frame}

\begin{frame}[fragile]
  \showsubsectionnonumber

  \begin{minipage}[t]{6cm}
    Array:
    \smallskip
    \begin{lstlisting}[gobble=6]
      char a[] = "Test";
    \end{lstlisting}
  \end{minipage}\hfill
  \begin{minipage}[t]{6cm}
    Zeiger:
    \smallskip
    \begin{lstlisting}[gobble=6]
      char *p = "Test";
    \end{lstlisting}
  \end{minipage}

  \bigskip

  \begin{itemize}
    \item
      In beiden Fällen wird ein Array von ganzen Zahlen\\
      (5 \lstinline{char}-Variable mit den Werten 84, 101, 115, 116 und 0)\\
      im Speicher angelegt.
    \medskip
    \item
      Links heißt das Array \lstinline{a};
      rechts ist es "`anonym"'.
    \item
      Rechts wird zusätzlich ein Zeiger \lstinline{p} im Speicher angelegt,\\
      der auf das (anonyme) Array zeigt.
    \medskip
    \item
      \lstinline{&a} ist {\color{red}fast} dasselbe wie \lstinline{a},\\
      nämlich die Adresse des Arrays {\color{red}bzw.\ das Array selbst,\\
      das zuweisungskompatibel zu einem Zeiger auf Elemente des Arrays ist.\\
      \lstinline{&} bewirkt hier eine (nicht explizite!) Typumwandlung.}
    \item
      \lstinline{&p} ist die Adresse des Zeigers.
    \item
      \lstinline{p} ist der Wert des Zeigers,\\
      momentan also die Adresse des (anonymen) Arrays.
  \end{itemize}

  \vspace*{-1cm}

\end{frame}

\begin{frame}[fragile]
  \showsubsectionnonumber

  \begin{minipage}[t]{7cm}
    Array:
    \smallskip
    \begin{lstlisting}[gobble=6]
      char *a[] = { "Dies", "ist", "ein", "Test" };
    \end{lstlisting}
  \end{minipage}\hfill
  \begin{minipage}[t]{5cm}
    Zeiger:
    \smallskip
    \begin{lstlisting}[gobble=6]
      char **p = a;
    \end{lstlisting}
  \end{minipage}

  \bigskip

  \begin{itemize}
    \item
      Array von Zeigern auf \lstinline{char}-Variable
    \item
      Zeiger auf das Array = Zeiger auf Zeiger auf \lstinline{char}-Variable
    \item
      Schleife durch äußeres Array mit \lstinline{p++} möglich
  \end{itemize}

\end{frame}

\begin{frame}[fragile]
  \showsubsectionnonumber

  \begin{minipage}[t]{7cm}
    Array:
    \smallskip
    \begin{lstlisting}[gobble=6]
      char a[][5] = { "Dies", "ist", "ein", "Test" };
    \end{lstlisting}
  \end{minipage}\hfill
  \begin{minipage}[t]{5cm}
    Zeiger:
    \smallskip
    \begin{lstlisting}[gobble=6]
      char *p = a[0];
    \end{lstlisting}
  \end{minipage}

  \bigskip

  \begin{itemize}
    \item
      zweidimensionales Array von \lstinline{char}-Variablen
    \item
      Zeiger auf Array-Komponente\\
      = Zeiger auf eindimensionales Array\\
      = Zeiger auf \lstinline{char}-Variable
    \item
      Schleife durch äußeres Array mit Zeiger-Arithmetik nicht möglich
  \end{itemize}

  \begin{picture}(0,0)
    \color{red}
    \thicklines
    \put(8.6,0.63){\line(1,0){0.85}}
    \put(9.05,0.4){\makebox(0,0)[t]{$\overbrace{\mbox{nur mit Trick:
                   \lstinline{p += 5}}}$}}
  \end{picture}

\end{frame}

\begin{frame}[fragile]
  \showsubsectionnonumber

  \begin{lstlisting}
    typedef char string5[5];
    string5 a[] = { "Dies", "ist", "ein", "Test" };
    string5 *p = a;
  \end{lstlisting}

  \bigskip

  \begin{itemize}
    \item
      Array von Array von \lstinline{char}-Variablen\\
      = zweidimensionales Array von \lstinline{char}-Variablen
    \item
      Zeiger auf zweidimensionales Array
    \item
      Schleife durch äußeres Array mit \lstinline{p++} möglich
    \bigskip
    \arrowitem
      Fazit:\\
      Ein Hoch auf \lstinline{typedef}!
    \arrowitem
      Trotzdem: {\color{red}Vorsicht!}\\
      Ein \lstinline{p++} auf einen Zeiger vom Typ \lstinline{string5 *p}\\
      ergibt anscheinend undefiniertes Verhalten!
  \end{itemize}

\end{frame}

\begin{frame}[fragile]
  \showsubsectionnonumber

  \begin{lstlisting}
    typedef char string5[5];
    string5 *p = { "Dies", "ist", "ein", "Test" };
  \end{lstlisting}

  \bigskip

  \begin{itemize}
    \item
      anonymes Array von Array von \lstinline{char}-Variablen\\
      = anonymes zweidimensionales Array von \lstinline{char}-Variablen
    \item
      Zeiger auf zweidimensionales Array
    \item
      Schleife durch äußeres Array mit \lstinline{p++} möglich
  \end{itemize}

%  \pause

  \begin{picture}(0,0)(-2,-0.4)
    \color{red}
    \thicklines
    \put(0,0){\line(2,1){4}}
    \put(0,2){\line(2,-1){4}}
  \end{picture}

  Das Konstrukt \lstinline|{ "Dies", "ist", "ein", "Test" }|\\
  steht für ein Array von 4 Zeigern auf \lstinline{char}-Variable.

  \smallskip

  \lstinline{string5 *p} hingegen erwartet einen Zeiger auf ein Array
  von 5 \lstinline{char}-Variablen.

  \smallskip

  Es bekommt die Adresse von \lstinline{"Dies"} zugewiesen.

  \smallskip

  Durch das Erhöhen von \lstinline{p} (um 5) zeigt es danach
  \emph{zufällig\/} auf das \lstinline{"ist"}.

  Bei nochmaligem Erhöhen zeigt es auf das \lstinline{"in"} von \lstinline{"ein"}.

  \smallskip

  (Auch ohne Optimierung werden die Strings \lstinline{"ist"}, \lstinline{"ein"}
  und \lstinline{"Test"}\\
  u.\,U.\ wegoptimiert.)

\end{frame}

\nosectionnonumber{\large\bf Übungsaufgabe: Verkettete Listen}

\begin{frame}

  \shownosectionnonumber

  \begin{enumerate}[\quad(a)]
    \item
      Schreiben Sie eine Funktion, die eine verkettete Liste\\
      in die umgekehrte Reihenfolge bringt.
    \item
      Schreiben Sie eine Funktion, die eine verkettete Liste\\
      in eine doppelt verkettete Liste umwandelt.
    \item
      Wieviel Rechenzeit (Landau-Symbol) benötigen Ihre Funktionen?
    \item
      Wieviel Speicherplatz (Landau-Symbol) benötigen Ihre Funktionen?
  \end{enumerate}

\end{frame}

\nosectionnonumber{\inserttitle}

\begin{frame}

  \shownosectionnonumber

  \begin{itemize}
    \item[\textbf{1}] \textbf{Einführung}
      \underconstruction
      \hfill\makebox(0,0)[br]{\raisebox{2.25ex}{\url{https://gitlab.cvh-server.de/pgerwinski/ad.git}}}
%    \item[\textbf{i}] \textbf{Gesellschaftliche Auswirkungen\\
%                              von Algorithmen und Datenstrukturen}
    \item[\textbf{2}] \textbf{Datenorganisation}
    \item[\textbf{3}] \textbf{Optimierung}
    \item[\textbf{4}] \textbf{Hardwarenahe Algorithmen}
    \item[\textbf{5}] \textbf{Datenkodierung}
    \color{gray}
    \item[\textbf{6}] \textbf{Numerik}
  \end{itemize}

\end{frame}

\iffalse

\section{Einführung in C++}
\addtocounter{subsection}{-1}
\subsection{Was ist C?}

\begin{frame}

  \showsection
  \showsubsection

  Etabliertes Profi-Werkzeug
  \begin{itemize}
    \item
      kleinster gemeinsamer Nenner für viele Plattformen\\
      \begin{picture}(0,1)
        \color{red}
        \put(7.2,0.6){\tikz{\draw[-latex](0.0,0.0)--(0.0,0.4);}}
        \put(7.2,0.5){\makebox(0,0)[t]{\color{black}Hardware und/oder Betriebssystem}}
      \end{picture}
    \item
      Hardware direkt ansprechen und effizient einsetzen
    \item
      \dots\ bis hin zu komplexen Software-Projekten
    \medskip
    \arrowitem
      Man kann Computer vollständig beherrschen.
  \end{itemize}

\end{frame}

\begin{frame}

  \showsection
  \showsubsection

  \begin{picture}(0,0)
    \put(5.3,-2.5){\makebox(0,0)[tl]{\begin{minipage}{7cm}
                     \emph{C makes it easy to shoot yourself in the foot.}
                     \begin{flushright}
                       Bjarne Stroustrup, ca.~1986\\
                       \href{http://www.stroustrup.com/bs_faq.html\#really-say-that}%
                            {\nolinkurl{http://www.stroustrup.com/bs_faq.html}\\
                             \nolinkurl{\#really-say-that}}
                     \end{flushright}
                   \end{minipage}}}
  \end{picture}%
  Etabliertes Profi-Werkzeug
  \begin{itemize}
    \item
      kleinster gemeinsamer Nenner für viele Plattformen
    \item
      Hardware direkt ansprechen und effizient einsetzen
    \item
      \dots\ bis hin zu komplexen Software-Projekten
    \item
      leistungsfähig, aber gefährlich
  \end{itemize}

  \medskip
  "`High-Level-Assembler"'
  \begin{itemize}
    \item
      kein "`Fallschirm"'
    \item
      kompakte Schreibweise
  \end{itemize}

  \medskip
  Unix-Hintergrund
  \begin{itemize}
    \item
      Baukastenprinzip
    \item
      konsequente Regeln
    \item
      kein "`Fallschirm"'
  \end{itemize}

\end{frame}

\subsection{Was ist C++?}

\begin{frame}

  \showsection
  \showsubsection

  \begin{picture}(0,0)
    \put(6.3,-0.2){\makebox(0,0)[tl]{\begin{minipage}{6cm}
                     \emph{C++ is a better C.}
                     \begin{flushright}
                        Bjarne Stroustrup, Autor von C++\\
                        \url{http://www.stroustrup.com/C++.html}
                     \end{flushright}
                   \end{minipage}}}
    \put(5.3,-2.5){\makebox(0,0)[tl]{\begin{minipage}{7cm}
                     \emph{C makes it easy to shoot yourself in the foot;\\
                     C++ makes it harder, but when you do\\
                     it blows your whole leg off.}
                     \begin{flushright}
                       Bjarne Stroustrup, Autor von C++, ca.~1986\\
                       \href{http://www.stroustrup.com/bs_faq.html\#really-say-that}%
                            {\nolinkurl{http://www.stroustrup.com/bs_faq.html}\\
                             \nolinkurl{\#really-say-that}}
                     \end{flushright}
                   \end{minipage}}}
  \end{picture}%
  Etabliertes Profi-Werkzeug
  \begin{itemize}
    \item
      kompatibel zu C
  \end{itemize}

  \medskip

  C++ unterstützt
  \begin{itemize}
    \item
      \newterm{objektorientierte\\
      Programmierung}
    \item
      \newterm{Datenabstraktion}
    \item
      \newterm{generische\\
      Programmierung}
  \end{itemize}

  \vspace{0cm plus 1 filll}

  \textbf{Motivation:}\\[\smallskipamount]
  Vermeidung unsicherer Techniken,\\
  insbesondere von Präprozessor-Konstruktionen und Zeigern,\\
  unter Beibehaltung der Effizienz

\end{frame}

\subsection{Elementare Neuerungen in C++ gegenüber C}

\begin{frame}[fragile]
  \showsubsection
  \begin{itemize}
    \pause
    \item
      Kommentare mit \lstinline{//}
    \pause
    \item
      Konstante:
      \begin{onlyenv}<3>
        \begin{lstlisting}[gobble=10]
          const int answer = 42;
        \end{lstlisting}
      \end{onlyenv}
      \begin{lstlisting}[gobble=8]
        const int n = 5;
        int prime[n] = { 2, 3, 5, 7, 11 };
      \end{lstlisting}
    \pause
    \item
      Ab C++11: \lstinline{constexpr}-Funktionen\\
%      \only<1->{{\color{red}\dots\ anscheinend auch ohne "`constexpr"' \dots}\\}
      C++11: darf nur aus einem einzigen \lstinline{return}-Statement bestehen\\
      \textarrow\ \lstinline{?:} statt \lstinline{if}, Rekursion statt Schleife\\
      C++-14: auch Verzweigungen und Schleifen erlaubt
    \pause
    \item
      leere Parameterliste: \lstinline{void} optional\\
      in C: ohne \lstinline{void} = Parameterliste wird nicht geprüft
    \pause
    \item
      Operatoren \lstinline{new} und \lstinline{delete}\\
      als Alternative zu den Funktionen \lstinline{malloc()} und \lstinline{free()}
  \end{itemize}
\end{frame}

\fi

\end{document}
