Mig og en bog af Michael Sipser

I dag lå der en pakke til mig. En bog, men ikke hvilken som helst bog. Jeg har siden 1996 brugt Michael Sipsers Introduction to the Theory of Computation i kurserne Syntaks og semantik og Beregnelighed og kompleksitet. I dag kom den nye udgave af Sipsers bog, den tredje af slagsen. Og den var en gave fra forlaget. Sørme.

Dette er klassisk og velfordøjet stof i teoretisk datalogi, så udvalget er stort. Jeg har tidligere brugt flere andre bøger om samme emner, men som man måske kan fornemme, var der ingen af dem jeg var særligt begejstret for. I 1996 så jeg ved et tilfælde en artikel i Usenet-nyhedsgruppen comp.theory af Michael Sipser, hvor han annoncerede den foreløbige udgave (ja, der var en udgave før den første), som man kunne bestille et eksemplar af. Allerede da gik det op for mig at hans bog ramte det rigtige indhold for mit kursus. Da jeg sad med bogen i hånden opdagede jeg, at den desuden havde det suverænt bedste bud på et overblik over sætninger og deres bevis. Især var og er jeg glad for at alle større beviser indledes med en bevisskitse. Valget var klart for mig.

Der er bestemt også andre gode bøger derude. Især vil jeg fremhæve en gammel klassiker, nemlig den gamle bog fra 1979 med næsten samme titel, Introduction to Automata Theory, Languages and Computation af John Hopcroft og Jeffrey Ullman – det er formodentlig ikke en bog for folk med svage nerver (den har nogle af de sværeste øvelser, jeg har set), men jeg havde alligevel glæde af den, da jeg selv var studerende. Vores kursusholder var en pædagogisk-didaktisk naturkatastrofe af en hollandsk gæsteprofessor, der bør være anonym – han fik faktisk senere en hædersbevisning fra Aalborg Universitet, og det var ikke for det han præsterede som underviser. Han bekymrede sig ikke om småting som undervisningsplan, forberedelse, opgaver eller valg af lærebog, og “man” blev enige om at han ikke skulle føre op til eksamen. Men inden da, mens kaos rådede, måtte vi selv støve litteratur op, og jeg fandt frem til Hopcroft og Ullmans bog. Senere kom der desværre en ny udgave, hvor Hopcroft og Ullman sammen med en tredje forfatter forfalder til at omdanne deres klassiker til en “snakkebog”. Den oprindelige udgave var nok ikke god til begyndere,  men den er en god matematikbog.

Nævnes skal også den meget nyere Automata and Computability af Dexter Kozen; det er en bog som er forbilledligt godt disponeret i små, overskuelige kapitler og i det hele taget er værd at gå på opdagelse i. Dexter Kozen har forresten en overgang boet i Danmark og lærte ved den lejlighed dansk – men dette kan han trygt læse. Hvis jeg skulle holde et kursus om automatteori og beregnelighed alene, kunne hans bog faktisk også være et godt valg.

Hvad er så det nye i tredje udgave af Sipsers bog? Ud over en masse rettelser rundt omkring er det især et langt afsnit om deterministiske pushdown-automater, jeg bemærker. Utallige er de studerende, der har troet på en ikke-eksisterende sætning om at der for enhver pushdown-automat findes en ækvivalent deterministisk pushdown-automat. (De studerende har mange sådanne yndlingssætninger, der desværre er falske!) Forhåbentlig kan vi nu gøre det af med netop denne yndlingssætning.

(Visited 252 times, 1 visits today)
Loading Facebook Comments ...

Én kommentar til “Mig og en bog af Michael Sipser”

  1. Det kan lige tilføjes, at vi som studerende også var rigtig glade for ITTOC. Den forklarer tingene meget metodisk og præcist. Måske er det netop i relief til et par andre lærebøger vi brugte på studiet, som bestemt ikke levede op til dette. De værste syndere på software-studiet var ERP-bogen og bogen til Agentprogrammering, som jeg desværre ikke kan huske navnene på.

    Jeg tror desværre ikke det er muligt at lave en bog eller en underviser der er dygtig nok til, at de ‘yndlingssætninger’ undgås. Desuden ville det jo også snyde dig og dine kollegaer for hvad jeg kun kan antage er en masse værdifuld underholdning.

Skriv et svar