Mitä ovat kaaviot, tietojenkäsittelytieteessä ja mitä niitä käytetään varten? Maallikkojen mieluiten mieluiten.
Olen lukenut määritelmän Wikipediasta :
Tietojenkäsittelytieteessä kaavio on abstrakti tietotyyppi, joka on tarkoitettu toteuttamaan kaavio ja hypergraafikäsitteet matematiikasta.
Kaaviotietorakenne koostuu äärellisestä (ja mahdollisesti muutettavasta ) joukko järjestettyjä pareja, joita kutsutaan reunoiksi tai kaariksi, tietyistä kokonaisuuksista, joita kutsutaan solmuiksi tai pisteiksi. Kuten matematiikassa, reunan (x, y) sanotaan osoittavan tai siirtyvän x: stä y: hen. Solmut voivat olla osa kuvaajan rakennetta tai ne voivat olla ulkoisia kokonaisuuksia, joita edustavat kokonaislukuindeksit tai viitteet.
mutta etsin vähemmän muodollista, helpommin ymmärrettävää määritelmää.
Kommentit
- Tarkoitatko graafisesti tietorakennetta?
- Kyllä, anteeksi. Tässä kuvatut kaaviot fi.wikipedia.org/wiki/Graph_(abstract_data_type) , vain minä vähemmän muodollinen, helpommin ymmärrettävä määritelmä.
- @ Justin984 Wikipedia linkittää sulkeisiin (ja niitä on niin paljon) älä ’ toimi, suluissa ei ole ’ ei toimi hyvin linkkien Markdown-muodon kanssa. Lisää tulevaa tarvetta varten selvennyksiä kysymykseesi itse kysymyksessä, ei kommenteissa. Ne eivät ole ’ t näkyviä ja se ’ s helppo unohtaa niitä.
muistan yllä olevaa kommenttiasi kysymyksessä …
Vastaa
Täydellisen maallikon esimerkki voi olla Facebook . Sinun, ystäviesi ja heidän ystäviään jne. kutsutaan yhdessä nimellä sosiaalinen kaavio .
Tässä ”kaaviossa” ihmisiä pidetään solmut kaaviosta ja
reunat ovat ystävyyslinkkejä .
Facebookissa ystävä on kaksisuuntainen suhde (A on B ”s Friend => B on A” s ystävä), joten kaavio on Ohjaamaton kaavio . Verkkoa, kuten Google+ tai Twitter, pidetään ohjattu kaavio , koska suhteen suuntaviivalla on merkitys tässä.
Kaikkia näitä kaavioita kutsutaan syklisiksi kaavioiksi, koska solmujen väliset suhteet voivat muodostaa jaksoja . Sukupuu on toisaalta erityinen kaavio, joka muun muassa on Asyklinen , koska sukupuun suhteellisuudessa ei voi olla syklejä. (Sitä kutsutaan teknisesti suunnatuksi asykliseksi kaaviona (DAG) , koska se on sekä suunnattu että asyklinen)
Tämän pitäisi kattaa kaikki kaavioiden sisältämät perussakeet, joten nyt sinun pitäisi pystyä seuraamaan muuta materiaalia kentällä.
kommentit
- voi ’ uskoa, että se ei ollut ’ t on mielestäni sitä mieltä, että se ’ s kutsui facebook-graafin apia. Hyvä esimerkki!
- Sukupuu ei syklinen? Sen ei pitäisi olla ’, mutta valitettavasti se on …
- @MarjanVenema, sukupuu on syklinen ? (Se ’ on suunnattu graafi, joten suunta on tärkeä syklien määrittelyssä, ja oletettavasti porrasuhteet eivät ole ’ ei todellakaan lasketa.)
- @dbaupp: Minulla ei ole halua mennä yksityiskohtiin tässä, joten mainitsen vain yhden ’ sana: insesti.
- @MarjanVenema, sinulta ’ puuttuu mielipiteeni.Suunnatun kaavion sykli on malli, kuten
A -> B -> C -> A(eli nuolien ympyrä), insesti antaa vainA -> B -> CjaA -> D -> C(eli timantti). Sukupuun sykli vaatii aikamatkaa.
Vastaus
Kaaviot ovat yksi tärkeimmistä matemaattisista käsitteistä. käytetään tietojenkäsittelytieteessä.
Olet nähnyt kaavioita monta kertaa. Kuvittele, että olet lentämässä lentoa kaupungista toiseen. Löydät väistämättä mukavan kiiltävän lehden lentoyhtiöltä istuimelta tasku edessäsi. Lehden takaosasta löytyy melkein aina kartta, joka kuvaa kaupunkeja, joita lentoyhtiö palvelee ympyröinä, ja lennot, jotka yhdistävät nämä kaupungit, ovat kaarevia viivoja. Tämä ”sa-kaavio! Kaupungit, jotka on esitetty ympyröinä, ovat tämän kaavion solmut ja lennot, jotka on esitetty kaarevina viivoina, ovat reunat. Kaaviot ovat vain asioita, joissa on solmut ja reunat, jotka yhdistävät solmut.
Voit koristella näitä yksinkertaisia kaavioita eri tavoin. Et halua nähdä vain joukkoa ympyröitä ja viivoja, kun katsot karttaa. Kyseisillä kaupungeilla on nimiä. Nimeämällä nämä kaupungit saat merkityn kaavion. (Voit myös merkitse reunat, esim. lento 1234.) Tietojenkäsittelytiede yhdistää tietoja usein solmuihin, joskus reunoihin, mutta se on vain tunnisteiden jatke. Se on edelleen merkitty kaavio. Toinen koriste on tulos, jos voit lentää suoraan kaupungista A kaupunkiin B, mutta ei kaupungista B kaupunkiin kaupunkiin A. Ilmeinen tapa kuvata tätä on laittaa nuoli kaupunkeja yhdistävään viivaan. tämän yksisuuntaisen suhteen kuvaamiseksi. Nyt sinulla on suunnattu kaavio.
Linkitetyt luettelot, puut, tilansiirtokaaviot ja monet muut tietojenkäsittelytieteen tietorakenteet ovat kaikki esimerkkejä kaavioista. Se on erittäin tehokas käsite.
Kommentit
- I ’ d laajennan esimerkkiä todellakin, että kaikki Esimerkissä kuvatut entiteetit voidaan kuvata kaavioiden pisteinä (kaupunki, taso, aikakauslehti, kartta jne.), itse kartta on vain yksi kärkipiste.
Vastaus
Parempi kysymys olisi ”Mihin ei käytetä kaavioita?”. Tietojenkäsittelytiede on monessa suhteessa graafien tutkimus.
Graafi on maallikoiden mielestä kokoelma mielivaltaisia abstrakteja objekteja, joita kutsutaan ”solmuiksi” tai ”pisteiksi” ja jotka edustavat yhteyspisteitä. Ne yhdistetään sitten ”polkujen” tai ”reunojen” kautta. Abstrakti tietotyyppi ”Graafi” on matemaattisen ”Graafin” toteutus. Joten pohjimmiltaan sinulla on solmuja ja reunoja kenttinäsi ja erilaisia toimintoja, joita voit suorittaa niillä. voi esimerkiksi lisätä uuden solmun kaavion kokoelmaan (tämä voi olla luettelo, taulukko tai jokin muu rakenne kielestä riippuen). Voit sitten linkittää kyseisen solmun olemassa oleviin solmuihin. Toimintoihin sisältyisi myös kaavion läpikäynti, sen tarkistaminen, ovatko kaksi solmua jakaneet reunan (ovat yhteydessä toisiinsa), arvojen noutaminen solmuista tai reunoista ja solmujen tai reunojen poistaminen kaaviosta.
Hyödyntämisen osalta Kaavioita käytetään kaikkialla. Verkostoituminen käyttää niitä erityisen paljon, mutta niitä löytyy keinotekoisesta älykkyydestä, tiedonlouhinnasta, pelinkehityksestä, geoinformatiikasta ja monista muista tieteenaloista. Muodollisessa tietojenkäsittelytieteessä he näkevät vielä enemmän käyttöä, nimittäin tapana edustaa tilaa.
Tehokkaasti kaikki, mitä voit edustaa yhteyksien joukona, voidaan esittää graafina ja toteuttaa ADT: n kautta joissakin lomake.
Tässä on esimerkkikuva, jonka tein:
Vastaus
Graafi on vain joukko objekteja, jotka on yhdistetty toisiinsa viivoiksi kutsuttuina viivoina.
Termi ”kaavio” on abstraktio ja yleistys monista ohjelmistokehityksessä käytetyt tietorakenteet. Linkitetyt luettelot, binaariset puut ja AST ovat kaikki kaavioita.
Periaatteessa kaikki objektikokoelmat, jotka on osoittimet, jotka yhdistävät objektit toisiinsa, on kaavio. Kun sinulla on kaavio, voit soveltaa siihen kaavioteorian periaatteita ratkaisemaan tiettyjä ongelmia .