Einführung In Die Programmierung, Programmiersprache C

6m ago
36 Views
0 Downloads
696.73 KB
43 Pages
Transcription

Programmieren 1Einführung in die Programmierung,Programmiersprache CDozent: Jonas Fritzsch, M.Sc.Kontakt: [email protected]

Organisatorisches Vorlesungszeiten, Termine Übungen, Projekt Webseite zur Vorlesunghttp://wwwlehre.dhbw-stuttgart.de/ fritzsch/Programmieren/ Skript KlausurTeil 2

Inhalte der Vorlesung Grundlegende Konzepte der Programmierung Algorithmisches Denken schulenProblem Algorithmus Programm Programmiersprache C Grundlegende Algorithmen(Felder, Listen, Suchen, Sortieren ) ÜbungenTeil 2

LiteraturProgrammieren in C. ANSI C (2. Ausgabe) / Brian W. Kernighan,Dennis M. Ritchie / Hanser FachbuchC von A bis Z / Wolf / Galileo Computinghttp://openbook.galileocomputing.de/c von a bis z/C als erste Programmiersprache / Manfred Dausmann et al. /Vieweg Teubner VerlagC Programmieren von Anfang an / Helmut Erlenkötter /rororo ComputerTeil 2Practical C Programming / Steve Qualline / O'ReillyC: A Reference Manual, Fifth Edition / Harbison, Steele / Prentice Hall

Teil I: rithmenSprachen

AllgemeinesAlgorithmenSprachenAllgemeinesKapitel 1: Einführung6

AllgemeinesAlgorithmenSprachenWas ist Informatik? (Information – Automatik, Mathematik)Def. 1 Informatik ist die Wissenschaft von der systematischen Verarbeitungvon Informationen - insbesondere deren maschinelle (automatische)Bearbeitung, Speicherung und Übertragung durch Digitalrechner (Computer).(Informatik Duden)Def. 2 Informatik umfasst die automatisierte Informationsverarbeitung inNatur, Technik und Gesellschaft (Fachliteratur "Grundlagen d. Informatik" ) Begriff 1957 von Karl Steinbuch eingeführt vgl. "computer science"E. W. Dijkstra: „Computer Science is no more about computers thanastronomy is about telescopes“ Informatik vs. Rechnertechnik Ende der 1960er Jahre erstmals StudienrichtungKapitel 1: Einführung7

AllgemeinesAlgorithmenSprachenTeil 1Teilgebiete der InformatikKapitel 1: Einführung9

AllgemeinesAlgorithmenSprachenInformation und DatenInformationDaten ieren DatenDatenInformation Bedeutungsgehalt von Zeichen, NachrichtenKapitel 1: Einführung10

tung und nKapitel 1: Einführung11

AlgorithmenAllgemeinesSprachenBitsInformationen werden repräsentiert als Folgen von Bits. Bit Binary DigitVerwendung:- Binärziffer- Maßeinheit für Datenmenge- Maßeinheit für Informationsgehalt- Wert 0 oder 1 / aus oder an / ja oder nein- elektrische Spannung:0 0 Volt1 5 Volt- Magnetisierung:0 entmagnetisiert 1 magnetisiertBitfolgen- mehr als 2 Zustände abbilden- Bitfolge aus 2 Bits 4 Zustände00011011 es gibt genau 2N mögliche Bitfolgen der Länge N BitKapitel 1: Einführung12

AllgemeinesAlgorithmenSprachenBeispiel: WindrichtungFrage: Aus welcher Himmelsrichtung weht der Wind?Codierung von estSüdostKapitel 1: Einführung13

AllgemeinesAlgorithmenSprachenHexziffern- Folgen von Nullen/Einsen sind unübersichtlich01001111011000010110110001101100- Idee: Anordnung in Gruppen zu 4 Bits0100 1111 0110 0001 0110 1100 0110 1100- Halb-Byte: 16 Zustände- Ziffern '0' bis '9' und Buchstaben 'A' bis 'F'0000 00100 41000 81100 C0001 10010 20011 30101 50110 60111 71001 91010 A1011 B1101 D1110 E1111 FKapitel 1: Einführung14

