Sólin Sólin Rís 07:58 • sest 18:31 í Reykjavík
Tunglið Tunglið Rís 00:00 • Sest 00:00 í Reykjavík
Flóð Flóð Árdegis: 09:00 • Síðdegis: 21:18 í Reykjavík
Fjaran Fjara Árdegis: 02:48 • Síðdegis: 15:22 í Reykjavík
Sólin Sólin Rís 07:58 • sest 18:31 í Reykjavík
Tunglið Tunglið Rís 00:00 • Sest 00:00 í Reykjavík
Flóð Flóð Árdegis: 09:00 • Síðdegis: 21:18 í Reykjavík
Fjaran Fjara Árdegis: 02:48 • Síðdegis: 15:22 í Reykjavík
LeiðbeiningarTil baka

Sendu inn spurningu

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=

Hvað er algrím og hvernig nýtist það í tölvufræði?

Snorri Agnarsson

Algrím er forskrift eða lýsing, á einhvers konar læsilegu mannamáli, sem segir glöggum lesanda hvernig leysa megi tiltekið reiknivandamál. Reiknivandamál er þá í víðum skilningi hvert það vandamál sem felst í að vinna úr tilteknum gerðum gagna og fá önnur gögn sem niðurstöður. Al-Khowârizmî ritaði því algrím samkvæmt þessari skilgreiningu. Til að nota algrím í tölvu verðum við fyrst að útfæra (forrita) algrímið í forritunarmáli sem tölvan getur unnið með. Og almennt er tölvuhugbúnaður samansafn af alls konar útfærslum á ýmsum algrímum sem í heild uppfylla okkar þarfir, þegar vel tekst til. Eldri orðmyndin, algorism, merkti hins vegar á sínum tíma aðferð til að reikna með arabískar tölur, sem við köllum yfirleitt tugatölur í dag. Algóristar voru þá þeir sem notuðu arabískar tölur í útreikningum. En abakistar voru aftur á móti þeir sem notuðu reiknigrind (abacus) til útreikninga. Við erum því flest algóristar nú á dögum og þykir það víst ekki lengur merkilegt.

Við kunnum því flestöll nokkur allflókin algrím, algrímin fyrir reikniaðgerðirnar fjórar, sem eru meðal upphaflegu algórismanna. Algrímið fyrir deilingu margra stafa talna er til að mynda með flóknari algrímum, trúlega flóknasta algrímið meðal þeirra algríma sem flestir læra. Og margföldunaralgrímið sem við lærum sem börn er kannski það næstflóknasta.

Oft eru til fjölmörg algrím fyrir tiltekið vandamál. Og algrím eru misgóð á ýmsan hátt. Sum eru nákvæmari en önnur, til dæmis þegar um flókna tölulega útreikninga er að ræða, eða almennt þegar ekki er raunhæft að finna nákvæmlega rétta lausn. Sum algrím eru hægvirk og önnur hraðvirk.

Verulegur hluti af menntun tölvunarfræðinga felst í að viða að sér þekkingu um algrím og verða sér úti um dómgreind á gæði algríma, bæði eigin og annarra.

Val algríma og hönnun þeirra getur skipt sköpum um raunhæfni þess að tölvuvæða verkefni. Algengt er að hægvirkt algrím taki svo langan tíma að leysa tiltekið vandamál að sólin væri útbrunnin áður en ofurtölva gæti skilað svari. En hraðvirkt algrím fyrir sama vandamál getur oft reiknað svarið á örskömmum tíma á hægvirkri tölvu. Og réttmæti algríma getur að sjálfsögðu einnig skipt sköpum. Til dæmis hafa röng algrím í stýritölvum fyrir lyftur orðið fólki að bana.



Algrím notað til hjálpar þegar lampi virkar ekki

Dæmi um tiltölulega hægvirkt algrím er eftirfarandi margföldunaralgrím:

Forsendur: Gefnar eru tvær heiltölur n og m, ekki minni en núll.
Markmið: Að skila margfeldinu nm.
Aðferð:
Skref 1:
[Frumstillingar.] Gefum breytunni s gildið núll og gefum breytunni i gildið n.
(Breytur þessar geta síðar, eins og aðrar breytur í algrímum, fengið annað gildi. Þær halda síðan hverju gildi uns þær fá ný í öðru skrefi. Athugið að breyta í algrími er ekki alveg það sama og breyta í stærðfræði. Í stærðfræðinni stendur breyta oftast fyrir óþekkt gildi, en í algrími er breyta oftast nokkurs konar geymsluhólf fyrir þekkt gildi og reikniniðurstöður. En við geymum oft mismunandi gildi í sömu breytu á mismunandi tímum.)
Skref 2:
[Er niðurstaða komin?] Ef i er núll þá er s jafnt margfeldinu nm og við hættum þá og skilum s.
Skref 3:
[Minnkum i og stækkum s.] Minnkum i um einn og leggjum m við s (i og s fá sem sé bæði ný gildi). Stökkvum síðan til baka í skref 2.

