onsdag 18. mai 2016

9 Algorithms That Changed the Future

"9 Algorithms That Changed the Future - The Ingenious Ideas That Drive Today's Computers" heiter ei bok av John MacCormick. Eg vart merksam på boka då eg las Paul Chaffeys blogg og hans omtale av den. MacCormick er professor ved Dickinson College (USA), Departement of Mathematics and Computer Science , der han forskar og underviser.

Manglande IT-utdanning og forståing for den
I forordet dveler Chris Bishop, professor ved University of Edinburgh, ved paradokset at sjølv om IT omgir oss på alle kantar, er det framleis ikkje eit eige fag før på universitetsnivå. Dersom det blir tilbydd undervisning før universitetsnivå, er det ofte berre opplæring i diverse verktøy og ikkje innføring i "computer science" slik ein gjer i fysikk og kjemi t.d.

Kva er algoritmar?
Ein skulle gjerne tru at ei bok med denne tittelen, og som handlar algoritmar, ville gått litt tilbake i historien og sett på den etymologiske tydinga av algoritme. Det gjer MacCormick ikkje; han stuper inn i detaljane ved dei ni algoritmane nesten utan vidare refleksjon. Det er den første svakheita ved boka.

Algoritme er eit sett instruksjonar for ei datamaskin. Ordet kjem frå den persiske matematikaren (og astronom + geograf) Muḥammad ibn Mūsā al-Khwārizmī. Han er rekna for ein av forfedrane til algebra og skreiv fleire bøker. I tillegg til opphavet for 'algoritme' er ha også opphavet til ordet 'algebra'. 'Algoritme' kjem av det latinske namnet til  al-Khwārizmī.

Utvalskriterium
Det trengst bøker som skaper entusiasme og forståing for det grunnleggjande ved datateknologi, og det er det MacCormick tek mål av seg til å bidra med. Som tittelen seier, tek boka hans for seg ni algoritmar som har endra framtida vår. Han sette opp følgjande kriterium for utveljinga:
  1. Algoritmen må vera i bruk dagleg av (datamaskin-)brukarar
  2. Algoritmen må adressera konkrete, reelle problem (real-world problems)
  3. Algoritmen må hovudsakeleg vera relatert til computer science-teori (og då fell alt som har med maskinvare bort)
Offentleg nøkkel-kryptografi og digitale signaturar
Ei anna svakheit er etter mitt syn dei ni algoritmane som er valde ut. Det er ikkje lett å velja dei ni viktigaste algoritmane i IT-verda, og det vil nødvendigvis bli mykje diskusjon rundt eit slikt val. Men å bruka to av dei ni plassane på offentleg nøkkel-kryptografi og digitale signaturar, meiner eg er feil. Offentleg nøkkel-kryptografi og digitale signaturar er to sider av same sak og burde vore omtalt under eitt - då kunne han fått plass til ein algoritme til.

PageRank byggjer på?
Ei tredje svakheit er at han i drøftinga av søk og Googles PageRank-algoritme ikkje nemner opphavsmannen til algoritmen: Eugene Garfield (som seinare vart tilsett i Google). Garfield utvikla ein siterings-algoritme (Science Citation Index) ved University of Pennsylvania i 1950-åra. Kjernen i algoritmen var at til meir meritterte forfattarane som siterte artikkelen din var, til høgre verdi fekk artikkelen din - den såkalla impact factor.

Kva med Bitcoin?
Boka kom ut i 2011 og eg kan difor vanskeleg kritisera han for ikkje å ha teke med Bitcoin; som elles burde hatt ein opplagt plass blant dei ni. Men MacCormick er snublande nær, for i det siste kapitlet der han spekulerer over kva algoritmar me kan komma til å sjå i framtida, diskuterer han zero knowledge proofs og ei løysing på dei bysantinske generalars problem. Bitcoin er jo nettopp svaret på den siste utfordringa, og kanskje skulle ein professor i computer science ha oppdaga det i 2011? 

Dei aktuelle algoritmane
Dei ni algoritmane han har valt ut, er:
  1. Search Engine Indexing
  2. PageRank
  3. Public Key Cryptography
  4. Error-Correcting Codes
  5. Pattern Recognition
  6. Data Compression
  7. Databases
  8. Digital Signatures
  9. What Is Computable?
Den siste er strengt teke ikkje ein algoritme, men ein gjennomgang av Alan Turings banebrytande bevis for at det er umuleg å forutsjå alle feil i eit dataprogram. Eller sagt på ein annan måte: Det finst ting som er umuleg å forutsjå: vil eit program eventuelt krasja eller vil det gå i det uendelege? Dette er kjendt som the halting problem og the undecidability problem.

