Vsak algoritem obravnava podatke - vhodne, vmesne in izhodne.

Ud. Razumemo ga na dva načina: prvič, algoritem je sestavljen iz posameznih elementarnih korakov ali dejanj in obstaja veliko različnih korakov, ki seveda sestavljajo algoritem. Drugič, algoritem se mora končati v končnem številu korakov. Če je konstruiran neskončen proces, ki konvergira k želeni rešitvi, se na določenem koraku prekine in dobljena vrednost se vzame kot približna rešitev obravnavanega problema. Natančnost približka je odvisna od števila korakov.

Elementarnost (razumljivost). Vsak korak algoritma mora biti preprost, da ga lahko naprava, ki izvaja operacije, izvede v enem koraku.

Diskretnost. Proces reševanja problema je predstavljen kot končno zaporedje posameznih korakov, vsak korak algoritma pa se izvede v končnem (ne nujno enotnem) času.

Determinizem (gotovost). Vsak korak algoritma mora biti enolično in nedvoumno definiran in ne sme dopuščati poljubne interpretacije. Po vsakem koraku je označeno, kateri korak je naslednji, ali pa je podan ukaz za zaustavitev, po katerem se delo algoritma šteje za zaključeno.

Produktivnost. Algoritem ima določeno število vhodnih količin – argumentov. Namen izvajanja algoritma je pridobiti specifičen rezultat, ki ima zelo specifičen odnos do izvirnih podatkov. Algoritem se mora ustaviti po končnem številu korakov, odvisno od podatkov, z navedbo, kaj je treba upoštevati kot rezultat. Če rešitve ni mogoče najti, je treba navesti, kaj se v tem primeru šteje za rezultat.

Množični značaj. Algoritem za reševanje problema je razvit v splošni obliki, tj. uporabna naj bi bila za določen razred problemov, ki se razlikujejo le po začetnih podatkih. V tem primeru lahko začetne podatke izberemo iz določenega območja, imenovanega področje uporabnosti algoritma.

Učinkovitost. Isti problem je mogoče rešiti na različne načine in posledično v različnih časih in z različnimi stroški pomnilnika. Zaželeno je, da je algoritem sestavljen iz minimalnega števila korakov in da rešitev izpolnjuje pogoj točnosti ter zahteva minimalno porabo drugih virov.

Natančna matematična definicija algoritma je zapletena zaradi dejstva, da interpretacija predpisanih navodil ne sme biti odvisna od subjekta, ki jih izvaja. Odvisno od njegove intelektualne ravni lahko bodisi sploh ne razume, kaj je mišljeno v navodilih, ali pa jih, nasprotno, razlaga nenamerno.

Težavo pravil tolmačenja je mogoče zaobiti, če sta poleg besedila predpisov opisana tudi zasnova in princip delovanja naprave za tolmačenje. S tem se izognete negotovosti in dvoumnosti pri razumevanju istih navodil. Da bi to naredili, je treba določiti jezik, v katerem so opisana številna pravila vedenja ali zaporedje dejanj, pa tudi samo napravo, ki lahko interpretira stavke, narejene v tem jeziku, in izvaja vsak natančno določen proces korak za korakom. Izkazalo se je, da je takšno napravo (stroj) možno izvesti v obliki, ki ostane nespremenjena ne glede na kompleksnost obravnavanega postopka.

Trenutno lahko ločimo tri glavne vrste univerzalnih algoritemskih modelov. Razlikujeta se v izhodiščnih predpostavkah glede definicije pojma algoritem.

Prva vrsta povezuje koncept algoritma z najbolj tradicionalnimi pojmi matematike – računanjem in numeričnimi funkcijami. Druga vrsta temelji na ideji algoritma kot določene deterministične naprave, ki je sposobna izvajati le zelo primitivne operacije v danem trenutku. Ta predstavitev zagotavlja nedvoumnost algoritma in elementarnost njegovih korakov. Poleg tega ta ideja ustreza ideologiji gradnje računalnikov. Glavni teoretični model te vrste, ustvarjen v tridesetih letih prejšnjega stoletja. Angleški matematik Alan Turing je Turingov stroj.

Tretja vrsta– to so pretvorbe besed v poljubnih abecedah, pri katerih so elementarne operacije zamenjave, tj. zamenjava dela besede (beseda je zaporedje abecednih znakov) z drugo besedo. Prednosti te vrste modela sta njegova največja abstraktnost in zmožnost uporabe koncepta algoritma za objekte poljubne (ne nujno numerične) narave. Primeri modelov tretje vrste so kanonični sistemi ameriškega matematika Emila L. Posta in normalni algoritmi, ki jih je predstavil sovjetski matematik A. A. Markov.

Modela drugega in tretjega tipa sta si precej blizu in se razlikujeta predvsem v hevrističnih poudarkih, zato ni naključje, da govorita o Postovem stroju, čeprav sam Post o tem ni govoril.

Posnetek algoritma v nekem jeziku je program. Če je program napisan v posebnem algoritemskem jeziku (na primer PASCAL, BASIC ali kakšnem drugem), potem govorimo o izvirni program. Pokliče se program, napisan v jeziku, ki ga lahko računalnik neposredno razume (običajno binarne kode). stroj, oz dvojiško.

Vsak način pisanja algoritma pomeni, da je vsak objekt, opisan z njegovo pomočjo, specificiran kot specifičen predstavnik pogosto neskončnega razreda objektov, ki jih je mogoče opisati na ta način.

Sredstva, uporabljena za pisanje algoritmov, so v veliki meri odvisna od tega, kdo bo izvajalec.

Če je izvajalec oseba, posnetek morda ni povsem formaliziran, jasnost in preglednost sta na prvem mestu. V tem primeru se lahko za zapis uporabijo diagrami algoritmov ali besedni zapis.

Za pisanje algoritmov, namenjenih izvajalcem avtomatov, je potrebna formalizacija, zato se v takih primerih uporabljajo formalni posebni jeziki. Prednost formalnega načina zapisa je v tem, da omogoča proučevanje algoritmov kot matematičnih objektov; v tem primeru formalni opis algoritma služi kot osnova za intelektualno dojemanje tega algoritma.

Za pisanje algoritmov se uporablja veliko različnih sredstev. Izbira orodja je odvisna od vrste algoritma, ki se izvaja. Razlikujejo se: Glavni načini pisanja algoritmov:

■ verbalno– algoritem je opisan v človeškem jeziku;

■ simbolično– algoritem je opisan z naborom simbolov;

■ grafični– algoritem je opisan z nizom grafičnih slik.

Splošno sprejeti načini pisanja algoritma so grafični zapis z uporabo diagramov algoritmov (diagramov poteka) in simbolni zapis z z uporabo nekega algoritemskega jezika.

Za opis algoritma se uporabljajo diagrami, ki prikazujejo povezano zaporedje geometrijskih likov, od katerih vsaka pomeni izvedbo določenega dejanja algoritma. Vrstni red dejanj je označen s puščicami.

V diagramih algoritmov se uporabljajo naslednje vrste grafičnih simbolov.

Začetek in konec Algoritem je označen z istimi simboli (slika 21.1).

riž. 21.1.

Korak algoritma, povezan z dodeljevanjem nove vrednosti določeni spremenljivki, pretvorbo določene vrednosti za pridobitev druge vrednosti, je predstavljen s simbolom "proces"(slika 21.2).

riž. 21.2.

Izbira smeri za izvajanje algoritma glede na nekatere spremenljive pogoje je predstavljena s simbolom " rešitev"(slika 21.3).

riž. 21.3.

Tukaj R pomeni predikat (pogojni izraz, pogoj). Če je pogoj izpolnjen (predikat ima vrednost TRUE), se izvede prehod na en korak algoritma, če ni izpolnjen, pa na drugega.

