2Informak–Überblick - mi.informatik.uni-siegen.demi.informatik.uni-siegen.de/teaching/lectures/EI/script/02Overview.pdf · • Einführung grundsätzlicher Informatik-Begriffe"

Prof. Dr. Volker BlanzFachgruppe Medieninformatik"

Algorithmen und Datenstrukturen

2 Informa*k – Überblick

Motivation: Ziele dieses Abschnittes"•  Abgrenzung „Was ist Informatik?“"•  Einführung grundsätzlicher Informatik-Begriffe"•  Erstes einfaches Modell zur Softwareentwicklung (→ EI-2)"!Herausforderungen: "•  Erkenntnis: Informatik ist Strukturwissenschaft

"Literatur: Diverse Abschnitte in [Claus] plus "•  [Ernst] Kapitel 1.2 "•  [Herold] Kapitel 2"•  http://www.zib.de/zuse/

2.1



Wortursprung: Unterschiedliche Aussagen zum Wortursprung: "•  [WikiInf]: Kombination aus Information & Mathematik nach Karl Steinbuch,

1957 "•  [Ernst]: Kombination aus Information & Automation (frz. informatique) nach

Phillippe Dreyfus, 1962"•  Nebenbei: im angelsächsischen Sprachraum existiert dieses Wort nicht.

Dort: Computer Science."

Wortbedeutung nach [Claus]:„Wissenschaft von der systematischen Darstellung, Erfassung, Speicherung, Verarbeitung und Übertragung von Informationen, besonders der automatischen Verarbeitung mit Hilfe von Digitalrechnern.“"

è Computer ist „nur“ Hilfsmittel, nicht Selbstzweck"è Informatik ist eine Strukturwissenschaft, d.h. zentral sind"•  Überführung realer Sachverhalte in Strukturen/Modelle (Abstraktion)"•  Verarbeitung der Strukturen bzw. mathematischen Modelle mittels Computern

(Transformation)"•  Rückinterpretation der Ergebnisse auf reale Sachverhalte

2.2

2.1 Was ist Informa*k?



Altertum: Manuelle Rechenapparate wie Abakus und Rechensteine"

"Das Zahlsystem hat großen Einfluss darauf, wie Rechnungen durchgeführt

werden:"Babylonier: 60er-System"Ägypter: Dezimalsystem"Inder: Dezimalsystem"Römer: additives System, das v.a. bei Multiplikationen sehr unhandlich ist."16.Jh: Dezimalsystem setzt sich in Europa durch (u.a. durch Adam Riese)

"!"

2.3

2.2 Eine kurze Geschichte der Informa*k



Hinzu kommen Rechenverfahren (ohne maschinelle Automatisierung)"Bei einfachen Rechnungen gibt es einen engen Zusammenhang zwischen "•  Algebra (symbolisches Rechnen mit Variablen, Lehre von Rechenverfahren

und math. Strukturen),"•  Algorithmen (Folgen von Anweisungen, genaue Definition siehe später)"!Babylonier: Mathematische Keilschrifttexte""Diese enthalten Rechnungen mit konkreten Zahlen und einer Beschreibung im

Text. Beispiel: Flächen und Getreideerträge von Feldern."“(…) 30 setze den Feldanteil, 20 setze das Getreide, das er geerntet hat. (…)

auf zwei Teile verteile sie, 15 und 15 bis zu seinem zweiten setze; das Reziproke von 30, dem Feldanteil, zerlege: 2. (…)”"

"Es fällt auf: "•  Alle Größen sind genau spezifiziert und können vom Leser leicht durch andere

Zahlen ersetzt werden."•  Die Zahlen, einschließlich der Ergebnisse, sind auffallend einfach."Die Tafeln können als erste Rechenanleitungen gewertet werden."!"

2.4




KeilschriBtafeln

•  Etwa handtellergrosse Tafeln aus Ton, die bei einem Hausbrand „versehentlich“ gebrannt und dadurch konserviert wurden.

5



Islamische Kultur im Mittelalter (Araber, Perser, ...) :"Texte zum kaufmännischen Rechnen. ""Abu Abd´ Allah Muhammad b. Musa Al-Khwarazmi, um 800, Perser"Übersetzungen: Robert von Chester (1145), Gerhard von Cremona (1114-1187)."•  Das Wort Algorithmus geht auf den Namen Al-Khwarazmi zurück,"•  Das Wort Algebra auf al-gabr: “Einrenken von (gebrochenen) Teilen,