AllgemeinesAlgorithmenSprachenBytes- Oktett von Bits: 8 Bits 1 Byte- Beispiel: (11000101)2 (C5)16 (197)10Beispiele der Codierung:- Zahl zwischen 0 und 255- Zahl zwischen -128 und 127- Zeichen im Zeichencode, z.B. ASCII CodeEinheiten:1 Kilobyte1 Megabyte1 Gigabyte1 Terabyte1 PetabyteKapitel 1: Einführung2102202302402501024 Bytes1.048.576 Bytes1.073.741.824 Bytes1.099.511.627.776 Bytes1.125.899.906.842.624 Bytes15

gung- Information (v. lat.: in-form-are) Kenntnis über irgendwas- Austausch über NachrichtenNachrichtZusammenstellung von Zeichen (Symbolen) zurInformationsübermittlungZeichen/Symbol Element eines Zeichenvorrates festgelegter Menge(z.B. Alphabet)WortFolge von Zeichen, die als Einheit betrachtet werdenBeispiel 1: Bei welcher Nachricht ist die Information größer?a) Am 1. Juli war die Temperatur größer als 25 Grad.b) Am 1. Juli betrug die Temperatur 29 Grad.Kapitel 1: Einführung16

gung- Information (v. lat.: in-form-are) Kenntnis über irgendwas- Austausch über NachrichtenNachrichtZusammenstellung von Zeichen (Symbolen) zurInformationsübermittlungZeichen/Symbol Element eines Zeichenvorrates festgelegter Menge(z.B. Alphabet)WortFolge von Zeichen, die als Einheit betrachtet werdenBeispiel 1: Bei welcher Nachricht ist die Information größer?a) Am 1. Juli war die Temperatur größer als 25 Grad.b) Am 1. Juli betrug die Temperatur 29 Grad.c) Am 1. Juli war die Temperatur größer als 25 Grad.d) Am 1. Januar war die Temperatur größer als 25 Grad.Kapitel 1: Einführung17

gungGehalt an Information unterscheiden sich je nach Empfänger Informationsgehalt einer Nachricht xShannonsches Informationsmaß:mit Gesamtzahl der möglichen Zeichen und gleicher Wahrscheinlichkeit des Auftretens vonmit und 1 Beispiel 2: Zeichenvorrat: 10 Zeichen {0, 1, 2, 3, 4, 5, 6, 7,8 ,9}, die mit gleicherWahrscheinlichkeit auftreten.Der Informationsgehalt einer Nachricht, bestehend aus 1 Zeichen, ist somit:I xKapitel 1: Einführung18

gungaus Beispiel 1: Bei welcher Nachricht ist die Information größer?c) Am 1. Juli war die Temperatur größer als 25 Gradd) Am 1. Januar war die Temperatur größer als 25 Grad.- je seltener ein Zeichen genauer:1 soll gelten:- für den Fall- es folgt:Kapitel 1: Einführungauftritt, desto größer sein Informationsgehalt0log19

gungaus Beispiel 1: Bei welcher Nachricht ist die Information größer?c) Am 1. Juli war die Temperatur größer als 25 Gradd) Am 1. Januar war die Temperatur größer als 25 Grad.- je seltener ein Zeichen genauer:auftritt, desto größer sein Informationsgehalt1 soll gelten:- für den Fall0log- es folgt:Schlussfolgerungen:Information 1 bitKapitel 1: Einführung Maß der Ungewissheit, mit der ein Empfänger eineNachricht erwarten kann.Information, welche bei gleicher Wahrscheinlichkeit zweierAlternativen durch die Kenntnis einer Alternative vermittelt wird.20

AllgemeinesAlgorithmenSprachenAlgorithmenKapitel 1: Einführung21

