§ 27. Definiția și proprietățile algoritmului
Subiectele principale ale paragrafului sunt:
♦ originea termenului "algoritm";
♦ executorul algoritmului;
♦ limbaj algoritmic;
♦ proprietățile algoritmului;
♦ definirea algoritmului;
♦ executarea formală a algoritmului;
♦ Care este programul.
Conceptul algoritmului este la fel de fundamental pentru informatica. precum și conceptul de informație. Prin urmare, este foarte important să o înțelegem.
Originea termenului "algoritm"
Cuvântul "algoritm" vine de la numele matematicianului restante al Orientului mijlociu, Mohammed al-Khwarizmi (787-850). El a fost oferit tehnici de efectuare a calculelor aritmetice cu numere cu numeroase valori (sunteți familiarizați cu ele din matematică școlară). Mai târziu în Europa, aceste tehnici au fost numite algoritmi, de la Algorithmi - ortografia latină a numelui al-Khwarizmi. În zilele noastre conceptul algoritmului este înțeles într-un mod mai larg, nu se limitează la calcule aritmetice.
Din paragraful anterior, ați aflat că un algoritm este o secvență de comenzi pentru controlul unui obiect. Am numit-o obiectul controlului sau executorul algoritmului. Ele pot fi atât un dispozitiv tehnic cât și o ființă vie.
Să luăm în considerare executorul-persoană. Pentru el, puteți formula un set de algoritmi, de exemplu, algoritmi de calcule aritmetice. Cu același succes, puteți să apelați algoritmilor o mulțime de instrucțiuni diferite, care să prescrie succesiunea acțiunilor unei persoane pentru a efectua orice lucrare. De exemplu, o rețetă este un algoritm pentru bucătar să gătească; instrucțiuni privind asamblarea unei mașini din detaliile designerului unui copil - un algoritm pentru un copil; instrucțiuni pentru utilizarea unui procesor de alimente - un algoritm pentru o gospodină.
Probabil nu v-ați gândit niciodată despre câți algoritmi știți. Experiența de viață a unei persoane crește odată cu creșterea numărului de algoritmi pe care el și-a stăpânit. De exemplu, pentru ca un copil să învețe cum să cumpere paine de la un magazin, trebuie să-i spună mai întâi (și să arate mai bine) cum se face. După ce a stăpânit "algoritmul de cumpărare a pâinii", va continua să realizeze cu succes această lucrare.
Căutarea unei tactici câștigătoare și, prin urmare, a algoritmului unui joc simplu este o sarcină interesantă și utilă. Luați în considerare unul dintre aceste jocuri, care se numește jocul Bachet.
Două joacă. Înainte de ele, 21 de articole, să zicem, pietre (de asemenea, pot fi 11, 16, 26 etc.). Jucătorii iau la rândul lor pietrele. Într-o mișcare puteți lua 1, 2, 3, 4 pietre. Cel care ia ultima piatră pierde.
Există o tactică câștigătoare pentru jucătorul care ia pietrele în al doilea rând. Aceasta constă în a lua o astfel de cantitate de pietre, care suplimentează numărul de pietre luate de adversar în cursul anterior, la cinci. Acest algoritm poate fi descris ca o secvență de comenzi:
Alg Game Bachet
devreme
1. Acordați mutarea adversarului.
2. A lua atâtea pietre care, în sumă cu cursul anterior al adversarului, sa dovedit a fi 5.
3. Dacă există o piatră rămasă, anunțați-vă câștigurile, altfel reveniți la execuția echipei 1.
joc
Un jucător care urmărește cu strictețe acest algoritm va câștiga întotdeauna, chiar dacă nu înțelege de ce se întâmplă acest lucru.
În exemplul de mai sus, sunt folosite simbolurile limbajului educațional algoritmic (AJ).
Din exemplul de mai sus este clar că atunci când scriem un algoritm pe AJ, este scris la începutul lui un titlu care începe cu cuvântul de serviciu alg (abreviat word "algorithm"). Apoi este indicat numele algoritmului, pe care autorul algoritmului îl prezintă. Următoarea parte este denumită corpul algoritmului. Începe cu cuvântul de serviciu nach (început) și se termină cu cuvântul kon (end). Corpul algoritmului este o secvență de comenzi pentru interpret.
Aici și în cele ce urmează, cuvintele de serviciu în algoritmi în limbaj algoritmic vor fi scrise cu caractere aldine. În limbile de programare (ca în AJ), cuvintele de serviciu sunt cuvinte care sunt folosite întotdeauna în același sens.
Procesul de rezolvare a problemei trebuie împărțit într-o secvență de pași executați separat.
Această proprietate a algoritmului se numește discretă.
Fiecare algoritm este compilat pe baza artistului specific, ținând seama de capacitățile sale. Pentru ca algoritmul să fie executat, este imposibil să includeți comenzi pe care interpretul nu le poate executa. Nu puteți să-i instruiți pe bucătar să lucreze ca un turnator, indiferent de instrucțiunile detaliate care îi sunt date. Fiecare artist are propria sa listă de comenzi pe care le poate face. O astfel de listă se numește sistemul de comandă de execuție a algoritmului (SIS).
Un algoritm compilat pentru un anumit interpret trebuie să includă numai acele comenzi care fac parte din sistemul de comenzi al executorului.
Această proprietate a algoritmului se numește claritate.
Fiecare comandă a algoritmului trebuie să determine acțiunea unică a interpretului.
Această proprietate a algoritmului se numește precizie.
Algoritmul nu ar trebui să fie conceput pentru a lua decizii independente de către executor, care nu sunt furnizate de compilatorul algoritmului.
O altă cerință importantă pentru algoritm este proprietatea finitei (uneori a spus - eficacitatea) algoritmului. Aceasta înseamnă că:
Execuția algoritmului trebuie realizată într-un număr finit de pași.
Pentru executarea cu succes a oricărei lucrări, nu este suficient să avem algoritmul său. Există întotdeauna o nevoie de date inițiale, cu care va funcționa interpretul (produse alimentare pentru prepararea vesela, părți pentru colectarea unui dispozitiv tehnic etc.). Performantul care rezolvă problema matematică necesită informațiile numerice inițiale. Problema este întotdeauna formulată după cum urmează: informația inițială este dată, este necesară obținerea unui rezultat. În matematică, sunteți obișnuiți să scrieți condițiile de sarcini în această formă. De exemplu:
Având în vedere: picioarele unui dreptunghiular
triunghi a = 3 cm; b = 4 cm.
Găsiți: hypotenuse cu
Algoritmul de rezolvare a acestei probleme poate fi reprezentat în această formă:
alg Hypotenuse
devreme
1, Desenați un pătrat.
2. Desenați un pătrat b.
3. Adăugați rezultatele etapelor 1 și 2.
4. Calculați rădăcina pătrată a rezultatului acțiunii 3 și luați-o ca fiind valoarea c.
con.
Fiecare dintre aceste comenzi poate fi realizată de oricine cunoaște elementele de bază ale matematicii, de aceea fac parte din sistemul său de comandă.
Doar având un set complet de date, puteți rezolva cu exactitate problema.
În sarcinile de gestionare a obiectelor fizice (mașină, avion, mașină etc.), datele inițiale sunt informații despre starea obiectului de control, despre mediul înconjurător.
Rezumând toate cele de mai sus, formulăm definiția algoritmului.
Algoritm - instrucțiune clară și precisă a executantului pentru executarea ultimei secvențe de comenzi, care conduce la datele inițiale până la rezultatul dorit.
Execuția oficială a algoritmului
Dacă algoritmul are proprietățile de mai sus, atunci lucrarea asupra acestuia va fi executată de executor
formal (adică fără elemente de creativitate din partea lui). Aceasta este baza pentru activitatea executanților controlați de software, cum ar fi roboții industriali. Manipulatorul de roboți poate efectua lucrul dispozitivului de strunjire dacă poate efectua toate operațiile dispozitivului de strunjire (porniți mașina, fixați mașina de tăiere, deplasați mașina de tăiere, măsurați produsul). Artistul nu are nevoie de o înțelegere a esenței algoritmului, el trebuie să execute comenzile cu exactitate, fără a le viola succesiunea.
Care este programul
Și care este programul? Este programul diferit de algoritm?
Un program este un algoritm scris în limba artistului.
Altfel, puteți spune așa; Algoritmul și programul nu diferă în ceea ce privește conținutul, dar pot diferi în formă.
Pe scurt despre principal
Cuvântul "algoritm" provine de la numele lui Muhammad al-Khorezmi, care a propus metodele de efectuare a operațiilor aritmetice cu numere multivite.
Executorul algoritmului este obiectul pentru care algoritmul este compilat.
Procesul de rezolvare a problemei trebuie împărțit într-o secvență de pași individuali (proprietatea discretă a algoritmului).
Sistemul de comenzi al performerului (SKI) este întregul set de comenzi pe care interpretul poate să le îndeplinească (înțelege). Algoritmul poate fi construit numai din comenzile care sunt incluse în SKI-ul artistului (proprietatea inteligibilității).
Fiecare comandă a algoritmului de control determină acțiunea unică a performerului (proprietatea de acuratețe).
Execuția algoritmului trebuie să ducă la un număr finit de pași (proprietatea finității).
Pentru a efectua cu succes lucrarea, sarcina trebuie comunicată artiștilor interpreți sau executanți cu un set complet de date inițiale.
Executorul execută algoritmul într-un mod formal.
Programul din algoritm poate diferi în formă, dar nu în conținut. Programul este un algoritm prezentat în limba artistului.
Întrebări și sarcini
1. Ce este un algoritm? De unde a venit acest cuvânt?
2. Ce este executorul algoritmului?
3. Care este sistemul executorilor comandantului?
4. Care sunt proprietățile principale ale algoritmului?
5. Denumiți executorii următoarelor tipuri de lucrări: colectarea gunoiului în curte; transportul pasagerilor; emiterea de salarii; examene; examene de examen; învățarea copiilor în școală. Încercați să formulați un SKI pentru fiecare dintre acești artiști.
6. Definiți setul complet de date pentru rezolvarea următoarelor sarcini de procesare a informațiilor:
• calcularea costului achizițiilor din magazin;
• calcularea sumei de bani pe care ați primit-o de la vânzător;
• Determinați ora televizorului pe televizorul care vă interesează;
• calcularea ariei triunghiului;
• Determinarea timpului de cădere a cărămizii de pe acoperișul casei;
• determinarea tarifului lunar pentru consumul de energie electrică;
• traducerea textului rus în limba italiană;
• traducerea textului italian în rusă.
7. Încercați să formulați algoritmi pentru procesarea informațiilor pentru sarcinile de la punctul 6, dacă sunteți executor. În acest caz, ce comenzi ar trebui să puteți efectua?
I. Semakin, L. Zalogova, S. Rusakov, L. Shestakova, Informatică, gradul 9
Cititorii au trimis de pe site-uri web
Dacă aveți corecții sau sugestii pentru această lecție, scrieți-ne.
Dacă doriți să vedeți alte ajustări și dorințe pentru lecții, consultați aici - Forumul educațional.
Articole similare
Trimiteți-le prietenilor: