01_Einleitung_v3.pdf

Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informatik I: Grundlagen der Programmierung...

Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informatik I: Grundlagen der Programmierung Kapitel 1: Einleitung Prof. Dr. Fabian Gieseke Institut für Wirtschaftsinformatik Universität Münster Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.1  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Übersicht 1 Informatik 2 Informationen und Daten 3 (Moderne) Computersysteme 4 Maschinenmodelle 5 Probleme & Algorithmen 6 Programme & Programmiersprachen 7 Zusammenfassung Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.2  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Übersicht 1 Informatik 2 Informationen und Daten 3 (Moderne) Computersysteme 4 Maschinenmodelle 5 Probleme & Algorithmen 6 Programme & Programmiersprachen 7 Zusammenfassung Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.3  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informatik Bildquelle: https://pixabay.com Fragen 1 Was ist Informatik? 2 Seit wann gibt es den Begriff? 3 Woher kommt der Begriff? Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.4  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Der Begriff Informatik“ ” Wurzeln der Informatik? Man kann das Jahr 1941 wählen, in dem Konrad Zuse seinen Rechenautomaten Z3 vorstellte, oder das Jahr ” 1947, in dem die erste Informatikgesellschaft in den USA entstand, oder man kann sich für das Jahr 1960 entscheiden, in dem der weltweite Informatik-Dachverband gegründet wurde. In Europa wurde das Wort Informatik in den sechziger Jahren eingeführt.“ Gesellschaft für Informatik, 2006, [fIe06] Was ist Informatik (eine Definition) Der Begriff Informatik“, der eine Wortneubildung bzw. eine Begriffsverschmelzung aus den beiden Wörtern ” ” Information“ und Automatik“ ist, wurde Ende der 1950er Jahre von dem Deutschen Karl Steinbuch ” ” eingeführt. [... ] Während sich in Europa dieser Begriff etabliert hat, wird in angelsächsischen Ländern stattdessen der Begriff computer science (Computerwissenschaft)“ verwendet. ” Informatik ist allerdings mehr als nur eine Computerwissenschaft, denn sie umfasst ganz allgemein die automatisierte Informationsverarbeitung in Natur, Technik und Gesellschaft. [HLWH17] Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.5  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informatik und ihre Teilgebiete Was ist Informatik (noch eine Definition) Die Wissenschaft Informatik befasst sich mit der Darstellung, Speicherung, Übertragung und Verarbeitung ” von Information. Dabei untersucht sie die unterschiedlichsten Aspekte: elementare Strukturen und Prozesse, Prinzipien und Architekturen von Systemen, Interaktionen in kleinen, mittleren und weltumspannenden Netzen, die Konzeption, Entwicklung und Implementierung von Hardware und Software bis hin zu hochkomplexen Anwendungssystemen und der Reflexion über ihren Einsatz und die Auswirkungen.“ Gesellschaft für Informatik, 2006, [fIe06] Teilgebiete der Informatik Theoretische Informatik: Befasst sich mit den theoretischen Grundlagen Angewandte Informatik und bildet die Basis für die technische und praktische Informatik. Technische Informatik: Befasst sich Frage: mit Grundlagen Welche der Sie? Technische Informatik im Bereichkennen Gebiete der Informatik Praktische Informatik technischen Entwicklung von Informationssystemen. Theoretische Informatik Praktische Informatik: Zielt auf grundlegende Konzepte zur Lösung von Problemen ab, wie z. B. der Entwicklung von effizienten Verfahren oder von neuen Programmiersprachen. Angewandte Informatik: Nutzt Verfahren der obigen Bereiche in den verschiedensten Fachgebieten. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.6  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Teilgebiete der Informatik Theoretische Informatik (Ausblick) Befasst sich mit den theoretischen Grundlagen und bildet die Basis für die technische und praktische Arbeitsband Informatik. Teilbereiche der theoretischen Informatik sind beispielsweise: # # 0 1 1 # # Lese-/ Automatentheorie Schreibkopf Aktueller (z. B. Analyse abstrakter Maschinen wie der Turingmaschine) Zustand Programm Berechenbarkeitstheorie CPU (z. B. Analyse, welche Probleme lösbar/berechenbar sind) Komplexitätstheorie M/B I/Os (z. B. Analyse des Ressourcenbedarfs von Verfahren) B Formale Sprachen Main Memory Disk (z. B. Analyse von Grammatiken und formalen Sprachen)... Angewandte Informatik Technische Informatik Praktische Informatik Theoretische Informatik Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.7  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Bildquelle: ZeptoBars, CC BY 3.0 https://creativecommons.org/licenses/by/3.0, via Wikimedia Commons Teilgebiete der Informatik https://pixabay.com Technische Informatik (Ausblick) Befasst sich mit Grundlagen im Bereich der technischen Entwicklung von Informationssystemen. Teilbereiche der technischen Informatik sind beispielsweise: Rechnerarchitektur (z. B. Entwurf neuer Computerprozessoren) Mikroprozessoren und Mikrocontroller (z. B. Entwicklung von kleinen Computern) Betriebssysteme (z. B. Verwaltung der Ressourcen eines Computers) Systeme für parallele Verarbeitung (z. B. Grafikkarten)... Angewandte Informatik Technische Informatik Praktische Informatik Theoretische Informatik Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.8  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Teilgebiete der Informatik Bildquelle: https://pixabay.com Praktische Informatik (Ausblick) Zielt auf grundlegende Konzepte zur Lösung von Problemen ab, wie z. B. der Entwicklung von effizienten Verfahren oder von neuen Programmiersprachen. Teilbereiche der praktischen Informatik sind beispielsweise: Algorithmen und Datenstrukturen candidate pairs! B buckets (z. B. Implementierung effizienter Algorithmen) per band 2 1 2 1 r rows 2 1 4 1 1 2 1 2 Datenbanken b bands (z. B. effiziente Speicherung und Verwaltung großer Datenmengen) Software Engineering Signature Matrix (z. B. Methodische Entwicklung großer Softwaresysteme) IT Security (z. B. Entwicklung von sicheren Systemen)... Angewandte Informatik Technische Informatik Praktische Informatik Theoretische Informatik Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.9  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Teilgebiete der Informatik Bildquelle: https://camunda.com/bpmn/ und Prof. Dr. med. Ali Yilmaz (UKM) Angewandte Informatik (Ausblick) Nutzt Verfahren der anderen Gebiete der Informatik in den verschiedensten Fachgebieten (z. B. Medizin, Physik, Wirtschaft,... ). Teilbereiche der angewandten Informatik sind beispielsweise: Geoinformatik (z. B. Analyse von Satellitendaten) Wirtschaftsinformatik (z. B. Modellierung von Prozessen) Medizin (z. B. Analyse von MRT-Aufnahmen) Machine Learning (z. B. Optimierung)... Angewandte Informatik Technische Informatik Praktische Informatik Theoretische Informatik Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.10  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Übersicht 1 Informatik 2 Informationen und Daten 3 (Moderne) Computersysteme 4 Maschinenmodelle 5 Probleme & Algorithmen 6 Programme & Programmiersprachen 7 Zusammenfassung Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.11  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationen & Daten Verarbeitung von Information? Informatik ist die Wissenschaft von der systematischen und automatisierten Verarbeitung von Informationen. ” Sie erforscht grundsätzliche Verfahrensweisen der Informationsverarbeitung und allgemeine Methoden ihrer Anwendung in den verschiedensten Bereichen.“ [Bal99] Information und Daten ([GS11]) Die Begriffe Information und Daten sind in der Informatik von zentraler Bedeutung. Daten: Messwerte, Zeichen, Fotos, Texte, Tabellen,... (Daten besitzen zunächst keine spezifische Aussagekraft (Rohwerte)) Information ▶ Beispiel: Die Zahl 19 oder der Text Leonardo Campus“ sind Daten. ” Repräsentation Abstraktion Information: Entsteht, wenn Daten verarbeitet, interpretiert oder in einen bestimmten Kontext gesetzt werden. Daten ▶ Beispiel: Die Zahl 19 im Kontext einer Wettervorhersage für die Temperatur ist eine Information ( Morgen wird es vermutlich bis zu 19◦ ” Grad warm.“) Repräsentation ist der Prozess, Information als Daten darzustellen. Den Prozess der Interpretation von Daten als Information nennt man Abstraktion. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.12  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationen & Daten Informationsverarbeitung Information Information Repräsentation Abstraktion Datenverarbeitung Daten Daten Informationsverarbeitung ([GS11]) Information kann von Maschinen nicht verarbeitet werden → wird auf Basis ihrer Repräsentation verarbeitet: 1 Information wird durch Daten repräsentiert. 2 Daten werden verarbeitet (Datenverarbeitung). 3 Neue Information wird aus den enstandenen Daten abstrahiert. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.13  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationen & Daten Das Bit ([GS11]) Ein Bit ist die kleinste Einheit von Information. Es beschreibt die Informationsmenge, die erforderlich ist, um die Antwort auf eine Ja/Nein-Frage mit genau zwei möglichen Antworten zu geben. ja oder nein wahr oder falsch links oder rechts... In der Informatik nutzt man allgemein die Zeichen 0 und 1 zur Repräsentation dieser Informationsmenge. Ein Bit kann physikalisch über elektrische Ladungen (0=ungeladen; 1=geladen), elektrische Spannungen (0=0 Volt; 1=5 Volt) oder Magnetisierung (0=unmagnetisiert; 1=magnetisiert) dargestellt werden. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.14  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Bitfolgen Bitfolgen ([GS11]) Wenn eine Frage mehrere mögliche Antworten zulässt, umfasst die Antwort mehr als ein Bit an Informationen. In diesem Fall verwendet man Bitfolgen, um die Antwort zu repräsentieren. Es gibt genau 2n verschiedene Bitfolgen der Länge n. Beispiel Aus welcher Himmelsrichtung weht der Wind?“ kann in zwei Ja/Nein-Fragen umgewandelt werden: ”▶ Weht der Wind aus einer der Richtungen Nord oder Ost (ja/nein)? ▶ Weht der Wind aus einer der Richtungen Ost oder West (ja/nein)? Mögliche Repräsentation: 10 entspricht ja auf die erste und nein auf die zweite Frage Dementsprechend können die vier Antworten anhand von Bitfolgen der Länge 2 repräsentiert werden: 00 ↔ Süd 01 ↔ West 10 ↔ Nord 11 ↔ Ost Beobachtung: Es kann auch eine andere beliebige (aber eindeutige) Zuordnung der Himmelsrichtungen zu diesen Bitfolgen verwendet werden. Entsprechend können 23 Himmelsrichtungen (Südost,... ) mit Bitfolgen der Länge 3 dargestellt werden. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.15  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Bytes (und viele Bytes) Byte Eine Gruppe von 8 Bits nennt man ein Byte. Es gibt dementsprechend 28 verschiedene Bytes (von 00000000 bis 11111111). Größenangaben (Dezimalsystem) Größenangaben (Binärsystem) 1 1 kB = 1000 Byte (Kilobyte) 1 KiB = 10241 Byte (Kibibyte) 2 1 MB = 1000 Byte (Megabyte) 1 MiB = 10242 Byte (Mebibyte) 1 GB = 10003 Byte (Gigabyte) 1 GiB = 10243 Byte (Gibibyte) 4 1 TB = 1000 Byte ist ein Megabyte? Was 1 Frage: Was(Terabyte) istTiB = 10244 Byte ein Mebibyte? (Tebibyte) 1 PB = 10005 Byte (Petabyte) 1 PiB = 10245 Byte (Pebibyte) 6 1 EB = 1000 Byte (Exabyte) 1 EiB = 10246 Byte (Exbibyte) 1 ZB = 10007 Byte (Zettabyte) 1 ZiB = 10247 Byte (Zebibyte) 8 8 1 YB = 1000 Byte (Yottabyte) 1 YiB = 1024 Byte (Yobibyte) International empfohlende Schreibweise Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.16  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.17  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Bitfolgen Hexziffern Lange Bitfolgen werden für Menschen schnell unübersichtlich. Bitfolgen werden daher manchmal in Gruppen von 4 Bits dargestellt, wobei für die Darstellung eines solchen Blocks auf sogenannte Hexziffern zurückgegriffen wird: 0000 = 0 0100 = 4 1000 = 8 1100 = C 0001 = 1 0101 = 5 1001 = 9 1101 = D 0010 = 2 0110 = 6 1010 = A 1110 = E 0011 = 3 0111 = 7 1011 = B 1111 = F Hierbei wird also auf die Ziffern ’0’ bis ’9’ sowie auf die Buchstaben ’A’ bis ’F’ zurückgegriffen, um die 24 = 16 möglichen Bitfolgen der Länge 4 darzustellen. Beispiel Bitfolge: 00011110111000110111110101001111 Folge von Hexziffern: 1EE37D4F Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.18  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung Information Repräsentation Abstraktion Daten Frage: Wie können Zahlen, Texte, Fotos, etc. repräsentiert werden? Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.19  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung: Zahlendarstellung Zahlendarstellung Sei x ∈ N0 eine beliebige nicht-negative ganze Zahl und sei B ∈ N \ {1} eine beliebige Basis. Dann kann x dargestellt werden durch n−1 X x = a0 B 0 + a1 B 1 +... + an−1 B n−1 = ai B i , (1) i=0 wobei ai ∈ N0 mit 0 ≤ ai < B die Ziffern (i = 0, 1,... , n − 1) und n die Länge der Ziffernfolge sind. Die Zahl x wird dann dargestellt durch x = (an−1... a0 )B ; für B = 16 (Hexadezimalziffern) wird stattdessen auch oft ein ’h’ angehängt oder ein 0x vorangestellt. Zahlensysteme Binärsystem (B=2): (1101)2 stellt x = 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = 13 dar Oktalsystem (B=8): (4711)8 stellt x = 4 · 83 + 7 · 82 + 1 · 81 + 1 · 80 = 2505 dar Dezimalsystem (B=10): (632)10 stellt x = 6 · 102 + 3 · 101 + 2 · 100 = 632 dar Hexadezimalsystem (B=16): (14F7)16 stellt x = 1 · 163 + 4 · 162 + 15 · 161 + 7 · 160 = 5367 dar Schreibweisen: 97 = (01100001)2 = (141)8 = (97)10 = (61)16 = 61h = 0x61 Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.20  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung: Natürliche Zahlen Natürliche Zahlen Wir können mit n Bits den Zahlenbereich von 0 bis 2n − 1 abdecken: 4 Bits: Es können 24 verschiedene Zahlen dargestellt werden (von 0 bis 15). 1 Byte: Es können 28 verschiedene Zahlen dargestellt werden (von 0 bis 255). 2 Byte: Es können 216 verschiedene Zahlen dargestellt werden (0 bis 65.535). 4 Byte: Es können 232 verschiedene Zahlen dargestellt werden (von 0 bis 4.294.967.295). 8 Byte: Es können 264 verschiedene Zahlen dargestellt werden (von 0 bis 18.446.744.073.709.551.615).... Beispiel (4 Byte) (0)10 = (00000000000000000000000000000000)2 (1)10 = (00000000000000000000000000000001)2 (4294967295)10 = (11111111111111111111111111111111)2 Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.21  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Rechenoperationen Division mit Rest (Beispiel): 17 div 5 = 3 und 17 mod 5 = 2 Addition (Beispiel) Seien x = (an−1... a0 )B und y = (bn−1... b0 )B zwei Zahlendarstellungen bzgl. einer Basis B ∈ N \ {1}. Die Zahlendarstellungen werden, analog zu Dezimalzahlen, addiert. Entsteht an einer Position i ein Übertrag (engl.: carry ), so wird dieser zur nächsthöheren Position addiert. Betrachte Positionen von rechts“ nach links“ (also von i = 0 bis i = n − 1). Für Position i sei ” ” s = ai + bi + ui−1 , wobei ui−1 ein möglicher Übertrag aus Position i − 1 ist (wir setzen u−1 := 0). Das Ergebnis der Addition für Position i ist ci = s mod B mit Übertrag ui = s div B. Beispiel ([GS11]) B=2 B=8 B = 16 11101010 352 EA + 10110011 + 263 + B3 110011101 635 1 9D Frage: Was passiert, wenn für B = 2 nur 1 Byte (n = 8) zur Speicherung/Darstellung verwendet wird und bei der letzten (höchsten) Position ein Übertrag entsteht? Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.22  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung: Ganze Zahlen Ganze Zahlen Die Zweierkomplementdarstellung ist die gängige Repräsentation ganzer (positiver und negativer) Zahlen im binären Zahlensystem. Beispielsweise erhält man für n = 4 Bits: 0000 = +0 0100 = +4 1000 = -8 1100 = -4 0001 = +1 0101 = +5 1001 = -7 1101 = -3 0010 = +2 0110 = +6 1010 = -6 1110 = -2 0011 = +3 0111 = +7 1011 = -5 1111 = -1 Das erste Bit von links stellt das Vorzeichen dar. Um Verwechslungen zu vermeiden, kennzeichnet man die Darstellung mit einem ’z’, also z. B. (1001)z. Sei n ∈ N mit n ≥ 2. Eine Zweierkomplementdarstellung (bn−1... b0 )z ist wie folgt definiert: ▶ (0 bn−2... b0 )z = (0 bn−2... b0 )2 ▶ (1 bn−2... b0 )z = −2n−1 + (0 bn−2... b0 )2 Für positive Zahlen stimmen beide Darstellungen überein... Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.23  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung: Ganze Zahlen Ausblick: Ganze Zahlen in Java 1 Byte: Es werden Zahlen von −128 bis 127 dargestellt (byte) 2 Byte: Es werden Zahlen von −32768 bis 32767 dargestellt (short) 4 Byte: Es werden Zahlen von −231 bis 231 − 1 dargestellt (int) 8 Byte: Es werden Zahlen von −263 bis 263 − 1 dargestellt (long) Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.24  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung: Kommazahlen Beispiel: Technisch-wissenschaftliche Darstellung Möglichkeiten: −273, 15 = −273, 15 · 100 = −27, 315 · 101 = −2, 7315 · 102 = −0, 27315 · 103 Normierte Darstellung: Erste Ziffer (ungleich 0) direkt vor dem Komma, also −2, 7315 · 102 Mantisse und Exponent: Die Folge 2, 7315 nennt man Mantisse und die Ziffer 2 Exponent. Alternative Schreibweise: −2, 7315 · 102 = (−1)1 (2, 7315) · 102 Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.25  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung: Kommazahlen Gleitkommadarstellung Gleitkommazahlen sind von der Form ! n−1 X v e v −i (−1) (a0 , a1 a2... an−1 )B · B := (−1) ai B Be, (2) wobei i=0 v ∈ {0, 1} das Vorzeichen, B ∈ N \ {1} die Basis, (a0 , a1 a2... an−1 )B mit ai ∈ N0 und 0 ≤ ai < B die Mantisse (zur Basis B) und e ∈ Z der Exponent ist. Die Zahl n ist die Mantissenlänge. Die Darstellung heißt normiert falls a0 ̸= 0. Beispiel B = 10: (−1)1 (2, 7315)10 · 102 = − 2 · 100 + 7 · 10−1 + 3 · 10−2 + 1 · 10−3 + 5 · 10−4 · 102 = −273, 15
B = 2: (−1)0 (1, 0101)2 · 21 = 1 · 20 + 0 · 2−1 + 1 · 2−2 + 0 · 2−3 + 1 · 2−4 · 21 = 2, 625
B = 2: (−1)0 (1, 0)2 · 2−3 = 1 · 20 + 0 · 2−1 · 2−3 = 0, 125
Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.26  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung: Kommazahlen Warnung: Werte x ∈ R werden i. A. nur approximiert gespeichert! Binäre Gleitkommazahlen (IEEE 754-Gleitkommazahl (32 Bit); auch float in Java) 1 Bit 8 Bits 23 Bits v e a1 a2... an−1 n−1 ai 2−i 2e−127 P  (−1)v i=0 Vorzeichenbit (1 Bit): Entweder 0 oder 1. Exponent (8 Bits): Der Exponent wird mit einem Verschiebewert von 127 gespeichert. Ein gespeicherter Wert von z. B. e = 132 entspricht einem tatsächlichen Exponenten von e = e − 127 = 5. Mantisse (23 Bits): Speichert die Mantisse in normierte Form (ohne a0 , da für B = 2 immer a0 = 1 gilt). Beispiel 1 Bit 8 Bits 23 Bits 0 10000011 10101000000000000000000 Ergebnis: (−1)0 · (1 · 20 + 1 · 2−1 + 0 · 2−2 + 1 · 2−3 + 0 · 2−4 + 1 · 2−5 ) · 24 = 26, 5 Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.27  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung: Text ASCII Um Texte darzustellen, kodiert man Buchstaben, Satzzeichen, Sonderzeichen, etc. als Bitfolgen. Der sogenannte ASCII-Code (American Standard Code for Information Interchange) ist ein standardisiertes Zeichensystem und ordnet einem (von 128) Zeichen eine Zahl von 0 bis 127 zu (ASCII 128). Repräsentation: 1 Byte (1 Kontrollbit + 7 Bits für 128 Zeichen) Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.28  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung: Text Zeichenketten Texte werden oft als eine Folge von Textzeichen, sogenannter Zeichenketten (engl.: strings), dargestellt. Text: Ist mir alles egal!“ ” ASCII (Dez): 73 115 116 32 109 105 114 32 97 108 108 101 115 32 101 103 97 108 33 0 ASCII (Hex): 49 73 74 20 6D 69 72 20 61 6C 6C 65 73 20 65 67 61 6C 21 00 ASCII (Binär): 01001001 01110011 01110100 00100000 01101101 01101001 01110010 00100000 01100001 01101100 01101100 01100101 01110011 00100000 01100101 01100111 01100001 01101100 00100001 00000000 Oft wird das Ende einer Zeichenkette mit dem (ASCII-)Zeichen NUL=00 markiert. Diese heißen dann nullterminierte Strings. ASCII-Erweiterungen Der ursprüngliche ASCII-Code nutzt nur 7 Bits und wurde in der Vergangenheit erweitert. Heutzutage üblich ist z. B. UTF-8 (UTF=Universal Character Set Transformation Format). Dieses Format ist eine Mehrbyte-Kodierung, d. h., es werden pro Zeichen 1 bis 6 Byte genutzt. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.29  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Informationsdarstellung: Fotos/Musik/... Beispiel: Fotos Ein Foto kann z. B. als Folge von Rasterpunkten (Pixeln) aufgefasst werden. Pro Pixel kann man z. B. ein Byte (einfarbig) oder drei Bytes (mehrfarbig) verwenden: ▶ RGB (Standard): Drei Grundfarben Rot, Grün und Blau (jeweils 1 Byte pro Kanal) ▶ Schwarzer Pixel: (0, 0, 0), Weißer Pixel: (255, 255, 255), Roter Pixel: (255, 0, 0) Oft werden Bilder in komprimierter Form gespeichert (z. B. JPG). (mehr dazu in Vorlesungen über Computer Vision/Machine Learning/... ) Beispiel Ein Bild mit einer Auflösung von 1920 × 1080 Pixeln und drei Farbkanälen (RGB; jeweils 1 Byte) kann durch eine Bitfolge der Länge 1920 · 1080 · 3 Bytes dargestellt werden (ca. 6,22 MB). Zusätzlich muss noch die Größe kodiert werden (z. B. Speicherung von Höhe und Breite). Bildquelle: https://pixabay.com Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.30  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Übersicht 1 Informatik 2 Informationen und Daten 3 (Moderne) Computersysteme 4 Maschinenmodelle 5 Probleme & Algorithmen 6 Programme & Programmiersprachen 7 Zusammenfassung Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.31  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Historische Entwicklung Rechenmaschinen Die Entwicklung von Rechenmaschinen reicht weit zurück. Bereits in der Antike wurden mechanische Geräte verwendet, um z. B. mathematische Berechnungen zu erleichtern: Abakus (ca. 1100 v. Chr.): Eine der ältesten Rechenmaschinen, bestehend aus z. B. Holztafel mit beweglichen Perlen/Steinen (Addition, Subktration). Wilhelm Schickard (1623): Erste Rechenmaschine (Addieren, Abakus Subtrahieren, Dividieren, Multiplizieren) Charles Babbage (1838): Prinzip der Analytics Engine (Zahlenspeicher, Rechenwerk,... ) → programmgesteuerte Maschine (mechanischer Vorläufer heutiger Rechner!)... Schickard (Skizze) Schickard (Nachbau) Bildquelle (Abakus): HB, Public domain, via Wikimedia Commons Bildquelle (Schickard, links): Wilhelm Schickard, Public domain, via Wikimedia Commons Bildquelle (Schickard, rechts): Herbert Klaeren, CC BY-SA 3.0, via Wikimedia Commons Analytics Machine (Nachbau) Bildquelle (Babbage): Bruno Barral (ByB), CC BY-SA 2.5, via Wikimedia Commons Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.32  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Historische Entwicklung Funktionsfähige Computer Mit der Einführung des elektrischen Stroms sowie der Elektrotechnik fanden entsprechende Komponenten zunehmend Verwendung bei dem Bau von Rechenmaschinen. Z3 (1941): Konrad Zuse entwickelte die Z3 (erster funktionsfähige programmgesteuerter Rechenautomat); z. B. binäre Gleitkommaarithmetik; programmierbar mit Lochstreifen Mark I (1944): Howard Aiken entwickelte Mark I (gemeinsam mit Z3 (Nachbau) Harvard University und IBM); vollständig aus elektromechanischen Bauteilen; programmierbar mit Lochstreifen ENIAC (1946): Fläche ca. 10 × 17 m groß; Gewicht 27 Tonnen; Addition/Subtraktion brauchte 0,2 Millisekunden; programmierbar durch Neuverkabelung Von-Neumann-Architektur (1945): Entwicklung der Fundamentalprinzipien einer Rechenanlage durch John Mark I ENIAC von Neumann → Konzept Grundlage für heutige Rechner! Bildquelle (Z3): Venusianer, CC BY-SA 3.0, via Wikimedia Commons... Bildquelle (Mark I): Daderot at English Wikipedia., CC BY-SA 3.0, via Wikimedia Commons Bildquelle (ENIAC): U.S. Army Photo, Public domain, via Wikimedia Commons Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.33  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Aktuelle Computersysteme: Beispiel I Bildquelle: https://pixabay.com Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.34  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Aktuelle Computersysteme: Beispiel II Bildquelle: OLCF at ORNL, CC BY 2.0, via Wikimedia Commons Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.35  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Aktuelle Computersysteme: Beispiel III Bildquelle: https://wiki.seeedstudio.com/xiao_esp32s3_getting_started/ Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.36  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Aktuelle Computersysteme: Mainboards Bildquelle: smial (FAL or GFDL 1.2), via Wikimedia Commons Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.37  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Abstraktion: Ein Kernelement der Informatik! Faster and smaller memories Internal Memory External Memory CPU L1 L2 L3 Registers Reale Computer + Maschinenmodelle Die technische Entwicklung/Verbesserung von Computern nur ein (kleiner) Bereich der Informatik. Oft ist die konkrete technische Umsetzung nicht relevant. Stattdessen werden gewisse Cache Main Memory Hard Disks Maschinenmodelle für die Entwicklung und Analyse von Verfahren angenommen. (Hintergrund: Berechnungsmodell für die Analyse von speicherintensiven Verfahren) GPU Wichtiges Konzept in der Informatik: Abstraktion! Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.38  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Übersicht 1 Informatik 2 Informationen und Daten 3 (Moderne) Computersysteme 4 Maschinenmodelle 5 Probleme & Algorithmen 6 Programme & Programmiersprachen 7 Zusammenfassung Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.39  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Abstraktion: Ein Kernelement der Informatik! Universelle Rechner Ein Universalrechner ist eine Maschine, die nicht für einen konkreten Zweck entwickelt wurde. Stattdessen kann sie die verschiedensten Probleme durch (mathematische) Berechnungen lösen und ist frei ” programmierbar“. Unabhängig von konkreter Computerarchitektur Verfahren/Programm ist Teil der Eingabe (→ frei programmierbar) Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.40  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Das von-Neumann’sche Rechnermodell Architektur ([HLWH17]) Die Von-Neumann-Architektur ist das Grundprinzip, auf dem die meisten modernen Computer basieren. Der Prozessor (engl.: central processing unit (CPU)) besteht aus: CPU ▶ Steuerwerk: Das Steuerwerk steuert die (sequentielle) Abarbeitung Steuerwerk von Instruktionen, welche durch ein Programm gegeben sind. ▶ Rechenwerk: Das Rechenwerk wird gesteuert und führt Rechenwerk arithmetische und logische Operationen aus. ▶ Registern: Ein Register ist eine Speicherzelle, welche wenige Bits Register speichern kann (Bitlänge pro Zelle fest pro Architektur). Speicher Speicher: Der Speicher besteht aus einer endlichen Folge von Eingabe Daten Programm Ausgabe Speicherzellen (Zugriff über Adresse/Nummer der Zelle), welche jeweils auch wenige Bits speichern können. Der Speicher enthält Datensignale sowohl das Programm als auch die Daten (Binärformat). Steuersignale Ein- und Ausgabe: Die Ein-/Ausgabeeinheiten (Bildschirm, Tastatur, Lochkarten,... ) nehmen neue Befehle/Daten entgegen und geben Daten aus. Verbindungsbus: Das Bussystem ist ein Kommunikationssystem, welches Daten und Steuersignale zwischen den verschiedenen Komponenten (CPU, Speicher, Ein-/Ausgabe,... ) überträgt. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.41  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Das von-Neumann’sche Rechnermodell CPU Steuerwerk Rechenwerk Register Speicher Eingabe Daten Programm Ausgabe Datensignale Steuersignale Ablauf der Befehlsverarbeitung 1 Laden: Das Steuerwerk holt eine Instruktion aus dem Speicher (mittels der Adresse der Instruktion). 2 Dekodieren: Das Steuerwerk dekodiert die Instruktion und prüft, welche Operation ausgeführt werden soll. 3 Ausführen: Befehl wird ausgeführt (z. B. eine Berechnung mit Rechenwerk). 4 Speichern: In Abhängigkeit von dem Befehl wird etwas in einem Register/im Speicher abgelegt. 5 Wiederholen: Der Zyklus beginnt mit der nächsten Instruktion von vorne. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.42  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Ausblick: Details z. B. in Vorlesung Das von-Neumann’sche Rechnermodell über IT-Systeme/Rechnerstrukturen CPU Steuerwerk Rechenwerk Register Speicher Eingabe Daten Programm Ausgabe Datensignale Steuersignale Beispiel: Ablauf der Befehlsverarbeitung 1 Laden: Das Steuerwerk holt die Instruktion add eax, 10 aus dem Speicher. 2 Dekodieren: Das Steuerwerk erkennt, dass es eine Additionsoperation ist und aktiviert das Rechenwerk. 3 Ausführen: Das Rechenwerk addiert den Wert 10 zu dem Register eax. 4 Speichern: Das Ergebnis wird in das Register eax geschrieben. 5 Wiederholen: Der Zyklus beginnt mit der nächsten Instruktion von vorne. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.43  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Turingmaschine Aufbau Eine Turingmaschine ist ein Modell benannt nach dem englischen Mathematiker Alan M. Turing (1912–1954). Besitzt ein nach beiden Seiten unbegrenztes Arbeitsband, welches in Felder aufgeteilt ist. Besitzt einen Lese-/Schreibkopf (LS-Kopf), der über das Arbeitsband bewegt werden kann und genau über einem Feld des Bandes (Arbeitsfeld) steht. Der LS-Kopf kann ein Zeichen in das Arbeitsfeld schreiben oder ein Zeichen aus dem Arbeitsfeld lesen. Befindet sich zu jedem Zeitpunkt in einem von endlich vielen Zuständen. Speichert ein Programm und den aktuellen Zustand. Arbeitsband # # 0 1 1 # # Lese-/ Schreibkopf Aktueller Zustand Programm Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.44  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Turingmaschine Definition: Alphabet Ein Alphabet ist eine endliche Menge von Zeichen. Beispiele Leeres Alphabet: {} Lateinisches Alphabet: {a, b, c,... , z, A, B,... , Z} Ziffern: {0, 1,... , 9} Noch ein Alphabet: {l, b, o, e, !, d} Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.45  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Turingmaschine Definition: Wort Die Menge aller Wörter über Σ bezeichnet man mit Σ∗ und kann wie folgt induktiv definiert werden: 1 Das leere Wort ε ist ein Wort über Σ, d.h., ε ∈ Σ∗. 2 Sei z ∈ Σ, dann ist z ein Wort über Σ, d.h. z ∈ Σ∗. 3 Sei w ∈ Σ∗ und z ∈ Σ, dann ist auch die Konkatenation wz von w und z ein Wort über Σ, d.h., wz ∈ Σ∗ 4 Jede Folge von Zeichen, die durch endlich viele Anwendungen der Regeln 1. bis 3. gebildet werden kann, ist ein Wort über Σ. Es gilt u = εu = uε für das leere Wort und ein beliebiges Wort u ∈ Σ∗. Die Länge |v| eines Wortes v ∈ Σ∗ ist definiert als die Anzahl der Zeichen, aus denen v besteht. Es gilt |ε| = 0 und |uv| = |u| + |v|. Beispiele w = 01100 ist ein Wort über dem Alphabet Σ = {0, 1} der Länge |w| = 5. v = bloed!!bloed!! ist ein Wort über dem Alphabet Σ = {l, b, o, e, !, d} der Länge |v| = 14. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.46  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Turingmaschine Definition: Sprache Eine Sprache L ist eine Menge von Wörtern über einem Alphabet Σ, also L ⊆ Σ∗. Beispiele Sei Σ ein Alphabet, dann ist L = ∅ ⊂ Σ∗ eine Sprache. Sei Σ ein Alphabet, dann ist L = {ε} ⊂ Σ∗ eine Sprache. Sei Σ = {0, 1}, dann ist z. B. L = {001, 100, 000, 111} ⊂ Σ eine Sprache. Sei Σ = { , 0,... , 9, a... , z, A,... , Z,′ }. Dann ist L = {zw | z ∈ { , a,... , z}, w ∈ Σ∗ } die Sprache der gültigen Haskell-Bezeichner für Funktionen (siehe Kapitel 2). Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.47  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Turingmaschine Definition: Turingmaschine Eine Turingmaschine kann als Tupel M = (Q, Σ, Γ, δ, q1 , #, E) beschrieben werden, wobei Arbeitsband Q = {q1 ,... , qN } eine endliche Menge von Zuständen, # # 0 1 1 # # Σ ein endliches Eingabealphabet, Lese-/ Γ ein endliches Bandalphabet mit Σ ⊂ Γ, Schreibkopf δ : (Q \ E) × Γ → Q × Γ × {L, S, R} eine Übergangsfunktion, Aktueller Turing-Tabelle (Programm) (entspricht dem Programm, darstellbar durch eine Tabelle) Zustand 0 1 # q1 q1 ,0,R q1 ,1,R q2 ,#,L q1 ∈ Q der Startzustand, q1 q2 q3 ,1,L q2 ,0,L q3 ,1,L q3 q3 ,0,L q3 ,1,L q4 , #, R # ∈ Γ \ Σ ein Bandzeichen ( leeres Feld“) und ” E ⊆ Q eine Menge von akzeptierenden Endzuständen ist. Ein Wort w ∈ Σ∗ über dem Alphabet Σ wird von der Turingmaschine M akzeptiert, wenn, ausgehend von dem Anfangszustand q1 durch Abarbeitung des Wortes w die Maschine in einen Endzustand q ∈ E überführt wird. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.48  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Turingmaschine Abarbeitung eines Wortes Sei M = (Q, Σ, Γ, δ, q1 , #, E) eine Turingmaschine. Ein Wort w ∈ Σ∗ wird wie folgt abgearbeitet: Arbeitsband 1 Das Wort w steht initial auf dem Arbeitsband. # # 0 1 1 # # 2 Der LS-Kopf steht initial auf dem ersten Zeichen von w (von links). Lese-/ 3 Der Rest des Arbeitsbands ist mit # beschrieben. Schreibkopf 4 Die Maschine befindet sich im Startzustand q1. Aktueller Turing-Tabelle (Programm) 5 Die Maschine M wiederholt die folgenden Schritte: Zustand 0 1 # ▶ Sei q der aktuelle Zustand der Maschine. q1 q1 q1 ,0,R q1 ,1,R q2 ,#,L q2 q3 ,1,L q2 ,0,L q3 ,1,L ▶ LS-Kopf liest ein Zeichen x ∈ Γ ein. q3 q3 ,0,L q3 ,1,L q4 , #, R ▶ Anwendung der Übergangsfunktion: (p, z, m) = δ(q, x) LS-Kopf schreibt Zeichen z ∈ Γ auf das Arbeitsband LS-Kopf wird nach links bewegt, falls m = L, nach rechts, falls m = R, und nicht bewegt falls m = S. Die Maschine wechselt in den neuen Zustand p ▶ Falls p ∈ E: Ende der Abarbeitung 6 Falls Abarbeitung beendet, dann steht Ausgabe auf dem Arbeitsband. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.49  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Turingmaschine: Beispiel I Beispiel ([GS11]) Arbeitsband Sei M = (Q, Σ, Γ, δ, q1 , #, E) eine Turingmaschine mit: # # 1 0 0 # # Zustandsmenge: Q = {q1 ,... , q4 } Lese-/ Endliches Bandalphabet: Γ = {0, 1, #} Schreibkopf Endliches Eingabealphabet: Σ = {0, 1} Aktueller Turing-Tabelle (Programm) Übergangsfunktion δ : (Q \ E) × Γ → Q × Γ × {L, S, R} Zustand 0 1 # q1 q1 ,0,R q1 ,1,R q2 ,#,L q4 Startzustand: q1 ∈ Q q2 q3 q3 ,1,L q3 ,0,L q2 ,0,L q3 ,1,L q3 ,1,L q4 , #, R Bandzeichen: # Menge von Endzuständen: E = {q4 } ⊂ Q Frage: Zu Beginn steht das Wort w = 011 ∈ Σ∗ auf dem Arbeitsband. Was macht diese Turingmaschine? Was ist ihre Ausgabe? Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.50  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Turingmaschine: Beispiel II Beispiel Arbeitsband Sei M = (Q, Σ, Γ, δ, q1 , #, E) eine Turingmaschine mit: # # # 1 0 1 0 0 # # Zustandsmenge: Q = {q1 ,... , q6 } Lese-/ Schreibkopf Endliches Bandalphabet: Γ = {0, 1, #} Turing-Tabelle (Programm) Endliches Eingabealphabet: Σ = {0, 1} Aktueller Zustand q1 0 q2 ,0,R 1 q1 ,1,R # q4 ,#,L q2 q3 ,0,R q2 ,1,R q5 ,#,S Übergangsfunktion δ : (Q \ E) × Γ → Q × Γ × {L, S, R} q6 q3 q4 q1 ,0,R q4 ,0,L q3 ,1,R q4 ,1,L q5 ,#,S q6 ,#,R q5 q5 ,0,S q5 ,1,S q5 ,#,S Startzustand: q1 ∈ Q Bandzeichen: # Menge von Endzuständen: E = {q6 } ⊂ Q Frage: Zu Beginn steht das Wort w = 10100 ∈ Σ∗ auf dem Arbeitsband. Was macht diese Turingmaschine? Was ist ihre Ausgabe? Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.51  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Turingmaschine & Lego :-) Bildquelle: https://ideas.lego.com/projects/10a3239f- 4562- 4d23- ba8e- f4fc94eef5c7 Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.52  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Was kann berechnet werden? Definition: Berechenbarkeit ([GS11]) Seien Σ ein (endliches) Eingabealphabet und B ein (endliches) Ausgabealphabet. Eine Funktion f : Σ∗ → B ∗ heißt berechenbar, wenn es eine Maschine gibt, die sie berechnet. Falls f nur auf einer Teilmenge def(f ) ⊂ Σ∗ definiert ist, also f : def(f ) → B ∗ , so heißt f eine partielle Funktion. Oft gibt man den Definitionsbereich def(f ) in diesem Kontext nicht explizit an und schreibt einfach f :: Σ∗ → B ∗. Da jedes Zeichen aus Σ oder B in Form einer Binärfolge kodiert/angegeben werden kann, können wir o. B. d. A. annehmen, dass Σ = {0, 1} und B = {0, 1} gilt. Da die Funktion g : {0, 1}∗ → N0 mit g(w) = (1w)2 − 1 eine bijektive Abbildung ist, kann jede Binärfolge als natürliche Zahl kodiert werden und umgekehrt. ▶ g(ε) = (1ε)2 − 1 = 1 − 1 = 0 für das leere Wort w = ε ∈ {0, 1}∗ ▶ g(0) = (10)2 − 1 = 2 − 1 = 1 für das Wort w = 0 ∈ {0, 1}∗ der Länge 1. ▶ g(001) = (1001)2 − 1 = 9 − 1 = 8 für das Wort w = 001 ∈ {0, 1}∗ der Länge 3. ▶ g(000) = (1000)2 − 1 = 8 − 1 = 7 für das Wort w = 000 ∈ {0, 1}∗ der Länge 3. Jede Funktion f :: Σ∗ → B ∗ kann in eine Funktion f :: N0 → N0 umgewandelt werden und umgekehrt. Man kann daher o. B. d. A. Funktionen f :: N0 → N0 betrachten. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.53  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Was kann berechnet werden? Turingberechenbar ([GS11]) Eine Funktion f :: N0 → N0 heißt Turing-berechenbar, falls es (mindestens) eine Turingmaschine gibt, die sie wie folgt berechnet: 1 Annahme: Eingabe n ∈ N0 steht auf dem ansonsten leeren Arbeitsband (nur Bandzeichen #). 2 Turingmaschine wird gestartet. 3 Falls n ∈ def(f ), so muss die Turingmaschine anhalten und am Ende f (n) auf dem Arbeitsband stehen (zudem muss sich der LS-Kopf über dem ersten Zeichen befinden). 4 Falls n ∈ / def(f ), so darf Turingmaschine nicht anhalten oder unter dem LS-Kopf steht das Zeichen #. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.54  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Was kann berechnet werden? Churche These Jede (vernünftige) Präzisierung des Begriffes Berechnen“ führt zur gleichen Menge berechenbarer Funktionen. ” Es handelt sich um eine Hypothese, da sie nicht bewiesen werden kann! (hängt von Begriff berechenbar“ ab; was heißt wenn es eine Maschine gibt, die sie berechnet“?) ” ” Bisher wurde keine Berechnungsmethode (bzw. eine vernünftige Präzisierung des Begriffs Berechnen“) ” gefunden, welche mehr als eine Turingmaschine berechnen kann. → These ist daher weiterhin akzeptiert! Konsequenz: Alles, was sich berechnen lässt, kann mittels einer Turingmaschine berechnet werden! Bildquelle: ChatGPT Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.55  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Was kann erprompted werden? Bildquelle: ChatGPT Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.56  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Noch eine Maschine (bzw. noch ein Berechnungsmodell) Ausblick: Informatik II Es gibt viele weitere Maschinenmodelle. Eines davon ist die sogenannten Real-RAM ([PS85]), welches wir in Informatik II für die Analyse von Algorithmen und Datenstrukturen verwenden werden. 1 Speicher besteht aus unendlich vielen Zellen. 2 CPU kann direkt auf Speicher zugreifen. 3 Jede Zelle kann eine (beliebige) reelle Zahl speichern. 4 Laufzeit als Anzahl der Elementaroperationen (bzgl. der Eingabegröße): ▶ Zugriff auf eine Speicherzelle (random access) ▶ Arithmetische Operationen (+, −, ×, ÷). ▶ Vergleich zweier reeller Zahlen (). ▶ Indirekter √ Speicherzugriff (ganzzahlige Adressen). ▶ Optional: x, log x,... Mehr dazu in ca. sechs Monaten... Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.57  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Übersicht 1 Informatik 2 Informationen und Daten 3 (Moderne) Computersysteme 4 Maschinenmodelle 5 Probleme & Algorithmen 6 Programme & Programmiersprachen 7 Zusammenfassung Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.58  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Spezifikation des Problems/der Aufgabenstellung Bildquelle: [GS11] Spezifikation ([GS11]) Eine Spezifikation ist eine vollständige, detaillierte und unzweideutige Problembeschreibung: Vollständig: Wenn alle Anforderungen und alle relevanten Rahmenbedingungen angegeben sind. Detailliert: Wenn klar ist, welche Hilfsmittel (z. B. Basis-Operationen) zur Lösung zugelassen sind. Unzweideutig: Wenn klare Kriterien angegeben werden, wann eine vorgeschlagende Lösung akzeptabel ist. Beispiel I Vollständig: ? Wie viele Wagen kann die Lok ziehen? Wie viele Wagen passen auf Gleisstück B? Detailliert: ? Welche Aktionen kann die Lok ausführen (fahren, koppeln,... )? Unzweideutig: ? Darf die Lok am Ende Eine Lokomotive soll die in Gleisabschnitt A befindlichen Wagen zwischen den Wagen stehen? Muss die Lok ” links/rechts stehen? 1,2,3 in der Reihenfolge 3,1,2 auf Gleisstück C abstellen.“ Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.59  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Spezifikation des Problems/der Aufgabenstellung Spezifikation ([GS11]) Eine Spezifikation ist eine vollständige, detaillierte und unzweideutige Problembeschreibung: Vollständig: Wenn alle Anforderungen und alle relevanten Rahmenbedingungen angegeben sind. Detailliert: Wenn klar ist, welche Hilfsmittel (z. B. Basis-Operationen) zur Lösung zugelassen sind. Unzweideutig: Wenn klare Kriterien angegeben werden, wann eine vorgeschlagende Lösung akzeptabel ist. Beispiel II Vollständig: ? Welche Zahlen M und N sind zugelassen? Positive Zahlen? Negative Zahlen? Rationale Zahlen? Ist 0 erlaubt? Berechne, für beliebige Zahlen M und N , den größten ” Detailliert: ? Welche Operationen sind für die gemeinsamen Teiler ggt(M, N ), also die größte Zahl, die sowohl M als auch N teilt.“ Berechnungen erlaubt (+,-,... )? Unzweideutig: ? Was heißt berechnen“? Wie ” soll das Ergebnis ausgegeben/gespeichert werden? Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.60  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Spezifikation des Problems/der Aufgabenstellung Vorbedingung und Nachbedingung ([GS11]) Eine Methode, Probleme genauer zu spezifizieren, besteht in der Angabe eines Paares P und Q von logischen Aussagen, wobei P die Vor- und Q die Nachbedingungen darstellen. Vorbedingung P : Alle relevanten Eigenschaften, die am Anfang gelten. Nachbedingung Q: Alle relevanten Eigenschaften, die am Ende gelten. Die weiteren Bedingungen und Voraussetzungen müssen durch Angabe der zur Verfügung stehenden Umgebung/möglichen Grundaktionen konkretisiert werden (z. B. Angabe eines Maschinenmodells). Beispiel II (genauer) Berechne, für beliebige Zahlen M und N , den P : {M, N ∈ N | 0 < M < 32767, 0 < N < 32767} ” größten gemeinsamen Teiler ggt(M, N ), also Q: {z = ggT (M, N ), d.h., z ist Teiler von M und N und die größte Zahl, die sowohl M als auch N teilt.“ für jede Zahl z ′ , die auch M und N teilt, gilt z ′ ≤ z } Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.61  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Der Begriff Algorithmus“ ” Algorithmen ([GS11]) Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen Lösung eines Problems. Diskretheit: Die Ausführung des Algorithmus erfolgt in einzelnen Schritten. Effektivität: Jeder Schritt besteht aus einer einfachen und offensichtlichen Grundaktion, die (von einer Maschine in endlicher Zeit) ausgeführt werden kann. (hängt von Umgebung/Maschinenmodell ab) Finitheit: Die Beschreibung des Algorithmus ist endlich. Deterministisch: Zu jedem Zeitpunkt muss klar sein, welcher Schritt als nächster auszuführen ist. Terminierend: Nach endlich vielen Schritten endet der Algorithmus. (nicht immer erwünscht) Beispiel I: Primzahltest ([Vah23]) Beispiel II: Primzahltest ([Vah23]) 1 Falls x = 2, so ist x eine Primzahl. 1 Berechne Tabelle mit allen Primzahlen. 2 Falls x = 3, so ist x eine Primzahl. 2 Überprüfe, ob x in der Tabelle enthalten ist. 3 Falls x = 4, so ist x keine Primzahl. Nein, nicht effektiv 4... Nein, keine endliche Beschreibung Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.62  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Algorithmen und Spezifikationen Vorbedingung und Nachbedingung ([GS11]) Eine Methode, Probleme genauer zu spezifizieren, besteht in der Angabe eines Paares P und Q von logischen Aussagen, wobei P die Vor- und Q die Nachbedingungen darstellen. Vorbedingung P : Alle relevanten Eigenschaften, die am Anfang gelten. Nachbedingung Q: Alle relevanten Eigenschaften, die am Ende gelten. Die weiteren Bedingungen und Voraussetzungen müssen durch Angabe der zur Verfügung stehenden Umgebung/möglichen Grundaktionen konkretisiert werden (z. B. Angabe eines Maschinenmodells). Algorithmen als Lösung einer Spezifikation Ein Algorithmus beschreibt, wie ein Problem gelöst werden kann. Ist das Problem durch das Paar P und Q gegeben, so schreibt man {P }A{Q} (3) falls der Algorithmus A die Vorbedingung P in die Nachbedingung Q überführt. Genauer: Wenn der Algorithmus A in einer Situation gestartet wird, in der P gilt, dann wird, wenn A beendet ist, Q gelten. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.63  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Algorithmen: Beispiel III Arbeitsband Beispiel (Wiederholung) # # 0 1 1 # # Sei M = (Q, Σ, Γ, δ, q1 , #, E) eine Turingmaschine mit: Lese-/ Zustandsmenge: Q = {q1 ,... , q4 } Schreibkopf Endliches Bandalphabet: Γ = {0, 1, #} Aktueller Turing-Tabelle (Programm) Endliches Eingabealphabet: Σ = {0, 1} Zustand 0 1 # q1 q1 ,0,R q1 ,1,R q2 ,#,L... q1 q2 q3 ,1,L q2 ,0,L q3 ,1,L q3 q3 ,0,L q3 ,1,L q4 , #, R Zu Beginn steht das Wort w = 011 ∈ Σ∗ auf dem Arbeitsband. Beispiel: Überprüfung Eigenschaften Diskretheit: Die Ausführung des Algorithmus erfolgt in einzelnen Schritten. ✓ Effektivität: Jeder Schritt besteht aus einer einfachen und offensichtlichen Grundaktion. ✓ Finitheit: Die Beschreibung des Algorithmus ist endlich. ✓ Deterministisch: Zu jedem Zeitpunkt muss klar sein, welcher Schritt als nächster auszuführen ist. ✓ Terminierend: Nach endlich vielen Schritten endet der Algorithmus. ✓ (?) Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.64  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Algorithmen: Beispiel IV Horner-Schema Sei x ∈ N0 eine beliebige nicht-negative ganze Zahl und sei B ∈ N \ {1} eine beliebige Basis. Dann kann x dargestellt werden durch: x = (an−1 an−2... a0 )B = an−1 B n−1 + an−2 B n−2 +... + a2 B 2 + a1 B 1 + a0 B 0 = ((((an−1 )B + an−2 ) B +... + a2 ) B + a1 ) B + a0 (4) Umwandlung von Dezimalzahl in Zahlendarstellung beliebiger Basis Modellannahmen (z. B. Grundaktionen): Addition, Divisionsrest (mod), Division ohne Rest (div), Eingabe (read), Ausgabe (print),... Vorbedingung P : Sei x ∈ N eine positive ganze Zahl und B ∈ N \ {1} die gewünschte Basis. Nachbedingung Q: Ausgabe der Zahlenfolge a0... an−1 mit x = (an−1... a0 )B. 1: read x, B 2: i ← 0 x = 46x = 5x = 0 B = 8 3: while x ̸= 0 do 4: ai ← x mod B // Divisionsrest i=0i=1i=2 5: print ai a0 = 6 a1 = 5 6: x ← x div B // Division ohne Rest Ausgabe: 6 5 7: i←i+1 8: end while Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.65  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Algorithmen: Beispiel IV Wie kann dies weiter präzisiert werden? Umwandlung von Dezimalzahl in Zahlendarstellung beliebiger Basis Modellannahmen (z. B. Grundaktionen): Addition, Divisionsrest (mod), Division ohne Rest (div), Eingabe (read), Ausgabe (print),... Modellannahmen (z. B. Grundaktionen): Addition, Divisionsrest (mod), Division ohne Rest (div), Eingabe (read), Ausgabe (print),... Vorbedingung P : Sei x ∈ N eine positive ganze Zahl und B ∈ N \ {1} die gewünschte Basis. Nachbedingung Q: Ausgabe der Zahlenfolge a0... an−1 mit x = (an−1... a0 )B. 1: read x, B 2: i ← 0 3: while x ̸= 0 do 4: ai ← x mod B // Divisionsrest 5: print ai 6: x ← x div B // Division ohne Rest 7: i←i+1 8: end while Beispiel: Überprüfung Eigenschaften Diskretheit: Die Ausführung des Algorithmus erfolgt in einzelnen Schritten. ✓ Effektivität: Jeder Schritt besteht aus einer einfachen und offensichtlichen Grundaktion. ✓ (?) Finitheit: Die Beschreibung des Algorithmus ist endlich. ✓ Deterministisch: Zu jedem Zeitpunkt muss klar sein, welcher Schritt als nächster auszuführen ist. ✓ Terminierend: Nach endlich vielen Schritten endet der Algorithmus. Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) ✓ 1.66  Informatik Informationen und Daten (Moderne) Computersysteme Maschinenmodelle Probleme & Algorithmen Programme & Programmiersprachen Zusammenfassung Übersicht 1 Informatik 2 Informationen und Daten 3 (Moderne) Computersysteme 4 Maschinenmodelle 5 Probleme & Algorithmen 6 Programme & Programmiersprachen 7 Zusammenfassung Prof. Dr. Fabian Gieseke Informatik I: Grundlagen der Programmierung – Einleitung (WS 2024/2025) 1.67  Informatik Informationen und Daten (Moderne) Computersysteme