Wiederherstellen eines Gleichgewichts”. Anfang eines Buchtitels von Al-Khwarazmi."

"Rechnen mit Unbekannten. Al-Khwarazmi hat aus Merksätzen eine Theorie

aufgebaut."Es geht, mathematisch, um das Lösen von einfachen Gleichungen."

2.6




Wilhelm Schickard (1592-1635)!•  Deutscher Professor für biblische Sprachen, Astronomie und Mathematik"•  1623: Additions- und Subtraktionsmaschine"•  1630: Handplanetarium mit Sonne, Erde und Mond

"

2.7





Grundlage der Schickard´schen Rechenmaschine sind Napierstäbe, eine einfache Rechenhilfe, die man aneinanderlegen kann, um Rechnungen durchzuführen.

•  1614: Lord John Napier of Merchiston

1650 Logarithmischer Rechenschieber!•  Eine einfache Rechenhilfe mit gegeneinander verschiebbaren Skalen"•  Lineare Skalen würden Addition und Subtraktion erlauben"•  Seit 1650 üblich: logarithmische Skalen für Multiplikation und Division"

8



Blaise Pascal (1623-1662)!•  Französischer Mathematiker, Naturwissenschaftler,

Philosoph"•  1641: Maschine zur Addition sechsstelliger Zahlen"•  1654: Abhandlungen über das Pascalsche Dreieck,

Zahlenordnungen und Zahlenkombinationen"

2.9




Gottfried Wilhelm Leibniz (1646-1716)"•  Deutscher Philosoph, Mathematiker, Physiker,

Historiker, Diplomat "•  Formulierte unabhängig von Isaac Newton die heute

noch gebräuchliche Infinitesimalrechnung (Differential- und Integralrechnung)"

•  Entwickelte die Dyadik (Binärsystem)"•  1674: Mechanische Rechenmaschine mit Staffelwalzen

für die vier Grundrechenarten ""Philipp Matthäus Hahn (1739-1790)!•  Deutscher Pfarrer, Konstrukteur und Erfinder"•  1774: Erste zuverlässige Rechenmaschine in Kleinserie"•  Rechen- und Ergebniswerk mit Staffelwalzen

2.10




Lochkarten in der Webtechnik: 1804 Joseph Maria Jacquard!

!!!!!!!!!Hermann Hollerith (1860-1929)!•  US-amerikanischer Unternehmer, Ingenieur und Erfinder"•  1886: Erste elektrisch arbeitende Zählmaschine für Lochkarten; Einsatz bei

einer Volkszählung in den USA"•  Volkszählung ohne seine Maschine und mit 500 Helfern: 7 Jahre

Volkszählung mit 43 seiner Maschinen und 500 Helfern: 4 Wochen

2.11




Charles Babbage (1792-1871) !•  Englischer Mathematiker, Philosoph, Erfinder

und politischer Ökonom"•  1838 : Erster Ansatz für Lochkarten-Steuerung

einer Rechenmaschine"•  Erstmals die Komponenten

Rechenwerk, Steuerwerk, Zahlenspeicher und Programmspeicher"

•  Damit programmierbar! "•  Zusammenarbeit mit Ada Lovelace:

erste Programme auf diesem Rechner."

2.12




Konrad Zuse (1910-1995)!•  Deutscher Bauingenieur, Unternehmer und Erfinder"•  Entwicklung programmgesteuerter Rechenmaschinen mit binärem

Zahlensystem"•  1938: Fertigstellung der elektromechanischen Z1"•  1941: Funktionsfähiger, programmgesteuerter Rechenautomat Z3:"§  2.000 Relais und Lochstreifenleser"§  Speicherkapazität: 64 Worte á 22 Bit. 4 Grundrechenarten und Wurzel."§  Multiplikationszeit: ca. 3s

2.13


Zuse Z1 (Berlin 1937)" Zuse Z3 (Nachbau Dt. Museum 1960)"



Relais!Ein elektromechanischer Schalter:

Fließt durch die Magnetspule ein Strom, so wird ein Mechanismus betätigt, der einen oder mehrere nebeneinanderliegende Schalter betätigt."