Þetta er mjög hægvirkt margföldunaralgrím ef tölurnar eru stórar því við verðum að fara margar umferðir og framkvæma fjölmargar aðgerðir áður en niðurstaða næst. Til dæmis getum við rakið framgang útreikninganna með því að líta á gildi breytanna i og s í skrefi 2 í gegnum þær 124 umferðir sem fara þarf ef n er 123 og m er 345.

Umferð Gildi i Gildi s
1 123 0
2 122 345
3 121 690
4 120 1035
. . .
. . .
. . .
121 3 41400
122 2 41745
123 1 42090
124 0 42435

Réttmæti þessa algríms má staðfesta með því að sannreyna að í skrefi 2 gildir ávallt jafnan nm = s+im. Þar með er ljóst að þegar við hættum þá er s jafnt nm, þar eð i er þá núll.

Eftirfarandi margföldunaralgrím, sem hefur sömu forsendur og markmið, er aftur á móti vel hraðvirkt:

Aðferð:
Skref 1:
[Frumstillingar.] Gefum breytunni s gildið núll, breytunni a gildið n og breytunni b gildið m.
Skref 2:
[Er niðurstaða komin?] Ef a er núll þá inniheldur breytan s margfeldið nm og við hættum því og skilum s.
Skref 3:
[Stækkum s ef við á.] Ef a er oddatala þá stækkum við s um b.
Skref 4:
[Minnkum a og stækkum b.] Helmingum a (ef a er oddatala þá sleppum við einfaldlega afgangnum, svo útkoman sé ávallt heiltala), tvöföldum b og stökkvum síðan til baka í skref 2.

Sem dæmi um notkun þessa algríms getum við litið á gildin í breytunum a, b og s í skrefi 2, miðað við að n sé 123 og m sé 345, eins og þau gildi breytast í hverri umferð útreikninganna.

Umferð Gildi a Gildi b Gildi s
1 123 345 0
2 61 690 345
3 30 1380 1035
4 15 2760 1035
5 7 5520 3795
6 3 11040 9315
7 1 22080 20355
8 0 44160 42435

Gildi breytunnar s í síðustu umferð í skrefi 2 er hér 42435, sem er einmitt margfeldi 123 og 345. Þetta margföldunaralgrím byggist að verulegu leyti á helmingun og tvöföldun. Það hefur þann stóra kost að notendur þess þurfa ekki að kunna margföldunartöfluna.

Réttmæti algrímsins má staðfesta með því að sannreyna að í skrefi 2 gildir ávallt jafnan nm = s+ab. Þar með er ljóst að þegar við hættum, þegar a er núll, þá er s jafnt nm.

Algrímið er eldgamalt og var notuð í Egyptalandi til forna. Það er stundum kallað rússneska bændaaðferðin, því sagt er að rússneskir smábændur eða leiguliðar á dögum keisaranna hafi notað þetta algrím. Algrímið er enn í notkun í einföldum reiknivélum og stýritölvum. Náskylt algrím er notað í sumum reikningum í tölvudulritun nú til dags.

Takið eftir að niðurstaðan 42435 fæst með því að leggja saman þau gildi í b-dálkinum þar sem gildið til hliðar, í a-dálkinum, er oddatala. Það er einmitt þannig sem rússnesku bændurnir reiknuðu. Þeir reiknuðu margfeldið með því að skrifa niður eftirfarandi runu:

Gildi a Gildi b
123 345
61 690
30 1380
15 2760
7 5520
3 11040
1 22080

Síðan lögðu þeir saman gildin í b-dálkinum, en slepptu þeim gildum þar sem samsvarandi gildi í a-dálki er slétt tala. Í þessu dæmi er aðeins eitt slíkt gildi, 1380, og er það auðkennt með gegnumstrikun.

Margfeldi talnanna 10 og 12 hefðu þeir getað reiknað með eftirfarandi runu:

Gildi a Gildi b
10 12
5 24
2 48
1 96

