Difference between revisions of "Reiknirit"

From Fab Lab Wiki - by NMÍ Kvikan
Jump to: navigation, search
(New page: '''Reiknirit''' er lausnaraðferð og skilgreint sem endanlegt mengi vel skilgreindra fyrirmæla til að leysa verkefni. Reiknirit skilar fyrirfram skilgreindri niðurstöðu að gefnu upp...)
 
 
Line 66: Line 66:
 
Reiknirit eru misskilvirk.  Til eru reiknirit sem tekur marga mannsaldra að leysa vandamál sem önnur skilvirkari reiknirit leysa á svipstundu.  Það er því mikilvægt ef leysa á stórt vandamál að reikniritið sé skilvirkt.  Skilvirkni er mæld í vaxtarhraða keyrslutíma, [[big Oh]], annars vegar og minnisnotkun hins vegar.  Þegar vandamálið sem leysa á er mjög lítið, t.d. að raða 10 stökum skiptir skilvirkni ekki öllu máli.
 
Reiknirit eru misskilvirk.  Til eru reiknirit sem tekur marga mannsaldra að leysa vandamál sem önnur skilvirkari reiknirit leysa á svipstundu.  Það er því mikilvægt ef leysa á stórt vandamál að reikniritið sé skilvirkt.  Skilvirkni er mæld í vaxtarhraða keyrslutíma, [[big Oh]], annars vegar og minnisnotkun hins vegar.  Þegar vandamálið sem leysa á er mjög lítið, t.d. að raða 10 stökum skiptir skilvirkni ekki öllu máli.
  
 +
== Kennslumyndbönd ==
 +
=== Introduction to Algorithms hjá MIT ===
 +
OpenCourseWare námskeiðið Introduction to Algorithms hjá MIT. (MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005)
  
