Algoritem: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m ustvarjeno s prevodom strani »Algorithm« |
m ustvarjeno s prevodom strani »Algorithm« |
||
Vrstica 26:
Na splošno je program lahko algoritem le v primeru, če se sčasoma ustavi<ref>Stone simply requires that "it must terminate in a finite number of steps" (Stone 1973:7–8).</ref> - čeprav so včasih [[Neskončna zanka|neskončne zanke]] tudi zaželene.
Prototipni primer algoritma je [[Evklidov algoritem]], ki se uporablja za določitev največjega skupnega delitelja dveh celih števil; primer (obstajajo tudi drugi) je opisan v zgornjem [[Diagram poteka|diagramu poteka]] in
Spodnji citat iz
{{Harvard citation text|Boolos|Jeffrey|1974, 1999|ref=CITEREFBoolosJeffrey1999}} ponuja neformalni pomen besede "algoritem":<blockquote>Nobeno človeško bitje ne more pisati dovolj hitro, dovolj dolgo ali majhno† (†"majhno in še manjše brez omejitve ... poskušali bi pisati na molekule, na atome, na elektrone"), da bi zapisalo enega za drugim imena vseh članov preštevne neskončne množice. Toda ljudje lahko naredimo v primeru nekaterih preštevnih neskončnih množic
Vrstica 126:
# Ko v naboru ni nobene številke, ki bi jo lahko ponovil, upoštevajte, da je trenutno največje število največje število nabora.
''(Kvazi) formalni opis:''
Input: A list of numbers ''L''.
Output: The largest number in the list ''L''.
Vrstica 140:
=== Evklidov algoritem ===
[[Slika:Euclid's_algorithm_Book_VII_Proposition_2_2.png|levo|sličica|263x263_pik| Primer diagrama Evklidovega algoritma iz TL Heath (1908). Evglid je problem definiral geometrijsko, kot problem iskanja "skupne mere" za dve daljici dane dolžine. To skupno mero je iskal tako, da je "odštel" krajšo daljico od daljše, in postopek ponavljal. Nikomah daje primer za 49 in 21: "Manjše odštejem od večjega; 28 je levo; nato spet od tega odštejem isto 21 (ker je to mogoče); 7 je levo; to odštejem od 21, 14 je levo; od tega spet odštejem 7 (ker je to mogoče); 7 je levo, 7 pa ni mogoče odšteti od 7. " Heath je ta primer komentiral: "Zadnji stavek zanimiv, vendar je njegov pomen dovolj očiten, kot tudi pomen stavka o končanju "na eni in isti številki ". (Heath 1908:300).]]
[[Evklid|Evklidov]] algoritem za izračun [[Največji skupni delitelj|največjega skupnega delitelja]] (GCD) dveh števil se pojavi kot Trditev II v Knjigi VII ("Elementarna teorija števil") njegovih ''[[Elementi (Evklid)|Elementov]]''.<ref>Heath 1908:300; Hawking's Dover 2005 edition derives from Heath.</ref> Evklid problem zastavi takole: "Dani sta dve števili, ki si nista praštevili, da bi našli njuno največjo skupno mero".
Da je Evklidove metode uspešna, morajo začetne dolžine izpolnjevati dve zahtevi: (i) dolžine ne smejo biti enake nič IN (ii) odštevanje mora biti "pravilno"; tj. test mora zagotoviti, da se od obeh števil odšteje manjše od večjega (ali pa sta lahko enaki, tako da rezultat odštevanja da nič).
Izvirni Evklidov dokaz dodaja še tretjo zahtevo: dolžini ne smeta biti praštevili eni drugi. Evklid je podal to zahtevo zato, da je lahko zgradil [[reductio ad absurdum]] dokaz, da je skupna mera obeh števil v resnici ''največja''.<ref>Euclid covers this question in his Proposition 1.</ref> Nikomahov algoritem je enak Evklidovemu, ko sta števili ena drugi praštevili, dobi število "1" za njuno skupno mero. Torej, če smo natančni, je to v resnici Nikomahov algoritem.
[[Slika:Euclids-algorithm-example-1599-650.gif|desno|sličica|350x350_pik| Grafični prikaz Evklidovega algoritma za iskanje največjega skupnega delitelja za 1599 in 650.<syntaxhighlight lang="text" highlight="1,5">
1599 = 650×2 + 299
650 = 299×2 + 52
299 = 52×5 + 39
52 = 39×1 + 13
39 = 13×3 + 0</syntaxhighlight>]]
==== Računalniški jezik za Evklidov algoritem ====
Le nakaj ''tipov'' inštrukcij je potrebnih za izvajanje Evklidovega algoritm - nekaj logičnih testov (pogojni GOTO), brezpogojni GOTO, prireditev (zamenjava) in odštevanje.
* ''Lokacijo'' simbolizirajo velike črke, npr. S, A itd.
* Spreminjajoča se količina (število) v lokaciji je napisana z malimi črkami in je (običajno) povezana z imenom lokacije. Na primer, lokacija L na začetku lahko vsebuje število ''l'' = 3009.
==== Neeleganten program za Evklidov algoritem ====
[[Slika:Euclid's_algorithm_Inelegant_program_1.png|desno|sličica|349x349_pik| "Neeleganten" je prevod Knuthove različice algoritma z odštevanjem-zanko na osnovi ostanka, ki nadomešča njegovo uporabo delitve (ali inštrukcijo "modul"). Izvira iz Knutha 1973: 2–4. Glede na dve števili lahko "Nneeleganten" izračuna g.c.d. v manj korakih kot "Eleganten".]]
Naslednji algoritem je formuliran kot Knuthova štiristopenjska različica Evkllidovega in Nikomahaovega algoritma, vendar namesto da bi za iskanje ostanka uporabil deljenje, uporablja zaporedna odštevanja krajše dolžine ''s'' od preostale dolžine ''r,'' dokler ''r'' ni manjše od ''s''. Opis na višjii ravni, prikazan v krepkem tisku, je povzet po Knuth 1973: 2–4:
'''VHOD''' :
{{Vidno sidro|1|el1}} [V dve lokaciji L in S vstavite število ''l'' in ''s,'' ki predstavljata dve dolžini]:
VHOD L, S
{{Vidno sidro|2|el2}} [Inicializiraj R: napravi preostalo dolžino ''r'' enako začetni/inicialni/vhodni dolžini ''l'']:
R ← L
'''E0: [Zagotovite, da je ''r'' ≥ ''s''.]'''
{{Vidno sidro|3|el3}} [Zagotovite, da je majše od dveh števil v S in večje v R]:
IF R > S THEN
je vsebina L večje število, zato preskoči na zamenjevalne-korake [[Algoritem#4|4]], [[Algoritem#5|5]] in [[Algoritem#6|6]]:
GOTO korak [[Algoritem#6|6]]
ELSE
zamenjaj vsebini R in S.
{{Vidno sidro|4|el4}} L ← R (ta prvi korak je redundanten, ampak uporaben za kasneje).
{{Vidno sidro|5|el5}} R ← S
{{Vidno sidro|6|el6}} S ← L
'''E1: [Najdi ostanek]''' : Dokler je preostala dolžina ''r'' v R manjša od krajše dolžine ''s'' v S, ponavljajte odštevanje merilnega števila ''s'' v S od preostale dolžine ''r'' v R.
{{Vidno sidro|7|el7}} IF S > R THEN
merjenje je zaključeno zato
GOTO [[Algoritem#10|10]]
ELSE
ponovno merjenje,
{{Vidno sidro|8|el8}} R ← R − S
{{Vidno sidro|9|el9}} [Ostanek-zanka]:
GOTO [[Algoritem|7]].
'''E2: [Ali je preostanek nič?]''' : ALI (i) je bil zadnja mera točna, ostanek v R je enak nič in program pa se lahko ustavi ALI (ii) pa se mora algoritem nadaljevati: zadnja mera je pustila ostanek v R manjši kot je merilno število v S.
{{Vidno sidro|10|el10}} IF R = 0 THEN
zaključeno zato
GOTO [[Algoritem#15|korak]] [[Algoritem#15|15]]
ELSE
CONTINUE TO [[Algoritem#11|korak]] 11,
'''E3: [Izmenjava ''s'' in ''r'' ]''' : Srž Evklidovega algoritma. Uporabite ostankek ''r,'' da izmerite katero je bilo prejšnje manjše število ''s''; L služi kot začasna lokacija.
{{Vidno sidro|11|el11}} L ← R
{{Vidno sidro|12|el12}} R ← S
{{Vidno sidro|13|el13}} S ← L
{{Vidno sidro|14|el14}} [Ponovi postopek meritve]:
GOTO [[Algoritem#7|7]]
'''IZHOD''' :
{{Vidno sidro|15|el15}} [Narejeno. S vsebuje [[največji skupni delitelj]]]:
PRINT S
'''KONČANO''' :
{{Vidno sidro|16|el16}} HALT, END, STOP.
The following version of Euclid's algorithm requires only six core instructions to do what thirteen are required to do by "Inelegant"; worse, "Inelegant" requires more types of instructions.[clarify] The flowchart of "Elegant" can be found at the top of this article. In the (unstructured) Basic language, the steps are numbered, and the instruction <syntaxhighlight lang="cbmbas" inline="">LET [] = []</syntaxhighlight> is the assignment instruction symbolized by ←.
== Klasifikacije ==
| |||