"Anwendungen:"•  Treppenhauslicht"•  Schalten eines starken Stromes mit einem schwachen Steuerstrom"•  Flipflop-Schaltung (quasi ein 1 bit Speicher)"

•  Aus dieser Zeit stammt die Bezeichnung Bug (Wanze) für Programmierfehler.""

2.14




Elektrischer „Schalter“ als Grundbausteine aller Computer"!Eine Steuerspannung an einem Kontakt legt fest, ob auf einer anderen

Leitung Strom fließen kann oder nicht.!!Relais: Ein Elektromagnet betätigt einen elektrischen Schalter.""Elektronenröhre: Wie in einer Fernsehbildröhre wird ein Elektronenstrahl im

Vakuum aufgebaut. Negative Steuerspannung an einem zu durchfliegenden Gitter hindert die Elektronen durch elektrostatische Abstoßung daran, zur Anode zu gelangen, der Strom dorthin wird unterbrochen."

"Transistor: Ein Halbleiter ist zunächst nicht-leitend, da alle

Elektronenzustände im Leitungsband aufgefüllt sind und dadurch kein Netto-Strom fließen kann. Ein Steuer-Strom oder ein elektrisches Feld (FET) generiert dort"

bewegliche Ladungsträger, sodass der Übergang " leitend wird.""" 2.15




John P. Eckert (1919-1995) und John W. Mauchly (1907-1980):!•  1946: Erste programmierbarer Rechner ENIAC auf Röhrenbasis, allerdings auf

Dezimal-Basis"•  17.000 Röhren"•  Multiplikationszeit: ca. 3ms

2.16




Alan Turing (1912-1954)!•  Britischer Logiker, Mathematiker, Kryptoanalytiker sowie „Erfinder“ der

Theoretischen Informatik"•  1936: Formulierung des theoretischen Modells der Turing-Maschine zur

Ausführung beliebiger Algorithmen: Lese-Schreibkopf auf Arbeitsband."•  ab 1946: Zahlreiche theoretische Arbeiten zur Programmierung und zur

Künstlichen Intelligenz (KI)"

John von Neumann (1903-1957) "•  Chemie-Ingenieur, Physiker und Mathematiker"•  Geboren als János Lajos Neumann, wählte später die

Namen Johann von Neumann und zuletzt John von Neumann"

•  1926-1930: Jüngster Privatdozent der Humboldt-Universität zu Berlin"

•  1945: Konzept des modernen General-Purpose-Computers (von Neumann-Architektur)."

•  Programme werden wie Daten gespeichert.

2.17




Computer-Generationen"

0. Generation: Z3 (Zuse, 1941) und MARK1 (Aiken, 1944)"•  Programmierbare elektromechanische Rechenmaschinen nach den Prinzipien

von Babbage"•  Arbeiteten mit Hilfe von Relais

"1.  Generation: ENIAC (Ecket & Mauchly, 1946) und PERM (TU München, 1952)"•  Statt Relais nun Nutzung von Röhren"•  Erste, nach heutiger Definition als Computer zu bezeichnende Maschinen"•  Weitere Rechner der Firmen Remington Rand und IBM (Typ 701)"•  Programmierung:"

§  Zunächst Assembler (maschinenlesbare Befehle)"§  Später in der ersten höheren Programmiersprache FORTRAN

2.18




2. Generation: Ersetzung der Röhren durch Transistoren"•  Erster Vertreter 1955 bei den Bell Laboratories gebaut"•  Deutlich kleiner, sparsamer und robuster"•  1956 entstand IPL, ein Vorgänger der Programmiersprache LISP"•  1960 erste kommerzielle Programmiersprache COBOL von IBM"•  Zeitgleiche Einführung von ALGOL als Alternative zu FORTRAN

"3. Generation: PDP 8 (DEC, 1960) und Serie 360 (IBM, 1964)"•  Transistoren durch integrierte Schaltkreise ersetzt ⇒ Erhöhte

Leistungsfertigkeit bei kleineren und preiswerteren Geräten "•  Zahlreiche weitere Programmiersprachen wie BASIC, PL/1 und PASCAL

2.19




4. Generation: Apple-Computer (Jobs & Wozniak, 1977) und Personal Computer (IBM, 1981)"

