C# 5

Denne bog er sammen med de andre bøger i denne serie en bog om programmering og C#. Når man taler om programmering, tænker man på metode, og hvordan man i praksis skriver gode programmer, og når man taler om C#, tænker man på programmeringssprog, og hvordan man skriver de enkelte sætninger til et program. De to begreber er naturligvis ikke uafhængige, og er vel to sider af samme sag, og man er ikke en god programmør, med mindre man er god til begge dele: Man skal kende og bruge velafprøvede metoder, og man skal kunne sit sprog. Denne bog har primært fokus på metode.

Man hører ofte, at programmering er svær at lære, hvilket nok også er korrekt. I hvert fald er der mange, som opgiver, men det skyldes nu nok mere, at man ikke finder programmering særlig spændende, end fordi det er svært, og faktisk er det endda blevet lettere, end det har været. Det er blevet lettere med fremkomsten af nye programmeringssprog, som dels kan lette arbejdet, da man skal skrive mindre, og dels resulterer i mere robuste programmer, fordi sprogene stiller en langt større værktøjskasse til rådighed, end tidligere var tilfældet. Omvendt er kravene til de programmer, der skal laves, vokset tilsvarende, og set fra programmørerne er udfordringerne egentlig de samme, at kunne udarbejde en god algoritme til at løse et konkret problem. Alle programmer er ikke lige heldige, og der er masser af eksempler på programmer, som er ineffektive og løser bestemte opgaver på en uhensigtsmæssig måde, og ofte er problemet, at der ikke har været fokus på algoritmen, men at man i lang større udstrækning har haft fokus på at få opgaven løst uden at skele til, hvordan opgaven blev løst. Derfor er algoritmen én af de to centrale emner i denne bog.

I virkeligheden skulle jeg nok have startet min historie om programmering med algoritmer, da det er det, som det hele drejer sig om. Man skal være god til algoritmer for at være en god programmør, men det gør det ikke alene, og en anden vigtig ting er motivation og herunder lysten til at arbejde med programmering og softwareudvikling. Man kan lære om algoritmer og metode, men man kan ikke skrive færdige programmer, som kan køre på en maskine, uden at have et programmeringssprog. Derfor starter de fleste indgange til programmeringsfaget med sproget, fordi man på den måde hurtigt når frem til at kunne skrive færdige programmer. De fleste vil gerne hurtigt "have fingrene på tasterne" og skrive færdige programmer, som laver noget interessant.

Denne bog er inddelt i to dele, og den første del omhandler algoritmer. Den første del belyser nogle vigtige begreber inden for algoritmer og herunder teknikker til at skrive algoritmer samt teknikker til at vurdere algoritmers egenskaber i forhold til hinanden. Bogens anden del omhandler datastrukturer og har i tilknytning hertil også stor fokus på algoritmer. Bogens del 1 er således en forudsætning for bogens del 2, som beskriver de klassiske datastrukturer.

En datastruktur er blot et andet navn for det, som .NET kalder for en collection klasse. Målet er at beskrive og forklare de klassiske collection klasser, men også at implementere dem som færdige klasser skrevet i C#. Man kan spørge, hvorfor man skal det, når nu de allerede findes som færdige og afprøvede klasser, og det er der to årsager til. For det første er det vigtigt at vide, hvordan klasserne er lavet, så man ved hvordan klassernes metoder i princippet virker og har de egenskaber, som dokumentationen beskriver. Kun med den viden til rådighed er man i praksis i stand til at træffe de rigtige valg og vælge den collection klasse, som passer bedst på den algoritme, som man skal skrive. Som en anden begrundelse for at beskæftige sig med implementeringen af de klassiske collection klasser kan nævnes, at ved at studere disse implementeringer introduceres man til nogle teknikker og metoder, som er vigtige for praktisk programmering. Det er altså vigtigt at understrege, at det ikke er målet at skrive et nyt collection API og collection klasser, som skal erstatte de klasser, som kommer som en del af .NET, men målet er at forklare, hvordan disse klasser i princippet er implementeret.

Da mange af datastrukturerne og også de eksempler, som skal illustrere anvendelser af både algoritmer og datastrukturer fylder meget, har jeg kun i begrænset udstrækning medtaget koden som en del af bogens tekst. Det er i modsætning til de øvrige bøger i samme serie, hvor sproget og dermed programkoden har været i centrum. For at få det fulde udbytte af bogen er det derfor vigtigt, at du også studerer de færdige programmer, og her specielt hvordan datastrukturerne er implementeret i C#. Al koden er samlet i en Visual Studio solution, som igen indeholder to projekter. Det ene projekt er et class library og dermed det projekt, som det hele drejer sig om. Dette library indeholder en række algoritmer fra del 1 (typisk implementeret som statiske metoder og evt. som extension metoder) samt alle collection klasser forklaret i del 2. Det andet projekt indeholder testklasser til algoritmer og collection klasser fra class librariet. Da selve programkoden kun i mindre grad er forklaret i bogens kapitler har jeg til gengæld gjort mere ud af kommentarer i koden, og den præcise forklaring til programkoden skal findes i disse kommentarer.

• Forord
• Del 1: Algoritmer

1. Eksempler på algoritmer
   1. Rekursion
   2. Søgning
   3. Fibonacci tallene
   4. Euklids algoritme
   5. Tværsum
   6. Primtal
2. Sweep
3. Algoritme analyse
   1. Kompleksiteten af lineær søgning
   2. Tidskompleksitet af binær søgning
   3. Flere eksempler
   4. Summen af det mindste og største tal
   5. Sortering
   6. Definition af kompleksitetsmål
   7. Merge
   8. Tidskompleksitet i praksis
   9. Pladskompleksitet
   10. Medianen
4. Korrekthed af algoritmer
   1. Korrekthed af Euklids algoritme
5. Sortering
   1. Bubble sort
   2. Selection sort
   3. Insertion sort
   4. Shell sort
   5. Merge sort
   6. Del, løs og kombiner
   7. Quick sort
6. Backtracking
   1. Permutation
7. Grådige algoritmer
8. Dynamisk programmering
   1. Primtal
   2. 0/1 Knapsack problemet

• Del 2: Collectionklasser

1. Array
2. Sequence
3. Stack
4. Buffer
5. Lister
   1. Enkelthægtet liste
   2. Dobbelthægtede lister
   3. Andre muligheder
   4. En ordnet liste
6. Køer
   1. Prioritets kø
7. Bitmap
   1. Eratosthenes
8. Træer
   1. Binære træer
   2. Binære søgetræer
   3. Egenskaber ved binære træer
   4. AVL træ
   5. Rødt-sort træ
   6. Afslutning på binære træer
   7. Søgetræer
   8. B træer
   9. B+ træer
9. Heap
   1. Klassen BinaryHeap
   2. Klassen Heap
   3. Heap sort
   4. Priority queue
10. Hashing
    1. Klassen Hashing
    2. Set
    3. HashTable
11. Grafer
    1. Implementering
    2. GraphTools
    3. Traversering af grafer
    4. Korteste veje
    5. Topologisk sortering
    6. Mindst udspændende træ