Klausur AUD PDF - Algorithmen und Datenstrukturen

C ++ Variablen Char - Buchstabe charss- Buchstaben > > string include-strings + - int-Zahl in -...

C ++ Variablen Char - Buchstabe charss- Buchstaben > > string include-strings + - int-Zahl in - neue Zeile Zahl Text - to-string... + in float - > Komma Zahl 4 Byte double - komma Zahl 8 Byte boo > - false , true void t nichts (in,... getline ↑ Text eingabe IEEE 754 -7 Exponent  Nicht Relevant -Geschichte - übersicht Programmiersprachen STL Sequenzielle Datenstrucktar in der - -Formale Sprachen -Graphen Suchalgorithmen - -Sortieralgorithmen Syntaxdiagramm  3.1$Von(Neumann$Rechnerarchitektur$ John!von!Neumann!(190311975):!Theore?sche$Überlegungen$zum$AuZau$eines$Rechners$ Grundprinzip$des$General(Purpose(Computers$(PCs,$Server)$ Ausnahmen$sind$z.B.$Parallelrechner$ Moderne$Dual($oder$Mul?core$CPUs$gehen$über$das$Prinzip$hinaus$ $ Grundprinzipien:$(nur$die$wich?gsten)$ Problemunabhängigkeit$→$Programm$steuert$konkreten$Ablauf$ Das$Programm$besteht$aus$einer$Sequenz$von$binären$Entscheidungen$ Das$Programm$wird$wie$die$Daten$im$Speicher$abgelegt.$$ Im$Speicher$sind$Daten,$Adressen$und$Programme$nicht$zu$unterscheiden.$ $ Komponenten!eines!Von1Neumann1Rechners! Steuerwerk:$Kontrolliert$Ablauf$im$Gesamtsystem$„Rechner $ Rechenwerk$(Arithme?c$&$Logic$Unit,$ALU):$Arithme?sche$&$logische$Opera?onen$und$ Berechnungen$ Arbeitsspeicher:$Enthält$maschinenlesbare$Programme$und$Daten$ Ein(/Ausgabeeinheit:$Bereitstellen$von$und$Speichern$auf$externen$Geräten$ Verbindungssystem$(Bussystem)$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.2$ Fachgruppe Medieninformatik  3.1$Von(Neumann$Rechnerarchitektur$ Prinzipieller$AuZau$des$von(Neumann$Rechners:$ Prozessor$(CPU)$ $ Steuerwerk$ $ Rechenwerk$ $ Verbindungssystem$(Bus)$ Speicher$ Eingabe$/$Ausgabe$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.3$ Fachgruppe Medieninformatik  3.1$Von(Neumann$Rechnerarchitektur$ PrinzipauIau!moderner!Rechner! Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.4$ Fachgruppe Medieninformatik  3.1$Von(Neumann$Rechnerarchitektur$ PrinzipauIau!moderner!Rechner!(Forts.)! CPU:!Central$Processing$Unit$(Zentrale$$ Verarbeitungseinheit)$ Aufgabe:$Befehle$interpre?eren$$ und$ausführen$ ! ROM:!Read$Only$Memory,$Festwertspei($ cher$mit$Lese(Zugriff$ ! RAM:!Random$Access$Memory,$Speicher$mit$Lese($und$Schreib(Zugriff$ ! Datenbus:!Übertragung$von$Daten$(als$Lese($oder$Schreibzugriff)$oder$Programmbefehlen$ Adressbus:!Übertragung$der$aktuellen$Speicheradresse$für$Lese($oder$Schreibzugriff! Steuerbus:!Übertragung$der$Steuerbefehle$vom$Steuerwerk$an$andere$ Verarbeitungseinheiten,$z.B.$ob$Lese($oder$Schreibzugriff$auf$RAM$erfolgen$soll.! $ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.5$ Fachgruppe Medieninformatik  3.1$Von(Neumann$Rechnerarchitektur$ Daten,!Adressen,!Befehle! $$$…sind$einheitlich$repräsen?ert$durch$binäre$Einheiten.$ $$$$$$$1$Bit$=$elementares$Ja/Nein$Signal$$0/1$ $$$$$$$1$Byte$=$8$Bit$ $$$$$$$1$Wort$=$eigentlich$definiert$durch$Breite$des$Datenbusses$(16,$32$oder$64$Bit)$ $$$$$$$$$$$$meist$aber$nach$Konven?on:$ $$$$$$$$$$$$$$$$$1$Wort$$$$$$$$$=$2$Byte$=$16$Bit,$$ $$$$$$$$$$$$$$$$$1$Langwort$=$4$Byte$=$32$Bit.$ $ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.6$ Fachgruppe Medieninformatik  3.1.1$Central$Processing$Unit$(CPU)$ Aufgabe:! Befehle$interpre?eren$und$ausführen$ Einfachster$Fall:$Zu$jedem$Zeitpunkt$wird$1$Befehl$ausgeführt,$der$1$Datenwert$ berechnet$(SISD,$Single$Instruc?on$Single$Data).$$ ! Speicherplatz!auf!der!CPU:$Register$und$Caches$ Register:$$ – sehr$schneller$Speicher$ – direkt$am$Rechenwerk$ – speichert$jeweils$ein$Elementardatum$(Zahl,$Adresse,$Befehl)$ – z.B.$Datenregister$D0(D7,$Adressregister$A0(A7$$(beim$M68000$Prozessor)$ Cache:$Zwischenspeicher$mit$schnellem$Zugriff$und$geringer$Kapazität$ Weitere$Register$zur$Speicherung$von$Ergebnissen$&$Zuständen$ Mikroprogramm(Speicher$(als$ROM)$ $ ! Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.7$ Fachgruppe Medieninformatik  3.1.1$Central$Processing$Unit$(CPU)$ Steuerwerk:$ Steuerung$der$an$Befehlsausführung$beteiligten$Einheiten,$$ insbesondere$Auswahl$der$Opera?onen$für$ALU$(Rechenwerk)$ Umsetzung$von$Maschinenbefehlen$(Befehlsdekodierer)$ Adressberechnung$für$Daten$und$Befehle$ ! Rechenwerk!(Arithme$c!Logical!Unit,!ALU):$ Ausführung$von$Opera?onen$(+,(,*,$∕, , ,…)$ Verknüpfung$von$je$höchstens$zwei$Operanden,$von$denen$mindestens$einer$ein$ Register$sein$muss.$ Ein(Adress(Maschine:$Einer$der$Operatoren$ist$ein$festes$Register,$der$Akkumulator.$ $$$$Z.B.$$$$$$$$$$akkumulator = akkumulator + x$ Man$muss$nur$die$Adresse$von$x$angeben$ Heute$meist:$Zwei(Adress$Maschinen:$Als$Akkumulator$dient$eines$der$Register,$man$ muss$dessen$Nummer$i mit$angeben:$Di = Di + x Drei(Adress$Maschine:$$Ergebnis$wird$nicht$mehr$in$einen$Akkumulator$ zurückgeschrieben,$sondern$in$eine$dri4e$Speicherstelle.$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.8$ Fachgruppe Medieninformatik  3.1.1$Central$Processing$Unit$(CPU)$ Maschinensprache:$$$ In$dieser$Form$liegt$das$ausführbare$Programm$im$Speicher$vor$ Befehle$sind$im$Wesentlichen$durchnummeriert$(OP(Code).$ Opera?onsteil$und$Adressteil$(=Speicheradresse$oder$Registernummer)$ Op(Code$ Operand$1$ Operand$2$ 4 Bit 6 Bit 6 Bit = 1 Wort Assembler1Sprache! Fast$äquivalent$zu$Maschinensprache,$aber$leichter$lesbar$für$Menschen$ Kürzel$für$Befehle$(mnemonics),$für$Register$und$verschiedene$Adressierungsarten$ Syntax$hängt$vom$Prozessortyp$ab$ Beispiele:$ $$$$$$$MOVE.W (A0) D1 Verschiebe$Inhalt$(Wort)$der$Adresse$A0$(RAM)$in$Register$D1$ $$$$$$$JMP A0 Springe$im$Programm$zum$Befehl$in$Adresse$A0$ $$$$$$$ADD.W (A0) D1 Addiere$Inhalt$von$$Adresse$A0$(RAM)$zu$Register$D1$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.9$ Fachgruppe Medieninformatik  3.1.1$Central$Processing$Unit$(CPU)$ Das!Steuerwerk! Beispiel(Programmbefehl:$$ $$$$MOVE.W (A0) D1 Dekodierer:$Entschlüsselung$des$$ Befehls$ Mikroprogrammeinheit:$Interpre($ ta?on$des$Befehls$als$Folge$von$$$ im$Rechenwerk$umsetzbaren$ Elementaropera?onen$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.10$ Fachgruppe Medieninformatik  3.1.1$Central$Processing$Unit$(CPU)$ Das!Steuerwerk!–!Register!&!Adresse! Befehlsregister$hält$auszuführen($ den$Befehl$$ Zerlegung:!Operand!&!Adresse$$ Adresse:$Lokalisiert$Daten$oder$$ Befehle$im$Speicher$(RAM$,ROM)$ Adresswert$i.A.$rela?v$(also$auf$einen$ Startwert$bezogen,$nicht$absolut)$$ (→$Adressberechnung$nö?g)$ Befehlszählregister$hält$Adresse$$ des$nächsten$Befehles$ ! Fortschreiten$(„+1 )$ ! Springen$(Befehl$JMP$A0)$ weitere$Zustandsregister$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.11$ Fachgruppe Medieninformatik  3.1.1$Central$Processing$Unit$(CPU)$ Das!Rechenwerk! Aufgabe:$Berechnung$durchführen$ Hier:$Ein(Adress(Maschine.$ Dann$Akkumulator:$ ! erster$Operand$für$Berechnung$ ! hält$Ergebnis$nach$Berechnung$ Zweiter$Operand$wird$direkt$vom$$ Datenbus$gelesen$ Rechenlogik:$Grundrechenarten,$$ logische$Opera?onen$ weitere$Arbeitsregister$ Ablaufsteuerung$durch$Folge$von$$ Elementaropera-onen.(Mikroprogramm). ! Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.12$ Fachgruppe Medieninformatik  3.1.1$Central$Processing$Unit$(CPU)$ Befehlsausführungszyklus! ! Programm!=$Folge$von$Befehlen$ ! Befehlszyklus:$Ausführung$eines$einzelnen$Befehls$ ! Konkreter!Ablauf!in$einem$Befehlszyklus$ 1. Aktuelle$Befehlsadresse$aus$Befehlzählregister$auf$Adressbus$legen$ 2. Laden$des$Befehls$in$das$Befehlsregister$ 3. Befehlszählregister$um$1$erhöhen$bzw.$bei$Sprungsbefehl$mit$neuer$Adresse$(aus$dem$ Adressteil$des$Befehls)$laden$ 4. Befehlsdekodierung$und$(interpreta?on$(Umsetzung$in$Elementaropera?onen)$ 5. Für$jede$Elementaropera?on$(ggf.$mehrfach$durchlaufen):$ I. Operandenbereitstellung$ II. Ausführung$der$Elementar(Opera?onen$ III. Ergebnisspeicherung$im$Akkumulator$ 6. Gesamtergebnis$wird$von$Akkumulator$auf$Datenbus$gestellt$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.13$ Fachgruppe Medieninformatik  3.1.2$Speicher$ 1. CPU1nahe!Speicher!! siehe$Folie$3.7.! 2.!Read1Only!Memory!(ROM):!Festwertspeicher$mit$Lesezugriff$ Iden?fika?on$der$Leseposi?on$erfolgt$über$Adressen$ Speichert$z.B.$erste$Befehle$für$das$Starten$des$Rechners! 3.!Random!Access!Memory!(RAM):!Speicher$mit$schnellem$Lese($&$Schreibzugriff$ speichert$Daten$und$Programme$ Iden?fika?on$der$Lese($bzw.$Schreibposi?on$über$Adressen$ keine$persistente$(dauerhawe)$Speicherung$von$Daten/Programmen$ Besonders$schneller$und$eng$mit$der$CPU$verbundener$RAM$in$Caches!(mehrere$Stufen$ L1,$L2,$L3,$teilweise$auf$der$CPU,$teilweise$daneben).$ – DRAM$=$dynamic$RAM:$Gate$des$Transistors$fungiert$als$Kondensator.$Muss$alle$ paar$Nanosekunden$aufgefrischt$werden.$Billig,$langsamer$Zugriff.$ – SRAM$=$sta?c$RAM:$kein$Auffrischen,$schnell,$dafür$teuer$(mehrere$Transistoren$pro$ Bit).$Es$muss$konstant$Spannung$angelegt$werden$–$Inhalt$verfällt$bei$Abschaltung.! 4.!Festpla`e:!Persistenter$Lese($und$Schreib(Speicher$auf$Basis$von$Magne?sierung$ $$$$$$$$$$oder$in$ähnlicher$Rolle:$SSD$(Solid$State$Drive,$also$Halbleiter)$mit$FLASH(Speicher$ 5.!Externe!Speichermedien:!CDROM,!FLASH(Speicher$auf$USB(S?cks,$…$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.14$ Fachgruppe Medieninformatik  3.1.2$Speicher$ Speicher1Hierarchie! Drei$Speicherebenen$für$Daten$&$Programme$$ $ $ $ $ $ $ $ $ $ $ $ Caches$speichern$ zuletzt$genutzte$Daten$ zuletzt$berechnete$Ergebnisse$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.15$ Fachgruppe Medieninformatik  3.1.2$Speicher$ Das!Lokalitätsprinzip! Grundsätzliches!Ziel:!Schneller$Zugriff$auf$Daten$&$Befehle$ Daten!&!Befehle!sind$im$Speicher$sequen?ell$angeordnet$ Zugriff!erfolgt$bei$langsamen$Speichern$(z.B.$Festpla4e)$über$„Leseköpfe $ $ $ $ $ $$$$$$$$$$$$$$$$$$$$$ !Zugriff!auf!benachbarte!Daten/Befehle!ist!schnell! $ Lokalitätsprinzip:$Nächster$Befehl$nutzt$mit$hoher$Wahrscheinlichkeit$Daten$benachbart$ zu$den$zuletzt$genutzten$Daten$ Konkrete$Lage$der$Daten$im$Speicher$beeinflusst$Performanz:$ $$$$schneller$Zugriff$auf$Daten$in$Nähe$der$zuletzt$geladenen$Daten$ $$$$langsamer$Zugriff$auf$Daten$enzernt$von$zuletzt$geladenen$Daten$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.16$ Fachgruppe Medieninformatik  3.1.3$Bus(System$ Ziel:!Verbindung$von$Rechner(Komponenten$zum$Austausch$von$Daten! Direkte!Verkabelung!„aller$mit$allen $wäre$extrem$platzintensiv$ ! Ansatz:!Mehrere$Geräte$nutzen$einen$Datenübertragungsweg$ zusätzliche$Steuerung:$Ein$Gerät$sendet,$mindestens$eines$empfängt$Daten$ ! Serieller!Bus:!Sequen?elle$Übertragung$von$Daten$im$Binärformat$(0(1(Folge)! Paralleler!Bus:!Gleichzei?ge$Übertragung$über$n$Leitungen$(n$ist$Busbreite)$ Typisch:$32(Bit$(n=32)$und$64(Bit$(n=64)$Busse$ ! Bandbreite!eines!Busses:!Übertragungsrate$pro$Zeiteinheit/Takt$ ! Systembus:!Gesamtheit$der$folgenden$drei$Busse:$ Datenbus:$Überträgt$Daten$&$Befehle$vom/zum$Speicher$ Adressbus:$Festlegung$der$Speicheradresse$ Steuerbus:$Übertragung$von$Steuerbefehlen$(z.B.$„Schreibe ,$„Lese )$ Daneben$gibt$es$noch$weitere$Busse$ PCI$Bus$(Peripheral$Component$Interconnect)$verbindet$Peripherie$(Festpla4e,$Grafikkarte,$ Soundkarte,$$…)$mit$der$host$bridge,$die$mit$CPU$und$Arbeitsspeicher$verbunden$ist.$$ USB$(Universal$Serial$Bus)$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.17$ Fachgruppe Medieninformatik  3.1.4$Probleme$der$Von(Neumann(Architektur$ Von1Neumann!Flaschenhals:!! Die$Bandbreite$des$Datenbusses$ist$rela?v$zur$CPU(Leistung$gering$ $$$$$$$Viele$Transfers$auf$dem$Datenbus$bestehen$aus$Befehlen$und$Adressen,$die$aus$dem$ Speicher$gelesen$wurden,$und$stehen$damit$im$Konflikt$zum$Transfer$von$Daten$ $ $Datenbereitstellung$bremst$u.U.$CPU$aus$ $ $ $ Beliebiger!Datenzugriff:!Einzelner$Befehl$legt$zu$verarbeitende$Daten$fest$ $Datenbereitstellung$erst$nach$Befehlsdekodierung$möglich!$ $ Lokalitätsprinzip:!Caches$versuchen$den$Flaschenhals(Effekt$zu$minimieren,$indem$Daten$ eines$CPU(fernen$Speichers$in$einen$CPU(näheren$Cache$kopiert$werden.$! Cache1Op$mierung:!Versuch,$die$Daten$bzgl.$der$Zugriffe$so$zu$strukturieren,$dass$das$ Lokalitätsprinzip$durch$Mehrfachnutzung$der$Cachedaten$maximal$ausgenutzt$wird,$ ansta4$bei$jedem$Befehl$einen$neue$Daten$in$den$Cache$zu$kopieren.! In!der!Praxis!kann$Cache(Op?mierung$ein$Programm$deutlich$beschleunigen$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.18$ Fachgruppe Medieninformatik  3.2$Wich?ge$Begriffe$ Datum:!Einzahl$von$Daten$ In$der$Informa?k:$Maschinenlesbare$und$(bearbeitbare$Struktur$zur$Repräsenta?on$ von$Informa?on$ – Informa?on$bezeichnet$also$etwas$Abstraktes$ – Daten$bezeichnen$dessen$konkrete$Repräsenta?on$ Wird$in$Zeichen$kodiert,$deren$AuZau$strengen$Regeln$(der$Syntax)$folgt$ ! Datei:!Daten(Verbund$auf$einem$Speichermedium$ Besitzt$einen$Namen$(z.B.$Inhalt.txt$oder$index.html)$ Besteht$aus$inhaltlich$zusammengehörigen$Daten$ Exis?ert$über$die$Laufzeit$eines$Programms$hinaus$(Persistenz)$ Daten$können$in$einem$menschen(lesbaren$Form$(ASCII)$oder$einer$maschinen(nahen,$ binären$Form$abgelegt$sein$ Dateiendung$(meist$die$letzten$drei$Zeichen$hinter$einem$Punkt)$bezeichnet$Typ$des$ Inhalts$(z.B.$txt$für$einfache$Text(Datei,$html$für$eine$HTML(Datei)$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.19$ Fachgruppe Medieninformatik  3.2$Wich?ge$Begriffe$ Algorithmus:!Handlungs($bzw.$Berechnungsvorschriw$zur$Lösung$eines$Problems$ Exakt$festgelegter$Ablauf,$mit$dessen$Hilfe$ein$bes?mmtes$Ziel$erreicht$werden$kann$ (auch$z.B.$Kochrezept)$ Abstraktes$Gegenstück$zu$der$Umsetzung$in$Form$eines$konkreten$Programms$ ! Programm:!von$griech.:$prógramma$=$Vorschriw$ Ein$Programm$ist$eine$konkrete$Umsetzung$(Implemen?erung)$eines$Algorithmus$ (oder$mehrerer$Algorithmen)$ Der$Ablauf$besteht$aus$einer$Folge$von$einzelnen$Befehlen,$die$von$der$CPU$ verarbeitet$werden$ Sowohl$der$in$einer$Programmiersprache$geschriebene$Quelltext,$als$auch$der$vom$ Computer$ausführbare$Maschinencode$wird$als$Programm$bezeichnet$ Quelltext$und$Maschinencode$werden$in$unterschiedlichen$Dateien$auf$der$Festpla4e$ gesichert.$Nur$der$Maschinencode$ist$durch$den$Prozessor$ausführbar$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 20$ Fachgruppe Medieninformatik  3.2$Wich?ge$Begriffe$ Assemblierer,!Compiler,!Interpreter:!Übersetzer$ Programme,$die$ein$Programm$(Quell(Programm)$einer$Sprache$in$eine$äquivalentes$ Ziel(Programm$überführen$ Compiler$übersetzen$Quelltext,$der$in$einer$Hochsprache$(Beispiel:$C++)$geschrieben$ wurde,$in$Maschinencode$(nur$dieser$kann$vom$Prozessoren$ausgeführt$werden)$ Interpreter$lesen$den$Quelltext$direkt$ein,$analysieren$ihn,$überführen$ihn$in$ Maschinencode$und$führen$jeden$Befehl$unmi`elbar$aus$(Beispiel:$Java)$ Assemblierer$übersetzen$maschinennahen$Assembler(Code$in$Maschinencode$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.21$ Fachgruppe Medieninformatik  3.2$Wich?ge$Begriffe$ Betriebssystem:!Programm$zum$Ausführen$von$Programmen$ Sowware$(Programm),$die$zum$Betreiben$eines$Computers$benö?gt$wird$ Verwaltet$Betriebsmi4el$wie$Speicher,$Prozessor$und$andere$Geräte$ Steuert$die$Ausführung$von$Programmen$ Besteht$aus$einem$Kern$(Kernel),$der$die$Hardware$steuert,$und$grundlegenden$ Systemprogrammen$ Schni4stellen$zur$Betriebsystemnutzung$und$Konfigura?on:$ ! Mindestens$Kommandozeileninterpreter$(auch$Shell$genannt)$ ! Graphische$Benutzeroberfläche$(GUI$=$Graphical$User$Interface)$ Populäre$Beispiele:$Unix/Linux,$Windows,$MacOS$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.22$ Fachgruppe Medieninformatik  3.2$Wich?ge$Begriffe$ Beispiel!Shell!in!Unix!/!Linux:!! Es$gibt$Befehle$wie$cd$(change$directory),$pwd$(print$working$directory),$ls$(list$all$files,$ z.B.$alle$Dateien$mit$Endung$ppt:$ls *.ppt),$cp$(copy),$mv$(move),$sowie$den$Aufruf$ von$Programmen$(sta4$Mausklick)$ $ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.23$ Fachgruppe Medieninformatik  3.3$Betriebsysteme$(BS)$ Benutzer:$Unterschiedliche$Form$der$Nutzung$eines$Rechners:$ Single(User:$Nur$ein$Nutzer$nutzt$Rechner/Programm$zur$Zeit$ Mul?(User:$Quasi(gleichzei?ge$Nutzung$durch$mehrere$Nutzer$ Remote(User:$Nutzer$arbeitet$auf$enzerntem$Rechner$ $ Weitere$Aufgaben$des$Betriebssystems:$ ! Dateisystem:$Logische,$i.a.$hierarchische$Verwaltungsstruktur$für$Dateien$ Rechteverwaltung$(„Welcher$Nutzer$darf$was? )$ Datensicherheit$z.B.$bei$Systemabstürzen$ $ Mul$1Tasking:!Verschiedene$Programme$laufen$quasi(gleichzei?g$ab$ BS$teilt$Programmen$Ressourcen$in$Zeitscheiben$zu$ BS$lagert$Programme$mit$Daten$in$CPU$&$Hauptspeicher$ein$bzw.$aus$ (nicht$zu$verwechseln$mit$Mul$processing:$Echte$Parallelverarbeitung$mit$mehreren$ Prozessoren)$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.24$ Fachgruppe Medieninformatik  3.3$Betriebsysteme$(BS)$ MS!Windows! 1990:!Windows$3.0$(später$3(1,$3(11);$fenster(gestützte$PC(Betriebssystem$Version$ ! 1995:!Windows$95;$erste$mul?tasking(fähige$Version$ ! bis!2001:!Windows$95,$Windows$NT,$Windows$98,$Windows$2000$ zunehmende$Stabilität$und$Hardwareunterstützung$ Client(Server(Anwendungen$ ! Windows!XP:!Ansatzweise$Mul?(User$und$Remote(User$ ! Stärken!und!Schwächen:!(unvollständig)$ geringe$Eins?egshürde$für$Anfänger,$stark$im$Clientbereich$ sehr$gute$Hardwareunterstützung,$inzwischen$gute$Systemstabilität$ viel$Anwendersowware,$meistens$allerdings$kostenpflich?g$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.25$ Fachgruppe Medieninformatik  3.3$Betriebsysteme$(BS)$ Unix/Linux! 1970er:!Entwicklung$von$Unix$als$mul?(tasking,$mul?(user$BS$auf$Basis$von$C$ ! 1980er:!Entwicklung$von$X(Windows$als$Graphische$Benutzeroberfläche$(GUI),$auch$für$ Remote$User$ Integra?on$von$Netzwerkdiensten$(TCP/IP)$ ! 1991:!Erste$Version$von$GNU/Linux$als$freies$Unix$Betriebssystem$für$PCs$ ! Stärken!und!Schwächen:!(unvollständig)$ früher$höhere,$heute$geringe$Eins?egshürde,$stark$im$Serverbereich$ sehr$gute$Systemstabilität,$$ zeitlich$verzögerte$Hardwareunterstützung,$da$Treiber$ow$nicht$sofort$lieferbar$sind.$ viel$freie$Anwendersowware$ viele$Distribu?ons(Derivate$(RedHat,$Debian,$…)$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.26$ Fachgruppe Medieninformatik  3.4$Zusammenfassung$ Wich?ge$Erkenntnisse$und$Inhalte$dieses$Abschni4s:$ von1Neumann!Architektur!als$Grundlage$moderner$PCs$ Grundprinzipien,$insb.$keine$Trennung$von$Daten$und$Programm$im$Speicher$ Komponenten,$insb.$CPU$(Steuerwerk$&$Rechenwerk),$Speicher$und$Busse$ Befehlsausführungszyklus$ Speicherarten$und$Hierarchie$ Lokalitätsprinzip:!Daten$in$lokaler$Nachbarschaw$schnell$zugreiZar$ Problem!der$v.(Neumann$Architektur:$U.U.$langsame$Datenbereitstellung$(Flaschenhals)$ Prak?scher$Hinweis:$Geschickte$Programmierung$nutzt$das$Lokalitätsprinzip$(Cache( Op?mierung)$ $schnellere$Programme$ Wich$ge!Begriffe,$wie$Algorithmus,$Programm$oder$Betriebssystem$ Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen! 3.27$ Fachgruppe Medieninformatik  4 Codierung... Prof. Dr. Volker Blanz 4.3 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme Additionssystem Symbole (Ziffern) für bestimmte (Grund-)Zahlen konkrete Zahl ergibt sich durch Addition der Ziffern die Position der Ziffern ist vertauschbar (kommutativ) Probleme: Schlechte Lesbarkeit, lange Zahlen, Operationen schwierig durchführbar Beispiel: Römisch-etruskische Zahlen Ziffern: I = 1, V = 5, X = 10, L = 50, C = 100,... Konvention: Ziffern werden mit abnehmender Wertigkeit notiert Zusatz: Vierfaches Auftreten einer Ziffer wird durch Subtraktion umschrieben: IIII = IV ⇒Vertauschbarkeit geht verloren Beispiele: 3 = III, 14 = XIV, 149 = CIL, 205 = CCV Prof. Dr. Volker Blanz 4.4 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme... Stellenwertsystem geht schon auf Inder und Perser zurück Wichtige Kennzeichen: Nutzung eines Satzes von b Ziffern für beliebige Zahlen (b Basis) Wertigkeit einer Ziffer ergibt sich aus ihrer Position Wertigkeit steigt in der Regel von rechts nach links an Zahl = an × b n + an-1 × b n-1 !a1 × b + a0 , ai Î Ziffernsat z n Zahl = å ai bi = (an an-1 ! a1a0 )Basis b i =0 Wichtige Beispiele: Dezimalsystem (b=10), Duodezimalsystem (b=12), Dualsystem (Binärsystem, b=2), Hexadezimalsystem (b=16), Oktalsystem (b=8) Prof. Dr. Volker Blanz 4.5 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme... Beispiel: Dezimalsystem Ziffern: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 104 103 102 101 100 5 6 3 8 6 5638610 = 10 4 × 5 + 103 × 6 + 10 2 × 3 + 101 × 8 + 10 0 × 6 Beispiel: Binärsystem Ziffern: 0, 1 24 23 22 21 20 1 0 1 1 0 101102 = 24 ×1 + 23 × 0 + 22 ×1 + 21 ×1 + 20 × 0 = 2210 Prof. Dr. Volker Blanz 4.6 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme... Beispiel: Oktalsystem Ziffern: 0, 1, 2, 3, 4, 5, 6, 7 84 83 82 81 80 7 3 2 6 7 732678 = 84 × 7 + 83 × 3 + 82 × 2 + 81 × 6 + 80 × 7 = 3039110 Beispiel: Hexadezimalsystem Ziffern: 0,... , 9, A(10), B(11), C(12), D(13), E(14), F(15) 164 163 162 161 160 A 9 5 F F A95 FF16 = 16 4 × A + 163 × 9 + 16 2 × 5 + 161 × F + 160 × F = 69375910 Prof. Dr. Volker Blanz 4.7 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme... Motivation: Wozu andere Stellenwertsysteme? Dezimalsystem ungeeignet für elektronische Rechner Rechner stellt nur zwei Zustände dar (Bit): Spannung liegt an oder nicht Bauteile für zwei Zustände sind einfach, günstig, robust und platzsparend realisierbar Bezug zu Aussagenlogik: 0 = false, 1 = true ⇒Operationen wie ,≥, ≠,... sind direkt integrierbar Theoretisch: Mehr Zustände unterscheidbar ⇒ Aber: Bereits kleine Spannungsschwankungen führen dann zu falschen Ergebnissen 2 Zustände: 50% Spannungsschwankung→Fehler 10 Zustände: 5% Spannungsschwankung→Fehler 1 9 0 0 Prof. Dr. Volker Blanz 4.8 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme... Oktal- und Hexadezimalsystem: Warum sind diese von Bedeutung? Basen 8 und 16 sind 2er-Potenzen ⇒Umrechnungen zwischen diesen Systemen besonders einfach Darstellungen von Binärdateien im Oktal- oder Hexadezimalsystem sind deutlich kompakter & lesbarer Beispiel: Vergleichen Sie folgende Zahlenpaare 1110101111011001110111011111110101112 1110101111011001110111101111110101112 7275473577278 7275473677278 EBD9 DDFD716 EBD9 DEFD716 Prof. Dr. Volker Blanz 4.9 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme... Umrechnung: Dezimal→Binär Vorüberlegung: Wie erfolgt die Umrechnung Binär nach Dezimal ? 10110 2 = 1⋅ 2 4 + 0 ⋅ 2 3 +1⋅ 2 2 +1⋅ 21 + 0 ⋅ 2 0 = 16 + 4 + 2 = 2210 oder wahlweise auch umgeformt in das folgenden Schema: = (1⋅ 2 3 + 0 ⋅ 2 2 +1⋅ 21 +1) ⋅ 2 + 0 d.h. 22 = (11) ⋅ 2 + 0 ( ) = (1⋅ 2 2 + 0 ⋅ 21 +1) ⋅ 2 +1 ⋅ 2 + 0 = (( 5) ⋅ 2 +1) ⋅ 2 + 0 = (((1⋅ 2 + 0) ⋅ 2 +1) ⋅ 2 +1) ⋅ 2 + 0 = (((2) ⋅ 2 +1) ⋅ 2 +1) ⋅ 2 + 0 = ((((1)⋅ 2 + 0) ⋅ 2 +1) ⋅ 2 +1) ⋅ 2 + 0 Also: eine Abfolge von Operationen „mal 2 plus Rest 0 oder 1“. Der als letztes addierte Rest sind die Einer-Stellen 20. Die Umkehrung erfolgt dann durch eine Abfolge von Operationen „Dividiere durch 2 mit Rest“. Der als erstes verbleibende Rest sind die Einer, der als letztes verbleibende Rest bezeichnet das höchstwertige Bit. Prof. Dr. Volker Blanz 4.10 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme... Umrechnung: Dezimal→Binär Vorgehen: Division mit Rest (Modulo-Rechnung) Beispiel: 2210 = ?2 22 : 2 = 11 Rest 0 11 : 2 = 5 Rest 1 5 : 2 = 2 Rest 1 2 : 2 = 1 Rest 0 1 : 2 = 0 Rest 1 Þ 2210 = 101102 Vorsicht: Reihenfolge der Ziffern im Ergebnis wird oft falsch angenommen! Der Rest der ersten Division bezeichnet die Einer, steht also ganz rechts ! Vorsicht: Einstieg und Ausstieg in das Schema: Am Anfang erst dividieren, dann Rest bilden oder umgekehrt (letzteres), was passiert am Schluss mit einer 2? Rest 0 und fertig oder noch ein nächsthöheres Bit setzen (letzteres). In der Informatik ist immer der Ein- und Ausstieg in Schleifen eine Fehlerquelle. Prof. Dr. Volker Blanz 4.11 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  Einschub 1: Modulo Modulo-Funktion, Gleichheit “modulo” n 21 = 2 ⋅ 8 + 5 21 = 2 ⋅ 8 Rest 5 21mod8 = 5 Allgemein: a mod n = b genau dann, wenn gilt: Es existiert eine natürliche Zahl c, sodass a = c ⋅ n + b, 0 ≤ b < n Insbesondere: a mod n = 0 genau dann, wenn a ein Vielfaches von n ist. Gleichheit modulo n: Es ist (21 = 5)mod 8 Allgemein: ( p = q )mod n genau dann, wenn (p mod n) = (q mod n) dann gilt: (p – q )mod n = 0, also: p - q ist Vielfaches von n. Prof. Dr. Volker Blanz 4.12 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  Einschub 2: Summen von Potenzen Bemerkung zu Binären Zahlen: Allgemein gilt die Geometrische Summenformel (Beweis z.B. durch Induktion oder einen einfachen Trick...) n b n+1 −1 ∑b i = b −1 i=0 Insbesondere für b=2: n ∑2 i = 2 n+1 −1 i=0 n ∑2 i +1 = 2 n+1 i=0 11112 +1 = 10000 2 Prof. Dr. Volker Blanz 4.13 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme... Addition Binärer Zahlen Vorgehen: Stellenweise Addition, beginnend mit niedrigster Stelle, mit Übertrag Beispiel: 101102 + 101002 10110 + 10100 1- 1 - -- Übertrag = 101010 Prof. Dr. Volker Blanz 4.14 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme... Multiplikation Binärer Zahlen Vorgehen: Weiterrücken der Binärstellen, dann Summe der Komponenten Beispiel: 10110 2 ×10100 2 = 10110 2 × (10000 2 + 1002 ) = 10110 2 ×10000 2 + 10110 2 ×1002 10110.100 = 1011000 + 10110.10000=101100000 = 110111000 Das Weiterrücken gilt ganz allgemein bei Multiplikation mit Zahlen der Form 100… , denn ( ) n n x × 1× b = å ai b × b = å ai bi + k = (an an -1 ! a1a0 0! 0)Basis b k i k i =0 i =0 Prof. Dr. Volker Blanz 4.15 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.1 Zahlensysteme... Umrechnung: Hexadezimal Binär Vorgehen: Einfaches Aneinanderreihen bzw. Blockbildung von Binärzahlen Beispiel: A95 FF16 = ?2 A16 = 1010 2 → ⋅16 4 → ⋅ 2 4⋅4 916 = 10012 → ⋅16 3 → ⋅ 2 3⋅4 516 = 01012 → ⋅16 2 → ⋅ 2 2⋅4 F16 = 11112 → ⋅161 → ⋅ 21⋅4 F16 = 11112 → ⋅16 0 → ⋅ 2 0⋅4 Þ A95FF16 = 1010 ! 1001 ! 0101 ! 1111 ! 1111 !2 A 9 5 F F Prof. Dr. Volker Blanz 4.16 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2 Zahlentypen Ziel: Darstellung verschiedener Zahlenarten (natürliche Zahlen, ganze Zahlen, reelle Zahlen,... ) und Umsetzung von Operationen (Addition) Zahlentypen sind eingeschränkte Darstellungen von Zahlenarten: fixe Anzahl von N Bits, d.h. nur 2N Werte darstellbar ⇒ einschränkter Wertebereiche und endliche viele Zahlenwerte ⇒ nicht alle Zahlen sind im Rechner darstellbar Zahlentyp entscheidet über die Interpretation von Werten (Zahlenart), die Genauigkeit der Darstellung und die minimale und maximale darstellbare Zahl Prof. Dr. Volker Blanz 4.17 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen Natürliche Zahlen Repräsentation im Binärsystem (s.o.) übliche Längen N: 16, 32 oder 64 bits Typename in C/C++: unsigned int: 32 bit (unsigned=vorzeichenlos, integer=Ganzzahl) unsigned short: 16 bit unsigned long: 64 bit Wertebereich: 0,... , 2N−1 Ganze Zahlen Typename in C/C++: int, short, long (gleiche Anzahl bits wie oben) Wertebereich: Hängt von der konkreten Repräsentation ab Beachte: Zur Wahl des optimalen Typs muss stets Wertebereich und Speicherplatz/Geschwindigkeit abgewogen werden. Prof. Dr. Volker Blanz 4.18 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Vorzeichen-Betrag Darstellung ,,Naiver“ Ansatz: Höchstwertiges Bit bestimmt Vorzeichen (0 positiv, 1 negativ) Restliche Bits werden zur Codierung des Betrags verwendet Probleme: Darstellung nicht eindeutig wegen der doppelt repräsentierten Null (+0,−0) Aufwändige Umsetzung der Addition Beispiel: 000 111 001 -3 0 = 1 610 01102 110 -2 2 010 - 610 = 1110VZB -1 3 -0 101 011 100 Zahlenkreis für 3 Bits VZB=vorzeichenbehaftet 111VZB = -(112 ) = -(2 + 1) = -3 Prof. Dr. Volker Blanz 4.19 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Vorzeichen-Betrag Darstellung Bei gesetztem (negativem) Vorzeichenbit wird von den übrigen Stellen in die negative Richtung gezählt. 0 000VZB 0 111VZB 1 111VZB 1 000VZB -7 0 710 (0 ist doppelt repräsentiert) Prof. Dr. Volker Blanz 4.20 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Addition und Subtraktion bei Vorzeichen-Betrag Addition: 1. beide Zahlen haben dasselbe Vorzeichen ⇒ Bitweise Addition der nachfolgenden Bits, VZ-Bit bleibt, (Overflow der nachfolgenden Bits wird ignoriert und liefert dann einen Fehler) 2. beide Zahlen haben unterschiedliche Vorzeichen ⇒ Bitweise Subtraktion der Beträge, VZ von betragsgrößerer Zahl Subtraktion: Addition mit der Gegenzahl, z.B. 5 − 7 = 5 + (−7) Beispiele mit 3 Wert-Bits 5 0101 −3 1011 -5 1101 -5 1101 + 2 + 0010 + −4 + 1100 + 2 + 0010 - 2 + 1010 7 0111 −7 1111VZB=-7 -3 1011 -7 1111 VZ bleibt VZ der -5-2=-5+(-2) 101+010=111 betragsgrößeren 101+010=111 Zahl. 101-010=011. Nachteil: Die Addition bei unterschiedlichen VZ erfordert eine (ungünstige) Fallunterscheidung Prof. Dr. Volker Blanz 4.21 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Zweierkomplement Gebräuchliche Darstellung ganzer Zahlen Typename in C/C++: int (32 bit), short (16 bit), long (64 bit) Darstellung für N = n + 1 bits bn bn-1 !b1 b0 n-1 Zahl = -bn × 2 + bn-1 × 2 + ! + b1 × 2 + b0 = -bn × 2 + å bi × 2i n n-1 n i =0 n -1 ⇒ bn = 1 ⇔negative Zahl, da 2 n > å 2i 000 i =0 111 001 ⇒ die Zahlen sind modulo 2n+1 kontinuierlich -1 0 1 aufgetragen. a mod b = Rest bei ganzzahliger Division a/b. 110 -2 2 010 -3 3 Hinweis: Für ganze Zahlen a, b ∈ ℤ gilt -4 101 011 100 ( a = b)mod N ⇔ ( a − b) mod N = 0 Zahlenkreis für 3 Bits bzw. a/N und b/N haben denselben positiven 111VZB = -4 + (112 ) = -4 + 3 = -1 Rest, z.B. (12 = 4) mod 8 110VZB = -4 + (10 2 ) = -4 + 2 = -2 (3 + 1) = 4 = −4 mod 8 100VZB = -4 + (00 2 ) = -4 + 0 = -4 Prof. Dr. Volker Blanz 4.22 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Zweierkomplement-Darstellung Das Vorzeichenbit verschiebt die Skala der übrigen Bits durch Subtraktion statt Addition von 2n um 2n+1 ins Negative. 0 0002erK 0 1112erK 1 0002erK 1 1112erK 1 0002erK 1 1112erK -8 -1 0 710 -16 Prof. Dr. Volker Blanz 4.23 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Vorzeichenwechsel durch Zweierkomplement Gegeben eine Zahl z, wie bekomme ich –z innerhalb der Zweierkomplementdarstellung ? Regel: Invertiere Zahl bitweise ( Schreibweise: a → a ) und addiere 1, z.B. 610 = 0110 2 Überprüfung : (- -6 = 6) - 610 = 01102 + 12 - 10102er-K = 10102 + 12 = 10012 + 12 = 01012 + 12 = 1010 2 er-K = 0110 2 = 610 Begründung: Sei z2 er-K = bn bn-1 !b1 b0 , dann z2 er-K + z2 er-K = 11%112 er-K = -2n + 2n-1 + % + 2 + 1 = -1 $!!#!! " =2n -1 z2er−K = −z2er−K −1 Þ - z2er-K = z2er-K + 1 Prof. Dr. Volker Blanz 4.24 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Addition und Subtraktion bei Zweierkomplement Addition: Bitweise (Overflow beim Vorzeichenbit bei zwei negativen Zahlen wird ignoriert und liefert dennoch richtiges Ergebnis, solange Wertebereich {-8,..., 7} nicht überschritten.) Subtraktion: Rückführung auf Addition der negativen Zahl 1. Negation der zweiten Zahl mittels Zweierkomplement+1 2. Addieren: Erste Zahl mit Zweierkomplement der zweiten Zahl Beispiele mit N = 4, n = 3 Bits 5 0101 −3 1101 -5 1011 -5 1011 + 2 + 0010 + −4 + 1100 + 2 + 0010 - 2 + 1110 7 0111 −7 10012er-K= -7 -3 1101 -7 1001 -10012er-K = 01102er-K +1 =01112er-K= 7 Bemerkung: Addition und Subtraktion bauen nur auf bitweiser Addition und Komplementbildung auf und benötigen keine Fallunterscheidung Zweierkomplementdarstellung hat keine mehrdeutige Null Prof. Dr. Volker Blanz 4.25 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Addition negativer Zahlen im Zweierkomplement Beobachtung: bei 2 negativen Zahlen sind jeweils die führenden bits gesetzt, also entsteht in der Summe immer ein overflow über die erlaubte Bit-Anzahl hinaus. Rechenregel: ignoriere dies, das overflow-bit läuft ins Leere. Beispiel 1: (-410) + (-410) = 11002erKompl + 11002erKompl = 1 10002erKompl = 10002erKompl = (-810) Beispiel 2: (-810) + (-810) = 10002erKompl + 10002erKompl = 1 00002erKompl = 00002erKompl = (010)... also falsch, da -16 ausserhalb des Wertebereiches liegt. Aber immerhin richtig modulo 16, also nicht ganz sinnlos: (0 = -16) mod 16 Also: bei negativen Zahlen, deren Summe nicht aus dem Wertebereich führt, sind die nicht-führenden, also positiv gezähten Bits zusammen so groß, dass sie in der Summe im führenden Bit eine 1 hervorrufen und damit wieder (richtigerweise) eine negative Zahl ergeben. Prof. Dr. Volker Blanz 4.26 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Addition von Zahlen im Zweierkomplement Auch bei nicht-negativen Zahlen kann ein overflow auftreten, und zwar: vom führenden Bit ins Leere, von den übrigen Bits ins führende Bit. Dabei gilt aber: die nicht-führenden Bits zeigen immer ins Positive -> Richtung stimmt immer modulo 2n+1 ist das Ergebnis nie falsch also: Sofern die Rechnung nicht ohnehin aus dem Wertebereich führt, bleibt sie korrekt. Prof. Dr. Volker Blanz 4.27 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Biased-Notation 00..0 repräsentiert die kleinstmögliche Zahl, 11..1 die größtmögliche Auf jede Zahl wird die sogenannte Magic Number addiert und das Ergebnis binär dargestellt. Beispiel: 8-bit Zahl (N = 8), Magic Number: 127 Zahl Berechnung Biased Notation der Binärdarstellung Kleinste -127 -127+127=0 00000000biased Zahl Größte Zahl 128 128+127=255 11111111biased Null: 0 0+127=127 01111111biased Vorteil: Größenvergleiche können bitweise durchgeführt werden Problem: Mathematische Operationen können nicht mehr direkt durchgeführt werden Prof. Dr. Volker Blanz 4.28 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.1 Repräsentation von Ganzen Zahlen... Biased Notation Der gesamte Zahlenbereich wird um die Magic Number verschoben. Bei einer 4bit Zahl wäre die Magic Number 7 ( = Mitte des Zahlenbereiches 0-16). Dann folgende Situation: 0000 0111 1111 -7 0000 Bias 0111 Bias 1000 Bias 1111 Bias -7 0 1 810 1510 Prof. Dr. Volker Blanz 4.29 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.2 Repräsentation von Gleitkommazahlen Gleitkommazahlen Bezeichnungen: float Länge: 32 Bit =4 Byte (auch 16 Bit half oder 64 Bit double) Wertebereich: Siehe folgende Folien Definiert im IEEE 754 Standard Beachte: Operationen auf Gleitkommazahlen sind wesentlich aufwändiger und damit langsamer als für ganze Zahlen Grundsätzliche Idee Verwendung der wissenschaftlichen Schreibweise (Scientific notation) Beispiele im Dezimalsystem: 1214.31 = 1$ " ×10.21431 ! #! 3¬ Exponent Mantisse 0.0213178 = 2.13178 ×10 -2 Prof. Dr. Volker Blanz 4.30 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.2 Repräsentation von Gleitkommazahlen... Wissenschaftliche Notation im Dezimalsystem: Nach welcher Regel ist der Exponent zu wählen? 0.0213178 = 0.213178 ×10 -1 = 2.13178 ×10 -2 = 21.3178 ×10 -3 Regel: Wähle Exponenten so, dass für die Mantisse m gilt: 1 £ m < 10 10 0 £ m < 101 Exponentialdarstellung bezüglich der Basis 2: 4.810 = 1.210 × 2 2 = (1.0011...2 ) × 2 2 = m × 2e Dabei gilt für die Mantisse nun 1£ m < 2 Beobachtung: In der Binärdarstellung von m ist damit das erste (Einer-)Bit immer gesetzt. Prof. Dr. Volker Blanz 4.31 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  Einschub: Binäre Kommazahlen Verwende Zweierpotenzen auch mit negativem Exponenten 22 21 20 2-1 2-2 2-3 2-4 1 0 1. 1 0 0 1 2 = 4 + 1 + 0.5 + 0.0625 = 5.5625 20 = 1, 2-1=1/2=0.5 2-2 = ¼ =0.25 2-3 = 1/8 = 0.125... Insbesondere sind Zahlen der Form 1.xxxxxx 2 immer in [1,2[ und 0.xxxxxx 2 immer in [0,1[, da für die Zahl 1.11111...2 gilt: ) +,) & " -& $-& ∑%"#$ = * ) → ) = 2 wenn 0 → ∞. ' -& -* * Prof. Dr. Volker Blanz Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.2 Repräsentation von Gleitkommazahlen... Gleitkommazahl-Repräsentation (IEEE 754) Aufbau: 1 Bit Vorzeichen (s), 8 Bit Exponent (e), 23 Bit Mantisse (m) Vorzeichen: 0 positiv, 1 negativ Exponent: Biased Notation mit Magic Number 127 (Hinweis: Im Lehrbuch [Ernst] steht hier fälschlicherweise 128) Mantisse: Im Dualsystem immer zwischen 1 und 2, also erstes Bit immer gesetzt. ⇒Stelle vor dem Komma ist immer 1, kann also weggelassen werden Dargestellte Gleitkommazahl: (- 1)s × (1.0 + m)× 2e-127. Prof. Dr. Volker Blanz 4.33 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.2 Repräsentation von Gleitkommazahlen... Konvertierung einer Gleitkommazahl nach IEEE 754 Gegeben: Gleitkommazahl der Form ± ( g10 + r10 ) mit : g10 ∈ ℕ ;r10 ∈ ℝ , 0 ≤ r10 < 1. Am Beispiel von 25.421875 : g10 = 25, r10 = 0.421875, Vorzeichen s = 0 1. Bilde g10 auf einen binären Wert g2 ab: 2510 = 110012 2. Bilde r10 auf einen binären Wert r2 ab (s.u): 0.42187510 = 0.0110112 3. Bilde vorläufige Mantisse m = g2 + r2 m = 110012 + 0.0110112 = 11001.0110112 4. Forme m in wissenschaftliche Schreibweise um m = 11001.0110112 = 1.1001011011 × 24 (e = 4) 5. Endgültige Mantisse durch Weglassen der ersten 1:m = 1001011011 6. Endgütliger Exponent durch Addieren von 127 e = 410 + 12710 = 1002 + 011111112 = 10000011biased Prof. Dr. Volker Blanz 4.34 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.2 Repräsentation von Gleitkommazahlen... Gesamtergebnis 25.42187510 = 0 10000011 1001011011 0000000000 000IEEE 754 Umwandlung von Nachkommastellen (Dezimal→Binär) Beispiel: 0.42187510 (Nachkommazahl von oben) Achtung: Direkte Umwandlung von 42187510 in Dualsystem und Interpretation als Nachkommawert ist falsch! Beobachtung: Multiplikation mit Basis bringt Nachkommastelle vor Komma: Zunächst rein dezimal:.10.10 0.42187510 ® 4.2187510 ; 0.2187510 ® 2.187510 Dies gilt auch für Multiplikation mit anderer Basis, hier 2: 0.421875 nach Binär:.2.2 0.421875 ® 0.84375 0.375 ® 0.75.2.2 0.84375 ® 1.6875 0.75 ® 1.5.2.2 0.6875 ® 1.375 0.5 ® 1.0 0.0110112 Prof. Dr. Volker Blanz 4.35 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.2 Repräsentation von Gleitkommazahlen... Kleine Zahlen in Gleitkomma-Repräsentation Problem: Die Zahl 0 ist wegen (1+m) Konvention nicht darstellbar ! Zur Mantisse wird ja immer noch die Vorkomma-Eins hinzuaddiert. Die Zahl 0 00000000 0000000000 0000000000 000 IEEE 754 = +1.0 × 2 -127 > 0 wäre damit die betragsmäßig kleinste darstellbare Zahl. Ausserdem kann man noch kleinere Zahlen nahe 0 darstellen, wenn man Mantissen wie 0.00000001 zulässt. Daher: Konvention: Die Mantissen-Regel (1+m) gilt nur für e>00000000, also bis 0 00000001 0000000000 0000000000 000 IEEE 754 = +1.0 × 2 -126 Für e=00000000 wird zu der Mantisse eine 0 als Vorkommastelle hinzugefügt, es können also Mantissen 0.m gebildet werden, z.B. 0.0000000001. Der Exponent bleibt -126, um eine Lücke zu verhindern 0 00000000 1111111111 1111111111 111IEEE 754 = +0.999 × 2 -126 0 00000000 0000000000 0000000000 001IEEE 754 = +2 -23 × 2 -126 = 2 -149 0 00000000 0000000000 0000000000 000 IEEE 754 = +0.0 × 2 -126 = 0 Prof. Dr. Volker Blanz 4.36 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.2.2 Repräsentation von Gleitkommazahlen... Darstellbare Werte in IEEE 754: Weitere Ziele: Erhöhung der Darstellungsgenauigkeit nahe 0 1 Codierung von Sonderfällen wie ∞ (unendlich) oder (Div. durch 0) 0 Normalisierte Gleitkommazahlen: Codierung wie zunächst (vor der vorigen Folie) vorgestellt Denormalisierte Zahl: Bei e = 0 wird statt 1.m 2−127 kodiert: 0.m 2−126 ⇒höhere Genauigkeit bei kleinen Zahlen, 0 wird darstellbar. S Exponent Mantisse Bedeutung 0/1 000000002 0..002 +/ − 0 (Null) * 000000012 bis 111111102 beliebig normalisierte Gleitkommazahl * 111111102 1..112 Größte darstellbare Zahl (3.4 · 1038) * 000000002 0..12 Kleinste darstellbare Zahl (2−149=1.4 · 10−45) 0/1 111111112 0..002 +/− unendlich * 111111112 ≠ 0..002 NaN (Not a Number) * 000000002 ≠ 0..002 denormalisierte Gleitkommazahl Prof. Dr. Volker Blanz 4.37 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.3 Zeichen-Codierung ASCII: American Standard Code for Information Interchange Ziel: Standardisierter Zeichensatz zum Austausch von Text Zuordnung von Zeichen der Schriftsprache zu Binärzahlen ⇒Nur so können Computer Zeichen kodieren! Ansatz: Basiert auf lateinischem Alphabet und arabischen Zahlen mind. 62 Standard-Zeichen (0-9, a-z, A-Z) plus Sonderzeichen ⇒mind. 7 bit notwendig (128 Zeichen) Alternative Zeichensätze, z.B. ISCII (Indisch) oder ISO8859 (15 verschiedenen Codierungen zur Abdeckung aller europäischen Zeichen und Thai) Prof. Dr. Volker Blanz 4.38 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.3 Zeichen-Codierung … ASCII (Forts.) NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US SP ! “ # $ % & ’ ( ) * + , -. / 0 1 2 3 4 5 6 7 8 9 : ; ¡ = ? ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ‘ a b c d e f g h i j k l m n o p q r s t u v w x y z { — } ~ DEL Tabelle 1: ASCII Tabelle Der ASCII Code ergibt sich durch Durchzählen in der Tabelle: ‚NUL‘=0, ‚ A‘ = 65... Erste 32 Codes: Steuerzeichen wie Leerzeichen (SP = space = 32) oder Glocke (BEL=bell) Viele der Steuerzeichen sind nicht-druckbar und historisch bedingt (z.B. Steuerung von Druckern) Prof. Dr. Volker Blanz 4.39 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.3 Zeichen-Codierung … Unicode und UTF Unicode: Legt einheitliche Codes für alle sinntragenden Zeichen aller Kulturen fest UTF (Unicode Transformation Format): bildet Unicode auf Codes unterschiedlicher Länge ab häufige Zeichen erhalten kurze Codes ASCII-Zeichen in UTF-8: Führende 0 und 7 bit umfassen ASCIIZeichen Beispiel: A = 1000001ASCII = 01000001UTF 8 Textspeicherung als Zeichenketten (Folge von Zeichen) Prof. Dr. Volker Blanz 4.40 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4 Informations-Codierung Wozu beschäftigen wir uns mit Information? Grundsätzlich: Die Übertragung und Speicherung von Daten erfordert Effizienz Beispiele: in deutschen Texten sind die Buchstaben ,,e“ und ,,s“ häufiger benötigt als andere⇒kurzer Morse-Code in einem einfarbigen Bild steckt im Grunde keine Information Fragestellung: Wie läßt sich daraus Nutzen ziehen, um Daten kompakt darzustellen (zu komprimieren)? Komprimierungsarten: Verlustfrei: Ursprüngliche Daten lassen sich vollständig wieder herstellen (wichtig z.B. bei Text) Verlustbehaftet: Ursprüngliche Daten lassen sich nur unvollständig wieder herstellen (z.B. bei Bildern: jpeg) Prof. Dr. Volker Blanz 4.41 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4 Einschub: Morsealphabet A ·− B −··· C −·−· D −·· E · F ··−· G −−· H ···· I ·· J ·−−− K −·− L ·−·· M −− N −· O −−− P ·−−· Q −−·− R ·−· S ··· T − U ··− V ···− W ·−− X −··− Y −·−− Z −−·· Prof. Dr. Volker Blanz 4.42 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4 Informations-Codierung … Zum Begriff ”Information“ Von verschiedenen Wissenschaften (Informatik, Informationstheorie, Semiotik,... ) unterschiedlich definiert Allgemein: Potenziell oder tatsächlich vorhandenes nutzbares oder genutztes Wissen Wesentlich sind Wiedererkennbarkeit und Neuigkeitsgehalt (in Bezug auf einen festgelegten vorhergehenden Wissensstand) Information ist für einen Betrachter in einem bestimmten Kontext von Bedeutung und verändert dessen inneren Zustand (beim Menschen: dessen Wissen) Vgl. Datum: Quasi ,,Einheit von Information, jedoch selbst keine Information, sondern ,,Informationsträger“ (Zeichen), Beispiel: ’xxxxxxxxxx’ = ,,10 Zeichen Daten“ aber dennoch möglicherweise ,,keine Information“ Prof. Dr. Volker Blanz 4.43 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.1 Information und Wahrscheinlichkeit Wichtige Begriffe Alphabet A: Besteht aus einer abzählbaren Menge von Zeichen...... und einer Ordnungsrelation ( = feste Reihenfolge, wird im Folgenden nicht benötigt) Üblicherweise endlicher Zeichenvorrat Beispiel: A = {a, b, c,... z} (Menge aller Kleinbuchstaben in alphabetischer Ordnung) A = {0, 1, 2,... 9} (Menge der ganzen Zahlen 0 bis 9 mit der ,,≤“ Relation ) Nachricht: Besteht aus Sequenz beliebiger Länge von Elementen von A Länge einer Nachricht X: |X| = Anzahl der Zeichen in X Alle Nachrichten einer fester Länge n: An = {X : |X| = n} Nachrichtenraum A*: Menge aller Nachrichten über A : A* = ! n An Prof. Dr. Volker Blanz 4.44 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.1 Information und Wahrscheinlichkeit … Shannon’scher Informationsbegriff (Claude Shannon, 1950) Ausgangspunkte: Eine Nachricht X = x1 x2 x3 ! xk Î A* Auftrittswahrscheinlichkeit eines Zeichens a ∈ A in X: Häufigkeit von a in X p X (a ) = Î [0,1], å p (a ) = 1 X Länge von X aÎX Shannons Informationsbegriff: Axiome für den zu definierenden Informationsgehalt IX(a) IX(a) groß, falls pX(a) klein, d.h. IX(a) ↑↓ pX(a) 100%-ige Auftrittswahrscheinlichkeit hat keine Information (,,weißes Bild“): p X (a ) = 1 Þ I X (a ) = 0 Informationsgehalt der Nachricht X : I ( X ) = å aÎX I X (a ) Konkrete Funktion für den Informationsgehalt: 1 I X (a ) = log 2 = - log 2 p X (a ) p X (a ) Prof. Dr. Volker Blanz 4.45 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.1 Information und Wahrscheinlichkeit … Shannon’scher Informationsbegriff: Hintergrund Gegeben die Häufigkeitsverteilung, wie viele Ja-Nein Fragen muss ich stellen, um an einer gegebenen Stelle im Text das nächste Zeichen zu erfragen? Fall 1: p X (a ) = 1 Þ I X (a ) = 0 0 Fragen, da von vornherein klar ist, dass auch das nächste Zeichen wieder ein a ist. 1 Fall 2: Gleichverteilung, jeder Buchstabe ist gleich häufig. pX ( a1 ) = pX ( a2 ) = Mit jeder Ja-Nein Frage kann ich die Zahl der A verbleibenden Möglichkeiten halbieren („erste Hälfte oder zweite Hälfte des Alphabets?“ usw.) wie beim Intervallhalbierungsverfahren aus der Mathematik. Mit k Fragen kann ich 2k Buchstaben unterscheiden, umgekehrt ergibt sich daher 1 I X ( a ) = log 2 ( A ) = log 2 = − log 2 pX ( a ) pX ( a ) Fall 3: Ungleiche, nicht-triviale Häufigkeitsverteilung. Hier gibt die Formel die zu erwartende Zahl von Fragen an, wenn man optimal fragt, indem man immer Fragen mit 50-50 Wahrscheinlichkeiten stellt, etwa am Anfang „Vokal oder Konsonant?“. Prof. Dr. Volker Blanz 4.46 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.1 Information und Wahrscheinlichkeit … Entropie Ausgangspunkt: Eine Nachricht X = x1 x2 x3 ! xk Î A* Bekannt: Statistischer Informationsgehalt IX(a) aller Zeichen von A Mittlerer Informationsgehalt (Entropie) der Nachricht X: ( ) H ( X ) = å I X (a )× pX (a ) = -å log2 pX (a ) × pX (a ) aÎA aÎA H entspricht der theoretischen Untergrenze von Bit pro Zeichen zur Codierung der Nachricht X Beachte: Nicht die Abfolge, sondern nur die Häufigkeit der Zeichen wird verwendet ⇒ ,,geschickte Codierung kann mit weniger als H Bits auskommen Etwa durch Codierung nicht auf Buchstaben- sondern auf Wortebene, wenn manche Worte oft in der Nachricht auftauchen. Hintergrund des Mittleren Informationsgehalts: Dies ist die zu statistisch zu erwartende Anzahl der ja-nein Fragen, die man stellen muss, um ein Zeichen xi in X zu erhalten, wenn man die Wahrscheinlichkeiten kennt und mit dieser Kenntnis optimal fragt. Da wir noch nicht wissen, welcher Buchstabe folgt, gewichten wir jedes IX(a) mit der Wahrscheinlichkeit, dass dieser Buchstabe auftritt: ein sogenannter Erwartungwert. Prof. Dr. Volker Blanz 4.47 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.1 Information und Wahrscheinlichkeit … Beispiel: Nachricht: AABBDCDDAD Alphabet: {A,B,C,D} Absolute Häufigkeiten: {3, 2, 1, 4} ì3 2 1 4ü Relative Häufigkeiten: í , , , ý î10 10 10 10 þ æ æ3ö 3 æ2ö 2 æ1ö 1 æ4ö 4ö H = -ç log 2 ç ÷ × + log 2 ç ÷ × + log 2 ç ÷ × + log 2 ç ÷ × ÷ » 1.85 è è 10 ø 10 è 10 ø 10 è 10 ø 10 è 10 ø 10 ø ⇒ Codierung eines Zeichens erfordert (theoretisch) mind. 1.85 Bit ⇒ Codierung der Nachricht (10 Zeichen) erfordert (theoretisch) mind. 10 * 1.85 = 18.5 Bit Weitere Beispiele: Rel. Häufigkeiten: {1,0,0,0} H = -(log 2 (1) ×1 + 3 × log 2 (0) × 0) = 0 æ ö ì1 1 1 1 ü ç æ1ö 1÷ Rel. Häufigkeiten:í , , , ý H = -ç 4 × log 2 ç ÷ × ÷ = 2 î4 4 4 4þ ç $ !#è! 4ø 4÷ " è = -2 ø Prof. Dr. Volker Blanz 4.48 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.2 Runlength-Encoding Ziel: Sehr einfacher, verlustfreier Kompressionsalgorithmus Ansatz: Verkürzte Sequenz für wiederholte Zeichen durch Speicherung ihrer Anzahl Beispiel: Alphabet A = {S,W} (schwarz-weiss in einem Bild) Vor der Anwendung: SSSSSSSSSSWSSSSSSSSSSWW Nach RLE: 10SW10S2W Probleme: Codierung der Wiederholzahl, wenn Zahlen selbst Teil des Alphabets sind Kontrollzeichen (Escape-Sequenz): Verwendung eines Sondersymbols (Escape-Zeichen), z.B. ’\’; Beispiel: \7 steht für Wiederholzahl 7 \\ steht für Zeichen \ Prof. Dr. Volker Blanz 4.49 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Vorüberlegungen: Morsealphabet A ·− B −··· Grundidee: Häufige Buchstaben bekommen kurzen Code. C −·−· D −·· E · TEST = -.... - F ··−· G −−· H ···· Versuch: Übersetzung in einen Binärcode:. = 0 und - =1 I J ·· ·−−− T E S T = 100001 K −·− L M ·−·· −− Es fehlt die Trennung zwischen den Zeichen. N −· Beachte die Pausen beim Morsen! O −−− P ·−−· Q −−·− -....- könnte z.B. auch gelesen werden als R S ·−· ··· D U T − U V ··− ···− Eindeutigkeit wird erreicht durch die W ·−− Fano-Bedingung (die beim Morsealphabet nicht gilt): X −··− Y −·−− Kein Wort des Codes darf Anfang eines anderen Wortes Z −−·· des selben Codes sein. Prof. Dr. Volker Blanz 4.50 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes Huffman-Codierung (David Huffman, 1952) Alternative Bezeichnung: Entropie-Codierung Ziel: Effiziente Codierung von Nachrichten unter Berücksichtigung der Auftrittswahrscheinlichkeiten der Zeichen und der Fano-Bedingung Idee: Verwendung von kurzen Codes für häufiger auftretende Zeichen ⇒Zeichen-Codes mit variabler Länge & abhängig von Nachricht Herausforderung: Fano Bedingung, hier ein weiteres Beispiel einer Mehrdeutigkeit: 3 Zeichen (A,B,C) mit steigender Wahrscheinlichkeit (p(A) < p(B) < p(C)) Ungeschickte Codierung: A = 10, B = 01, C = 0 Nun kann die Zeichenfolge 10010 entweder ABC oder ACA bedeuten Lösung durch Fano-Bedingung: Kein Code für ein Zeichen darf Anfang eines anderen Codes sein. Im Beispiel ist die Codierung für C Anfang der Codierung für B Prof. Dr. Volker Blanz 4.51 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Algorithmus: Huffman-Codierung 1. Sortiere Zeichen aufsteigend nach ihrer Wahrscheinlichkeit 2. Zusammenfassung der beiden Zeichen mit der geringsten Wahrscheinlichkeit Vergabe von (zusätzlichen) Bits für beide Zeichen Addition der Wahrscheinlichkeiten beider Zeichen 3. Wiederhole die Schritte, bis sich nur noch ein Zeichen in der Sortierung befindet Beispiel: Nachricht ,,HAAAALLO“ Z p Code Z p C Z p C Z p Code Entropie: 1.75 (bit/Zeichen) H 1/8 - H 0 H 00 H 000 Codierung der Nachricht (8 Zeichen): 2/8 Theor. Untergrenze: 14 bit O 1/8 - 0 1 0 4/8 01 0 001 8/8 Tatsächlich: 14 bit L 2/8 - L 2/8 - L 1 L 01 A 4/8 - A 4/8 - A 4/8 - A 1 HAAAALLO = 000 1 1 1 1 01 01 001 = 00011110101001, 14 Zeichen Prof. Dr. Volker Blanz 4.52 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Bemerkungen: Die Zuordnung der Bits 0/1 ist jeweils willkürlich. Ebenso ist es bei gleicher Häufigkeit egal, welche Knoten man als erste verknüpft. Es gibt daher viele Möglichkeiten, den Huffman-Algorithmus auszuführen. Dies zeigt die folgende Folie, die eine andere grafische Darstellung verwendet. Prof. Dr. Volker Blanz 4.53 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Nochmals das Beispiel: “HAAAALLO” 4/8 2/8 1/8 1/8 A L H O Prof. Dr. Volker Blanz 4.54 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Nochmals das Beispiel: “HAAAALLO” 4/8 2/8 2/8 A L 0 1 1/8 1/8 H O Prof. Dr. Volker Blanz 4.55 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Nochmals das Beispiel: “HAAAALLO” 4/8 4/8 A 0 1 2/8 2/8 L 0 1 1/8 1/8 H O Prof. Dr. Volker Blanz 4.56 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Nochmals das Beispiel: “HAAAALLO”. 8/8 0 1 4/8 4/8 A 0 1 2/8 2/8 L 0 1 1/8 1/8 H O A=0 L=10 H=110 O=111 Prof. Dr. Volker Blanz 4.57 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Weiteres Beispiel: “ABCDE” 1/5 1/5 1/5 1/5 1/5 A B C D E Prof. Dr. Volker Blanz 4.58 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Weiteres Beispiel: “ABCDE” 1/5 1/5 1/5 2/5 A B C 0 1 1/5 1/5 D E Prof. Dr. Volker Blanz 4.59 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Weiteres Beispiel: “ABCDE”. Beachte: bei allen 0,1 Ziffern wird es sich um Endziffern handeln. 1/5 2/5 2/5 A 0 1 0 1 1/5 1/5 1/5 1/5 B C D E Wichtig: hier wird ein neuer Baum angelegt, die Buchstaben D, E werden zunächst nicht weiterverfolgt. Also: nicht immer nur an existierenden Baum anbauen! Prof. Dr. Volker Blanz 4.60 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Weiteres Beispiel: “ABCDE”. Das A kann mit B,C oder D,E zusammengefasst werden. 3/5 2/5 0 1 0 1 1/5 1/5 1/5 2/5 D E A 0 1 1/5 1/5 B C Prof. Dr. Volker Blanz 4.61 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … Weiteres Beispiel: “ABCDE”. 5/5 0 1 3/5 2/5 0 1 0 1 1/5 1/5 1/5 2/5 D E A 0 1 1/5 1/5 B C A=00 B=010 C=011 D=10 E=11 Prof. Dr. Volker Blanz 4.62 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes: Falsche Lösung! Falsch wäre: Die (gewichtete) Summe der Zeichenlängen ist höher 5/5 als auf voriger Folie: hier 14/5, dort 12/5. 0 1 1/5 4/5 A 1 0 1/5 3/5 B 0 1 1/5 2/5 C 0 1 1/5 1/5 D E A=0 B=10 C=110 D=1110 E=1111 Prof. Dr. Volker Blanz 4.63 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … 31% 20% 20% 13% 7% 3% 3% 3% E R L N S T I A Prof. Dr. Volker Blanz 4.64 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … 31% 20% 20% 13% 7% 3% 6% E R L N S T 0 1 3% 3% I A Prof. Dr. Volker Blanz 4.65 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … 31% 20% 20% 13% 7% 9% E R L N S 0 1 3% 6% T 0 1 3% 3% I A Prof. Dr. Volker Blanz 4.66 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … 31% 20% 20% 13% 16% E R L N 0 1 7% 9% S 0 1 3% 6% T 0 1 3% 3% I A Prof. Dr. Volker Blanz 4.67 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … 31% 20% 20% 29% E R L 0 1 13% 16% N 0 1 7% 9% S 0 1 3% 6% T 0 1 3% 3% I A Prof. Dr. Volker Blanz 4.68 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … 31% 40% 29% E 0 1 0 1 20% 20% R L 13% 16% N Verschiebe das E 0 1 zum rechten Baum! 7% 9% S 0 1 3% 6% T 0 1 3% 3% I A Prof. Dr. Volker Blanz 4.69 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … 40% 60% 0 1 0 1 20% 20% R L 31% 29% E 0 1 13% 16% N 0 1 7% 9% S 0 1 3% 6% T 0 1 3% 3% I A Prof. Dr. Volker Blanz 4.70 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.4.3 Huffman-Codes … 100% 0 1 40% 60% 0 1 0 1 20% 20% R L 31% 29% E 0 1 13% 16% N 0 1 7% 9% S 0 1 3% 6% T 0 1 3% 3% I A R=00 L=01 E=10 N=110 S=1110 T=11110 I=111110 A=111111 Prof. Dr. Volker Blanz 4.71 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  4.5 Zusammenfassung Wichtige Erkenntnisse und Inhalte dieses Abschnitts: Codierung befasst sich mit der binären Repräsentation ,,beliebiger“ Daten Zahlensysteme der Informatik: Binär (1 Bit), oktal (3 Bits), hexadezimal (4 Bits) Repräsentation von Zahlen im Rechner durch Zahlentypen Einschränkung durch fixe Anzahl Bits: Feste Ober- u. Untergrenze, eingeschränkte Genauigkeit Natürliche Zahlen (unsigned int) mittels Binärsystem Ganze Zahlen mittels Vorzeichen-Betrag, Zweierkomplement (Standard für Ganzzahldarstellung) oder Biased Darstellung Gleitkommazahlen im IEEE-754 Format auf Basis der wissenschaftlichen Schreibweise Repräsentation von Schriftzeichen bzw. Text ASCII Zeichensatz und internat. Erweiterungen (ISO-8859, UTF-8) Informations-Codierung zur Komprimierung von (Text-)Daten Prof. Dr. Volker Blanz 4.72 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  6 Die Programmiersprache C++... Motivation: Ziele dieses Abschnittes ❍ Einführung in C++ als imperative Sprache (Objektorientierung später) ❍ Erläuterung und Übung grundlegender Sprachelemente Herausforderungen: ❍ Vielzahl von Sprachelementen, insb. Zeiger ❍ erfolgreiches Erlernen der Sprache nur durch praktische Übung ❍ Achtung: Wir betrachten keine C-Sprachelemente, die in C++ nicht genutzt werden! Literatur: [Gumm] behandelt nur Java ❍ [Ernst] Kapitel 7.3 zu C und 7.4 zu C++ als Erweiterung von C ❍ [Herold] Kapitel 7.4 und 7.5 ❍ [Deitel] Deitel, H. und P.: C++ How to Program, Pearson Higher Education, 2005 ❍ [Stroustrup] Stroustrup, B.: Die C++ Programmiersprache, Addison- Wesley, 2000 ❍ Online-Tutorials: www.cplusplus.com, www.cppreference.com/ Prof. Dr. Volker Blanz 6.2 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  6 Die Programmiersprache C++... Einleitung C++ ❍ Eine der am weitesten verbreiteten höheren Programmiersprachen ❍ Entwicklung Anfang 80er Jahre unter Leitung von Bjarne Stroustrup bei AT&T ❍ C++ ist eine hybride Programmiersprache und unterstützt u.a.: ❑ Prozedurale (imperative) Programmierung ❑ Maschinennahe Programmierung ❑ Modulare Programmierung ❑ Generische Programmierung (parametrisierte Typen, Templates) ❑ Objektorientierte Programmierung ❍ Basiert auf der Programmiersprache C ❍ Vorlesung Algorithmen und Datenstrukturen: Konzentration auf imperativen Teil von C++ ❍ Objektorientierung: Schwerpunkt in Vorlesung Objektorientierte und Funkt. Programmierung Prof. Dr. Volker Blanz 6.3 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  6.1 Ein einführendes Programmbeispiel Ziele: ❍ Einfaches Programm zum ,,ersten Kennenlernen“ der Sprache C++ ❍ Beispiel: Berechnung der Fakultät einer natürlichen Zahl Definition der Fakultät einer natürlichen Zahl n ∈ ℕ: n Das Produktsymbol P folgt n! := ∏ i =1⋅ 2 ⋅... ⋅ ( n −1) ⋅ n der gleichen Syntax wie das i=1 Summenzeichen S. Hier: Produkt aller i von 1 bis n. Algorithmus zur Berechnung von n! für gegebenes n 1. setze Ergebnis auf 1: result ← 1 2. setze Zählvariable auf 1: i ← 1 3. solange i 0: 2.1. result ← result ・ n 2.2. n ← n – 1 Vorteil: Man spart sich die Variable i. Nachteil: Etwas schwerer lesbar. Algorithmus 3: Nutze n! = n ⋅ ( n −1)! für n > 1, sonst 1. (rekursiver Funktionsaufruf, siehe später) Grundsätzlich gilt: Programmiere so, dass 1. Du selbst und andere den Code schnell (wieder) verstehen 2. Das Risiko eines bugs (Fehlers) minimal ist. Prof. Dr. Volker Blanz 6.5 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  6.1 Ein einführendes Programmbeispiel... Programm zur Berechnung der Fakultät #include int factorial( int n ) { int result = 1; int i; for (i=1; i 3 = 3 10 (=000000112) ❍ 19 ^ 28 = 15 10 (=000011112) ❍ 25 & 28 = 24 10 (=000110002) ❍ ~19 = 236 10 (=111011002) Einsatzbeispiel: Kompakte Beschreibung mehrerer Zustände const int lightOn = 0x01; // Bit 1: Licht ist an const int engineOn = 0x02; // Bit 2: Motor ist an const int heatingOn = 0x04; // Bit 3: Heizung ist an int carState = 0; // Initialer Zustand des Autos: alles aus... carState |= lightOn; // Licht wird eingeschaltet. carState= carState | lightOn;... if ( carState & heatingOn ) {... } // wenn die Heizung an ist, mache... Beachte: Hier zahlt es sich aus, dass alle Werte !=0 als true interpretiert werden. Prof. Dr. Volker Blanz 6.39 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  6.11 Blöcke und Geltungsbereiche Ziel: ❍ Zusammenfassung von Anweisungen, Variablendeklarationen und Typdefinitionen. Ein Block wird syntaktisch als eine einzige Anweisung behandelt. Damit Strukturierte Programmierung ohne goto. ❍ Festlegung des Gültigkeitsbereichs von Variablen, Konstanten, Typen und Funktionen. Syntax eines Blocks: {Blockinhalt} Allgemein: ❍ Variablen, Konstanten, Funktionen und Typen sind nur innerhalb des aktuellen Blocks bekannt und gültig, in dem sie deklariert sind. ❍ Bezeichner müssen innerhalb von Blöcken eindeutig sein! ❍ Alternative Bezeichnung: Scope von Variablen,... Geltungsbereiche: Alles, was außerhalb aller Blöcke steht, ist global, ansonsten lokal im innersten Block, also der unmittelbar umgebenden Blockstruktur Nutzung Variablen Konstanten Funktionen Typen Global sparsamst! möglich Regelfall möglich Lokal Normalfall möglich eingeschränkt möglich Prof. Dr. Volker Blanz 6.40 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  6.11 Blöcke und Geltungsbereiche... Beispiel: Geltungsbereich für Variablen // Deklaration von globalen Variablen und Funktionen unsigned int _count = 2; // führendes ’_’ ist Konvention void doSomething() { float ff; // lokale Variable int count=1; // lokale Variable _count = 12; // ändert globale Variable if ( count > 0 ) { float ff =1; // Achtung: Neue lokale Variable!! unsigned int _count=1; // Achtung: Neue lokale Variable!! _count = 23; // ändert lokale Variable aus diesem Block! ff = 1.1212; // ändert lokale Variable aus diesem Block! } // hier gehen lokale Versionen ff, _count verloren } // hier gehen ff, count verloren Bemerkung: Es ist üblich, Variablennamen (vor allem i, n, x, count, …) in verschiedenen Funktionen immer wieder lokal zu deklarieren. Dagegen sind die im Beispiel gezeigten, neu deklarierten lokalen Variablen ff, count innerhalb des if – Blocks schlechter Programmierstil, da leicht Fehler entstehen können, zum Beispiel wenn die Zeile der Neudeklaration ( float ff=1; ) verloren geht. Mit anderen Worten: Variablennamen können immer wieder neu deklariert und verwendet werden in Blöcken, die nacheinander stehen, aber besser nicht in Blöcken, die ineinander geschachtelt sind. Prof. Dr. Volker Blanz 6.41 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  6.11 Blöcke und Geltungsbereiche... Bemerkung: Codingstyle für C++ Ziel: Einheitliches Erscheinungsbild von Quellcode & gute Lesbarkeit Codingstyle: Eine Konvention mit Regel zur Festlegung von ❍ Bezeichnern für Variablen, Funktionen, Konstanten und Typen ❍ Layout des Quellcodes zur besseren Lesbarkeit Layout des Quelltextes im wesentlichen durch Einrücken der Blöcke bestimmt; häufige Konventionen: Funktions-Dekl.{ Funktions-Dekl. Funktions-Dekl. Blockinhalt { { } Blockinhalt Blockinhalt } } Beachte: Whitespaces (Leerzeichen, Tabulator, Zeilenumbruch) haben, außer bei Präprozessor-Kommandos (beginnend mit #) keinen Einfluss. Namenskonvention für Bezeichner hat zum Ziel ❍ Bezeichnernutzung (global, lokal, Variable, Funktion, Typ, Konstante) wird unmittelbar erkennbar. Z.B.: Kleinbuchstaben für Variablen und Funktionen, Grossbuchstaben für Konstanten, Gross-Kleinschreibung für Typen, “_” für global. ❍ Name gibt unmittelbaren Aufschluss über die Aufgabe der Funktion etc. Prof. Dr. Volker Blanz 6.42 Algorithmen und Datenstrukturen Fachgruppe Medieninformatik  6.11 Blöcke und Geltungsbereiche... Beispiel: Guter und schlechter Codingstyle #include #include unsigned int factorial( unsigned int n ) unsigned int f( { unsigned int Nn ) { unsigned int result = 1; unsigned int Result = 1; for( unsigned int LAUFVARIABLE=Nn; for( unsigned int i=n; i>=1; i-- ) { LAUFVARIABLE >= result = result ∗ i; 1; LAUFVARIABLE-- ) { } Result = Result ∗ LAUFVARIABLE; } return result; return Result;} } int main( int int main( int argc, char ∗ argv[] ) argc, char ∗ ∗ { argv ){ unsigned int n = 10; unsigned int EingabeWert = 10; unsigned int result; unsigned int result; result = factorial(n); result = f(EingabeWert) std::cout