close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Kap. 1, Einleitung - G-CSC Home

EinbettenHerunterladen
Grundlagen der
Programmierung 1
WS 14/15
Sebastian Reiter, Martin Rupp,
Dr. Andreas Vogel, Dr. Konstantinos Xylouris
Prof. Dr. Gabriel Wittum
G-CSC
Kettenhofweg 139
http://www.gcsc.uni-frankfurt.de
wittum@gcsc.uni-frankfurt.de
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Organisatorisches
Übungsorganisation:
• Dr. Andreas Vogel, Kettenhofweg 139, Raum 206
• Sebastian Reiter, Kettenhofweg 139, Raum 101
• Martin Rupp, Kettenhofweg 139, Raum 201
• Dr. Konstantinos Xylouris, Kettenhofweg 139, Raum 101
Tutoren: Studierende aus höheren Semestern
Fragen / Anregungen sehr erwünscht !!!
Meine Sprechstunde: Mo 14.00-15.00 (nach der Vorlesung), Kettenhofweg 139, Raum 105
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Organisatorisches
Vorlesung: Montag, Freitag (vierzehntägig): Neue Konzepte
Übung: Vertiefung und Besprechung der Übungsblätter
Übungsbeginn: KW 43
17 Übungsgruppen
Anmeldung zur Übung (Gruppeneinteilung) online
offen bis 22.10.
Alle, die Kreditpunkte (CP) wollen, bitte anmelden!!!
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Organisatorisches
Erfolgreiche Übung
20% der Punkte der Übungsblätter zählen zur Klausur
Bestehen der Klausur => CP für PRG 1
EPR: Programmierpraktikum,
-Bestehen durch erfolgreiche Code Reviews
Aktuelle Infos zur Vorlesung auf der Webseite
http://www.gcsc.uni-frankfurt.de
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Organisatorisches
Vorlesungsmaterial
Folien werden online zur Verfügung ge-
stellt
Quellen und Literatur
• Informatik 1 - Programmieren und Softwaretechnik,
G. Wittum, Univ. Heidelberg, Vorlesung
WS 2001/2002 und WS 2006/2007
• Wikisource
http://de.wikibooks.org/wiki/C%2B%2B-Programmierung
• Wikipedia: http://www.wikipedia.de
• Informatik 1, D. Kossmann, Univ. Heidelberg, WS 2004/05
• Informatik 1, P. Bastian, Univ. Heidelberg, 2001
•…
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Informatik
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Was ist Informatik?
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Wikipedia
•
„Wissenschaft von der systematischen Verarbeitung von Informationen, besonders der automatischen Verarbeitung mit Hilfe
von Digitalrechnern”
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Wikipedia
Digitalrechner
Alltag
Arbeit
• Software
• Hardware
Schule
http://de.wikipedia.org/wiki/Datei:Macintosh_128k_transparency.png, © http://www.allaboutapple.com/
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Freizeit
Wikipedia (Digitalrechner)
Computer
Informatik
•
Metadisziplin an der Schnittstelle verschiedener Disziplinen,
die ihre Bedeutung dem Siegeszug des Computers verdankt,
den man auch als Siegeszug der Informatik bezeichnen kann.
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Wikipedia (Digitalrechner)
Computer
Informatik
•
Metadisziplin an der Schnittstelle verschiedener Disziplinen,
die ihre Bedeutung dem Siegeszug des Computers verdankt,
den man auch als Siegeszug der Informatik bezeichnen kann.
=>
Computer Science
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Wikipedia (Digitalrechner)
Computer
Bestandteile
•
Mathematik
•
Theroret. Informatik
•
Elektrotechnik/Physik
•
Technische Informatik
•
Anwendungen
•
Angewandte Inf.
•
Psychologie
•
…
•
…
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Geschichte
Abakus
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Geschichte
Wilhelm Schickard, Tübingen, baut 1623 „Rechenmaschine”
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Geschichte
Spezialrechner: Datenverarbeitung mit Lochkarten (1723 Webstuhl – 1889 Hollerith Volkszählung USA)
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Geschichte
Erster Rechner Z1, Konrad Zuse (1910-1995) Berlin 1938
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Geschichte
Erster Digitalrechner
Rechner Z1, Konrad
Z1, Konrad
Zuse (1910-1995)
Zuse (1910-1995)
Berlin Berlin
1938 1938
Binärdarstellung,
Takt: ca. 1 Hz,
Wortlänge: 22 Bit
Speicher: 64 Wörter
mechanisch (Bleche)
Antrieb: Staubsaugermotor
ca 1 Tonne Gewicht
http://de.wikipedia.org/wiki/Datei:Zuse_Z1-2.jpg© ComputerGeek
unzuverlässig, da die Bleche immer wieder klemmten
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Geschichte
Erster „turingmächtiger” Rechner Z3, Konrad Zuse, Berlin 1941
http://de.wikipedia.org/wiki/Datei:Z3_Deutsches_Museum.JPG© Venusianer
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Modell, Simulation
Geschichte
Grund für Zuses Idee, einen Rechner zu bauen
•
„Ich war zu faul zum Rechnen”
•
Maschine zum Lösen großer Gleichungssysteme
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Modell, Simulation
Modellierung
und Simulation
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Modell, Simulation
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Modell
•
Abstrakte Beschreibung eines realen Objekts oder Prozesses
•
beschränkt auf das „Wesentliche”,
d.h. nur sinnvoll in Zusammenhang
mit konkreter Fragestellung
alles Überflüssige wird weggelassen
•
Einstein:
„Man soll die Dinge so einfach machen wie möglich,
aber nicht einfacher!”
Problem: Komplexität der Realität
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Modellierung und Simulation
Modelle, Algorithmen und Simulationssoftware für
- Biologie, Biotechnologie, Neurowissenschaften…
- Umweltforschung…
- Energieforschung…
- Technik, Strömungen…
- Finanzmathematik…
…
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Modellierung und Simulation
Möglichkeit für
Vertiefende Veranstaltungen:
Vorlesungen, Praktika, Seminare
Bachelor- und Masterarbeiten (auch in der Industrie)
Hiwi-Stellen
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Algorithmus
• Verfahren mit eindeutig definiertem Ablauf. Muß ausgehend
von Eingabedaten nach endlich vielen Schritten eine Ausgabe
liefern. Schritte müssen ausführbar sein.
• Wort kommt von Abu Abdallah Muhammad
ibn Musa al-Chwarizmi (al Charazmi) (persisch:
) (*
um 780; † zwischen 835 und 850) war ein persischer Mathematiker.
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Algorithmus
Funktionale Sicht: welche Aufgabenstellung bewältigt der Algorithmus (Eingabe, Ausgabe) ?
Operationale Sicht: welche Schritte beinhaltet der Algorithmus
(Kontrollfluss, elementare Schritte, verwendete Daten)?
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Algorithmus
Bsp: Geld holen und einkaufen
1.
Gehe zur Bank
2.
Hole Geld
3.
Solange Geld da ist, kaufe ein
Falls Geld weg, gehe zu Schritt 1.
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Algorithmus
Bsp: Geld holen und einkaufen
1.
Gehe zur Bank
2.
Hole Geld
3.
Solange Geld da ist, kaufe ein
Falls Geld weg, gehe zu Schritt 1.
Problem: terminiert nicht!
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Algorithmus
Bsp: Geld vom Bankkonto holen und einkaufen
1.
Gehe zur Bank
2.
Wenn Geld auf Konto, hole Geld, sonst geh nach hause.
3.
Solange Geld da ist, kaufe ein
Falls Geld weg, gehe zu Schritt 1.
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Formale Darstellungen
Daten sind formale Repräsentationen für Informationen
Zeichenketten
Alphabet: z.B. A = {a,b,c,….}
A* : Menge der endlichen Worte über einem Alphabet A
Leeres Wort
Sprache
Teilmenge L ‰ A*
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Beschreibung/Sprache
Syntax
Formale Regeln
Welche Elemente (Zeichenfolgen / Bildelemente) sind
für die Darstellung erlaubt?
Semantik
Bedeutung
Pragmatik
Methodik des Gebrauchs
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Formale Darstellungen
Sprachen
Daten sind formale Repräsentationen für Informationen
• Beispiele
– deutsch, LEO, C++,XML, Z, UML, Lisp, Prolog, ...
– Gebärdensprache, ...
• Aufgabe
– beschreibt ein Modell, Algorithmus, Datenstruktur,
so dass eine Maschine es verstehen kann
• Formal
– Alphabet + Syntax (+ Semantik)
• Praxis: Sprachen für verschiedene Aufgaben
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Die Sprache „LEO”
X, Y
•
L stehe für ein beliebiges (auch leeres) Wort
Sei LE ein gültiges Wort der Sprache
Regeln:
(1)
Wenn XE ein gültiges Wort ist, dann auch XEO
(2)
Wenn LX ein gültiges Wort ist, dann auch LXX
(3)
Wenn XEEEY ein gültiges Wort ist, dann auch XOY
(4)
Wenn XOOY ein gültiges Wort ist, dann auch XY
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Die Sprache „LEO”
X, Y
•
L stehe für ein beliebiges (auch leeres) Wort
Sei LE ein gültiges Wort der Sprache
Regeln:
(1)
Wenn XE ein gültiges Wort ist, dann auch XEO
(2)
Wenn LX ein gültiges Wort ist, dann auch LXX
(3)
Wenn XEEEY ein gültiges Wort ist, dann auch XOY
(4)
Wenn XOOY ein gültiges Wort ist, dann auch XY
Sind LEE, LOE, LEO und OLE
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
L?
Die Sprache „LEO”
• LEE:
LE – (2) –> LEE => LEE
• LOE:
LEE – (2) –> LEEEE – (3) –> LOE => LOE L
• LEO:
LE – (1) –> LEO => LEO
• OLE:
Die Regeln (1)-(4) geben keine Möglichkeit,
ein Wort nach links zu verändern.
Alle Wörter X ∈ L beginnen mit L,
L kommt nur an erster Stelle vor
=> OLE ∉ L.
L
L
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Auswirkung der Regeln
X, Y
•
L stehe für ein beliebiges (auch leeres) Wort
Sei LE ein gültiges Wort der Sprache
Regeln:
(1)
Wenn XE ein gültiges Wort ist, dann auch XEO
=> Anhängen von O möglich
(2)
Wenn LX ein gültiges Wort ist, dann auch LXX
k
=> Verdoppeln der Endsilbe, erzeugt Wörter L(X)2
(3)
Wenn XEEEY ein gültiges Wort ist, dann auch XOY
=> Ersetzen von EEE durch O
(4)
Wenn XOOY ein gültiges Wort ist, dann auch XY
=> Eliminieren von OO
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Auswirkung der Regeln
X, Y L stehe für ein beliebiges (auch leeres) Wort
•
•
Sei LE ein gültiges Wort der Sprache
2k
(2): Ausgehend von LE sind auch L(E)
2k
•
(1): Damit gehören auch L(E)
•
(3): Dies erzeugt die Wörter L(E)2
für k, m N und 3m 2k
•
O zur Sprache
k-3m
2k-3m
(4): Ergibt L(E)
für k N Wörter
k-3m
Om und L(E)2
O[m/2]
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Om+1
Systematische Darstellung
LE
2
1
LEO
1
2
LEOEO
2
LEOEOEOEO
LEE
LEEO
2
LEEOEEO
2
LEEEE
1
2
3
3
LEEEEO LEEEEEE LOE
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
LEO
Systematische Darstellung
LE
Baum
2
1
LEO
1
2
LEOEO
2
LEOEOEOEO
LEE
LEEO
2
LEEOEEO
2
LEEEE
1
2
3
3
LEEEEO LEEEEEE LOE
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
LEO
Systematik
• Der Baum enthält alle Wörter der Sprache LEO.
• Wenn ein Wort in der Sprache vorkommt, dann taucht es im
Baum auf.
• Die Wörter der Sprache LEO werden „rekursiv” erzeugt.
• Die Wörter lassen sich numerieren.
• Es gibt „abzählbar viele” Wörter in L, d.h. so viele wie natürliche Zahlen.
• Die Menge L nennt man „rekursiv abzählbar”.
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Systematik
• Ein Wort, das in der Sprache nicht vorkommt, wird nie erreicht.
• Verfahren zur Feststellung, ob X
L
• Vorgehen: Um festzustellen ob X
L, baue den Baum vo.n L
durch systematische Anwendung der Regeln auf
L, wird X irgendwann gefunden und das Verfahren
• Ist X
kommt zum Ziel, es terminiert.
L, wird X leider nie gefunden und das Verfahren
• Ist X
kommt nicht zum Ziel, es terminiert nicht.
• Das Verfahren ist nur brauchbar, wenn X
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
L
Turingmaschine
EBNF
- Metasprache
(TM)
• Erweiterte Backus-Naur-Form (EBNF): Regeln zur Definition der
Syntax von Programmiersprachen
• Beschreibung von Grammatiken
• Terminale Zeichen (Alphabet): unterstrichen
• Nichtterminale Zeichen (Repräsentanten): <A>
• Leeres Wort:
• Produktionen: ::=
• Auswahl: |
• Wiederholung: {} (beliebig) {}+ (mind. einmal)
• Option: [] (keinmal oder einmal)
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Turingmaschine
EBNF
- Metasprache
Beispiele
(TM)
• Erweiterte Backus-Naur-Form (EBNF): Regeln zur Definition der
• Ziffern
<Ziffer> ::= 1|2|3|4|5|6|7|8|9|0
• Taschenrechner
<Ausdruck> ::= <Mult>
<Mult> ::= <Zahl> | ( <Add> ) | <Mult> * <Mult>
<Add> ::= <Mult> + <Mult>
<Zahl> ::= { <Ziffer> }+
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Turingmaschine (TM)
•
Alan Turing, 1936: Untersuchung der Berechenbarkeit
•
Struktur:
http://de.wikipedia.org/wiki/Datei:Turingmaschine.svg, © TripleWhy
•
Fester Teil (Hardware), variabler Teil (Software)
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Steuerung: Programm
• Aktionen
– Schreibe Zeichen a und gehe nach rechts: (a, r)
– Schreibe Zeichen a und gehe nach links: (a, l)
• Programme = Zustandsübergangsfunktionen
– Zustand, Zeichen -> Aktion, neuer Zustand
– Definition von Startzustand und Endzuständen
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Beispiel 1: Lösche alle Einsen
Gegeben:
• Alphabet: 0, 1
• Startzustand: A (Lesekopf links)
• Endzustand: B
Programm:
• Zustand A, Eingabe 1 -> (0, r), Zustand A
• Zustand A, Eingabe 0 -> (0, l), Zustand B
• Zustand B: fertig
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Zustandstabelle
Zustand
Eingabe
Operation Folgezustand Kommentar
A
1
0, rechts
A
0
0, rechts
B
B
Anfangszstd.
Ende
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Graphische Darstellung
Deterministischer endlicher Automat
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Zustandstabelle
Beispiel
2
Was macht folgender Algorithmus?
Alphabet: { 0, 1, #}, #: Ende der Zeichenkette
Zustand
Zustand
A
A
B
Eingabe
Eingabe
1
0
0
1
#
Operation Folgezustand Kommentar
Operation Folgezustand Kommentar
0, rechts
A
Anfangszstd.
1, rechts
A
Anfangszstd.
0, rechts
B
0, rechts
A
Ende
#, rechts
B
B
Ende
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Zustandstabelle
Beispiel
2 graphisch
Zustand
Zustand
A
A
B
1: (0,r)
Eingabe Operation Folgezustand Kommentar
Eingabe Operation Folgezustand Kommentar
1
0, rechts
A
Anfangszstd.
0
1, rechts
A
Anfangszstd.
0
0, rechts
B
#:
(#,l)
1
0, rechts
A
Ende
#
#, rechts
B
B
Ende
0: (1,r)
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Church‘s These
• Die TM hat alles was ein Computer braucht.
• D.h.: C++ ist nicht mächtiger als TM.
• Wozu braucht man dann C++?
• Turingtest: Der Mensch ist nicht mächtiger als TM!
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Von Neumann Maschinen
Register
CPU
Rechenwerk
Cache
Bus
BefehlsIU
zähler
Daten, Befehle
Hauptspeicher (RAM)
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Von Neumann Maschinen
Register
CPU
Rechenwerk
Cache
Bus
BefehlsIU
zähler
Daten, Befehle
Hauptspeicher (RAM)
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Von Neumann Maschinen
Programmiersprachen
ddot:
Eingabe von Daten und Befehlen
• Maschinensprache (Assembler)
• Befehl holen
• Befehl dekodieren
• Befehl ausführen
push EBP
mov EBP, ESP
push EAX
push EBX
push ECX
push EDX
mov EAX, [EBP+8]
cmp EAX, 0
Daten,
Befehle
je fehler
mov EBX, [EBP+12]
cmp EBX, 0
je fehler
mov ECX, [EBP+16]
cmp ECX, 0
je fehler
mov EDX, 0
fldz
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Von Neumann Maschinen
Programmiersprachen
ddot:
• Höhere Programmiersprachen
Der Programmierer soll Programme möglichst
•
schnell
•
effizient
•
korrekt
Daten, Befehle
erstellen können.
Wir lernen C++
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Trends der Informatik
• Mooresches Gesetz:
Prozessoren verdoppeln Geschwindigkeit alle 18 Monate
gilt auch für viele (aber nicht alle!) andere Hardware
• Auto (BMW 7er Serie, 2003)
– 96 Prozessoren (!), mehrere Kilometer Kabel
– 10 Millionen Lines of Code
• ADAC: 50% der Pannen in 2002 waren E-Fehler
• Leistung eines Programmierers
– 10.000 neue Programmzeilen pro Jahr
– 2 Programmzeilen ändern pro Tag
Programmieren 1
G. Wittum, G-CSC, Universität Frankfurt
Document
Kategorie
Bildung
Seitenansichten
17
Dateigröße
2 088 KB
Tags
1/--Seiten
melden