Informatik A - WiederholungVom Lernen und Vergessen Am Ende einer Vorlesung wissen die Studenten...

Informatik A - Wiederholung

Informatik A - Wiederholung

Norbert Fuhr

Informatik A - Wiederholung

Vom Lernen und Vergessen

Am Ende einer Vorlesung wissen die Studenten noch ca. 50%des vorgetragenen StoffesNach einer Woche erinnern sie sich noch an 10-15%Nach drei Monaten ist die Menge des behaltenen Wissenspraktisch nicht mehr messbar

„Sage es mir, und ich vergesse es;zeige es mir, und ich erinnere mich;lass’ es mich tun, und ich behalte es.“(Konfuzius)

Informatik A - WiederholungI Logik

I.1 Aussagenlogik

I.1 Aussagenlogik

Definition/Konstruktion von FormelnKlausel, konjunktive Form, disjunktive FormBegriffe: Interpretation, Modell, unerfüllbare Formel,TautologieBeweis über WahrheitstafelnAxiomatische Beweisverfahren

ÄquivalenzregelnDefinition: FolgerungsbegriffSchlussregelnAnforderungen an AxiomensystemeHilberts AxiomensystemAutomatisches Beweisen

Informatik A - WiederholungI Logik

I.2 Prädikatenlogik

I.2 Prädikatenlogik

SyntaxSemantik: Interpretation der syntaktischen SymboleSchlussregeln und ÄquivalenzenEntscheidbarkeit von PL1

Informatik A - WiederholungII Schaltfunktionen

II.1 Zahlendarstellung

II.1 Zahlendarstellung

Definition b-adisches SystemUmrechnung Dezimal ↔ Basis bNegative Zahlen: Einer- Zweierkomplement,Gleitkommazahlen nach IEEE

Darstellungnormalisierte/unnormalisierte DarstellungNull, ∞, NaNUmwandlung Dezimal → Binär

Informatik A - WiederholungII Schaltfunktionen

II.2 Boolesche Algebra

II.2 Boolesche Algebra

DefinitionGesetzePotenzmenge und Boolesche Algebra

Informatik A - WiederholungII Schaltfunktionen

II.3 Schaltfunktionen

II.3 Schaltfunktionen

Definition: Schaltfunktion, totale Sf, Boolesche SfDisjunktive Normalform

Minterme, einschlägiger Index, DarstellungssatzFunktionale Vollständigkeit

Konjunktive NormalformMaxtermeUmwandlung disjunktive → konjunktive Normalform

Informatik A - WiederholungII Schaltfunktionen

II.4 Schaltnetze

II.4 Schaltnetze

Arten von BausteinenKriterien für SchaltungenGraphen

Definitionungerichteter/gerichteter GraphPfadZyklusDAG: Gerichteter, azyklischer graph

Darstellung eines Schaltnetzes als Graph

Informatik A - WiederholungII Schaltfunktionen

II.5 Ringsummennormalform

II.5 Ringsummennormalform

Definition RNFÄquivalenzenDefinition komplementfreie RNFHerleitung der komplementfreien RNF

Informatik A - WiederholungIII Schaltnetze und ihre Optimierung

III.2 Vereinfachung von Schaltnetzen

III.2 Vereinfachung von Schaltnetzen

Vereinfachung durch ResolutionKarnaugh-Diagramme

AufbauMaximaler Block/Minimaler AusdruckPartielle Boolesche FunktionenVerkürzte Ringsummennormalform

Disjunktive Form, KostenmaßImplikanten und PrimimplikantenQuine & Clusky Verfahren

Informatik A - WiederholungIII Schaltnetze und ihre Optimierung

III.3 Fehlerdiagnose von Schaltnetzen

III.3 Fehlerdiagnose von Schaltnetzen

FehlermöglichkeitenSchaltungsabhängige Fehlerdiagnose: Annahmen, Ansatz

1 Fehlerfunktionen2 Äquivalente Funktionen3 Ausfallmatrix4 Fehlermatrix

Schaltungsunabhängige Fehlerdiagnose: Annahmen, Ansatz1 Testpaare2 Minimale Testmenge

Informatik A - WiederholungIII Schaltnetze und ihre Optimierung

III.4 Hazards in Schaltnetzen

III.4 Hazards in Schaltnetzen