AllgemeinesAlgorithmenSprachenAlgorithmus LösungsverfahrenMenge von Regeln für ein Verfahren, um aus gewissen Eingabegrößenbestimmte Ausgabegrößen herzuleiten"Der Algorithmus ist als Oberbegriff zu Programm zu betrachten, bei dem imGegensatz zu einem Programm die strengen syntaktischen Regeln derProgrammiersprache nicht eingehalten zu werden brauchen"aus "Programmieren in C" R.Klima/S.Selberherr"Wenn ein Algorithmus für ein Problem existiert,dann ist das Problem durch Computer lösbar.""Dixit algorismi" ( "so sprach Al Khowarismi")Al Khowarismi (783-850): "Regeln derWiedereinsetzung und Reduktion"Kapitel 1: Einführung22

AllgemeinesAlgorithmenSprachenBeispiel: "Gulaschsuppe zubereiten"Zu manipulierende Objekte:350 g Rindfleisch, 3 Zwiebeln, 50 g Schweineschmalz, 15 g Mehl, 1 kleineDose Tomatenmark, 3/4 l Wasser, Salz, Paprika, MajoranHilfsobjekte:Herd, KochgeschirrAnweisungen:Fleisch und Zwiebeln würfelnin Schmalz andünstenmit Mehl bestäuben und kurz anröstenTomatenmark zugebenmit Wasser auffüllengarenmit Salz, Paprika und Majoran abschmeckenKapitel 1: Einführung23

AllgemeinesAlgorithmenSprachenEigenschaften Finitheit, endliche Vorschrift Effektivität Determiniertheit Determinismus Abstrahierung Terminierung Eingabespezifikation (Anforderungen) Ausgabespezifikation (Zusicherungen)Kapitel 1: Einführung24

AllgemeinesAlgorithmenSprachenEigenschaften Finitheit, endliche VorschriftVerfahren muss in einem endlichen Text vollständig beschreibbar sein EffektivitätJeder Schritt des Verfahrens muss effektiv (d.h. tatsächlich) mechanisch ausführbar sein. DeterminiertheitWiederholbarkeit bzgl. Ein- Ausgabedaten Determinismusvorherbestimmter Ablauf zu jedem Zeitpunkt Abstrahierunganwendbar auf eine Klasse von Problemen (steuerbar über Parameter) Terminierungliefert Ergebnis nach endlich vielen Schritten Eingabespezifikation (Anforderungen)genaue Spezifikation der erforderlichen Eingabegrößen Ausgabespezifikation (Zusicherungen)genaue Spezifikation der zugesicherten Ausgabegrößen bzw. ResultateKapitel 1: Einführung25

AllgemeinesAlgorithmenSprachenTypische und bekannte Algorithmen Euklidischer Algorithmus zur Bestimmung des ggT Algorithmen zur Bestimmung von Primzahlen Gaußscher Algorithmus zur Lösung eines LGS Suchen und Sortieren Bearbeiten bestimmter Datenstrukturen (z.B. Listen, Bäume, Graphen) Zeichenketten-Verarbeitung Mustererkennung Statistische BerechnungenKapitel 1: Einführung26

ngsgesetz:0 Beginne mit irgendeiner natürlichen Zahl Istgerade, so nimm als nächstes /2 Istungerade, so nimm als nächstes 3 Wiederhole die Vorgehensweise mit der erhaltenen Zahl1So erhält man zum Beispiel für die Startzahl 19 die Folge:19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, Collatz-Vermutung:Jede so konstruierte Zahlenfolge mündet in den Zyklus 4, 2, 1,egal, mit welcher natürlichen Zahl n man beginnt.Kapitel 1: Einführung27

AllgemeinesAlgorithmenSprachenMöglichkeiten der Darstellung natürliche Sprache Pseudo-Code (formale Sprache) Programmablaufplan (PAP) Struktogramm ProgrammierspracheKapitel 1: Einführung28

AllgemeinesAlgorithmenSprachenProgrammablaufplan Collatz-ProblemKapitel 1: Einführung29

Programmablaufplan (PAP) nach DIN66001 - Ausgewählte Symbole

AllgemeinesAlgorithmenSprachenSprachenKapitel 1: Einführung31

AllgemeinesAlgorithmenSprachenSoftware - die Programmausstattung- Bearbeitungsvorschriften für Hardware- Unterteilung Betriebssystem - AnwendersoftwareProgrammieren- Umsetzung Algorithmus in Computerprogramm- Verwendung einer ProgrammierspracheProgrammiersprache- Ausdrucksmittel Menschen - Maschine- klare Definition durch Syntax und Semantik- Programmiersprache erlernen vs. Programmieren erlernenKapitel 1: Einführung32