•  Einsatz von höchstintegrierten Schaltkreisen"•  Vollständige CPU auf einem Chip"•  “Home Computer“: 1981 ZX-81, später z.B. C64"•  Erste Prozessoren mit 32-Bit Adressierung ab 1988"•  Programmierprachen: LISP, PROLOG, C"•  Betriebsysteme DOS (IBM), später MS-DOS (Microsoft)"§  Freies Betriebssystem UNIX"•  Erste elektronische Taschenrechner von Texas Instruments (1973) und Hewlett

Packard (1973); später frei programmierbare Versionen (1976, HP)

2.20




„Homecomputer“ der 80er

21

1981: ZX-81 (Sinclair, 1Kb) 1981: TI 99 4a (Texas Instruments, 16 kB)

1982: C64 (Commodore, 64kB) 1985: Atari ST (1MB)



5. Generation: Gegenwart und Zukunft"•  Parallele Entwicklung zur 4. Generation seit Mitte der 80er Jahre"•  Objektorientierte Programmierprachen:"

§  Smalltalk, SIMULA"§  C++"§  Java"

•  Wesentliches Merkmal neuester Architekturen: Teilweise Abkehr vom von-Neumann-Prinzip Ziel: Parallele Verarbeitung mit mehreren Prozessoren und unter Einsatz neuer Bauelemente (Multi-Kernel-Architektur, GPU) "

•  Anwendungen in allen Lebensbereichen

2.22




2.3 Vom Problem zum Programm

2.23

Abstrak*on/Modell

Denkschweiß Programmierung

Reale Welt

Lösungsidee Algorithmus Programm

Ausführbare Anwendung

Problem

Krea*vität/Intui*on automa*sch

Lösung



Beispiel: CAD-‐CAM basierte Zahnmedizin

•  Aus einem 3D Scan des Restzahnes soll die fehlende Zahnfläche geschätzt werden. •  Keramik-‐Inlay wird automa*sch aus einem Würfel geschliffen (CNC-‐Schleifmaschine)

24



Beispiel: CAD-‐CAM basierte Zahnmedizin

Lösungsidee: •  Lerne aus Beispielen, wie Zähne aussehen können •  Entwickle ein deformierbares Modell •  Passe das Modell an die Restzahnsubstanz an Algorithmen: •  Aufarbeitung der Beispielzähne •  Anpassung an Restzahnsubstanz Programm: •  läuB heute auf dem Computer vieler Zahnärzte

25

∑∑ +−=i i

i

kkkE 2

22'

σα

ηxx


Algorithmen und Datenstrukturen 2.26


Das Wasserfallmodell!Systemanalyse und

-‐spezifika*on

System-‐ und Algorithmenentwurf

Programmierung

Programmtest

Dokumenta*on

Installa*on

Wartung und Pflege



Eine idealisierte Vorgehensweise: Das Wasserfallmodell!1. Systemanalyse und –spezifikation" (Spezifikation = (mathematisch) präzise Formulierung der Aufgabe"•  Saubere, formale Erfassung der Problemstellung"•  Szenarien, Nebenbedingungen, Sonderfälle, Formate, … sind zu

berücksichtigen""2. System- und Algorithmenentwurf"•  Analyse der Problemstellung"•  Ähnliche Probleme bekannt? Aufteilung in Teilprobleme möglich?"•  Auswahl, Anpassung und Erstellung mathematischer Algorithmen"•  Definition der Systemstruktur (Funktion einzelner Module und Kommunikation

zwischen diesen)""3. Programmierung"•  Konkrete Implementierung der entworfenen Algorithmen und Strukturen

2.27




4. Programmtest"•  Überprüfung der Funktionalität"•  Beseitigung von Fehlern""5. Dokumentation"•  Nicht nur Benutzerhandbuch, sondern auch Entwicklerdokumentation""6. Installation"•  Installation auf dem Kundensystem und wiederum Überprüfung der

Funktionalität""7. Wartung und Pflege"•  Häufig der zeitaufwändigste Teil der Softwareentwicklung"•  Anpassung der Software an neue Wünsche des Kunden"•  Erweiterung des ursprünglichen Systems"•  Umstellung des Systems auf neue Hardware oder Datenformate"

2.28




Entscheidendes Merkmal des Wasserfallmodells:"•  Erst wenn ein Arbeitsschritt komplett abgeschlossen ist, wird mit dem nächsten