Margfeldið fæst þá sem summan 24+96=120.

Þessi runa gefur sama margfeldi:

Gildi a Gildi b
12 10
6 20
3 40
1 80

Margfeldið fæst þá sem summan 40+80=120.

Í forritunarmálinu Java má forrita algrímið á eftirfarandi hátt:

// Gefnar eru heiltölurnar n og m,

// sem eru ekki neikvæðar

s=0; a=n; b=m;

while( a!=0 ) {

if( a%2==1 ) {

s = s+b;

}

a = a/2;

b = 2*b;

}

// Þegar hér er komið þá er s=nm

Einnig má forrita algrímið á mjög svipaðan hátt í íslenska forritunarmálinu Fjölni:

;; Gefnar eru heiltölurnar n og m,

;; sem eru ekki neikvæðar

s:=0, a:=n, b:=m,

meðan a<>0 lykkja

ef a%2=1 þá

s := s+b,

eflok,

a := a/2,

b := 2*b,

lykkjulok,

;; Þegar hér er komið þá er s=nm

Meðal elstu þekktu algríma eru hin fornu algrím Evklíðs til að reikna stærsta sameiginlega deili tveggja talna og til að reikna minnsta samnefnara (minnsta sameiginlega margfeldi). Þessi algrím eru í notkun í tölvum í dag í örlítið breyttri mynd. Og þau eru reyndar ekki aðeins notuð í útreikningum með tölur, heldur einnig til reikninga með flóknari stærðfræðileg fyrirbæri svo sem margliður af ýmsum gerðum. En til eru mun eldri algrím. Til dæmis kunnu Babýloníumenn til forna hraðvirkt algrím til að reikna ræðar nálganir á kvaðratrótum. Og vafalaust eru mörg forn algrím gleymd.

Meðal mest notuðu algríma eru ýmis algrím til að raða runum gilda í vaxandi eða minnkandi röð. Þar má nefna röðunaralgrímið quicksort, sem lýst er annars staðar á vísindavefnum.

Margt af því sem hér kemur fram má finna í bókum Donald E. Knuth, The Art of Programming, bindum I og III.

Frekara lesefni af Vísindavefnum:

Mynd: Skýringarmynd - Sótt 22.07.10

Höfundur

Snorri Agnarsson

prófessor í tölvunarfræði við HÍ

Útgáfudagur

14.3.2001

Spyrjandi

Ólafur Guðmundsson

Tilvísun

Snorri Agnarsson. „Hvað er algrím og hvernig nýtist það í tölvufræði?“ Vísindavefurinn, 14. mars 2001, sótt 8. október 2024, https://visindavefur.is/svar.php?id=1378.

Snorri Agnarsson. (2001, 14. mars). Hvað er algrím og hvernig nýtist það í tölvufræði? Vísindavefurinn. https://visindavefur.is/svar.php?id=1378

Snorri Agnarsson. „Hvað er algrím og hvernig nýtist það í tölvufræði?“ Vísindavefurinn. 14. mar. 2001. Vefsíða. 8. okt. 2024. <https://visindavefur.is/svar.php?id=1378>.

Chicago | APA | MLA

Senda grein til vinar

=

Hvað er algrím og hvernig nýtist það í tölvufræði?
Algrím er forskrift eða lýsing, á einhvers konar læsilegu mannamáli, sem segir glöggum lesanda hvernig leysa megi tiltekið reiknivandamál. Reiknivandamál er þá í víðum skilningi hvert það vandamál sem felst í að vinna úr tilteknum gerðum gagna og fá önnur gögn sem niðurstöður. Al-Khowârizmî ritaði því algrím samkvæmt þessari skilgreiningu. Til að nota algrím í tölvu verðum við fyrst að útfæra (forrita) algrímið í forritunarmáli sem tölvan getur unnið með. Og almennt er tölvuhugbúnaður samansafn af alls konar útfærslum á ýmsum algrímum sem í heild uppfylla okkar þarfir, þegar vel tekst til. Eldri orðmyndin, algorism, merkti hins vegar á sínum tíma aðferð til að reikna með arabískar tölur, sem við köllum yfirleitt tugatölur í dag. Algóristar voru þá þeir sem notuðu arabískar tölur í útreikningum. En abakistar voru aftur á móti þeir sem notuðu reiknigrind (abacus) til útreikninga. Við erum því flest algóristar nú á dögum og þykir það víst ekki lengur merkilegt.