AllgemeinesAlgorithmenSprachenMaschinensprache- Maschinensprache Satz von Befehlen für eineganz bestimmte Rechenmaschine- Programmieren in Maschinensprache ist mühsamund 1R1,aHöhere Programmiersprache- Orientierung an Problemen statt Maschinena b c - 2;Vorteile: - schnellere und sichere Programmerstellung- bessere Lesbarkeit- Wiederverwendbarkeit (Portierbarkeit)Nachteil: - Programme können nicht unmittelbar ausgeführt werden Übersetzung notwendig (Interpreter und Compiler)Kapitel 1: Einführung33

itionenHardware:Maschine-John Von-Neumann-Modell (1947)-EVA-Prinzip (Eingabe, Verarbeitung, Ausgabe)-allzwecktauglich (General Purpose Computer)-nicht selbstständig arbeitsfähig, Anwendungsmaschine durch maler HW-Aufwand)hohe Flexibilität(bei genügend elementarenBefehlen)Kapitel 1: Einführung34

AllgemeinesAlgorithmenSprachen1.2 Begriffe,DefinitionenRegistermaschineauf Basisdes von-Neumann-Modells-Befehle und Daten im gleichen Speicher-sequentielle Verarbeitung von Befehl und Datum-einzelner Verbindungsweg zwischen CPU SpeicherKapitel 1: Einführung35

onenBeispiel:Programm"Summe"Aufgabe: Summe von einzugebenden Zahlen ermitteln und ausgeben,Abbruch bei Eingabe von "0"ProgrammstartZahl einlesenWenn Zahl 0, springe zur ErgebnisausgabeZahl auf bisherige Summe aufaddierenSpringe zum ProgrammstartErgebnis ausgebenProgrammendeKapitel 1: Einführung36

AllgemeinesAlgorithmenSprachen1.2 Begriffe, DefinitionenKapitel 1: Einführung37

AllgemeinesAlgorithmenSprachen1.2 Begriffe, enJohnny - A Simulator of a Simple von-Neumann -uni-bochum.de/Daniel.Reinert/Software/von NUSim8085http://www.gnusim8085.orgKapitel 1: Einführung38

AllgemeinesAlgorithmenSprachen1.3Einteilung der–ProgrammiersprachenMaschinenspracheHöhere ProgrammierspracheSprachevolutionKapitel 1: Einführung39

AllgemeinesAlgorithmenSprachenImperative Programmiersprachen- Sprachen der ersten bis dritten Generation- Beschreibung von Programmabläufen (Funktionsorientierte Methode)1) Problemlösung Folge von Einzelschritten (- Algorithmus)BeginneProgrammAnweisung 1Anweisung 2Anweisung 3.BeendeProgramm2) Programm Vereinbarungen und Verarbeitungen (- Algorithmus)3) Anwendung des Prinzips der Strukturierten Programmierung Kapitel 1: Einführungsprachenübergreifendes ProgrammierparadigmaMethoden und Regeln zum Entwurf von Algorithmen/Programmenvollständige Aufteilung des Problems in TeilproblemeHerabsetzung der Fehleranfälligkeit40

AllgemeinesAlgorithmenSprachenPrinzipien der Strukturierten Programmierung (1) Struktur-Theorem (Edsger W. Dijkstra 1972) Hierarchische Programmorganisation (Trennung Steuerung - Verarbeitung) Beschränkung der Ablauf-Steuerung auf 3 Grundelemente:Kapitel 1: Einführung41

AllgemeinesAlgorithmenSprachenPrinzipien der Strukturierten Programmierung (2) Vorgehensweise: Top-Down Zerlegung, schrittweise VerfeinerungKapitel 1: Einführung42

AllgemeinesAlgorithmenSprachenPrinzipien der Strukturierten Programmierung (3)- Verzicht auf Sprünge ("GOTO")Kapitel 1: Einf