Obstajajo primitivi za operacije vnosa in izpisa podatkov ter drugi grafični simboli. Trenutno so opredeljeni s standardom GOST 19.701-90 (ISO 5807-85) "Enotni sistem programske dokumentacije, sheme programov in sistemov in pravil izvajanja." Skupaj zbirka ESPD obsega 28 dokumentov.

Z uporabo diagrama algoritma je enostavno sestaviti začetni program v algoritemskem jeziku.

Glede na zaporedje dejanj v algoritmu ločimo algoritme linearne, razvejane in ciklične strukture.

V algoritmih linearna struktura dejanja se izvajajo zaporedno eno za drugim.

V algoritmih razvejana struktura Glede na izpolnjevanje ali neizpolnjevanje katerega koli pogoja se izvajajo različna zaporedja dejanj. Vsako tako zaporedje dejanj se imenuje veja algoritma.

V algoritmih ciklična struktura odvisno od izpolnjevanja ali neizpolnjevanja katerega koli pogoja se izvede ponavljajoče se zaporedje dejanj, imenovano telo cikla. Ugnezdena zanka je tista, ki je znotraj telesa druge zanke. Iterativni cikel je cikel, katerega število ponovitev ni določeno, ampak se določi med izvajanjem cikla.

V tem primeru se kliče ena ponovitev cikla ponovitev.

