Dette materiale er forelæsningsnoter til et kombineret programmerings- og datastrukturkursus (Programmeringssystemer 1), som blev afholdet på Aalborg Universitet fra 1991-1994. Programmeringsdelen er baseret på Eiffel.
Forelæsningnoterne har form af anoterede slides. Forelæsningen er opdelt i ca. 30 lektioner, og for hver lektion er der en PDF version af materialet tilrådighed.
Herefter følger materialet disponeret efter de overordnede emner objekt-orienteret programmering i Eiffel, algoritmer og datastrukturer samt andre relaterede emner.
I forbindelse med kurset blev der afholdt skriftlig eksamen. Opgaverne fra disse eksamener kan have interesse for andre, som underviser i emnerne, og er således også tilgængelige sammen med vejledende løsninger.
I denne del af materialet indgår lektioner om generel objekt-orienteret programmering samt en del materiale, der er specifik for Eiffel. Materialet knytter sig til Eiffel 3.
Vi benyttede lærebogen Object-oriented Software Construction af Betrand Meyer på denne del af kurset.
I forbindelse med kurset evaluerede vi Eiffel som sprog og omgivelse til introducerende undervisning i objekt-orienteret programmering. Henvis til resultatet her.
Dette kapitel stater med et motiverende eksempel for objekt-orienteret programmering, hvor vi ser på top-down udvikling af et program, som vi kalder 'mini-bank' Dernæst diskuterer vi strukturering af et program: efter data eller funktion, og vi definerer en abstrakt datatype og dertil tilknyttede begreber. Vi ser også på fænomener, begreber og begrebsdannelse. Endelig udvikler vi programmet 'mini-bank' på objekt-orienteret vis.
I dette kapitel gennemgår vi den algebraiske specifikations teknik for abstrakte datatyper. Vi ser på to eksempler: specifikation af naturlige tal og af mængder.
I dette kapitel introducerer vi objekt-orienteret programmering på en sproguafhængig måde. Klasser i forhold til abstrakte datatyper og record-typer. Begreberne variable og operationer, klasse-interfaces, information hiding, klasse-instantiering og initialisering og klienter og leverandører bliver berørt.
I dette kapitel genfortæller vi stoffet fra Basal objekt-orienteret programmering I, men her specifikt for programmeringssproget Eiffel.
I dette kapitel introduceres begreber fra Eiffel programmeringsomgivelsen (Eiffel 3). Dette omfatter klynger og univers, ACE systembeskrivelsesfiler, oversigt over Eiffel compilering, compiler options, oversigt over biblioteker samt dokumentationsværktøj.
Dette kapitel er Eiffel-specifik. Der introduceres en række detaljer i sproget såsom assignments, kald, betingede kommandoer, iterative kommandoer og udtryk. Kapitlet starter med en diskussion af typesammenlignelighed. I kapitlet diskuteres også invarianter og varianter af løkker.
I dette kapitel diskuteres specifikation med logiske udtryk. Kapitlet er således et alternativ til det tidligere kapitel om algebraisk specifikation. Konkret gennemgås pre- og postbetingelser og klasseinvarianter. Den sidste del af kapitlet er specifik i forhold til Eiffel.
Kapitlet starter med en generel diskussion af fejlhåndteringsproblematikken. Den sidste del af kapitlet er helliget en diskussion af Eiffel's exception handling mekanisme.
Dette er det første af 3 kapitler om nedarvning. Dette kapitel er sproguafhængigt. Følgende begreber diskuteres: Udvidelse og specialisering, klassehierarkier, interfaces, statiske og dynamiske typer af variable, polymorfi, dynamisk binding og virtuelle operationer, samt abstrakte klasser.
Dette kapitel genfortæller stoffet fra Nedarvning I, men her specifikt for Eiffel. Renaming og redefinition gennemgås. Ligeledes reverse assignment attempt og deferred classes (abstrakte klasser).
I dette kapitel diskuteres multipel nedarvning samt forholdet mellem nedarvning og assertions (i Eiffel).
I dette kapitel diskuteres objekt-orienterede designteknikker, primært ud fra Eiffel BON-teknikken.
Dette er materiale til en repetitionslektion om objekt-orienteret programmering. Sidst i kapitlet beskriver vi covarians og kontravarians problematikken.
Hovedvægten i dette materiale har, hvad programmering angår, været objekt-orienteret programudvikling i Eiffel. I dette kapitel beskriver vi kort objekt-orienteret programmering i sprog, som har et modulbegreb. Dernæst gennemgår vi de væsentligste muligheder i C++.
I denne del af materialet er der annoterede slides til et kursus på ca. 10 lektioner i algoritmer og datastrukturer. Kurset er baseret på lærebogen Data Structures and Algorithm Analysis af Mark Allen Weiss, fra Benjamin Cummings.
I dette kapitel diskuteres klassisk algoritmeanalyse. Begreberne problemstørrelse og køretid samt estimering med store O, omega og theta gennemgåes. Dertil kommer en række eksempler på algoritmeanalyse.
Dette er en gennemgang af basale datastrukturer og deres egenskaber. Hvor det er mulig ser vi på algebraiske specifikationer for strukturerne. Der relateres også til Eiffel's tilsvarende klasser.
I dette kapitel introduceres træer. Først præsenteres en række definitioner (knude, kant, sti, blad, højde, dybde, grad). Vi ser på repræsentation af træer. Dernæst kommer gennemløb af træer.
I dette kapitel diskuteres først lineær og binær søgning. Dernæst introduceres søgetræer. Søgning, indsættelse og sletning i sådanne træer behandles. Dernæst ser vi på balancerede binære søgetræer med AVL balance.
I dette kapitel ser vi på træer af grad højere end 2, altså multivejstræer, til søgeformål. Både B-træer og B+ træer bliver behandlet. Indsættelse såvel som sletning i B-træer beskrives. Endelig analyseres indsættelse og sletning i et B-træ.
I dette kapitel ser vi på hashing. Først introduceres problematikken og hashnfunktioner. Herefter åben og lukket hashing, lineær og kvadratisk probing, samt indsættelses-, sletning og søgeoperationer.
Efter en introduktion af filbegreber (og filer i Eiffel) diskuteres en række forskellige indiceringsteknikker. Der skitseres også nogle Eiffel klasser, som gør det muligt på en systematisk måde at lagre objekter på filer. Tries omtales lige som der sammenlignes med B+ træer, set som indekser.
Først introduceres strengbegrebet og leksikografisk ordning blandt strenge. Vi ser på en abstrakt datatype for strenge, som vi delvis specificere algebraisk. Hovedindholdet er dog patten matching, hvor vi ser på den naive teknik, Knuth-Morris-Prat patternmatching samt Boyer-Moore patternmatching.
Hobe introduceres som en abstrakt datatype. En effektiv implementation af hobe i et array beskrives, og vi udvikler operationer til indsættelse, sletning af minimum/maximum, og hob-konstruktion. Interne, effektive hjælpeoperationer kaldet siv-op og siv-ned beskrives også.
Eiffel implementation af hob.
I dette kapitel introduceres sorteringsproblematikken, og et antal simple sorteringsteknikker behandles. Dette er spandsortering/radixsortering, sortering ved udvælgelse, sortering ved indsættelse, Shellsort og boblesortering. I de fleste teknikker ser vi på centrale løkkeinvarianter i sorteringsprocedurerne.
I dette kapitel ser vi på et antal mere avancerede og bedre sorteringsteknikker. Disse er sortering ved fletning, quicksort og heapsort. Vi behandler også (perifert i materialet) nedre grænser for sortering.
I dette kapitel diskuterer vi ekstern sortering, hvilket vil sige forskellige former for flettesortering med magnetbånd. Polyfasesortering er den mest udviklede teknik, som behandles her.
Del-og-hersk algoritmer introduceres, og vi ser på en række eksempler på sådanne: Det maksimale delsums problem, multiplikation af tal, samt Towers Of Hanoi. Dernæst introduceres dynamisk programmering, hvor beregning af Fibonaccital er et eksempel. Rygsækproblemet (Knapsack) og veksleproblemet behandles også.
Dette er et appendiks om en Eiffel klasse vi har udviklet, som hedder SIMPLE_LIST. Denne klasse ses som et alternativ til Eiffels LINKED_LIST.
Linke til Simple list klassen.
Her følger materiale til nogle få lektioner, som ikke fitter i det ovenstående. Kapitlet om grundbegreber er allerførste lektion i kurset. Til de to kapitler om programbeviser benyttede vi lokalt udviklede noter af Jan Stage.
I dette kapitel beskrives nogle vigtige programmeringsmæssige grundbegreber såsom syntaks og semantik, datatyper, kontrolstrukturer (selektion og iteration) udtryk, abstraktioner, parametermekanismer, blokke og navnebindinger samt scope og scoperegler.
I dette første kapitel om programbeviser introducerer vi et matematisk maskineri, som gør det muligt at bevise simple programmer. Hoare-sætninger og bevisregler bringes på banen. Dernæst bevisregler for en række konstruktioner i Pascal. Der vises et antal simple eksempler på programbeviser.
Kapitlet fortsætter hvor Programbeviser I slap. Vi beviser korrektheden af en ny række simple programmer.