Ursachen für HazardsArten von HazardsStatischer Funktionshazard

DefinitionBestimmung

Statischer Schaltungshazard: Definition

Informatik A - WiederholungIV Schaltwerke

IV.1 Flip-Flops

IV.1 Flip-Flops

Verhalten von Bistabiler KippstufeRS-Flip-Flop: Aufbau, WahrheitstabelleJK-Flip-Flop: Aufbau, WahrheitstabelleD-Flip-Flop: Aufbau, Wahrheitstabelle

Informatik A - WiederholungIV Schaltwerke

IV.2 Sequentielle Schaltungen

IV.2 Sequentielle Schaltungen

Mealy-Automat: DefinitionBeispiele

2-Bit Register1–Bit AdditionModulo 6 Zähler

Automat, Übergangstabelle, Realisierung

Informatik A - WiederholungIV Schaltwerke

IV.3 Lineare Schaltkreise

IV.3 Lineare Schaltkreise

BausteineCodierung/DecodierungMultiplikationsschaltungDivisionsschaltung

Informatik A - WiederholungV Programmierbare Logische Arrays (PLAs)

V Programmierbare Logische Arrays (PLAs)

BasisbausteineAufbau: UND-, ODER-EbeneProgrammieren von PLAs

2m Bits als SteuerungsprogrammVariante: Einspeisung von Variablen und deren NegationVariante: feste Produktterme (PAL)

Anwendung: ROMAnwendung: Schaltwerke

Informatik A - WiederholungVI VLSI-Schaltungen

VI VLSI-Schaltungen

TechnologieMaßzahlenKomplexität: # Anschlüsse, Rechenzeit

Informatik A - WiederholungVII Schaltungen für Addition und Subtraktion

VII Schaltungen für Addition und Subtraktion

Serieller VolladiererPipeline-AddiererVon-Neumann-AddierwerkCarry-Look-Ahead AdditionMultiplikationsschaltungMultiplikationsalgorithmus

Informatik A - WiederholungVIII Von–Neumann–Rechner

VIII Von–Neumann–Rechner

Grundlegende ArchitekturAufbau einer (minimalen) CPU

DatenprozessorBefehlsprozessor

Zwei-Phasen-VerarbeitungSpeicheraufbau:

DimensionenHierarchie

Busse: Adressbus, Datenbus, I/O-BusseInput/Output: Asynchronität, I/O-ControllerInteruptsOptimierung

PipeliningParallelität

Informatik A - WiederholungIX Eine kleine Programmiersprache

IX.1 Syntaktische Beschreibungsmittel

IX.1 Syntaktische Beschreibungsmittel

Chomsky-GrammatikGrammatik-TypenErweiterte Backus–Naur–FormSyntaxdiagrammeÜberführung von EBNF in Syntaxdiagramme

Informatik A - WiederholungIX Eine kleine Programmiersprache

XI.2 Syntax von Mini–Pascal

XI.2 Syntax von Mini–Pascal

Variablen, Konstanten, ProzedurenStatementsExpressionsVerzweigungen und SchleifenBlockschachtelung

Informatik A - WiederholungIX Eine kleine Programmiersprache

XI.3 Mini-Assembler

XI.3 Mini-Assembler

InstruktionenStapelmaschine

DatenstapelAktivierungsblockInstruktionszählerProgrammspeicher

Semantik von Befehlen

Informatik A - WiederholungIX Eine kleine Programmiersprache

XI.4 Semantik von Mini–Pascal

XI.4 Semantik von Mini–Pascal

Übersetzung von ExpressionsÜbersetzung von StatementsÜbersetzung von Verzweigungen und Schleifen

Informatik A - WiederholungX Von Mini–Pascal zu Pascal

X.1 Pascal Datentypen

X.1 Pascal Datentypen

Begriffe: Typ, Variable, ZuweisungEinfache DatentypenTypkonstruktoren

arrayrecord, caseset

Zeigertypen: Deklaration, OperationenListenoperationen mit Zeigern

ErzeugenEinfügenSuchenLöschen

Dateien: Deklaration, Operationen

Informatik A - WiederholungX Von Mini–Pascal zu Pascal

X.2 Kontrollstrukturen, Prozeduren, Funktionen

X.2 Kontrollstrukturen, Prozeduren, Funktionen