Det som er bra med boka
Sidan eg har vore ganske kritisk til MacCormick innleiingsvis får eg ta med det som er positivt også. Han har skrive ei lettlesen og pedagogisk god bok. Det skin gjennom at MacCormick verkeleg er interessert i å formidla dette, og han gjer det som sagt på ein god pedagogisk måte. 

6 kommentarer:

Lars Marius Garshol sa...

Databaser er vel heller ikke en algoritme. Egentlig virker lista ganske datert, med mindre "Pattern recognition" (som heller ikke er en algoritme) handler om nevrale nettverk.

Jeg ser ikke helt sammenhengen mellom Garfields algoritme og PageRank, dog. Jeg har ikke klart å finne noen beskrivelse av "impact factor" som vekter de som siterer en artikkel. Uansett er PageRank et ganske annerledes dyr. Faktisk får du PageRank hvis du tar et av de sentrale teoremene om Markov-kjeder og legger på noen workarounds for grafer som ikke er helt velformede Markov-kjeder. Hvis du har mer informasjon om sammenhengen med Garfield vil jeg veldig gjerne se den.

Voluntaryisten sa...

Bitcoin og blokkjedeteknologi går også under offentlig nøkkel kryptografi.

Det at IT undervises først på universitetet er ikke nødvendigvis en dårlig ting.
Vi lever i en økende spesialisert økonomi der man må spesialisere seg for å kunne produsere verdier som en bedrift ser på som verdifull.

Svein Ø sa...

@Lars Marius: Databasar er klart på eit anna nivå enn algoritmar. Rett nok har MacCormick plukka ut eit par algoritmar vesentlege for moderne databasar, men det er databasen som algoritme han framhevar. Eg er einig i at lista hans ikkje er særleg god, og ser ut til å vera minst 10 år gammal.

Eg har teke fram att Page & Brin sin PageRank-artikkel og lurer på om det faktum at den første dei siterer, Eugene Garfield, er grunnen til at han ofte blir nemnt som "far" til PageRank-algoritma. På eit overordna nivå kan ein seia at Garfields siteringsalgoritme og Journal Impact Factor (JIF) ligg til grunn for tenkinga bak PageRank. Samtidig er nok PR også ein del meir enn rein siteringsvekting. Her er ein Wired-artikkel om koplinga mellom Garfield, h-indeks og PageRank (vel, eigentleg viser den inga kopling..): http://www.wired.com/2009/05/mf-impactfactor/?currentPage=all

Wikipedia omtalar også Garfields siteringsalgoritme som grunnleggjande for m.a. PageRank:
"Garfield's work led to the development of several Information Retrieval algorithms, like HITS and Pagerank."

@Voluntaristen: Ja, Bitcoin er også offentleg nøkkel-kryptografi (pluss ein del meir). Og det kan også innvendast at Bitcoin ikkje er nokon algoritme, heller ei samling algoritmar.

Eg meiner IT burde komme tidlegare på læreplanane og at det etter kvart bør behandlast som dei grunnleggjande realfaga - og då i betydninga "computer science" som forfattaren også argumenterer for. "Lær kidsa koding" er ein del av eit slikt initiativ, men eg såg gjerne at IT vart teke opp i større breidde og behanlda like seriøst som matematikk og fysikk frå ungdomsskulen av.

Lars Marius Garshol sa...

Jeg så på PageRank-artikkelen nå. Jeg er enig i at det er en konseptuell kobling fra å telle citations til PageRank, og det er jo ekstra tydelig når Page & Brin peker på den selv. Gitt at Garfield er far til citations osv så er det vel lett å tenke at han er "far" til PageRank, men for å være helt ærlig ser det jeg har sett av citation-metoder ekstremt primitivt ut. PageRank er riktignok relativt enkel, men på et helt annet nivå.

Ironisk nok ser det ut til at for å rangere artikler ut fra citation-struktur fungerer helt vanlig citation-telling a la Garfield mye bedre enn PageRank. Men så er jo ikke PageRank ment for det formålet, heller. (Har testet det selv, og det ser ut som PageRank fungerer dårligere.)

Intenst enig i at IT må komme tidligere i læreplanene. De må også inneholde mer matematikk, og da særlig statistikk. Det er selvsagt flott å snakke om innovasjon osv, men virkelig innovasjon krever kunnskap og evne til å levere.

Anonym sa...

Vennligst stem opp borgelønn i Arbeiderpartiets parti program.
http://www.dittforslag.no

Unknown sa...

Gjerne! (men dette er vel feil bloggpost..)