a l g o r i f m) je eden od osnovnih pojmov logike in matematike. Z A. mislimo na natančno navodilo, ki določa izračun. proces, ki vodi od začetnih podatkov, ki se lahko razlikujejo, do želenega rezultata. Besed "računalništvo" in "računalniški", ki se pojavita zgoraj, ne bi smeli razumeti v ozkem pomenu digitalnega računalništva. Tako že pri šolskem tečaju algebre govorijo o črkovnih izračunih, pa čeprav tudi tu črke igrajo vlogo nadomestkov za številke, že pri aritmetiki. Pri izračunih se pojavijo simboli, ki ne označujejo nobenih količin: oklepaji, enačaji, aritmetični znaki. dejanja. Lahko gremo še dlje in razmislimo o izračunih s poljubnimi simboli in njihovimi kombinacijami; V tem širokem smislu je izraz "izračun" razumljen, ko opisuje koncept "A.". Tako lahko govorimo o A. prevajanju iz enega jezika v drugega, o A. delu vlakovnega dispečerja (obdelava informacij o gibanju vlakov v ukaze) in drugih primerih algoritmov. opisi nadzornih procesov, ki jih proučuje kibernetika. POMEN A. Sama beseda "A". sega v 9. stoletje. (izhaja iz Algoritmi, kar je latinska transliteracija, očitno narejena v 12. stoletju, arabskega imena horezmskega matematika al-Khwarizmija). Danes se najpreprostejši A. pojavljajo že v osnovni šoli - to je A. aritmetika. dejanj (v Evropi sredi stoletja je A. natanko tisto, kar se je imenovala sodobna šolska aritmetika, tj. decimalni pozicijski številski sistem in umetnost štetja v njem, saj je bila al-Hvarizmijeva razprava ena prvih, če ne prva, zahvaljujoč Poleg tega se je Evropa seznanila s položajnim sistemom). Naj poudarimo, da se v osnovni šoli poučuje A. računi. Ko govorimo o človekovi sposobnosti seštevanja števil, ne mislimo na to, da bo za kateri koli dve števili prej ali slej lahko našel njuno vsoto, temveč na to, da pozna določeno enotno metodo seštevanja, ki je uporabna za kateri koli dve specifični zapisi števil. , tj. z drugimi besedami A. seštevanje (primer takega A. je znano A. seštevanje števil v »stolpcu«). A. najdemo v znanosti na vsakem koraku, sposobnost reševanja problema "v splošni obliki" vedno pomeni v bistvu obvladovanje določenega A. Pojem problema "v splošni obliki" se razjasni s pomočjo koncept množičnega problema. Izraz "problem" lahko razumemo kot nalogo iskanja predmeta, ki ima določene lastnosti; ta predmet se imenuje rešitev problema (zlasti za problem iskanja odgovora na vprašanje je rešitev odgovor "da" ali "ne" na zastavljeno vprašanje). Problem je nerešljiv, če nima rešitve, tj. ni predmeta, ki bi imel zahtevane lastnosti. Jasno je torej, da nerešljivost problema ni razlog za agnosticizem. sklepi; nasprotno, ugotavljanje nerešljivosti določenega problema je pomembno spoznanje. dejanje Masovni problem je definiran z nizom ločenih, "enotnih" problemov in je sestavljen iz zahteve po iskanju splošne metode (tj. A.) za njihovo rešitev. Nerešljivost množičnega problema pomeni nezmožnost iskanja korespondenc. A. Masovni problemi so izjemno značilni in pomembni za logiko in matematiko. Celo rešitev posameznega problema je pogosto dragocena prav zato, ker hkrati zagotavlja splošno metodo za rešitev celotnega razreda problemov; hkrati pa formulacija množičnega problema pomeni preoblikovanje določenega razreda problemov v en sam problem - problem iskanja odgovora za rešitev vseh problemov tega razreda; tukaj se kaže povezava med kategorijami dialektike, kot so individualno, posebno in univerzalno. Vloga množičnih problemov določa pomen A. Ugotavljanje nerešljivosti določenega množičnega problema (tj. odsotnosti enotnega algoritma, ki omogoča iskanje rešitev za vse posamezne probleme določene serije) je najpomembnejše kognitivno dejanje, ki kaže, da so za reševanje specifičnih posameznih problemov v osnovi potrebne metode, specifične za vsak tak problem. Obstoj nerešljivih množičnih problemov služi torej kot konkretna utelešenje neizčrpnosti spoznavnega procesa. Vsebuje. fenomeni, ki so bili osnova za nastanek koncepta "A", so dolgo zasedali pomembno mesto v znanosti. Številni problemi, ki so se pojavili v matematiki in logiki, so bili v iskanju določenih konstruktivnih metod. Iskanje takšnih metod se je še posebej okrepilo v povezavi z ustvarjanjem priročne matematike in logično simbolizem, pa tudi razumevanje temeljne odsotnosti teh metod v številnih primerih - vse to je bil močan dejavnik pri razvoju znanosti. znanja. Spoznanje o nezmožnosti reševanja katerega koli problema z neposrednim izračunom je privedlo do nastanka v 19. st. teoretična množica. koncepti. Šele po obdobju hitrega razvoja tega koncepta (v okviru katerega se vprašanje konstruktivnih metod v njihovem sodobnem razumevanju sploh ne pojavi) je bilo v zadnjih desetletjih mogoče ponovno vrniti se k vprašanjem konstruktivnosti, vendar na novi ravni. , obogaten s kristaliziranim konceptom »A.« (še ena ilustracija Leninovega stališča o spiralni naravi razvoja znanja). In čeprav koncept "A." ni tako daljnosežna abstrakcija kot na primer koncept "množice", ni mogoče šteti za naključje, da je zgodovinsko prvi od teh konceptov nastal pozneje kot drugi. PRIMERI A. Podobno kot koncepti "množica", "korespondenca", "naravno število", "relacija" itd., koncept "A." je primarna logično-matematična koncept (ena od kategorij logike in matematike). Ne dopušča formalne definicije s preprostejšimi koncepti, ampak je (kot druge matematične kategorije) abstrahirana neposredno iz izkušenj. Koncept "A." se lahko naučimo le s primeri. Primer 1. Možni začetni podatki so končne neprazne kombinacije, sestavljene iz paličic (I), tj. objekti I, II, III itd. A. sestoji iz naslednjega. pravila (ki jih je treba upoštevati od pravila 1°): 1°. Podčrtajte skrajno levo palico spodaj in nadaljujte s pravilom 2°. 2°. Postavite skrajno desno palico na vrh in nadaljujte s pravilom 3°. 3°. Preglejte podčrtano palico in, če ni podčrtana, nadaljujte s pravilom 4°. 4°. Upoštevajte palico takoj za podčrtano; če ni podčrtano, nadaljujte s pravilom 5°; če je podčrtano, nadaljujte z izvajanjem pravila 7°. 5°. Premaknite spodnjo vrstico s podčrtane palice na naslednjo takoj za njo in nadaljujte s pravilom 6°. 6°. Premaknite zgornjo črto s prekrižane palice na tisto, ki je tik pred njo, in nadaljujte z izvajanjem pravila 7°. 7°. Izbrišite prekrižano palico in vse palice za njo ter nadaljujte s pravilom 8°. 8°. Izbrišite spodnjo vrstico podčrtane palice; kar se je zgodilo je rezultat. Če uporabimo ta A. za kombinacijo ||||, vzeto kot začetni podatek, dobimo zaporedno: po pravilu 1° – |||, po pravilu 2° – ? || , po pravilih 3°, 4°, 5° – | ? | , po pravilih 6°, 3°, 4° – | ? | po pravilu 7° – | ?, po pravilu 8° – || (rezultat). Če poskušamo A. uporabiti za kombinacijo |||, dobimo: po pravilu 1° – ? ||, po pravilu 2° – ? | , po pravilih 3°, 4°, 5° – | ? , po pravilu 6° – | I |, potem morate nadaljevati z izvajanjem pravila 3°, vendar je pravilo 3° izvedljivo le pod pogojem, da podčrtana paličica ni podčrtana. Tako za sedanje razmere A. ne vsebuje navodil, kako postopati; ti neučinkovita zaustavitev (ustavitev, ki je ne spremlja rezultat). Preprosto je opaziti, da je bilo na splošno oblikovano. A. daje rezultat, ko se uporablja za katero koli kombinacijo sodega števila palic, rezultat pa je v tem primeru kombinacija, sestavljena iz polovice števila palic; A. ne daje nobenega rezultata, če se uporablja za katero koli kombinacijo, sestavljeno iz lihega števila palic. Primer 2. V logiki in matematiki se imenuje katera koli končna množica znakov. »abeceda«, vanjo vključeni znaki so »črke« abecede, končno (tudi prazno) zaporedje črk, napisanih ena za drugo k.-l. abeceda imenovana "beseda" v tej abecedi. Na primer, arabske številke tvorijo abecedo in vsaka decimalna predstavitev celega števila je beseda v tej abecedi. Razmislite o abecedi (a, b) dveh črk: a in b. Primeri besed v tej abecedi so: v, aw, vva aaavavv itd. Dogovorimo se, da prehod iz besede v tej abecedi v drugo besedo v isti abecedi imenujemo "dopusten" v skladu z enim od naslednjih. dve pravili: 1) če ima beseda obliko aP, kjer je P poljubna beseda, pojdite na besedo Pb; 2) če je beseda videti kot va?, kje? – katera koli beseda, pojdite na besedo Rava. Nato se oblikuje sled, navodilo: »začenši z besedo k.-l (vzeto kot začetni podatek), naredite dopustne prehode, dokler ne dobite besede v obliki aa?; , zavrzite prvi dve črki in kar ostane, je rezultat." Ker je vsakič izvedljivo največ eno prehodno pravilo, oblikujemo recept tvori abecedo, katere možni začetni podatki so besede v abecedi (a, b). Za začetni podatek vzemimo besedo vavaa. Po pravilu 2 dobimo waaava. Če ponovno uporabimo pravilo 2, dobimo aavaava. Na podlagi naših navodil se moramo ustaviti; rezultat (aplikacije A. na besedo vavaa) je vavaa. Za začetni podatek vzemimo besedo vaava. Po pravilu 2 dobimo avaava. Po pravilu 1 dobimo vaavav. Nato dobimo zaporedno avavava, vavavav, vavavava itd. Lahko se dokaže, da se proces ne bo nikoli končal (tj. beseda, ki se začne z dvema črkama a, se ne bo nikoli pojavila in za vsako od nastalih besed bo mogoče narediti veljaven prehod). Tako A. ne daje nobenega rezultata, če se uporablja za besedo vaava. Za začetni podatek vzemimo besedo vaav. V zaporedju dobimo vaavv, avvav, vvavav. Poleg tega nobeno od pravil 1 in 2 ni izvedljivo, hkrati pa se rezultat ni obnesel. Zato, ko se uporablja za besedo awaav, tudi A. ne daje rezultatov. Glavne značilnosti A. Po A. A. Markovu so za A. značilne naslednje glavne značilnosti. značilnosti: a) določnost algoritemskih. predpisovanje, ki je sestavljeno iz njegove natančnosti in splošne razumljivosti, ki ne dopušča poljubnosti (zaradi te gotovosti predpisovanja je algoritemski proces determinističen: vsaka stopnja procesa enolično določa naslednjo stopnjo); b) masa, ki je sestavljena iz možnosti za vsak A. izhajajo iz začetnih podatkov, ki se spreminjajo v določenih mejah; c) učinkovitost, ki je osredotočena na doseganje želenega rezultata. Določenost A. zagotavlja možnost komunikacije ene osebe z drugo osebo, tako da bo ta druga oseba lahko izvajala A. brez sodelovanja prve; Ta ista lastnost determinizma omogoča prenos izvedbe A. na stroj. Množična narava analize predpostavlja, da obstaja določen nabor (za vsako analizo svoj) možnih začetnih podatkov. Kako je ta totalnost postavljena, je drugo vprašanje. Lahko domnevamo, da niz možnih začetnih podatkov, ki ustrezajo kateremu koli A., ni določen ločeno od A., ampak je označen z naravnimi. sliko po sami vsebini tega A. (npr. za A. seštevanje po stolpcu je ustrezna množica sestavljena iz vseh parov zapisov števil v decimalnem sistemu). Ko je določen predmet izbran kot začetni podatek A., potem govorimo o uporabi A. za ta predmet. Če A. daje rezultat, ko se uporablja za določen predmet, potem pravijo, da se uporablja za ta predmet. Učinkovitost A. sploh ne pomeni, da mora biti A. uporaben za kateri koli predmet iz ustreznega nabora možnih začetnih podatkov (glej primera 1 in 2). Tukaj je na mestu opozoriti, da je mogoče sestaviti takšen algoritem, za katerega ne obstaja A., ki bi iz poljubnih začetnih podatkov prvega A. prepoznal, ali je prvi A. zanje uporaben ali ne. Osnovne abstrakcije teorije A. V znanstvenem. V praksi so se razvile številne posebnosti. za matematiko in logične abstrakcije. To so najprej abstrakcija dejanske neskončnosti, abstrakcija identifikacije, abstrakcija potencialne uresničljivosti. Sov. znanstvenik A. A. Markov je pokazal, da sta zadnja dva potrebna pri obravnavi A. algoritma. proces je razdeljen na oddelke. korakov, od katerih se domneva, da je vsak tako elementaren, da je njegova možnost dejanska. izvajanje ni dvoma. Hkrati je lahko število teh elementarnih korakov, potrebnih za dosego rezultata, tako veliko, da se lahko šteje, da je doseganje rezultata praktično nemogoče. Vendar pa je ideja praktična izvedljivost ali neizvedljivost določenega števila korakov je relativna. Z razvojem računalništva se spreminja. sredstva (načeloma se lahko spremeni tudi ideja o elementarnosti določenega koraka). V teoriji A. torej abstrahirajo "praktično izvedljivost" in menijo, da je izvedljivo vsako končno število korakov. Tako je pri študiju A. omogočajo abstrakcijo potencialne izvedljivosti, ki je sestavljena iz abstrakcije od realnih meja naših zmožnosti. Razvoj hitrega elektronskega računalništva. stroji hitro premikajo te meje vedno dlje. Kar je bilo še včeraj le potencialno izvedljivo, danes postane praktično izvedljivo. S tem se teorija aritmetike približa praksi računalništva. stroje in omogoča, da se ti dve disciplini medsebojno bogatita. Prenos opravil na stroj na s.l. serija je nemogoča brez predizbora. sestavljanje A. odločb. Sestavljanje takega A. je praviloma temeljnega pomena (na primer pri problemu strojnega prevajanja je glavna stvar sestavljanje A. prevoda). Abstrakcija potencialne izvedljivosti je nujna pri obravnavi ne le algoritemskih. procese, ampak tudi same objekte, ki sodelujejo v teh procesih (vključno z "začetnimi podatki" in "rezultati"). Da bi torej lahko govorili o katerem koli naravnem številu (natančneje o zapisu tega števila, recimo v decimalnem sistemu), si moramo dovoliti zapise števil šteti za tako velike, da ti zapisi ne bi stali na zemeljski obli; tako in tukaj abstrahiramo od fizičnega. izvedljivosti takega zapisa uporabite abstrakcijo potencialne izvedljivosti. Na splošno se je treba zateči k abstrakciji potencialne izvedljivosti, da bi sklepali o poljubno dolgih besedah ​​v dani abecedi. Objekti, katerih konstrukcija in obravnava sta mogoča v okviru abstrakcije potencialne izvedljivosti (v nasprotju z abstrakcijo dejanske neskončnosti), imenovani. konstruktivni objekti. To so naravna števila, ki jih predstavljajo njihovi vpisi v k.-l. njihov zapisni sistem, besede v dani abecedi itd., kot tudi pari, trojčki in na splošno končna zaporedja, sestavljena iz zapisov številk, besed v abecedi itd.; racionalna števila (ki jih lahko predstavimo kot trojčke naravnih števil) itd. Konstruktivni objekti so tudi tako imenovani izrazi. računa ali formalnih sistemov, ki omogočajo uporabo aparata teorije A na slednjega. Vsako A. (razumljeno kot recept) je mogoče (po zapisu tega recepta v obliki kombinacije nekaterih simbolov). kot konstruktiven objekt. Nasprotno, objekti, katerih obravnava je nemogoča brez vključevanja abstrakcije dejanske neskončnosti, ne sodijo med konstruktivne objekte. Tako na primer konstruktivni objekti niso realna števila (v smislu Cantorja, Dedekinda ali Weierstrassa), geometrijska. točke (ker analiza takšne abstrakcije, kot je "točka", vodi do ideje o točki kot dejansko neskončnem sistemu majhnih teles) itd. Strukturni objekti so razvrščeni naravno. način v agregatu, katerega primeri so zbirka vseh besed v dani abecedi in na splošno katera koli zbirka vseh predmetov razreda. "tip" s seznama. zgoraj navedene vrste strukturnih objektov. Vsak tak niz strukturnih objektov je določen z metodo konstrukcije objektov, ki mu pripadajo. Druge osnovne Abstrakcija, ki se uporablja pri obravnavanju konstruktivnih objektov in arhitekture, je abstrakcija identifikacije. V nekaterih primerih se o dveh predmetih govori kot o enakih. Pogoji »istosti« se vsakokrat vzpostavijo glede na dano situacijo. Torej, na primer, ko oseba naredi izračune na papirju, je pisava, v kateri so zapisane številke, običajno brezbrižna, vnosa 1647 in 1647 pa se štejeta za enaka; lahko pa si predstavljamo situacije, kjer je razlika med romanskimi in ležečimi pisavami pomembna (kot na primer pri zaznavanju besed v tej filozofski enciklopediji). Takrat bosta oba zapisa že obravnavana kot neenaka, zapisa 1647 in 1647 pa bosta še vedno – v običajnih primerih – enaka (čeprav sta fizično različna objekta). Običajno je sprejeto, da so konstruktivni objekti sestavljeni iz določenih precej preprostih "elementarnih delov" (tako kot so besede sestavljene iz črk) in dva konstruktivna predmeta se štejeta za enaka, če sta sestavljena iz enakih elementarnih delov, razporejenih v istem vrstnem redu. Brez koncepta »istosti«, na podlagi katerega se na primer s kredo napisana števila na tabli in s črnilom v zvezku štejejo za enaka, je učenje nemogoče. Abstrakcija identifikacije nam omogoča, da o enakih objektih govorimo kot o enem in istem objektu. Vodi do oblikovanja pojma »abstraktni objekt«: dva enaka konkretna objekta namreč veljata za predstavnika istega abstraktnega objekta. Vsako A., uporabljeno za enake predmete, vodi tudi do enakih predmetov. Zato lahko domnevamo, da vsak A. določa proces preoblikovanja abstraktnih konstruktivnih objektov. Ta lastnost A. (skupaj z determinizmom) določa njihovo ponovljivost ali obnovljivost: A., ki je bil razvit v obliki A. nad abstraktnimi konstruktivnimi predmeti, se lahko večkrat reproducira za vse specifične konstruktivne objekte, ki so dovoljeni za določen A. Iz zgornjega mora postati jasno, da so začetni podatki enaki končnim podatkom. rezultatov, ki izhajajo iz izvajanja k.-l. A., so vedno konstruktivni objekti (vsako »stanje« algoritemsko. proces je konstruktiven objekt!). Nezmožnost celo potencialno izvedljivih procesov na nekonstruktivnih objektih je povezana tudi s pomanjkanjem načina, da bi jih prepoznali kot enake ali različne (prim. znano stališče kibernetike o prednostih diskretnih oblik shranjevanja informacij pred kontinuiranimi). ). Obstajajo različni pogledi. glede metod, dopustnih pri preučevanju A. Eden od njih, ki so ga predstavili predstavniki konstruktivne smeri v matematiki in logiki, je, da ker za oblikovanje koncepta A. zadostujejo abstrakcije identifikacije in potencialne izvedljivosti, potem razvoj teorije A. je treba izvesti v okviru teh abstrakcij. Še en pogled omogoča preučevanje A. vseh metod, ki so splošno dovoljene v logiki in matematiki, vklj. in zahtevajo abstrakcijo dejanske neskončnosti. Tako si lahko predstavljamo primer, ko bo treba za dokazovanje, da bo določeno A., ko ga uporabimo za določen predmet, dalo rezultat, uporabiti zakon izključene sredine, ki je tesno povezan z abstrakcijo. dejanske neskončnosti. Osnovni koncepti teorije A. Med osnovnimi. pojmi, ki nastanejo na podlagi pojma aritmetike, vključujejo pojme izračunljive funkcije, rešljive množice in števne množice. Funkcija se imenuje izračunljiva, če obstaja algoritem, ki to funkcijo izračuna na naslednji način. smisel: a) A. je uporaben za kateri koli objekt, ki je vključen v domeno definicije funkcije, in daje kot rezultat vrednost funkcije, ki jo ima za ta objekt, vzet kot svoj argument; b) A. se ne uporablja za noben predmet, ki ni vključen v obseg funkcije. Imenuje se množica, ki se nahaja v določeni zbirki konstruktivnih objektov (tj. množica, sestavljena iz nekaterih predmetov te zbirke). rešljiv (glede na obdajajočo množico), dokler obstaja A., ki to množico (glede na navedeno množico) razreši v naslednjo. smisel: A. je uporaben za kateri koli predmet iz obsegajoče množice in kot rezultat daje odgovor na vprašanje, ali ta predmet pripada obravnavani množici ali ne. Končno se pokliče neprazna množica (glej prazno). števen, dokler obstaja A, ki našteva ta niz v naslednjem. smisel: a) rezultat uporabe A. na poljubno naravno število obstaja in pripada obravnavani množici; b) vsak element obravnavane množice je mogoče dobiti kot rezultat uporabe aritmetike za neko naravno število. Po definiciji je tudi prazna množica običajno razvrščena kot števna. Isto izračunljivo funkcijo (oziroma rešljivo množico, števno množico) je mogoče izračunati (oziroma razrešiti, oštevilčiti) s pomočjo različnih A. Iz definicij sledi, da so argumenti in vrednosti izračunljive funkcije, elementi rešljiva ali števna množica so vedno konstruktivni objekti. Zamenjava konstruktivnih objektov (določen roj fiksnih agregatov) z njihovimi številkami v poljubnem algoritmu številčenja (tj. takšnega številčenja, za katerega obstaja algoritem za pridobitev njegovega števila iz predmeta in obratno), se lahko, kot se pogosto počne v teoriji aritmetike, omejimo na upoštevanje samo takih izračunljivih funkcij, argumentov in vrednosti katerih so naravna števila, in samo take rešljive in štetne množice, katerih elementi so tudi naravna števila. Dokaže se lahko, da je vsaka rešljiva množica šteljiva. Hkrati je bilo mogoče zgraditi šteto, a ne rešljivo množico. Ta prvi konkreten primer (objavil ga je ameriški znanstvenik A. Church leta 1936 v članku »En nerešljiv problem v elementarni teoriji števil«) odsotnosti algoritma (namreč algoritma, ki razrešuje konstruirano množico) je bil vir ali primer skoraj vsi nadaljnji primeri te vrste. Izkazalo se je, da je množica rešljiva, če in samo če sta tako ona kot njen komplement (obdajajoči množici objektov) štetljiva. Tako obstajajo dopolnila k številskim množicam, ki same po sebi niso štete. Povezava med teorijo logike in logiko. Koncepti odločljivih in števnih množic so tesno povezani s klasifikacijo definicij (tukaj se omejujemo le na take definicije, od katerih vsaka definira objekte določene vrste ali, kar je isto, določen razred objektov). Kot veste, obstajata dve glavni. definicijske sheme: »skozi rodovno in vrstno razliko« in »z indukcijo«. Pri opredelitvi »skozi rod in specifično razliko« je določen določen obsegajoč niz predmetov (»rod«) in označena značilnost (»vrstna razlika«), ki med predmeti razlikuje odlok, zbirko razreda definiranih predmetov . če; menijo, da je ta definicija konstruktivna, tj. da so objekti konstruktivni in da je prisotnost ali odsotnost vrstne razlike v elementu rodu algoritemsko prepoznavna, se definirana množica izkaže za odločljivo (in vsako odločljivo množico je mogoče definirati na ta način). Tako se topne množice identificirajo z množicami, ki so konstruktivno definirane skozi rod in specifično razliko. Definicija »po indukciji« je sestavljena iz dveh delov: osnovnega dela, ki vsebuje določen seznam predmetov, za katere je razglašeno, da pripadajo definiranemu razredu, in induktivnega dela, ki pravi, da če objekti takšne in drugačne vrste pripadajo definirani razred, potem objekti takšnega in drugačnega tipa, ki so s prvimi objekti povezani z določeno relacijo, prav tako pripadajo definiranemu razredu. (Možni so tudi bolj zapleteni primeri t.i. navzkrižnih definicij, ko je več razredov objektov istočasno definiranih drug skozi drugega). Če predpostavimo, da je definicija konstruktivna, tj. objekti so konstruktivni, seznam začetnih objektov, ki jih vsebuje osnovni del, je končen, pravila za prehod od že definiranih objektov k novim algoritemskim, ki jih vsebuje induktivni del (v smislu, da je prisotnost ali odsotnost relacije, obravnavane v induktivni del je prepoznan skozi nekakšen A.), potem pridemo do koncepta množice, ki je konstruktivno definirana z indukcijo, ali (sinonim) učinkovito generirane množice (ker taka definicija določa učinkovit proces generiranja, na določenih stopnjah razvoj katerega definirani objekti "se pojavijo" ali "generirajo"). Primer konstruktivne definicije z indukcijo je definicija dopustnih šahovskih pozicij (to je pozicij, ki se lahko pojavijo na plošči med igro). Osnovni del vsebuje eno enoto. začetni položaj. Induktivni del vsebuje pravila za poteze figur. Nabor dopustnih položajev je tako dejansko generiran. Drug primer učinkovito generirane množice je množica vseh dokazljivih formul k.-l. formalni sistem ali račun: osnovni del definicije dokazljivih formul vsebuje aksiome, induktivni del pa pravila sklepanja (aksiome razglasimo za dokazljive po definiciji in potem rečemo, da če so katere koli formule dokazljive, potem formule, dobljene iz njih po na pravila sklepanja so tudi dokazljivi). Generacijski proces je tukaj postopek dokazovanja vseh dokazljivih formul. Končno je postopek zavračanja vseh ponareljivih formul v računstvu tudi primer učinkovitega generativnega procesa. Koncept učinkovitega procesa generiranja je zelo tesno povezan s konceptom A. Podali smo definicijo (približno) učinkovitega procesa generiranja, ki temelji na konceptu A. Koncept procesa generiranja pa nam omogoča, da definiramo na njeni osnovi, če ne sam koncept A, pa v vsakem primeru koncept izračunljive funkcije. Dejansko naj bo določen proces generiranja sposoben "generirati" objekte, ki imajo obliko parov (x, y), in naj imata katera koli dva "generirana" para s sovpadajočimi prvimi členi tudi enaka druga člena. Nato sledi postopek. definira funkcijo y = f(x) na ta način: funkcija je definirana za objekt x0, če in samo če je x0 prvi član c.-l. generirani par: vrednost funkcij za argument x0 je v tem primeru enaka drugemu članu tega para. Funkcija, opredeljena v odloku. v smislu učinkovitega procesa generiranja je očitno izračunljiv [da bi našli f(x0), moramo proces razširiti, dokler ne najdemo parov z x0 kot prvim členom]. Nasprotno pa je vsako izračunljivo funkcijo mogoče definirati z učinkovitim procesom generiranja. Algoritemsko procesi in procesi ustvarjanja so si logično blizu. stališča. Vsak od njih temelji le na konstruktivnih konceptih. Razlika med njima je, da algoritem proces se odvija na podlagi zahteve, generativni proces pa se odvija na podlagi dovoljenja delovati na določen način. Tu se kaže razlika med nujnim in mogočim (v algoritemskem procesu je vsaka stopnja edinstveno, tj. nujno določena s prejšnjo stopnjo, medtem ko ko se generativni proces odvija po vsaki stopnji, se pojavi samo množica možnosti za naslednjo). stopnja). S pravilnimi izboljšavami koncepta učinkovitega generiranega procesa se izkaže, da je vsaka efektivno generirana množica šteljiva in obratno. Ta okoliščina nam v kombinaciji z zgornjimi razmerji med števljivimi in odločljivimi množicami omogoča, da sklepamo naslednje. Vsak razred objektov, ki dopušča konstruktivno definicijo skozi rod in specifično razliko, dopušča tudi konstruktivno definicijo z indukcijo, ne pa obratno: obstaja razred objektov, ki je konstruktivno definiran z indukcijo, vendar ne dopušča konstruktivne definicije skozi rod in posebna razlika; dodatek k temu razredu objektov (nad obdajajočim nizom strukturnih objektov) ne omogoča učinkovite induktivne definicije. Vsak konstruktivni generativni proces lahko predstavimo kot postopek za pridobivanje dokazljivih formul ustreznega računa. Zato lahko primer razreda, ki ima pravkar opisane lastnosti, sestavimo kot razred vseh dokazljivih formul določenega računa. Poleg tega se je izkazalo, da se ta okoliščina pojavi pri vsakomur, ki je dovolj zadržan. račun (na primer za račun predikatov ali za račune, ki formalizirajo aritmetiko), kajti če je račun dovolj smiseln, potem se v njem lahko izrazi vsak učinkovit generacijski proces. Razred vseh dokazljivih formul takega računa (ki je seveda števen) ni odločljiv, zato ni algoritma, ki bi prepoznal dokazljivost računskih formul; v tem smislu pravimo, da je račun neodločljiv. Ker razred vseh dokazljivih računskih formul ni odločljiv, se bo dopolnjeval. zanj razred vseh nedokazljivih formul ni preštev in ga zato ni mogoče dobiti z nobenim postopkom generiranja; predvsem pa je nemogoče zgraditi takšen račun, ki bi "ovrgel" vse nedokazljive formule izvirnika. račun in samo oni; Poleg tega vseh teh nedokazljivih formul ni mogoče ovreči s pomočjo izvirnika. računa, torej v zač. v računstvu obstajajo t.i neodločljive (tj. niti dokazljive niti ovrgljive) formule. V teh premislekih se lahko omejimo samo na take formule, ki vsebujejo. interpretacije računa izražajo smiselne (tj. resnične ali napačne) predloge in zato med takimi formulami najdejo neodločljive. Iz tega sledi, da je mogoče predstaviti formulo, ki izraža pravo sodbo, vendar je ni mogoče dokazati v računstvu; v tem smislu naj bi bil sistem nepopoln. Poudarjamo, da je zaradi splošne narave sklepanja, ki se izvaja, lastnost nepopolnosti neločljivo povezana z vsem dovolj vsebovanim. račun. Koncept neodločljivosti računa temelji na konceptu aritmetike in ni presenetljivo, da je dejstvo neodločljivosti ugotovljeno na podlagi raziskav na področju teorije računa. Zelo pomembno (in morda na prvi pogled nepričakovano) je dejstvo, da tako splošno logiko. dejstvo, kot je nepopolnost izračunov (dejstvo, ki izraža temeljno nezmožnost popolne formalizacije procesa logičnega sklepanja in ga je prvič strogo dokazal avstrijski znanstvenik K. Gödel leta 1931, preden je bil razjasnjen koncept »A.«), lahko mogoče pridobiti, kot smo pravkar videli, s pomočjo teorije aritmetike. Že sama ta okoliščina kaže ogromne možnosti uporabe teorije aritmetike pri vprašanjih logike. Te aplikacije niso omejene na navedeni primer. Leta 1932 so Sovjeti. znanstvenik A. N. Kolmogorov je predlagal razlago konstruktivne logike, ki so jo ustvarili intuicionisti z uporabo content. sredstva, ki nimajo nobene zveze z držami intuicionizma; Kolmogorov je namreč predlagal, da se vsak stavek konstruktivne logike razlaga kot problem. Koncept problema pa je zahteval specifikacijo, ki jo je bilo mogoče podati le na podlagi že razvite teorije A. Dva posebna razreda problemov, primerna za razlago konstruktivne logike, sta predlagala amer. znanstvenik S.K. Kleene leta 1945 in sov. znanstvenik Yu. T. Medvedev leta 1955. Leta 1956 sove. znanstvenik N.A. Shanin je predstavil nov koncept, po katerem vsaka izjava konstruktivne logike ne zahteva razlage v obliki problema. Ta krog idej vključuje vprašanja "konstruktivizacije" ali "iskanje konstruktivnih analogov", klasična. matematični koncepti in predlogi; tudi rešitev teh vprašanj je mogoča le na podlagi teorije A. Konstruktivizacija osnovnega. matematične pojme analiza je privedla do tako imenovane, ki se zdaj razvija. konstruktivna matematika analizo. Začrtani so načini konstruktivizacije in drugih matematičnih. teorije. Eden od glavnih tehnike, uporabljene pri konstruktivizaciji, je prehod od preučevanih predmetov do njihovih imen, ki so vedno konstruktivni objekti. REŠITEV TEŽAV. Poseben primer množičnih problemov so rešitve problemov. Problematika reševanja k.-l. množice je problem konstruiranja algoritma, ki rešuje to množico. Dopisovanje vrsto posameznih problemov tu sestavljajo problemi odgovora na vprašanje o pripadnosti množici, ki se postavi za vsak objekt iz obsegajoče množice konstruktivnih objektov. Nasprotno pa vsak problem mase oz. vrsto posameznih problemov odgovora na vprašanje, lahko obravnavamo kot problem reševanja določenega niza, in sicer niza tistih posameznih problemov, katerih odgovor je "da". To pojasnjuje pomembno vlogo reševanja težav. Oni so bili tisti, ki so jih proučevali z vidika. njihova rešljivost. Med reševalnimi problemi izstopajo problemi, postavljeni za razrede dokazljivih računskih formul. Problem razrešitve razreda vseh dokazljivih formul k.-l. računica imenovana tudi problem reševanja samega računa. (V ruskih besedilih se problem razrešitve običajno imenuje "problem rešljivosti", vendar je "problem rešljivosti" bolje imenovati problem: "odgovoriti, ali ima dani problem rešitev."). Nerešljivi množični problemi. Problem dovoljenja za k.-l. Pri računstvu vedno obstaja problem razrešitve števne množice. Na splošno so se vsi problemi razrešitve, ki so se naravno pojavili v matematiki, izkazali za probleme razrešitve števnih množic. Gre za zgoraj omenjeni prvi primer problema nerešljive rešitve (in hkrati prvi primer problema nerešljive mase nasploh), ki ga je Church objavil leta 1936. To je t.i. problem identitete za asociativne sisteme sta dokaze o nerazločljivosti oblike 1947 neodvisno drug od drugega objavila A. A. Markov in amer. znanstvenik E. L. Post; ta rezultat je zanimiv kot prvi primer dokaza o nerešljivosti množičnega problema, ki je nastal (že leta 1914) zunaj logike in teorije. dokazano leta 1952. znanstvenik P. S. Novikov (Leninova nagrada, 1957). Vsak od problemov identitete je sestavljen iz iskanja algoritma, ki ugotavlja enakovrednost ali neenakovrednost dveh besed v dani abecedi (ali imamo opravka z asociativnim sistemom ali skupino, je odvisno od ene ali druge definicije enakovrednosti). Zato lahko problem identitete obravnavamo kot problem razrešitve množice vseh med seboj enakovrednih parov besed (glede na množico vseh možnih parov besed). Še več, ker je mogoče določiti generativni postopek za pridobitev vseh parov besed, ki so enakovredni drug drugemu, je množica vseh takšnih parov številna. Doslednost. Od Cerkvenega primera leta 1936 do leta 1944 so bili vsi dokazi o nerešljivosti množičnih problemov izvedeni ali bi se lahko izvedli na naslednji način. enotna metoda. Očitno nerešljiv problem, ki ga proučuje Church, je bil reduciran na obravnavani problem mase, tako da če bi bil obravnavani problem mase rešljiv, bi se tudi Churchov problem izkazal za rešljivega (v tem smislu lahko rečemo, da je dokaz o nerazločljivost obravnavanega problema zreducirala na dokaz nerazločljivosti Churchovega problema). Postavljalo se je vprašanje, ali je mogoče za vsak nerešljiv problem rešitve na ta način ugotoviti njegovo nerešljivost. To vprašanje, imenovano problem reducibilnosti, je postavil Post leta 1944; Obenem je Post navedel več primerov nerešljivih problemov rešitve, katerih nerešljivost je ugotovil z metodo, ki je drugačna od zgoraj opisane (ti primeri še niso rešili problema reducibilnosti, saj je ostalo odprto vprašanje, ali je zanje ni bilo mogoče najti takih dokazov nerešljivosti, ki so bili reducirani, da bi dokazali nerešljivost Churchovega problema; takšni dokazi so bili dejansko najdeni za nekatere od zgornjih primerov). Problem reducibilnosti je bil v središču raziskav teorije aritmetike do leta 1956, ko ga je samostojno rešila Sovjetska zveza. znanstvenik A. A. Muchnik in amer. znanstvenik R. M. Friedberg. Konstruiral je primer neodločljivega problema rešitve (za naštevo množico), katerega neodločljivosti ni mogoče dokazati z redukcijo Churchovega problema na ta problem. Muchnik je pokazal še več, namreč, da ne samo problem Cerkve, ampak noben drug problem ne more služiti kot "standardni neodločljiv problem" v smislu, da bi dokaz neodločljivosti katerega koli neodločljivega problema rešitve za naštevo množico lahko