Við kunnum því flestöll nokkur allflókin algrím, algrímin fyrir reikniaðgerðirnar fjórar, sem eru meðal upphaflegu algórismanna. Algrímið fyrir deilingu margra stafa talna er til að mynda með flóknari algrímum, trúlega flóknasta algrímið meðal þeirra algríma sem flestir læra. Og margföldunaralgrímið sem við lærum sem börn er kannski það næstflóknasta.

Oft eru til fjölmörg algrím fyrir tiltekið vandamál. Og algrím eru misgóð á ýmsan hátt. Sum eru nákvæmari en önnur, til dæmis þegar um flókna tölulega útreikninga er að ræða, eða almennt þegar ekki er raunhæft að finna nákvæmlega rétta lausn. Sum algrím eru hægvirk og önnur hraðvirk.

Verulegur hluti af menntun tölvunarfræðinga felst í að viða að sér þekkingu um algrím og verða sér úti um dómgreind á gæði algríma, bæði eigin og annarra.

Val algríma og hönnun þeirra getur skipt sköpum um raunhæfni þess að tölvuvæða verkefni. Algengt er að hægvirkt algrím taki svo langan tíma að leysa tiltekið vandamál að sólin væri útbrunnin áður en ofurtölva gæti skilað svari. En hraðvirkt algrím fyrir sama vandamál getur oft reiknað svarið á örskömmum tíma á hægvirkri tölvu. Og réttmæti algríma getur að sjálfsögðu einnig skipt sköpum. Til dæmis hafa röng algrím í stýritölvum fyrir lyftur orðið fólki að bana.



Algrím notað til hjálpar þegar lampi virkar ekki

Dæmi um tiltölulega hægvirkt algrím er eftirfarandi margföldunaralgrím:

Forsendur: Gefnar eru tvær heiltölur n og m, ekki minni en núll.
Markmið: Að skila margfeldinu nm.
Aðferð:
Skref 1:
[Frumstillingar.] Gefum breytunni s gildið núll og gefum breytunni i gildið n.
(Breytur þessar geta síðar, eins og aðrar breytur í algrímum, fengið annað gildi. Þær halda síðan hverju gildi uns þær fá ný í öðru skrefi. Athugið að breyta í algrími er ekki alveg það sama og breyta í stærðfræði. Í stærðfræðinni stendur breyta oftast fyrir óþekkt gildi, en í algrími er breyta oftast nokkurs konar geymsluhólf fyrir þekkt gildi og reikniniðurstöður. En við geymum oft mismunandi gildi í sömu breytu á mismunandi tímum.)
Skref 2:
[Er niðurstaða komin?] Ef i er núll þá er s jafnt margfeldinu nm og við hættum þá og skilum s.
Skref 3:
[Minnkum i og stækkum s.] Minnkum i um einn og leggjum m við s (i og s fá sem sé bæði ný gildi). Stökkvum síðan til baka í skref 2.

Þetta er mjög hægvirkt margföldunaralgrím ef tölurnar eru stórar því við verðum að fara margar umferðir og framkvæma fjölmargar aðgerðir áður en niðurstaða næst. Til dæmis getum við rakið framgang útreikninganna með því að líta á gildi breytanna i og s í skrefi 2 í gegnum þær 124 umferðir sem fara þarf ef n er 123 og m er 345.

Umferð Gildi i Gildi s
1 123 0
2 122 345
3 121 690
4 120 1035
. . .
. . .
. . .
121 3 41400
122 2 41745
123 1 42090
124 0 42435

Réttmæti þessa algríms má staðfesta með því að sannreyna að í skrefi 2 gildir ávallt jafnan nm = s+im. Þar með er ljóst að þegar við hættum þá er s jafnt nm, þar eð i er þá núll.

Eftirfarandi margföldunaralgrím, sem hefur sömu forsendur og markmið, er aftur á móti vel hraðvirkt:

Aðferð:
Skref 1:
[Frumstillingar.] Gefum breytunni s gildið núll, breytunni a gildið n og breytunni b gildið m.
Skref 2:
[Er niðurstaða komin?] Ef a er núll þá inniheldur breytan s margfeldið nm og við hættum því og skilum s.
Skref 3:
[Stækkum s ef við á.] Ef a er oddatala þá stækkum við s um b.
Skref 4:
[Minnkum a og stækkum b.] Helmingum a (ef a er oddatala þá sleppum við einfaldlega afgangnum, svo útkoman sé ávallt heiltala), tvöföldum b og stökkvum síðan til baka í skref 2.

