Hyppää sisältöön
    • Suomeksi
    • In English
Trepo
  • Suomeksi
  • In English
  • Kirjaudu
Näytä viite 
  •   Etusivu
  • Trepo
  • Kandidaatintutkielmat
  • Näytä viite
  •   Etusivu
  • Trepo
  • Kandidaatintutkielmat
  • Näytä viite
JavaScript is disabled for your browser. Some features of this site may not work without it.

Kruskalin ja Primin algoritmien vertailu pienimmän virittävän puun etsimisessä

Rantanen, Juuso (2019)

 
Avaa tiedosto
Rantanen.pdf (1.008Mt)
Lataukset: 



Rantanen, Juuso
2019

Tietotekniikka
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2019-04-18
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-201904181416
Tiivistelmä
Graafiteoria on matematiikan osa-alue, jota hyödynnetään laajasti useilla muilla tieteenaloilla. Virittävät puut ovat osa graafiteoriaa. Virittäviä puita käytetään usein suunnittelun apuna, sillä reaalimaailman asioita voidaan monesti mallintaa graafien avulla. Pienimpiä virittäviä puita etsitään graafeista algoritmien avulla ja niiden löytämiseen on tarjolla useita eri algoritmeja. Tässä työssä tutkittiin ja vertailtiin kahta pienimmän virittävän puun etsimiseen käytettyä Kruskalin algoritmia ja Primin algoritmia. Ohjelmoitujen algoritmien tehokkuuksia sekä toteutuksia tutkittiin ja vertailtiin toisiinsa tarkoituksena selvittää niiden tehokkuutta pienintä virittävää puuta etsittäessä eri kokoisissa graafeissa. Molempien algoritmitien asymptoottinen tehokkuus vastasi odotettua asymptoottista tehokkuutta. Lisäksi molemmat algoritmit olivat mahdollisia toteuttaa käyttämällä C++-ohjelmointikielen standardikirjastoa ja standardikirjaston sisältämiä tietorakenteita. Tehokkuuksia vertailtaessa Kruskalin algoritmi oli tehokkaampi kuin Primin algoritmi kaikissa tilanteissa. Lisäksi Kruskalin algoritmin optimaalinen toteuttaminen oli helpompaa kuin Primin, joka olisi vaatinut joko kolmannen osapuolen kirjastoja tai oman prioriteettijonon toteuttamista.
Kokoelmat
  • Kandidaatintutkielmat [5755]
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste
 

 

Selaa kokoelmaa

TekijätNimekkeetTiedekunta (2019 -)Tiedekunta (- 2018)Tutkinto-ohjelmat ja opintosuunnatAvainsanatJulkaisuajatKokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste