Abstrakti tietotyyppi

Abstrakti tietotyyppi (, "ADT") on tyypin määrittely, joka määrittelee vain tyypin tietosisällön ja tyyppiin kuuluvat operaatiot, ei tyypin toteutustapaa. Toisin sanoen ADT määrittelee tarkalleen ja täydellisesti tyypin julkisen rajapinnan eikä mitään muuta. Esimerkiksi abstraktin tietotyypin "Stack" (pino) määrittely voisi kertoa muun muassa, että tallennettavat alkiot ovat kokonaislukuja, alkion pinon päällimmäiseksi lisäävä operaatio on "push" ja pinon päältä alkion poistava operaatio on "pop". Tietorakenteen toteutustapaan ADT ei ota mitään kantaa.
ADT siis määrittelee eräänlaisen rakenneosan, jota voidaan käyttää muita ohjelmia rakennettaessa. Ohjelmoija voi (ja hänen pitääkin) kirjoittaa ohjelmansa siten, että se käyttää vain ADT:n määrittelyn mukaisia ominaisuuksia, jolloin ohjelma toimii edelleenkin vaikka esimerkiksi kokonaislukutaulukkoon perustuva pino vaihdettaisiinkin linkitettyyn listaan perustuvaksi pinoksi.
Abstraktit tietotyypit.
Esimerkiksi kokonaisluvut ovat ADT, jotka määritellään arvoina ..., -2, -1, 0, 1, 2, ... sekä yhteen-, vähennys-, kerto- ja jakolaskutoimituksista sekä suurempi kuin, pienempi kuin jne., jotka käyttäytyvät tutun matematiikan mukaisesti (jakolasku huomioiden), riippumatta siitä, kuinka tietokone esittää kokonaisluvut. Käyttäytyminen sisältää erilaisten aksioomien noudattamisen (yhteenlaskujen assosiatiivisuus ja kommutatiivisuus jne.) sekä operaatioiden ennakkoehdot (ei voi jakaa nollalla). Tyypillisesti kokonaisluvut esitetään tietorakenteessa binäärilukuina, useimmiten kahden komplementtina, mutta ne voivat olla binäärikoodattuja desimaalilukuja tai yhden komplementteja. Useimmissa tarkoituksissa käyttäjä voi työskennellä abstraktion kanssa konkreettisen esitystavan sijaan ja käyttää tietoja ikään kuin tyyppi olisi abstrakti.
ADT ei koostu vain laskutoimituksista, vaan myös arvojen määrittelyjoukoista ja rajoituksista määriteltyjä laskutoimituksia varten. "Rajapinta" viittaa tyypillisesti vain laskutoimituksiin ja ehkä joihinkin toimintojen rajoituksiin, kuten ennakko- ja jälkiehtoihin; mutta ei muihin rajoituksiin, kuten toimintojen välisiin suhteisiin.
Esimerkiksi abstrakti pino, joka on "viimeksi sisään, ensimmäiseksi ulos" -rakenne, voidaan määrittää kolmella toiminnolla: push: lisää alkion pinon päällimmäiseksi; pop: poimii pinon päällimmäisen alkion; ja peek tai top: palauttaa pinon päällimmäisen alkion poistamatta sitä. Abstraktilla jonolla, joka on "ensimmäiseksi sisään, ensimmäiseksi ulos" -rakenne, on myös kolme toimintoa: enqueue: lisää alkion jonon viimeiseksi; dequeue: poimii jonon ensimmäisen alkion; ja front, joka käsittelee jonon ensimmäistä alkiota. Jos nämä olisivat rakenteiden koko määritelmät, näitä kahta tietorakennetta ja niiden erilaista odotettua järjestyskäyttäytymistä ei voitaisi erottaa toisistaan. Siten käyttöön otetaan rajoitus, joka pinolle määrittää, että jokainen pop- käsky palauttaa (ja poistaa) aina viimeksi työnnetyn alkion, johon ei ole vielä käytetty pop- käskyä, ja jonolle (päinvastoin) määrittää, että pop toimii ensimmäiseksi lisätylle alkiolle.
Algoritmien tehokkuutta analysoitaessa voidaan myös määritellä, että kaikki toiminnot vievät saman ajan riippumatta siitä, kuinka monta alkiota pinoon on työnnetty ja että pino käyttää vakiomäärää tallennustilaa kullekin elementille. Aikarajoja ei kuitenkaan aina pidetä osana ADT:n määritelmää.
Johdanto.
Abstraktit tietotyypit ovat puhtaasti teoreettisia kokonaisuuksia, joita käytetään (muun muassa) yksinkertaistamaan abstraktien algoritmien kuvausta, luokittelemaan ja arvioimaan tietorakenteita sekä kuvaamaan muodollisesti ohjelmointikielten tyyppijärjestelmiä. ADT voidaan kuitenkin toteuttaa tietyillä tietotyypeillä tai tietorakenteilla, monin tavoin ja monilla ohjelmointikielillä; tai kuvailtuna virallisella määrityskielellä. ADT:t toteutetaan usein moduuleina: moduulin käyttöliittymä ilmoittaa ADT-toimintoja vastaavat proseduurit, joskus rajoituksia kuvaavilla kommenteilla. Tämä tiedon piilotus menetelmä mahdollistaa moduulin toteutuksen muuttamisen asiakasohjelmia häiritsemättä.
Termiä abstrakti tietotyyppi voidaan pitää myös useiden algebrallisten rakenteiden, kuten hilan, ryhmien ja renkaiden, yleisenä lähestymistapana. Abstraktien tietotyyppien käsite liittyy tiedon abstraktion käsitteeseen, joka on tärkeä olio-ohjelmoinnissa ja sopimuspohjaisessa ohjelmoinnissa.