Razumljivost - algoritem mora biti sestavljen iz ukazov, ki so izvajalcu »razumljivi« (vključeni v sistem izvajalčevih ukazov).

Diskretnost (diskontinuiteta, ločenost) - algoritem mora predstavljati proces reševanja problema kot zaporedno izvajanje enostavnih (ali predhodno definiranih) korakov.

Gotovost - tj. Vsako pravilo algoritma mora biti jasno, nedvoumno in ne sme dopuščati poljubnosti. Zahvaljujoč tej lastnosti je izvajanje algoritma formalne narave in ne zahteva dodatnih navodil ali informacij o problemu, ki ga rešujemo.

Učinkovitost (ali končnost) - algoritem mora pripeljati do rešitve problema (oz. do odgovora, da rešitve ni) v končnem številu korakov.

Množični značaj - algoritem za reševanje problema je razvit v splošni obliki, tj. uporabna naj bi bila za določen razred problemov, ki se razlikujejo le po začetnih podatkih. V tem primeru lahko izhodiščne podatke izberemo iz določenega področja, ki se imenuje območje uporabnosti algoritma.

Glavna značilnost vsakega algoritma je njegova formalna izvedba, ki omogoča, da določena dejanja (ukaze) izvajajo ne samo ljudje, ampak tudi tehnične naprave (izvajalci). Tako so lahko izvajalci algoritmov na primer človek, računalnik, tiskalnik, robotski manipulator, strojno orodje z numeričnim krmiljenjem, živa celica, dresirana žival, računalniški program, računalniški virus, “ želva« v Logowriterju ali Logomirsu (geometrični izvajalec) itd.