begonnen. Die Metapher des Wasserfalls steht für eine Reihe von Becken mit Überlauf: erst wenn ein Becken voll ist, fließt Wasser durch den Überlauf ins nächst tiefere Becken."

2.29




Beispiel: Errichtung eines Großmarkts für Südfrüchte!Zunächst: Das Wasserfallmodell kann in abgewandelter Form auch auf nicht-

informatische Probleme angewendet werden."!Systemanalyse und -spezifikation, hier:"•  Welche Anforderungen gibt es? (Kunde bestellt, Großhändler liefert, ..)"•  Was steht zur Verfügung? (Zeit, Geld, Gebäude, …)"!System- und Algorithmenentwurf, hier:"•  Planung der internen Abläufe (Verwaltungsaufgaben, Lagerplanung, etc.)"•  Planung der externen Abläufe zum Kunden (Konfektionierung, Rechnungsstellung,

Warenversand, Online-Dienste)"•  Benötigte Mitarbeiter, Büroräume, Lager, Verkaufsfläche, Software, Computer etc."!Programmierung, hier:"•  Aufbau des Gebäudes, der Inneneinrichtung und der notwendigen Infrastruktur

2.30




Programmtest, hier:"•  Test der Infrastruktur für interne und externe Abläufe"Dokumentation, hier:"•  Handbuch über die internen und externen Abläufe"•  Notfallpläne (z.B. bei Ausfall des Kühlaggregats)"•  Informationsmaterial für die Kunden"Installation, hier:"•  Einweisen der Mitarbeiter, Anbringen von Hinweistafeln"•  Öffnen der Pforte"Wartung und Pflege, hier:"•  Erweiterung des Großmarktes"•  Bei Problemen: Entwicklung einer Lösung, d.h."

§  Planung alternativer interner oder externer Abläufe"§  Realisierung und Test"§  Anpassung der Dokumentation

2.31




Bemerkung: Wasserfallmodell!!In der Praxis ist dieses Vorgehen nicht in dieser starren Form möglich, z.B."•  sind Änderungen/Anpassungen aufgrund neuer Erkenntnisse im Verlauf der

Entwicklung unvermeidlich,"•  müssen Tests zur Fehlerbeseitigung bereits in frühen Stadien an einzelnen

Teilen der Algorithmen bzw. Software durchgeführt werden und"•  bessere Kommunikation zwischen den Entwicklern durch frühzeitige und

aktuelle Dokumentation""Frühzeitige Kommunikation mit dem Kunden/Nutzer ist sehr wichtig:"•  Entwicklung von Prototypen, um Kunden frühzeitig Einblicke zu geben."•  Vermeidung von Fehlern, die nach der Abnahme beim Kunden auftauchen."•  Manche (neue) Kundenwünsche sind mit den zur Verfügung stehenden

Resourcen (Personal, Geld, Zeit,…) nicht (mehr) lösbar

2.32



Algorithmen und Datenstrukturen 2.33


Systemanalyse und -‐spezifika*on

System-‐ und Algorithmenentwurf

Programmierung

Programmtest

Dokumenta*on

Installa*on

Wartung und Pflege



Wichtige Erkenntnisse und Inhalte dieses Abschnitts:"!Informatik ist eine Strukturwissenschaft, die auf Mathematik aufbaut und Abstraktion

von realen Sachverhalten erfordert"!Rechenmaschinen haben eine fast 400-jährige Historie"!Informatik-Konzepte sind teilweise alt (Dualzahlen), größtenteils aber erst nach 1936

(Alan Turing) entstanden"!Von-Neumann-Architektur ist zentrales Prinzip moderner Computer"!Software-Entwicklung ist ein komplexer Prozess und erfordert"•  praktische Erfahrung (insb. Programmiererfahrung),"•  gute Kenntnisse grundlegender Algorithmen, theoretischer Grundlagen und

Vorgehensweisen,"•  weitgehende Kompetenz im konkreten Anwendungskontext und"•  soziale Fähigkeiten (Umgang mit Kunden, Arbeit in Projektteams ..)

2.34

2.4 Zusammenfassung

Documents

2Informak–Überblick - mi.informatik.uni-siegen.demi.informatik.uni-siegen.de/teaching/lectures/EI/script/02Overview.pdf · • Einführung grundsätzlicher Informatik-Begriffe"