Kontrollstrukturen: repeat, for, if, caseProzeduren, forward-DeklarationWert- vs. ReferenzparameterFunktionenBeispiel: Minicompiler

HauptprogrammRegel für WertzuweisungRegel für AusdruckRegel für TermRegel für Faktor

Informatik A - WiederholungX Von Mini–Pascal zu Pascal

X.3 Objektorientierte Programmierung in Pascal

X.3 Objektorientierte Programmierung in Pascal

Grundbegriffe der Objektorientierten ProgrammierungObjekttypKapselungVererbungKonstruktorDestruktorMethoden

Informatik A - WiederholungX Von Mini–Pascal zu Pascal

X.4 C vs. Pascal

X.4 C vs. Pascal

Unterschiede im TypsystemUnterschiede in den OperatorenUnterschiede in den KontrollstrukturenProzeduren, Funktionen

Informatik A - WiederholungXI Prolog

XI.1 Von Logik zu Prolog

XI.1 Von Logik zu Prolog

HornklauselnImperative Programmiersprachen vs. LogiksprachenKomponenten eines Prologprogramms

FaktenRegelnAnfragen

Rekursive Regeln

Informatik A - WiederholungXI Prolog

XI.2 Syntax und Semantik von Prolog

XI.2 Syntax und Semantik von Prolog

Syntax: Konstante, VariablenSyntax: StrukturenSemantik: Grundbegriffe: Instanziierung, UnifikationGleichheitGleichheit: BeispieleSemantik: InferenzInferenz: Und-Oder-Baumfail: Erzwingen von BacktrackingCut: Unterbinden von Backtracking

Informatik A - WiederholungXI Prolog

X.3 Rekursive Regeln

X.3 Rekursive Regeln

Begriffeclosed world assumptionProzedurale BedeutungDeklarative Bedeutung

Rekursive Inferenz: richtige/falsche Anordnung

Informatik A - WiederholungXI Prolog

XI.4 Listen

XI.4 Listen

Notationsmöglichkeiten: flach, Kopf+Rest, Punktnotation,FunktornotationMitgliedschaftKombinationHinzufügen und LöschenTeillisten und InverseMengenoperationenDesign Pattern für Umgang mit ListenSortieren durch EinfuegenBubblesortQuicksort

Informatik A - WiederholungXI Prolog

XI.5 Umgang mit Baumstrukturen

XI.5 Umgang mit Baumstrukturen

Symbolisches DifferenzierenVereinfachung Arithmetischer AusdrückeSymbolisches Differenzieren mit Vereinfachung

Informatik A - WiederholungXII Funktionale Programmiersprachen

XII.1 Überblick

XII.1 Überblick

Charakteristika funktionaler ProgrammiersprachenFunktionen als “first class values”Striktes TypsystemFreiheit von Seiteneffekten

Informatik A - WiederholungXII Funktionale Programmiersprachen

XII.2 Variablen und Funktionen

XII.2 Variablen und Funktionen

VariablenzuweisungLexikalisches ScopingFunktionendeklarationFunktionen als ”first class values”CurryingFunktionen höherer OrdnungRekursive Funktionen

Informatik A - WiederholungXII Funktionale Programmiersprachen

XII.3 Pattern Matching

XII.3 Pattern Matching

SyntaxBereichspatternsUnvollständige Matches

Informatik A - WiederholungXII Funktionale Programmiersprachen

XII.4 Polymorphismus, Tupel, Listen

XII.4 Polymorphismus, Tupel, Listen

Parametrisierte TypenTupelListenPolymorphe ListenFunktionen höherer Ordnung auf ListenQuicksort in OCaml

Informatik A - WiederholungXII Funktionale Programmiersprachen

XII.5 Union Types

XII.5 Union Types

Binäre BäumePatternmatching mit Union TypesUngeordnete Bäume

EinfügenSuchen

Geordnete BäumeEinfügenSuchen

Informatik A - WiederholungXII Funktionale Programmiersprachen

XII.6 Objektorientierte Programmierung in OCaml

XII.6 Objektorientierte Programmierung in OCaml

Deklaration von Klassen, Instanzvariablen und MethodenAufruf von MethodenInstanziierung von ObjektenAufruf eigener MethodenInitializerVirtuelle MethodenPrivate MethodenVererbungMehrfachvererbung