Izvajalec algoritma je krmilna naprava, povezana z nizom orodij. Krmilna naprava razume algoritme in organizira njihovo izvajanje z ukazovanjem ustreznim orodjem. In orodja izvajajo dejanja z izvajanjem ukazov iz krmilne naprave. Preden ustvarite algoritem za rešitev problema, morate ugotoviti, katera dejanja lahko izvede predlagani izvajalec.

Ta dejanja imenujemo veljavna dejanja izvajalca. Samo njih je mogoče uporabiti.

Izvajalec računskih algoritmov se imenuje kalkulator. Kalkulator lahko obravnava števila in spremenljivke, ki predstavljajo števila. Tako je algoritem organizirano zaporedje dejanj, ki so sprejemljiva za nekega izvajalca. Isti izvajalec se lahko simulira na računalniku na več načinov.

Kompleksnost algoritma

Kompleksnost algoritma nam omogoča, da ocenimo, kako hitro raste kompleksnost algoritma z večanjem količine vhodnih podatkov. Intenzivnost dela se nanaša na število osnovnih operacij, ki jih je treba izvesti za rešitev problema z uporabo danega algoritma. Običajno je ocena kompleksnosti algoritma izražena kot O(f(N)), kjer je O funkcija kompleksnosti, N pa število obdelanih primerov ali primerov. Najcenejši so algoritmi, pri katerih ima funkcija kompleksnosti obliko f(N)=C in f(N)=C*N, kjer je C konstanta. V prvem primeru računski stroški niso odvisni od količine obdelanih podatkov, v drugem primeru pa rastejo linearno. Najdražji so algoritmi, katerih kompleksnost je potenčno in faktorsko odvisna od števila obdelanih opazovanj.