:''Þessi grein var upprunalega fengin frá greininni "[http://is.wikipedia.org/wiki/Reiknirit Reiknirit]" á Wikipedia, Frjálsa alfræðiritinu. Sótt 7. júlí 2009.''
+
* [http://www.youtube.com/watch?v=JPyuH4qXLZ0&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 1]
 +
* [http://www.youtube.com/watch?v=whjt_N9uYFI&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 2]
 +
* [http://www.youtube.com/watch?v=-EQTVuAhSFY&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 3]
 +
* [http://www.youtube.com/watch?v=vK_q-C-kXhs&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 4]
 +
* [http://www.youtube.com/watch?v=0VqawRl3Xzs&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 5]
 +
* [http://www.youtube.com/watch?v=mR_RUjsJnV8&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 6]
 +
* [http://www.youtube.com/watch?v=JZHBa-rLrBA&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 7]
 +
* [http://www.youtube.com/watch?v=s7QSM_hlS1U&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 8]
 +
* [http://www.youtube.com/watch?v=vgELyZ9LXX4&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 9]
 +
* [http://www.youtube.com/watch?v=O3hI9FdxFOM&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 10]
 +
* [http://www.youtube.com/watch?v=RHyGlha7bjE&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 11]
 +
* [http://www.youtube.com/watch?v=kBwUoWpeH_Q&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 12]
 +
* [http://www.youtube.com/watch?v=qh5lSHCBiRs&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 13]
 +
* [http://www.youtube.com/watch?v=2RxCCEHlEys&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 14]
 +
* [http://www.youtube.com/watch?v=V5hZoJ6uK-s&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 15]
 +
* [http://www.youtube.com/watch?v=FPEMBWg_WlY&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 16]
 +
* [http://www.youtube.com/watch?v=xhG2DyCX3uA&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 17]
 +
* [http://www.youtube.com/watch?v=Ttezuzs39nk&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 18]
 +
* [http://www.youtube.com/watch?v=Sygq1e0xWnM&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 19]
 +
* [http://www.youtube.com/watch?v=PYvJmLKhM-Y&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 20]
 +
* [http://www.youtube.com/watch?v=F0VsQWWVWU4&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 22]
 +
* [http://www.youtube.com/watch?v=cJOHERGcGm4&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 23]
 +
* [http://www.youtube.com/watch?v=zjUDy6a5vx4&feature=SeriesPlayList&p=8B24C31197EC371C Fyrirlestur 24]
 +
 
 +
=== Data Structures and Algorithms hjá IIT ===
 +
Opið námskeið um reiknirit og [[gagnagrindur]] hjá [http://www.iit.ac.in IIT].
 +
 
 +
* [http://www.youtube.com/watch?v=zWg7U0OEAoE Lecture - 1 Introduction to Data Structures and Algorithms]
 +
* [http://www.youtube.com/watch?v=g1USSZVWDsY Lecture - 2 Stacks]
 +
* [http://www.youtube.com/watch?v=PGWZUgzDMYI Lecture - 3 Queues and linked lists]
 +
* [http://www.youtube.com/watch?v=BmayUdDaDYM Lecture - 4 Dictionaries]
 +
* [http://www.youtube.com/watch?v=KW0UvOW0XIo Lecture - 5 Hashing]
 +
* [http://www.youtube.com/watch?v=tORLeHHtazM Lecture - 6 Trees]
 +
* [http://www.youtube.com/watch?v=eWeqqVpgNPg Lecture - 7 Tree walks and traversals]
 +
* [http://www.youtube.com/watch?v=bvOYfDpk940 Lecture - 8 Ordered dictionaries]
 +
* [http://www.youtube.com/watch?v=KyMiqaA0ijM Lecture - 9 Deletion]
 +
* [http://www.youtube.com/watch?v=gtWw_8VvHjk Lecture - 10 Quick Sort]
 +
* [http://www.youtube.com/watch?v=mRGQylRWAsI Lecture - 11 AVL Trees]
 +
* ...
 +
* [http://www.youtube.com/watch?v=7FtGk9yr66A Lecture - 33 Prims Algorithm for minimum spanning trees]
 +
 
 +
:''Þessi grein er byggð á greininni "[http://is.wikipedia.org/wiki/Reiknirit Reiknirit]" á Wikipedia, Frjálsa alfræðiritinu. Sótt 7. júlí 2009.''
 
[[Category:Forritun]]
 
[[Category:Forritun]]

Latest revision as of 13:34, 7 July 2009

Reiknirit er lausnaraðferð og skilgreint sem endanlegt mengi vel skilgreindra fyrirmæla til að leysa verkefni. Reiknirit skilar fyrirfram skilgreindri niðurstöðu að gefnu upphafsskilyrði. Reiknirit eru einkum notuð í stærðfræði og tölvunarfræði við lausn vandamála.

Saga

Reiknirit er einnig kallað algrím eða algóriþmi. Uppruna orðsins algóriþmi má rekja til stærðfræðings sem var uppi á 10. öld, Abu Abdullah Muhammad bin Musa al-Khwarizmi. Al-Khwarizmi er af mörgum talinn upphafsmaður nútíma algebru og var hann sannfærður um að hægt væri að leysa öll stærðfræðileg vandamál ef þeim væri skipt upp í minni skref.

Eitt frægasta reiknirit allra tíma er reiknirit Evklíðs sem finnur stærsta sameiginlega deili tveggja heiltalna, en það var birt árið 300 fyrir Krist.

Fyrsta reikniritið sem skrifað var fyrir tölvur var skrifað af Ada Byron árið 1842, en það var aldrei útfært.

Framsetning reiknirita

Reiknirit eru oft í upphafi hönnunar skrifuð í sauðakóða sem er nokkurs konar millistig almenns ritmáls og forritunarmáls og er því óháð því forritunarmáli sem reikniritið verður útfært í. Það auðveldar útfærslu reikniritsins í hinum ýmsu forritunarmálum, enda er sauðakóðinn auðskiljanlegur öllum forriturum óháð forritunarbakgrunn þeirra.

Dæmi um reiknirit í sauðakóða:

 if tala er slétt tala then
 deila í tölu með tveimur
 else hækka tölu um einn heilan og deila svo í hana með tveimur
 end if
 skrifa tölu á skjá

Dæmi um sama reiknirit í C++

 if  (nr % 2 == 0) 
    nr = nr/2;
 
 else
    nr = (nr + 1) / 2;
  
 std::cout<<nr<<endl;

Nokkrar tegundir reiknirita

Reiknirit geta verið einföld þar sem þau eru framkvæmd í röð eins og farið sé eftir uppskrift. Reiknirit geta líka verið flóknari. Sum reiknirit nota samanburð og rökaðgerðir til að ákvarða næsta skref, sbr. dæmið hér að ofan, önnur nota lykkjur og ítrun og enn önnur eru endurkvæm. Til eru margar gerðir leitarreiknirita sem leita að tilteknu staki í lista t.d. Dæmi um slík reiknirit eru t.d. línuleg leit og tvíundarleit. Einnig eru til mörg röðunarreiknirit. Algengast þeirra er sennilega reikniritið quick-sort.

Dæmi um reiknirit sem notar lykkju:

Reikniritið margfaldar saman heiltölurnar frá 1 og til og með 9. Einnig kallað hrópfall.

 int nr = 1;
 
 for (int i = 2, i < 10, i++)  
 {
    nr = nr * i;
 ) 
 std::cout<<nr<<endl;

Dæmi um endurkvæmt reiknirit sem gerir það sama: Fallið kallar í sjálft sig með n-1 þar til n er minna en 1 og reiknar sig svo til baka.

 int factorial(n) 
  
 {
    if (n <= 1)
       return n;
    else
       return n * factorial(n-1);
 }

Greining reiknirita

Við greiningu reiknirita erum við að skoða hvort reiknirit sé ákjósanlegt. Þar er aðallega horft til tveggja þátta, einfaldleika og skilvirkni. Greining reiknirita er mjög mikilvæg þar sem við getum oft valið um fleiri en eitt reiknirit til lausnar á sama vandamáli. Það er mikilvægt að skilvirkni reiknirits sé skoðuð áður en það er útfært. Þá er notast við sauðakóða framsetningu reiknirits.

Einfaldleiki reiknirita

Einfalt reiknirit er auðvelt að útfæra, prófa, viðhalda og sýna fram á að það sé rétt. Kostir einfaldra reiknirita eru því margir en sé reiknirit mjög óskilvirkt og það eigi að nota til að leysa stórt vandamál er það í raun ónothæft þó það sé mjög einfalt.

Skilvirkni reiknirita

Reiknirit eru misskilvirk. Til eru reiknirit sem tekur marga mannsaldra að leysa vandamál sem önnur skilvirkari reiknirit leysa á svipstundu. Það er því mikilvægt ef leysa á stórt vandamál að reikniritið sé skilvirkt. Skilvirkni er mæld í vaxtarhraða keyrslutíma, big Oh, annars vegar og minnisnotkun hins vegar. Þegar vandamálið sem leysa á er mjög lítið, t.d. að raða 10 stökum skiptir skilvirkni ekki öllu máli.

Kennslumyndbönd

Introduction to Algorithms hjá MIT

OpenCourseWare námskeiðið Introduction to Algorithms hjá MIT. (MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005)

Data Structures and Algorithms hjá IIT

Opið námskeið um reiknirit og gagnagrindur hjá IIT.

Þessi grein er byggð á greininni "Reiknirit" á Wikipedia, Frjálsa alfræðiritinu. Sótt 7. júlí 2009.