Details

<p><b>Einleitung 19</b></p> <p>Über dieses Buch 19</p> <p>Konventionen in diesem Buch 19</p> <p>Was Sie nicht lesen müssen 20</p> <p>Törichte Annahmen über den Leser 20</p> <p>Wie dieses Buch aufgebaut ist 21</p> <p>Teil I: Programmieren 21</p> <p>Teil II: Algorithmen 21</p> <p>Teil III: Mathematik 21</p> <p>Teil IV: Codierung 22</p> <p>Teil V: Praktische Informatik 22</p> <p>Teil VI: Theoretische Informatik 22</p> <p>Teil VII: Top-Ten-Teil 23</p> <p>Symbole, die in diesem Buch verwendet werden 23</p> <p>Wie es weitergeht 24</p> <p>Bitte und Danke sagen 24</p> <p><b>Teil I: Programmieren 25</b></p> <p><b>Kapitel 1 Programmieren in Java</b> <b>27</b></p> <p>Wertzuweisung 27</p> <p>Variablen deklarieren 28</p> <p>Wozu Datentypen? 28</p> <p>Einen Wert zuweisen 29</p> <p>Einen Wert überschreiben 30</p> <p>Numerische Datentypen und Operationen 31</p> <p>Typumwandlung bei numerischen Datentypen 32</p> <p>Bedingte Anweisung 33</p> <p>If-Anweisung 33</p> <p>If-Else-Anweisung 34</p> <p>Flussdiagramme zeichnen 35</p> <p>Datentyp boolean 36</p> <p>Boolesche Operationen 38</p> <p>Kommentare 39</p> <p>Zum Üben 39</p> <p><b>Kapitel 2 Programmschleifen, Datenfolgen und Zeichenketten</b> <b>41</b></p> <p>While-Schleife 41</p> <p>Fakultäten berechnen 43</p> <p>Programmschleifen entwerfen 44</p> <p>Iterationsschema aufstellen 44</p> <p>Iterationsgleichungen ableiten 44</p> <p>Regeln für das Aufstellen der Iterationsgleichungen 45</p> <p>Iterationsgleichungen in eine While-Schleife umsetzen 45</p> <p>For-Schleife 46</p> <p>Arrays 47</p> <p>Array erzeugen 47</p> <p>Array durchlaufen 48</p> <p>Strings 49</p> <p>Strings verketten 50</p> <p>String-Methoden anwenden 50</p> <p>Zum Üben 52</p> <p>Iterationsschema aufstellen und in While-Schleife umsetzen 52</p> <p>Primzahlen mit dem Sieb des Eratosthenes 52</p> <p><b>Kapitel 3 Funktionen</b> <b>55</b></p> <p>Funktionen definieren und aufrufen 55</p> <p>Funktionsdefinition 56</p> <p>Funktionsaufruf 57</p> <p>So funktioniert ein Stack 58</p> <p>Lokale Variablen benutzen 59</p> <p>Funktionen mit mehreren Parametern 60</p> <p>Funktionen ohne Parameter 61</p> <p>Funktionen ohne Rückgabewert 61</p> <p>Rekursive Funktionen 63</p> <p>Ausführung einer rekursiven Funktion 63</p> <p>Zum Üben 66</p> <p>Ziehung der Lottozahlen 66</p> <p><b>Kapitel 4 Objektorientiert programmieren</b> <b>69</b></p> <p>Klasse und Objekt 69</p> <p>Attribute und Methoden 69</p> <p>Kommentare und Benennungen 70</p> <p>Bruchrechnung 70</p> <p>Methoden 71</p> <p>Rechenoperationen mit Brüchen 73</p> <p>Bruch normalisieren 74</p> <p>Bruch kürzen 75</p> <p>Objektorientierung in Java 76</p> <p>Zum Üben 76</p> <p><b>Teil II: Algorithmen 77</b></p> <p><b>Kapitel 5 Algorithmus</b> <b>79</b></p> <p>Typische Anweisungsformen 79</p> <p>Algorithmisch denken 80</p> <p><b>Kapitel 6 Binäre Suche</b> <b>81</b></p> <p>Suchstrategie 81</p> <p>Logarithmus 82</p> <p>Algorithmus binäre Suche 83</p> <p>Zum Üben 84</p> <p><b>Kapitel 7 Einfaches Sortieren</b> <b>85</b></p> <p>Minimum einer Datenfolge bestimmen 85</p> <p>Selectionsort 86</p> <p>Array sortieren 87</p> <p>Programm 87</p> <p>Zeitkomplexität 88</p> <p>Analyse von Selectionsort 89</p> <p><b>Kapitel 8 Zeitkomplexität von Algorithmen</b> <b>91</b></p> <p>Zeitkomplexität 92</p> <p>Untere und obere Schranken 92</p> <p>Schlechtester Fall 93</p> <p>Asymptotische Analyse 93</p> <p>O-Notation 94</p> <p>Zum Üben 95</p> <p><b>Kapitel 9 Mergesort</b> <b>97</b></p> <p>Divide-and-Conquer-Strategie 97</p> <p>Ablauf von Mergesort 98</p> <p>Verschmelzen zweier sortierter Hälften eines Arrays 98</p> <p>Implementierung 99</p> <p>Zeitkomplexität 101</p> <p>Untere Schranke für das Sortieren 101</p> <p>Zum Üben 102</p> <p><b>Kapitel 10 Kürzeste Wege in einem Graphen</b> <b>103</b></p> <p>Idee des Verfahrens 103</p> <p>Greedy-Strategie 105</p> <p>Umsetzung in einen Algorithmus 105</p> <p><b>Kapitel 11 Kürzeste Rundreise 107</b></p> <p>Problem des Handlungsreisenden 108</p> <p>Die Mengen P und NP 108</p> <p>Nichtdeterministischer Algorithmus 109</p> <p>Polynomielle Zeitkomplexität 110</p> <p>NP-vollständige Probleme 111</p> <p>Erfüllbarkeitsproblem (SAT) 112</p> <p>Reduktion von SAT auf CLIQUE 112</p> <p><b>Teil III: Mathematik 115</b></p> <p><b>Kapitel 12 Logik</b> <b>117</b></p> <p>Logische Aussagen 117</p> <p>Logische Verknüpfungen 118</p> <p>Formale Logik 120</p> <p>Allgemeingültige Aussagen 121</p> <p>Gesetze der Logik 121</p> <p>Logik im Alltag 123</p> <p>Entweder Oder oder Entweder-Oder 123</p> <p>Wenn-dann in der Umgangssprache 123</p> <p>Die Tücken der logischen Folgerung 124</p> <p>Prädikate 125</p> <p>Quantoren 125</p> <p>Zum Üben 127</p> <p><b>Kapitel 13 Menge</b> <b>129</b></p> <p>Mengen bilden 129</p> <p>Teilmenge 131</p> <p>Die leere Menge 132</p> <p>Potenzmenge 134</p> <p>Mengen verknüpfen 134</p> <p>Komplement 135</p> <p>Gesetze der Mengenlehre 136</p> <p>Duale Gesetze 136</p> <p>Zum Üben 137</p> <p><b>Kapitel 14 Relation</b> <b>139</b></p> <p>Kartesisches Produkt 139</p> <p>Relation als Teilmenge eines kartesischen Produkts 140</p> <p>Schreibweise von Relationen 141</p> <p>Relationen anschaulich darstellen 141</p> <p>Eigenschaften von Relationen 143</p> <p>Beispiele dieser Eigenschaften 143</p> <p>Ordnungsrelation und Äquivalenzrelation 144</p> <p>Operationen auf Relationen 145</p> <p><i>n</i>-stellige Relationen 146</p> <p>Wozu brauchen wir das? 146</p> <p>Zum Üben 147</p> <p><b>Kapitel 15 Abbildung</b> <b>149</b></p> <p>Abbildung als spezielle Relation 149</p> <p>Schreibweise für Abbildungen 151</p> <p>Wertetabelle einer Abbildung 151</p> <p>Funktion 152</p> <p>Verknüpfungen 153</p> <p>Wertetabelle einer Verknüpfung 153</p> <p>Verknüpfungstafel 154</p> <p>Eigenschaften von Abbildungen 154</p> <p>Injektive Abbildung 154</p> <p>Surjektive Abbildung 155</p> <p>Wertetabellen von injektiven und surjektiven Abbildungen 156</p> <p>Bijektive Abbildung 157</p> <p>Mächtigkeit von Mengen 157</p> <p>Folgen 158</p> <p>Endliche Folgen 158</p> <p>Zum Üben 159</p> <p><b>Kapitel 16 Graph</b> <b>161</b></p> <p>Knoten und Kanten 161</p> <p>Pfad 162</p> <p>Baum 163</p> <p>Ungerichteter Graph 164</p> <p>Markierte Graphen 165</p> <p>Zum Üben 166</p> <p><b>Kapitel 17 Teilbarkeit und Modulo-Rechnung</b> <b>167</b></p> <p>Teilbarkeit 167</p> <p>Ist null durch null teilbar? 168</p> <p>Teiler einer Zahl 169</p> <p>Größter gemeinsamer Teiler 169</p> <p>Primzahlen 170</p> <p>Modulo-Rechnung 171</p> <p>Modulo <i>n </i>rechnen 173</p> <p>Zum Üben 174</p> <p><b>Kapitel 18 Gruppen, Ringe und Körper</b> <b>175</b></p> <p>Die Gruppenaxiome 175</p> <p>Elemente verknüpfen 176</p> <p>Halbgruppe 177</p> <p>Gruppe 178</p> <p>Die Gruppe 𝕫^∗<i>_n </i>179</p> <p>Ring 180</p> <p>Körper 181</p> <p>Zum Üben 181</p> <p><b>Kapitel 19 Beweistechniken</b> <b>183</b></p> <p>Direkter Beweis 183</p> <p>Äquivalente Umformung 183</p> <p>Direkte Umformung 184</p> <p>Kontraposition 184</p> <p>Beweis durch Widerspruch 185</p> <p>Es gibt unendlich viele Primzahlen 185</p> <p>Varianten des Widerspruchsbeweises 186</p> <p>√2 ist irrational 186</p> <p>Gaußsche Summenformel 187</p> <p>Beweis durch Induktion 187</p> <p>Dominoeffekt 188</p> <p>Zum Üben 190</p> <p><b>Teil IV: Codierung 191</b></p> <p><b>Kapitel 20 Boolesche Funktionen</b> <b>193</b></p> <p>Boolesche Funktionen darstellen 194</p> <p>Boolesche Funktionen minimieren 195</p> <p>Algebraische Umformung 195</p> <p>KV-Diagramm 196</p> <p>Blöcke mit Einsen zusammenfassen 197</p> <p>Drei und vier Argumentvariablen 197</p> <p>Anwendung 199</p> <p>Realisierung mit Nand-Verknüpfungen 200</p> <p>Zum Üben 201</p> <p><b>Kapitel 21 Zahlendarstellung 203</b></p> <p>Zahlensysteme zur Basis <i>b </i>203</p> <p>Zwischen Zahl und Darstellung hin und her rechnen 204</p> <p>Programme 206</p> <p>Zahlensysteme zu anderer Basis 207</p> <p>Ganze Zahlen im Binärsystem 207</p> <p>Betrag-Vorzeichen-Darstellung 208</p> <p>Exzess-Darstellung 208</p> <p>Einerkomplement-Darstellung 209</p> <p>Zweierkomplement-Darstellung 209</p> <p>Kommazahlen im Binärsystem 210</p> <p>Rechnen mit Kommazahlen 211</p> <p>Genauigkeit von Gleitkommazahlen 211</p> <p>Zum Üben 212</p> <p><b>Kapitel 22 Einfache Codes</b> <b>213</b></p> <p>Blockcodes 214</p> <p>Hamming-Abstand 216</p> <p>Fehlererkennung 216</p> <p>Binärcode mit Paritätsbit 217</p> <p><b>Kapitel 23 Daten komprimieren</b> <b>219</b></p> <p>Konstruktion des Huffman-Baums 219</p> <p>Konstruktion des Huffman-Codes 221</p> <p>Eigenschaften des Huffman-Codes 221</p> <p>Informationsgehalt eines Textes 222</p> <p>Zum Üben 222</p> <p><b>Kapitel 24 Fehler erkennen mit CRC</b> <b>223</b></p> <p>Idee des Verfahrens 223</p> <p>Polynom 224</p> <p>Polynomdivision 225</p> <p>Der CRC-Algorithmus 225</p> <p>Erkennung von Fehlern 226</p> <p>Zum Üben 227</p> <p><b>Teil V: Praktische Informatik 229</b></p> <p><b>Kapitel 25 Datenbanken</b> <b>231</b></p> <p>Datenbankrelationen 232</p> <p>Attribut 233</p> <p>Schlüssel 234</p> <p>Datenbankentwurf 235</p> <p>Entitäten und Beziehungen 235</p> <p>Schlüssel und Fremdschlüssel 236</p> <p>Entity-Relationship-Diagramm 237</p> <p>Datenbankanfragen 238</p> <p>Index 240</p> <p>Datenbankmanagementsystem 242</p> <p>Zum Üben 242</p> <p><b>Kapitel 26 Computernetze</b> <b>243</b></p> <p>Adressen 243</p> <p>Protokoll 244</p> <p>Protokolle im täglichen Leben 244</p> <p>Protokollstapel 245</p> <p>Schnittstellen 246</p> <p>Protokolle in der Informatik 246</p> <p><b>Kapitel 27 Verschlüsseln mit öffentlichem Schlüssel 249</b></p> <p>Diffie-Hellman-Schlüsselvereinbarung 250</p> <p>Ablauf des Verfahrens 251</p> <p>Problem des diskreten Logarithmus 251</p> <p>Public-Key-Verschlüsselung 252</p> <p>RSA-Verfahren 253</p> <p>Schlüssel erzeugen 254</p> <p>Sicherheit 254</p> <p>Berechnungsverfahren 254</p> <p>Primzahltest 254</p> <p>Schnelle Exponentiation 255</p> <p>Größter gemeinsamer Teiler 257</p> <p>Zum Üben 257</p> <p><b>Teil VI: Theoretische Informatik 259</b></p> <p><b>Kapitel 28 Berechenbarkeit</b> <b>261</b></p> <p>Das Halteproblem 262</p> <p>Praktisch nicht berechenbar 263</p> <p><b>Kapitel 29 Reguläre Sprachen</b> <b>265</b></p> <p>Regulärer Ausdruck 266</p> <p>Reguläre Operationen 266</p> <p>Endlicher Automat 268</p> <p>Arbeitsweise des Automaten 269</p> <p>Formale Definition 270</p> <p>Deterministisch und nichtdeterministisch 271</p> <p>Simulation eines nichtdeterministischen endlichen Automaten 273</p> <p>Teilmengenkonstruktion 275</p> <p>Endliche Automaten und reguläre Sprachen 276</p> <p>Sprachen, die nicht regulär sind 277</p> <p>Zum Üben 278</p> <p><b>Kapitel 30 Kontextfreie Grammatik und Stackautomat</b> <b>279</b></p> <p>Kontextfreie Grammatik 279</p> <p>Wörter ableiten 280</p> <p>Eine Sprache erzeugen 281</p> <p>Wörter reduzieren 281</p> <p>Rechtslineare Grammatik 282</p> <p>Noch ein Beispiel 283</p> <p>Stackautomat 283</p> <p>Erkennung von Wörtern 285</p> <p>Zum Üben 286</p> <p><b>Kapitel 31 Sprachklassen und Turingmaschinen</b> <b>289</b></p> <p>Hierarchie der Sprachklassen 289</p> <p>Die Sprachklassen <i>L</i>₀ und <i>L</i>₁ 290</p> <p>Grammatiken für <i>L</i>₀ 290</p> <p>Grammatiken für <i>L</i>₁ 290</p> <p>Turingmaschine 292</p> <p>Formale Definition 293</p> <p>Arbeitsweise der Turingmaschine 293</p> <p>Turingtabelle 294</p> <p>Mit Turingmaschinen erkennbare Sprachen 295</p> <p>Entscheidbare Sprachen 295</p> <p>Nichtdeterministische und deterministische</p> <p>Turingmaschinen 296</p> <p><b>Kapitel 32 Parser und Compiler</b> <b>299</b></p> <p>Grammatik als Ausgangspunkt 299</p> <p>Parser für arithmetische Ausdrücke 300</p> <p>Compiler für arithmetische Ausdrücke 303</p> <p>Basisfunktionen für Parser und Compiler 304</p> <p>Zum Üben 307</p> <p><b>Teil VII: Top-10-Teil 309</b></p> <p><b>Kapitel 33 Vier mal sieben</b> <b>311</b></p> <p>Die 7 elementarsten Begriffe 311</p> <p>Die 7 verrücktesten Dinge 312</p> <p>Die 7 cleversten Algorithmen 313</p> <p>Die 7 bedeutendsten Informatik-Pioniere 315</p> <p><b>Teil VIII: Anhang 317</b></p> <p><b>Anhang A: Lösungen zu den Übungsaufgaben</b> <b>319</b></p> <p>Teil I: Programmieren 319</p> <p>Teil II: Algorithmen 323</p> <p>Teil III: Mathematik 325</p> <p>Teil IV: Codierung 329</p> <p>Teil V: Praktische Informatik 331</p> <p>Teil VI: Theoretische Informatik 333</p> <p><b>Anhang B: Zum Weiterlesen</b> <b>337</b></p> <p>Literaturverzeichnis 341</p> <p>Stichwortverzeichnis 345</p>

Hans Werner Lang studierte Informatik an der Universität Kiel und promovierte dort 1990 zu einem Thema aus dem Bereich "Parallele Architekturen und Algorithmen". Von 1994 bis 2017 war er Professor für Informatik an der Hochschule Flensburg und hat in dieser Zeit zahlreiche Vorlesungen zur Informatik gehalten.

DE