RAZVRŠČANJE

Razvrščanje je postopek razvrščanja številnih podobnih informacijskih objektov v naraščajočem ali padajočem vrstnem redu njihovih vrednosti. Na primer, seznam i n elementov bo razvrščen v naraščajočem vrstnem redu vrednosti elementov, če i<= i <= ... <= i.

Obstajata dve vrsti algoritmov za razvrščanje: razvrščanje nizov, ki se lahko nahajajo v operativnem pomnilniku ali na disku kot datoteka z neposrednim dostopom, in razvrščanje zaporednih datotek, ki se nahajajo na diskih ali magnetnih trakovih.

Glavna razlika med razvrščanjem matrike in zaporednim razvrščanjem datotek je v tem, da je vsak element matrike dostopen kadar koli. To pomeni, da lahko katerikoli element matrike kadar koli primerjamo s katerim koli drugim elementom matrike in da lahko katera koli dva elementa matrike zamenjata mesti. Nasprotno pa je v zaporedni datoteki naenkrat na voljo le en element. Zaradi teh razlik se metode razvrščanja med obema vrstama razvrščanja bistveno razlikujejo.

Na splošno se pri razvrščanju podatkov kot ključ za razvrščanje uporablja le del informacij, ki se uporabljajo pri primerjavah. Ko se izvede izmenjava, se prenese celotna struktura podatkov.

