Git-versiohallinnan matemaattiset perusteet

Työssä esitetään Git-versiohallintajärjestelmään liittyviä tietorakenteita ja toimintoja matemaattisesta näkökulmasta. Kuvaillaan Gitin käyttämä tietojen tallennustapa ja annetaan yleiskuva Gitin tärkeimmistä toiminnoista. Erityisen tarkasti Gitin toiminnoista esitetään pakkausmenetelmä, tiedostojen erojen vertailu ja pakettitiedostoissa käytettävä deltapakkaus. Deflate-pakkausmenetelmästä tutustutaan sen käyttämään Huffman-koodaukseen, LZ77- koodaukseen ja koodauskaavioiden pakkaukseen. Lisäksi määritellään deflate-pakatun tietovirran rakenne. Esitetään tiedostojen erojen vertailun matemaattinen määritelmä sekä näytetään miten tähän liittyvä pisimmän yhteisen alijonon hakeva algoritmi voidaan toteuttaa erilaisilla menetelmillä, joiden aikakompleksisuudet poikkeavat merkittävästi toisistaan. Kuvaillaan Gitin pakettitiedoston rakenne ja sen muodostamisen algoritmeja. Lisäksi annetaan matemaattinen määritelmä siinä käytetylle deltapakkaukselle ja esitetään deltapakkauksen algoritmi ja siinä käytetty Rabinin sormenjälki. Esitettävissä algoritmeissa esiintyy muutamia perusmenetelmiä kuten dynaaminen ohjelmointi, ahnas algoritmi sekä hajota ja hallitse -menetelmä.