Sem dæmi um notkun þessa algríms getum við litið á gildin í breytunum a, b og s í skrefi 2, miðað við að n sé 123 og m sé 345, eins og þau gildi breytast í hverri umferð útreikninganna.

Umferð Gildi a Gildi b Gildi s
1 123 345 0
2 61 690 345
3 30 1380 1035
4 15 2760 1035
5 7 5520 3795
6 3 11040 9315
7 1 22080 20355
8 0 44160 42435

Gildi breytunnar s í síðustu umferð í skrefi 2 er hér 42435, sem er einmitt margfeldi 123 og 345. Þetta margföldunaralgrím byggist að verulegu leyti á helmingun og tvöföldun. Það hefur þann stóra kost að notendur þess þurfa ekki að kunna margföldunartöfluna.

Réttmæti algrímsins má staðfesta með því að sannreyna að í skrefi 2 gildir ávallt jafnan nm = s+ab. Þar með er ljóst að þegar við hættum, þegar a er núll, þá er s jafnt nm.

Algrímið er eldgamalt og var notuð í Egyptalandi til forna. Það er stundum kallað rússneska bændaaðferðin, því sagt er að rússneskir smábændur eða leiguliðar á dögum keisaranna hafi notað þetta algrím. Algrímið er enn í notkun í einföldum reiknivélum og stýritölvum. Náskylt algrím er notað í sumum reikningum í tölvudulritun nú til dags.

Takið eftir að niðurstaðan 42435 fæst með því að leggja saman þau gildi í b-dálkinum þar sem gildið til hliðar, í a-dálkinum, er oddatala. Það er einmitt þannig sem rússnesku bændurnir reiknuðu. Þeir reiknuðu margfeldið með því að skrifa niður eftirfarandi runu:

Gildi a Gildi b
123 345
61 690
30 1380
15 2760
7 5520
3 11040
1 22080

Síðan lögðu þeir saman gildin í b-dálkinum, en slepptu þeim gildum þar sem samsvarandi gildi í a-dálki er slétt tala. Í þessu dæmi er aðeins eitt slíkt gildi, 1380, og er það auðkennt með gegnumstrikun.

Margfeldi talnanna 10 og 12 hefðu þeir getað reiknað með eftirfarandi runu:

Gildi a Gildi b
10 12
5 24
2 48
1 96

Margfeldið fæst þá sem summan 24+96=120.

Þessi runa gefur sama margfeldi:

Gildi a Gildi b
12 10
6 20
3 40
1 80

Margfeldið fæst þá sem summan 40+80=120.

Í forritunarmálinu Java má forrita algrímið á eftirfarandi hátt:

// Gefnar eru heiltölurnar n og m,

// sem eru ekki neikvæðar

s=0; a=n; b=m;

while( a!=0 ) {

if( a%2==1 ) {

s = s+b;

}

a = a/2;

b = 2*b;

}

// Þegar hér er komið þá er s=nm

Einnig má forrita algrímið á mjög svipaðan hátt í íslenska forritunarmálinu Fjölni:

;; Gefnar eru heiltölurnar n og m,

;; sem eru ekki neikvæðar

s:=0, a:=n, b:=m,

meðan a<>0 lykkja

ef a%2=1 þá

s := s+b,

eflok,

a := a/2,

b := 2*b,

lykkjulok,

;; Þegar hér er komið þá er s=nm

Meðal elstu þekktu algríma eru hin fornu algrím Evklíðs til að reikna stærsta sameiginlega deili tveggja talna og til að reikna minnsta samnefnara (minnsta sameiginlega margfeldi). Þessi algrím eru í notkun í tölvum í dag í örlítið breyttri mynd. Og þau eru reyndar ekki aðeins notuð í útreikningum með tölur, heldur einnig til reikninga með flóknari stærðfræðileg fyrirbæri svo sem margliður af ýmsum gerðum. En til eru mun eldri algrím. Til dæmis kunnu Babýloníumenn til forna hraðvirkt algrím til að reikna ræðar nálganir á kvaðratrótum. Og vafalaust eru mörg forn algrím gleymd.

Meðal mest notuðu algríma eru ýmis algrím til að raða runum gilda í vaxandi eða minnkandi röð. Þar má nefna röðunaralgrímið quicksort, sem lýst er annars staðar á vísindavefnum.

Margt af því sem hér kemur fram má finna í bókum Donald E. Knuth, The Art of Programming, bindum I og III.

Frekara lesefni af Vísindavefnum:

Mynd: Skýringarmynd - Sótt 22.07.10...