METODE ISKANJA

Iskanje informacij v nerazvrščenem nizu zahteva zaporedno skeniranje polja. Pregledovanje se začne od prvega elementa in konča tako, da se najde element ali doseže konec niza. To metodo je treba uporabiti za nesortirane podatke, lahko pa jo uporabite tudi za razvrščene podatke. Če so podatki razvrščeni, se lahko uporabi binarno iskanje, ki je veliko hitrejše.

sistem pravil, oblikovan v izvajalcu razumljivem jeziku, ki določa proces prehoda od sprejemljivih začetnih podatkov do določenega rezultata in ima lastnosti mase, končnosti, gotovosti in determinizma.

Beseda "algoritem" izhaja iz imena velikega srednjeazijskega znanstvenika 8.-9. stoletja. Al-Khorezmi (zgodovinska regija Horezm na ozemlju sodobnega Uzbekistana). Od Al-Khorezmijevih matematičnih del sta do nas prišli le dve: algebra (iz naslova te knjige se je rodila beseda algebra) in aritmetika. Druga knjiga je dolgo časa veljala za izgubljeno, vendar so leta 1857 njen prevod v latinščino našli v knjižnici Univerze v Cambridgeu. Opisuje štiri pravila aritmetičnih operacij, skoraj enaka tistim, ki se uporabljajo zdaj. Prve vrstice te knjige so bile prevedene takole: »Rečeni algoritem. Bogu, našemu voditelju in zaščitniku, dajmo dolžno hvalo.« Tako je ime Al-Khorezmi postalo Algoritem, od koder izvira beseda algoritem. Izraz algoritem je bil uporabljen za označevanje štirih aritmetičnih operacij in je v tem pomenu vstopil v nekatere evropske jezike. Na primer v verodostojnem angleškem slovarju Webster's New World Dictionary, objavljenem leta 1957, je beseda algoritem označena kot "zastarela" in razložena kot izvajanje aritmetičnih operacij z uporabo arabskih številk.

