Informatik A - WiederholungVom Lernen und Vergessen Am Ende einer Vorlesung wissen die Studenten noch ca. 50% des vorgetragenen Stoﬀes Nach einer Woche erinnern sie sich noch an

Informatik A - Wiederholung


Norbert Fuhr


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


II.2 Boolesche Algebra

II.2 Boolesche Algebra

DefinitionGesetzePotenzmenge und Boolesche Algebra


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


II.4 Schaltnetze

II.4 Schaltnetze

Arten von BausteinenKriterien für SchaltungenGraphen

Definitionungerichteter/gerichteter GraphPfadZyklusDAG: Gerichteter, azyklischer graph

Darstellung eines Schaltnetzes als Graph


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


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


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


IV.2 Sequentielle Schaltungen

IV.2 Sequentielle Schaltungen

Mealy-Automat: DefinitionBeispiele

2-Bit Register1–Bit AdditionModulo 6 Zähler

Automat, Übergangstabelle, Realisierung


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


XI.2 Syntax von Mini–Pascal

XI.2 Syntax von Mini–Pascal

Variablen, Konstanten, ProzedurenStatementsExpressionsVerzweigungen und SchleifenBlockschachtelung


XI.3 Mini-Assembler

XI.3 Mini-Assembler

InstruktionenStapelmaschine

DatenstapelAktivierungsblockInstruktionszählerProgrammspeicher

Semantik von Befehlen


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


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


X.3 Objektorientierte Programmierung in Pascal

X.3 Objektorientierte Programmierung in Pascal

Grundbegriffe der Objektorientierten ProgrammierungObjekttypKapselungVererbungKonstruktorDestruktorMethoden


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


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


X.3 Rekursive Regeln

X.3 Rekursive Regeln

Begriffeclosed world assumptionProzedurale BedeutungDeklarative Bedeutung

Rekursive Inferenz: richtige/falsche Anordnung


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


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


XII.2 Variablen und Funktionen

XII.2 Variablen und Funktionen

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


XII.3 Pattern Matching

XII.3 Pattern Matching

SyntaxBereichspatternsUnvollständige Matches


XII.4 Polymorphismus, Tupel, Listen

XII.4 Polymorphismus, Tupel, Listen

Parametrisierte TypenTupelListenPolymorphe ListenFunktionen höherer Ordnung auf ListenQuicksort in OCaml


XII.5 Union Types

XII.5 Union Types

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

EinfügenSuchen

Geordnete BäumeEinfügenSuchen


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

Documents

Informatik A - WiederholungVom Lernen und Vergessen Am Ende einer Vorlesung wissen die Studenten noch ca. 50% des vorgetragenen Stoﬀes Nach einer Woche erinnern sie sich noch an