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!
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:
Snorri Agnarsson. „Hvað er algrím og hvernig nýtist það í tölvufræði?“ Vísindavefurinn, 14. mars 2001, sótt 24. nóvember 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. 24. nóv. 2024. <https://visindavefur.is/svar.php?id=1378>.
Sólin
Rís 10:26 • sest 16:02
Tunglið
Rís 01:04 • Sest 15:19
Flóð
Árdegis: 01:05 • Síðdegis: 13:31
Fjara
Árdegis: 07:12 • Síðdegis: 20:04