Beseda "algoritem" se je ponovno začela uporabljati s pojavom elektronskih računalnikov za označevanje niza dejanj, ki sestavljajo določen proces. To ne pomeni samo postopka reševanja določenega matematičnega problema, ampak tudi kulinarični recept in navodila za uporabo pralnega stroja ter številna druga zaporedna pravila, ki niso povezana z matematiko; vsa ta pravila so algoritmi. Beseda "algoritem" je dandanes znana vsem, tako samozavestno je vstopila v pogovorni govor, da zdaj na straneh časopisov in v govorih pogosto najdemo izraze "algoritem vedenja", "algoritem uspeha" itd. politiki.

Turing A. Ali lahko stroj razmišlja?? M., Mir, 1960
Uspenski V. Postov avto. Znanost, 1988
Cormen T., Leiserson, Rives R. Algoritmi. Konstrukcija in analiza. M., MTsNMO, 1999

Poiščite "ALGORITEM" na

Zagotovo lahko rečemo, da mnogi poznajo izraz "algoritem". Uporablja se zelo široko in ne samo na področju računalniške tehnologije in programiranja. Nesporno je tudi, da so si mnogi izoblikovali lastno (tudi če večinoma intuitivno) razumevanje pomena tega pojma.

Izraz "algoritem" izhaja iz imena srednjeveškega matematika Abu Ja'farja ibn Muse al-Khwarizmija. Revizija zadnjega dela imena znanstvenika v evropskih državah je privedla do oblikovanja izraza "algoritem" ali "algoritem". Evropejci, ki so v 12. stoletju začeli obvladovati sodobni decimalni številski sistem, so se seznanili z deli arabskih znanstvenikov in delo zgoraj omenjenega prebivalca Horezma, posvečenega pravilom štetja v decimalnem številskem sistemu, je bilo splošno znana. Zato je bila vsebina izraza "algoritem" naslednja: operacije s števili.

Skozi stoletja se je staro, prejšnje razumevanje tega izraza začelo izgubljati in ta izraz se je začel uporabljati za en sam algoritem - evklidski algoritem, namenjen iskanju največjega skupnega delitelja para celih števil.

4.1. Definicija algoritma

Sodobno vsebino pojma algoritem lahko definiramo na naslednji način.

Algoritem– natančen opis, ki definira algoritemski proces, ki se začne s poljubnimi začetnimi podatki (iz določenega nabora začetnih podatkov, ki so možni za dani algoritem) in je namenjen pridobitvi rezultata, ki je v celoti določen s temi začetnimi podatki.

Algoritemski proces– proces zaporednega preoblikovanja konstruktivnih objektov (besed, števil, parov besed, parov števil, stavkov itd.), ki poteka v diskretnih "korakih". Vsak korak je sestavljen iz zamenjave enega strukturnega objekta z drugim.

Ker se algoritmi lahko uporabljajo za zelo poljubne objekte (številke, črke, besede, grafe, logične izraze itd.), Definicija algoritma uporablja poseben izraz - "konstruktivni objekt", ki združuje vse te možne primere. Tako lahko v spodaj opisanem algoritmu konstruktivne objekte razumemo kot trojčke števil.

4.2. Lastnosti algoritma

Vsak algoritem mora imeti naslednje lastnosti:

diskretnost(to pomeni, da je algoritem končno zaporedje posameznih korakov, od katerih vsak definira dokončano dejanje);

determinizem(to pomeni, da mora biti vsak korak algoritma razumljiv izvajalcu in se ga ne sme razlagati dvoumno);

množični značaj(to pomeni, da mora biti algoritem zasnovan tako, da izvaja cel razred podobnih nalog in ne za eno specifično nalogo);

učinkovitost(to pomeni, da mora algoritem pripeljati do enakega rezultata z enakimi začetnimi podatki, razen če algoritem delno ali v celoti temelji na dejanjih s psevdonaključnimi števili in v končnem času).

Za določitev algoritma je potrebno opisati njegove naslednje elemente:

nabor predmetov, ki sestavljajo celoto možnih začetnih podatkov, vmesnih in končnih rezultatov;

pravilo začetka;

pravilo za neposredno obdelavo informacij (opis zaporedja dejanj);

pravilo konca;

pravilo za pridobivanje rezultatov.

Algoritem je vedno zasnovan za določenega izvajalca. V našem primeru je tak izvajalec računalnik. Za zagotovitev možnosti izvedbe na računalniku mora biti algoritem opisan v računalniku razumljivem jeziku, to je v programskem jeziku.

4.3. Osnovni načini opisovanja algoritmov

Glavni načini za opisovanje algoritmov vključujejo naslednje:

verbalno-formularno (korak za korakom);

strukturni ali blokovni diagram;

uporaba grafičnih diagramov;

z uporabo Petrijevih mrež.

Pred sestavljanjem programov se najpogosteje uporabljajo metode besednih formul in diagramov poteka.

Metoda korak za korakom (verbalno-formula).. Algoritem je zapisan v obliki besedila s formulami po točkah ( koraki), ki določa zaporedje dejanj. Vsak od korakov predstavlja zelo specifično dokončano dejanje.

Primer opisa algoritma. Reševanje kvadratnih enačb. Na besedni in formulacijski način lahko algoritem za rešitev tega problema zapišemo v naslednji obliki:

1. korak: Vnesite tri številke a,b,c.

Korak 2. Izračunajte diskriminanco

Korak 3. Preverite pogoj: če d<0, то идти на шаг 8, иначе идти на шаг 4.

Korak 4. Izračunajte 1. koren

Korak 5. Izračunajte 2. koren

Korak 6. Natisnite dve številki x 1 ,x 2 .

Korak 7. Pojdite na korak 9.

Korak 8. Prikažite besedilo "Enačba nima pravih korenin."

Korak 9. Končaj.

Blok diagram je usmerjen graf, katerega oglišča so lahko ena od treh vrst, prikazanih na sl. 6.1.

Funkcionalen zgornji del uporablja se za predstavitev funkcije f: X→Y.

Predikatno oglišče uporablja se za predstavitev funkcije (ali predikata) str:X→(T,F), to je logični izraz, ki prenaša nadzor po eni od dveh možnih vej.

Sestava (sledi)	Izbira (razvejanje)	Ponovitev (zanka)

Združevalni vrh predstavlja prenos nadzora z ene od dveh vhodnih vej na eno odhodno vejo.

Blok diagram je blokovni diagram, ki ga lahko izrazimo kot sestavo štirih elementarnih blokovnih diagramov (slika 4.1).

Vsak strojni program je mogoče predstaviti s blokovnim diagramom.

Pomembna lastnost zgornjih struktur je, da imajo en vhod in en izhod.

Strukturirano programiranje– proces razvoja algoritmov z uporabo strukturnih blokovnih diagramov.

V širšem smislu strukturirano programiranje omogoča več različnih nadzornih struktur od štirih predlaganih. Razlog za razširitev raznolikosti struktur je zahteva po udobju in naravnosti.

Programiranje od zgoraj navzdol je postopek postopnega razbijanja algoritma na vse manjše dele, da bi dobili elemente, za katere je mogoče napisati posebne ukaze. Strukturirano programiranje od zgoraj navzdol je proces programiranja od zgoraj navzdol, omejen na uporabo strukturiranih blokovnih diagramov.

Strukturirano programiranje je ena najbolj razširjenih tehnologij programiranja. Največjo pozornost namenja fazi načrtovanja programa, med katero je priporočljivo upoštevati naslednja osnovna načela, t.i. načela strukturiranega programiranja:

princip modularnosti;

princip razvoja programa od zgoraj navzdol;

strukturni nadzor od konca do konca;

načelo preproste zgradbe programa.

Ta načela, ki so jih predlagali ameriški strokovnjaki ob koncu dvajsetega stoletja, ostajajo pomembna tudi v našem času, zlasti pri razvoju velikih in zapletenih programskih sistemov.