Informatik-Skript fu¨r den Unterricht von C. Jost am Studienkolleg fu¨r ausl¨andische Studierende der Technischen Universit¨at Darmstadt Dr. Christof Jost Version 2020/09/10 2 Vorbemerkungen Dieses Werk bzw. dessen Inhalt steht unter einer Creative Commons Namensnennung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland Lizenz (CC BY-SA 3.0 DE), siehe https://creativecommons.org/licenses/by-sa/3.0/de/. Autor: Christof Jost Es gibt mit Sicherheit etliche Fehler in diesem Skript. Ich bitte, die Fehler an die Adresse [email protected] mitzuteilen. Der Autor u¨bernimmt keinerlei Verantwortung fu¨r die Korrektheit der Inhalte. Die Links zu (anderen) www-Dokumenten in der elektronischen Version wurden nach bestem Wissen und Gewissen erstellt. Der Autor u¨bernimmt dennoch keine Haftung fu¨r die Inhalte verlinkter Seiten. Die Informatik ist die Wissenschaft von der Verarbeitung von Information, insbesondere die automatische Verarbeitung von Information mittels Rechnern. Die Informatik kann in die folgenden Teilgebiete aufgeteilt werden: • Praktische Informatik Zur Praktischen Informatik z¨ahlen Programmierung, die im Unterricht am Studienkolleg und daher auch in diesem Skript viel Raum einnimmt, und beispielsweise Betriebssysteme, Netzwerke, Datenbanken. • Theoretische Informatik Die Theoretische Informatik wird im Unterricht am Stu- dienkolleg und damit auch im vorliegenden Skript beim Thema Komplexit¨atstheorie gestreift. Weitere Themenbereiche der Technischen Informatik sind beispielsweise Be- rechenbarkeitstheorie und Automatentheorie. Etwas vereinfacht k¨onnte man sagen, das Teilgebiet Theoretische Informatik ist der Grenzbereich zwischen der Informatik und der Mathematik. • Technische Informatik Wenn die Theoretische Informatik die Grenze der Informa- tik zur Mathematik darstellt, dann ist die Technische Informatik der Grenzbereich zwischen Informatik und Elektrotechnik. Die Boolesche Algebra, die am Studienkolleg und in diesem Skript behandelt wird, stellt eine wichtige Grundlage der Technischen Informatik dar. • Angewandte Informatik Die Angewandte Informatik besch¨aftigt sich mit der An- wendung der Informatik auf andere Gebiete, z.B. Medizininformatik. Sicher bedient sich der Informatikunterricht am Studienkolleg an Beispielen aus anderen Disziplinen, aber eine explizite Besch¨aftigung mit Angewandter Informatik findet nicht statt. Inhaltsverzeichnis 1 Erste Schritte in Java 5 1.1 Tools fu¨r Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Hallo Welt! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Bedingte Anweisung und Verzweigung . . . . . . . . . . . . . . . . . . . . . 7 1.4 Die while-Schleife . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 Die for-Schleife . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Verschachtelte Schleifen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 Algorithmik 13 2.1 Einfu¨hrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Programmablaufpl¨ane und Pseudocode . . . . . . . . . . . . . . . . . . . . . 14 2.3 Probleme aus der Zahlentheorie . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Probleme aus der Graphentheorie . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4.1 Einige Begriffe aus der Graphentheorie . . . . . . . . . . . . . . . . . 16 2.4.2 Minimale Spannb¨aume: Prim- und Kruskal-Algorithmus . . . . . . . 19 2.4.3 Ku¨rzeste Wege: Algorithmus von Dijkstra . . . . . . . . . . . . . . . 21 3 Programmieren in Java 23 3.1 Nieder mir Eclipse, es lebe Eclipse! . . . . . . . . . . . . . . . . . . . . . . . 23 3.1.1 Programm ohne Eclipse laufen lassen . . . . . . . . . . . . . . . . . . 23 3.1.2 Austausch von Quellcode . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.3 Debugger verwenden . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.1 Methoden ohne Ru¨ckgabe . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.2 Methoden mit Ru¨ckgabe . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2.3 Sichtbarkeit von Variablen . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.4 Begriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Arrays und Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3.1 Typen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3.2 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.3 Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4 Inhaltsverzeichnis 3.4 Objektorientierte Programmierung . . . . . . . . . . . . . . . . . . . . . . . 39 3.4.1 Beispiele zur Einfu¨hrung: Fahrr¨ader und Bru¨che . . . . . . . . . . . . 39 3.4.2 Beispiele aus der linearen Algebra . . . . . . . . . . . . . . . . . . . . 42 4 Technische Informatik 45 4.1 Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2 Boolesche Algebra und Schaltnetze . . . . . . . . . . . . . . . . . . . . . . . 46 4.2.1 Boolesche Funktionen von einer Variablen . . . . . . . . . . . . . . . 46 4.2.2 Boolesche Funktionen von zwei Variablen . . . . . . . . . . . . . . . . 47 4.2.3 Gatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2.4 Vollst¨andige Operatorensysteme . . . . . . . . . . . . . . . . . . . . . 51 4.2.5 Umformungen Boolescher Ausdru¨cke . . . . . . . . . . . . . . . . . . 52 4.2.6 Kanonische Normalformen . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2.7 Minimale Normalformen und Karnaugh-Diagramme . . . . . . . . . . 58 4.2.8 Ein Beispiel mit Don’t-Cares . . . . . . . . . . . . . . . . . . . . . . . 62 4.2.9 Der Carry-Ripple-Addierer . . . . . . . . . . . . . . . . . . . . . . . . 64 5 Rekursion 69 5.1 Ein schlechtes Beispiel zur Einfu¨hrung: Fakult¨at . . . . . . . . . . . . . . . . 69 5.2 Ein besseres Beispiel: Tu¨rme von Hanoi . . . . . . . . . . . . . . . . . . . . . 72 6 Algorithmen im Vergleich: Komplexit¨at und andere Kriterien 75 6.1 Selectionsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.2 Kriterien zur Bewertung von Sortieralgorithmen . . . . . . . . . . . . . . . . 76 6.3 Weitere einfache Sortierverfahren . . . . . . . . . . . . . . . . . . . . . . . . 78 6.4 Teile-und-herrsche-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 7 Anhang 85 7.1 Zahlensysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 7.1.1 R¨omische Zahlen – ein Additionssystem . . . . . . . . . . . . . . . . 85 7.1.2 Das Dezimalsystem – ein Stellenwertsystem . . . . . . . . . . . . . . 86 7.1.3 Das Dualsystem – ein Stellenwertsystem . . . . . . . . . . . . . . . . 87 7.1.4 Weitere Stellenwertsysteme . . . . . . . . . . . . . . . . . . . . . . . 89 7.1.5 Vorzeichendarstellung im Dualsystem . . . . . . . . . . . . . . . . . . 91 7.1.6 Gleitkommazahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 7.2 Literatur zu Java und zur Programmierung . . . . . . . . . . . . . . . . . . . 95 Kapitel 1 Erste Schritte in Java 1.1 Tools fu¨r Java Um ein Programm zu schreiben und zu testen, ben¨otigt man ein paar Hilfsmittel: • ManbrauchteinenEditor,eineArtprimitiveTextverarbeitung,umdenProgrammcode u¨berhaupt zu schreiben. • Einen Compiler, der den in der Programmiersprache geschriebenen Code vor der Aus- fu¨hrung in Maschinencode oder – wie bei Java – einen Zwischencode u¨bersetzt, fach- sprachlich kompiliert. • Man ben¨otigt eine Umgebung, in der man das Programm oder auch nur Teile davon problemlos testen kann. Am besten, man installiert eine integrierte Entwicklungsumgebung, neudeutsch IDE von Inegrated Development Environment. Die IDE bringt einen Editor mit, der unter anderem durchdurchfarblicheKennzeichnungenhilft,denU¨berblickzubehalten,außerdemintegriert sie gegebenenfalls den Compiler und die Laufzeitumgebung. Damit braucht man nur noch die IDE, um Programme zu erstellen. Es gibt viele IDEs fu¨r die Java-Entwicklung. Am Studienkolleg setzen wir Eclipse ein. Aufgabe 1.1 Tools fu¨r die Java-Programmierung auf dem eigenen Rechner Installieren Sie die Tools, um Java-Programme entwickeln zu k¨onnen, auf Ihrem eigenen Rechner. Zuerst mu¨ssen Sie ein Java Development Kit (JDK) installieren. Dieses beinhal- tet unter anderem den Compiler und die Standard-Bibliothek mit Programmbausteinen. Sie k¨onnen das OpenJDK installieren, dass man unter https://openjdk.java.net/ findet oder das JDK von Oracle, das man auf https://www.oracle.com/technetwork/java/javase/downloads/index.html findet. Eclipse muss ein JDK vorfinden, daher sollte man Eclipse nach dem JDK installieren. Eclipse findet man unter https://www.eclipse.org/. Beachten Sie die Lizenzbedingungen. 6 Kapitel 1. Erste Schritte in Java 1.2 Hallo Welt! Die erste Aufgabe in einer neuen Programmiersprache ist traditionell, den Text Hallo Welt! auszugeben, um einen ersten Eindruck von der Syntax zu bekommen. Dafu¨r erzeugt man in Eclipse ein neues Java-Projekt und darin eine Klasse. Eine Klasse ist, zumindest fu¨r diesen Einstieg, eine Datei mit Java-Code. Der Name der Klasse sollte gem¨aß den Java- Konventionen mit einem Großbuchstaben beginnen. Er darf keine Leerzeichen enthalten. Als Beispiel w¨ahle ich MeineErsteKlasse. Unter der Frage Which method stubs would you like ” create?“ sollte man das H¨akchen bei public static void main(String[] args) setzen, andernfalls muss man diese Zeile, die in jedem Java-Programm vorkommt, selbst tippen. Dann best¨atigt man durch Bet¨atigen der Schaltfl¨ache Finish und erh¨alt den folgenden Code: 1 public class MeineErsteKlasse { 2 3 public static void main(String [] args) { 4 // TODO Auto−generated method stub 5 } 6 } Die erste Zeile ist die U¨berschrift der Klasse. Mit der ¨offnenden geschweiften Klammer beginnt der Rumpf der Klasse. Leerzeilen sind fu¨r den Programmablauf unerheblich und dienen nur der U¨bersichtlichkeit. Zeile 3 ist die U¨berschrift, fachsprachlich Signatur der main()-Methode, mit der jedes Java-Programm gestartet wird. Die Bedeutung der einzelnen Begriffe erfolgt sp¨ater. Mit der ¨offnenden geschweiften Klammer beginnt der Rumpf der main()-Methode. Die Zeichen // beginnen einen Kommentar. Kommentare sind Notizen fu¨r den Programmierer und beeinflussen nicht die Programmausfu¨hrung. Die schließende Klammerindern¨achstenZeilebeendetdiemain()-Methode,dieweitereschließendeKlammer beendet die Klasse. Aufgabe 1.2 Hallo Welt! L¨oschen Sie den Kommentar aus der Klasse und fu¨gen Sie statt dessen die folgende Anweisung ein: 1 System. out . println (”Hallo Welt!”); Speichern (Diskettensymbol in Eclipse) und starten Sie (gru¨ner Pfeil) das Programm. Das Programm sollte den Text Hallo Welt! ausgeben. Wenn es nicht funktioniert, versuchen Sie, die Fehlermeldung in Eclipse zu verstehen und den Fehler zu beheben. Aufgabe 1.3 Ausgabeanweisung In der vorigen Aufgabe haben Sie die Anweisung System.out.println() benutzt, die ei- ne Zeichenkette, fachsprachlich einen String, auf dem Bildschirm ausgibt. In der folgenden Aufgabe lernen Sie eine Variante der Ausgabeanweisung kennen und lernen einiges u¨ber das Aufbauen von Strings. 1.3. Bedingte Anweisung und Verzweigung 7 a) Schreiben Sie folgende main()-Methoden und probieren Sie sie aus: 1 public static void main(String [] args){ 2 System. out . println (”1. Zeile”); 3 System. out . println (”2. Zeile”); 4 System. out . println (”3. Zeile”); 5 } und 1 public static void main(String [] args){ 2 System. out . print (”1. Zeile”); 3 System. out . print (”2. Zeile”); 4 System. out . print (”3. Zeile”); 5 } Was ist der Unterschied zwischen println und print? b) Wie wird der Ausdruck 2 * 2 + 3 in den folgenden main()-Methoden ausgewertet? 1 public static void main(String [] args){ 2 System. out . println (”2∗2+3”); 3 } und 1 public static void main(String [] args){ 2 System. out . println (2∗2+3); 3 } c) Schreiben Sie folgende Methoden und probieren Sie sie aus: 1 public static void main(String [] args){ 2 System. out . println (”2∗2+3 ist ” +(2∗2+3) + ”Stimmt ’s?”) ; 3 } Welche Rolle spielt das Zeichen +“? Was passiert, wenn man bei +(2*2+3) die Klam- ” mern weg l¨asst? 1.3 Bedingte Anweisung und Verzweigung Das folgende kleine Programm benutzt außer der Ausgabe auch eine Eingabe, außerdem kommt eine bedingte Anweisung (if, englisch: falls) vor: 1 import java . util .Scanner; 2 public class Brief { 3 public static void main(String [] args) { 8 Kapitel 1. Erste Schritte in Java 4 Scanner sc = new Scanner(System. in) ; 5 System.out. println (”Masse des Briefs in Gramm?”) ; 6 int m = sc . nextInt () ; 7 sc . close () ; 8 if (m <= 20) { 9 System.out. println (”Masse ” + m +” g, Porto 0,80 Euro”) ; 10 } 11 } 12 } Um die Eingabe zu erm¨oglichen, werden durch die import-Anweisung in Zeile 1 Code- Bausteine aus der Bibliothek eingebunden, so dass wir diesen Code nicht selbst erstellen mu¨ssen. Dies erm¨oglicht es, in Zeile 6 ein Objekt vom Typ Scanner zu erstellen und es der Variablen sc zuzuweisen. Dieser Scanner erledigt in Zeile 8 die Eingabe. Dort wird ei- ne Variable m vom Typ int, das steht fu¨r Integer, ganze Zahl, erstellt, in der die Eingabe des Benutzers abgespeichert wird. Das Zeichen =, das auch schon in Zeile 6 vorkam, nennt man in diesem Zusammenhang Zuweisungsoperator, weil damit der Variablen links davon der Wert des Ausdrucks rechts von diesem Zeichen zugewiesen wird. In Zeile 9 wird der Scanner geschlossen, damit er nicht l¨anger unn¨otig Arbeitsspeicher belegt. In Zeile 10 steht die if-Anweisung, die festlegt, dass die Anweisungen in der folgenden geschweiften Klammer nur ausgefu¨hrt werden, wenn die Bedingung in der if-Anweisung erfu¨llt ist. Bevor man eine Variable benutzen kann, muss sie immer zun¨achst deklariert und dann initialisiert werden. Bei der Deklaration schreibt man den Typ der Variablen und den Be- zeichner, z.B. int m;“ deklariert eine Variable vom Typ int. Bei der Deklaration einer int- ” Variablen wird der Speicherplatz im Arbeitsspeicher des Rechners fu¨r diese Variable reser- viert. Bei der Initialisierung wird einer Variablen zum ersten Mal ein Wert zugeordnet, z.B. durch m = 42;“. Deklaration und Initialisierung k¨onnen auch, wie im Programm geschehen, ” in einer einzigen Zeile erfolgen, beispielsweise int m = 42;“. ” Aufgabe 1.4 else (andernfalls) a) Erg¨anzen Sie im obigen Programm zwischen den Zeilen 12 und 13 die Zeilen 1 else { 2 System. out . println (”Kann nicht fuer 0,80 Euro verschickt werden.”); 3 } b) Wie kann man das Programm aus Teil a ohne Verwendung von else schreiben? if- und else-Anweisungen du¨rfen auch geschachtelt werden wie in der folgende main()- Methode: 1.3. Bedingte Anweisung und Verzweigung 9 1 public static void main(String [] args) { 2 Scanner sc = new Scanner(System. in) ; 3 System.out. println (”Masse des Briefs in Gramm?”) ; 4 int m = sc . nextInt () ; 5 System.out. println (”Dicke des Briefs in Zentimeter?”) ; 6 double h = sc .nextDouble() ; 7 sc . close () ; 8 if (m > 20){ 9 System.out. println (”Zu schwer fuer 0,80 Euro!”) ; 10 } 11 else { 12 if (h > 0.5) { 13 System.out. println (Zu dick fuer 0,80 Euro!”) ; 14 } 15 else { 16 System.out. println (”Porto: 0,80 Euro”) ; 17 } 18 } 19 } In dem Beispiel kommt der Datentyp double vor. Er steht fu¨r eine Zahl mit Komma. Wenn es Sie st¨ort, dass man die Zahl mit Komma eingeben muss, sie aber mit Punkt ausgege- ben wird, dann k¨onnen Sie nach Zeile 2 noch die Zeile sc.useLocale(Locale.US); einfu¨gen, außerdem ganz oben import java.util.Locale;. Wenn Sie die Ausgabe mit Komma statt mit Punkt haben m¨ochten, dann k¨onnen Sie in Zeile 14 des obigen Programms h durch String.valueOf(h).replace(”.”, ”,”) ersetzen. Bedingungen k¨onnen aus mehreren Teilbedingungen, die mit UND, in Java &&, oder ODER, in Java ||, zusammengesetzt sind, aufgebaut sein. Beispiel: 1 if (m <= 20 && h <= 0.5){ 2 System.out. println (”Porto: 0,80 Euro”) ; 3 } 4 if (m > 20 || h > 0.5){ 5 System.out. println (”Kostet mehr als 0,80 Euro”) ; 6 } Aufgabe 1.5 Portoberechner a) Schreiben Sie ein Programm, das den Benutzer auffordert, Masse m, L¨ange l, Breite b und H¨ohe h eines Briefs einzugeben und dann das n¨otige Porto berechnet oder den Benutzer darauf hinweist, dass die Sendung nicht als Brief versendet werden kann. Es gilt: • Standardbrief 0,80 e: m <= 20 g, 14 cm <= l <= 23,5 cm, 9 cm <= b <= 12,5 cm, h <= 0,5 cm 10 Kapitel 1. Erste Schritte in Java • Kompaktbrief 0,95 e: m <= 50 g, 10 cm <= l <= 23,5 cm, 7 cm <= b <= 12,5 cm, h <= 1,0 cm • Großbrief 1,55 e: m <= 500 g, 10 cm <= l <= 35,3 cm, 7 cm <= b <= 25 cm, h <= 2,0 cm • Maxibrief 2,70 e: m <= 1000 g, 10 cm <= l <= 35,3 cm, 7 cm <= b <= 25 cm, h <= 5,0 cm b) Beru¨cksichtigen Sie auch folgende Regel: Bei einem Standard- oder Kompaktbrief muss die L¨ange mindestens das 1,4-fache der Breite betragen. 1.4 Die while-Schleife Wenn ein Benutzer im Portorechner eine negative Masse des Briefs eingibt, dann ist mit der Eingabe etwas faul. Am besten, sie wird sofort wiederholt. Dies k¨onnte man durch folgende Zeilen bewerkstelligen: 1 System.out. println (”Masse des Briefs in Gramm?”) ; 2 int m = sc . nextInt () ; 3 if (m < 0) { 4 System.out. println (”Nochmal! Masse kann nicht negativ sein , du Depp!”) ; 5 m = sc . nextInt () ; 6 } Diese L¨osung hat allerdings zwei kleine Nachteile. Zum einen: Falls Sie je vorhaben, Ihr Geld damit zu verdienen, Programme an potentielle Anwender zu verkaufen, sollten Sie sich h¨oflicher ausdru¨cken. Zum anderen: Ein guter Programmierer redet seine Benutzer zwar nicht als Depp“ an, dennoch geht er davon aus, dass der Benutzer vielleicht nicht sehr klug ” ist. Dies ist hier nicht der Fall: Der Benutzer k¨onnnte zweimal hintereinander eine negative Zahl einzugeben. Dagegen hilft ein zweites if. Was aber, wenn der Benutzer dreimal einen negativen Wert eingibt? Eine gute L¨osung sieht so aus: 1 System.out. println (”Masse des Briefs in Gramm?”) ; 2 int m = sc . nextInt () ; 3 while (m < 0) { 4 System.out. println (”Bitte eine positive Masse in Gramm eingeben .”) ; 5 m = sc . nextInt () ; 6 } Eine noch elegantere L¨osung erh¨alt man, wenn man die kopfgesteuerte durch eine fußge- steuerte while-Scheife, manchmal auch do-while-Schleife genannt, ersetzt: