Conceptul algoritmului în sens intuitiv, proprietățile de bază ale algoritmului

Definiția intuitivă a algoritmului

Intuitiv, care este, format pe baza experienței. În secolul al 19-lea AD - Al Harezmi a călătorit de la țară la țară, rezultând în așa a venit termenul „algoritmi“, adică „algoritm“. Al Harezmi a dezvoltat regulile aritmetice. Algoritmul intuitiv este definit ca (școală) un executor clar și precis de instrucțiuni pentru a face o anumită secvență de acțiuni pentru a atinge un anumit scop. Prescripție medicală într-un alt mod - comanda. Artist - este ceva care poate accepta o comandă și punerea în aplicare a acestora, așa cum este înzestrat cu capacitatea de a efectua un anumit set de acțiuni, sub influența unui sistem de comenzi (comenzi).

Algoritmul (Biblioteca de referință programatorului) - de obicei, format într-o anumită limbă și definirea procesului de conversie a datelor valabile necesare și care îndeplinește următoarele proprietăți:

Mass.
Potențialul de fezabilitate.
Inteligibilității.
Certitudine.

Algoritmul - este exact formulat într-o anumită limbă descriere finită a unei metode generale bazată pe utilizarea executabilelor elementare Tats de control numărul de rulare.

Modalități de reprezentare algoritmi intuitive

printr-o descriere grafică sau verbal (grafic - Schema bloc limbaj)
sub formă de tabel
secvență formule
în limbajul de programare sau limbaj de programare

Diagrama bloc este reprezentat ca un grafic al unui tip special. Vârfurile corespund anumitor părți ale algoritmului, iar arcele indică posibile tranziții.

Forma de prezentare a rezultatelor științifice
Ghid pentru acțiune atunci când decizia a studiat deja programe
Instrument care vă permite să salvați mentale
solutii pas de automatizare a problemelor
Instrument sau dispozitiv, de cercetare noi probleme.
Mijloace de descriere matematică
Un mijloc de a descrie procese complexe

Principii de proiectare algoritm pentru aplicații

Cea mai importantă componentă a programului este dezvoltarea de algoritmi. În prima etapă a predominat abordare operațională (în timp ce primele calculatoare), adică algoritmul este orientat spre operațiuni specifice (de atribuire, comparație, condiționată (necondiționat) salt, aritmetice). Acesta a fost bazat pe caracteristicile specifice ale computerului. Abordarea structurală (apariția din generația a treia (70)) - structura de program logic poate fi exprimată printr-o combinație de trei structuri de bază (Bohm-Yakopini teorema):

Abordarea structurală este programe și algoritmi modularitatea și proiecția în jos (problema este împărțită într-un număr de subactivități). (Exemplu - Pascal)

Obiectul - conceptul de bază al programării orientate pe obiecte. Procedura descrie algoritmul din cadrul acestui program, pentru care este proiectat. Obiectul poate fi atribuit o altă zonă subiect, executat într-un stil diferit. Problema inițială este reprezentat ca un set de interacțiune obiect (Delphi).

abordare declarativă (introdus in anii '40) are ca scop gama de probleme ale inteligenței artificiale. Programator descrie proprietățile datelor originale, care ar trebui să aibă proprietăți de rezultat. Și nici un algoritm, sarcini care ar trebui să fie stabilite în mod automat de către sistem.

Versiune logică (prolog) - sarcină descrie setul de reguli și fapte într-un limbaj formal.
funcțională (Lispt) - descris relații funcționale între fapte.

Dezvoltarea ideii de programare paralelă și altele.

Până în secolul al 20-lea noțiunea intuitivă de algoritm a fost suficient. Situația sa schimbat în secolul al 20-lea, când au fost formulate probleme, soluție algoritmică care nu a fost evidentă. Pentru a dovedi existența unui algoritm pentru a rezolva o problemă care aveți nevoie pentru a utiliza acest algoritm sau de a dezvolta altele noi. Mai greu a fost problema de a dovedi non-existenta a algoritmului pentru o anumită clasă de probleme.

Un alt aspect de construcție motiv algoritm precis este conceptul vag de un pas elementar în definiția intuitivă. Când la începutul matematician secolului 20 a apelat la studiul proprietăților obiectelor complexe (matrice, determinanți), conceptul de un pas elementar a încetat să mai existe și nu a fost nevoie de o definiție exactă a termenului „algoritm“ - este comună tuturor tipurilor de algoritmi. Ar trebui să fie în mod oficial strictă și să se conformeze intuitiv. Ceea ce a dus la o știință independentă - teoria algoritmilor, care studiază metode pentru a demonstra proprietățile procedurilor matematice, etc. Apariția tehnologiei de calculator a arătat că baza informatică ar trebui să se bazeze pe conceptul de „algoritm“. Prima lucrare fundamentală pe teoria algoritmilor au fost obținute la mijlocul anilor '30. Și în 1931, Gödel a demonstrat că anumite probleme matematice nu pot fi rezolvate prin algoritmi de o anumită clasă. Și în mijlocul anilor '30, Turing a pus bazele teoriei algoritmilor. La începutul anilor '50 semnificativă contribuția adusă de Kolmogorov și Markov. Abordările teoretice la determinarea definiția strictă a termenului „algoritm“ izolat 3 fixat:

Asociat cu conceptul de „funcții de calcul“ și funcții recursive parțiale.
Datorită mașinii matematică. proces algoritmică - un proces care poate face aparatul aranjate în mod corespunzător din punct de vedere matematic descris mașini de clase înguste: mașină Turing, Postul Mare; Sa dovedit că este posibil să se pună în aplicare toate procesele algoritmice cunoscute prin aceste mașini.
Este legat de conceptul de „algoritm normal“ și a dezvoltat marca sa în 1954.

În ciuda diferitelor abordări, se dovedește că acestea sunt echivalente.

Markov algoritmi normali

În 1954, A. A. Markov a propus un sistem în care, ca într-o mașină Turing tradus cuvinte, dar bazate pe alte principii - și anume, nu există conceptul de „bandă“ și a însemnat acces imediat la diferite părți ale cuvintelor convertite. Acest sistem a fost numit Markov algoritmul normal.

Alege unele alfabet sursă, cuvintele sunt construite pe ea. Apoi, algoritmul normal poate fi scris după cum urmează:

înlocuire efectuează procesul de înlocuire și se termină (opriri)

set ordonat de perechi de cuvinte (în care A1 ... An - poate fi atât un semn și un cuvânt), legate între ele prin săgeți de două tipuri. Fiecare pereche reprezintă o formulă permutare pentru a înlocui subwords convertite într-un cuvânt. Efectuarea unui algoritm normale este împărțit în baruri. Fiecare ciclu include o primă comandă de căutare cu formula substituție aplicabilă și utilizarea acestei formule. Primul ciclu începe cu verificare: dacă partea cuvântul A1 a cuvântului de intrare, care este un factor.

De exemplu, în „informatică“ cuvânt este o apariție a cuvântului „Institutul“. Dacă este inclus, acesta subword înlocuit pe partea dreaptă - B1, etc. Astfel, există o schimbare a cuvântului de intrare prin substituirea unui subword de altul. Dacă nu există nici o intrare, se verifică a doua pereche, etc. Dacă încercați să aplicați formula de substituție are mai multe apariții ale lui Ai, aceasta se înlocuiește cu intrarea din stânga, iar în cazul în care un fel de formulă nu a putut fi aplicată, atunci există o încercare de a aplica următoarea formulă. Procesul de executare a algoritmului normale se încheie în următoarele cazuri:

sau toate formulele care nu sunt valabile, adică, într-un cuvânt prelucrat nu există evenimente de orice stânga.
sau pur și simplu a fost folosit formula finală, conectat final săgeată.

În oricare dintre aceste cazuri, se crede că algoritmul normală este aplicabil unui anumit cuvânt.

În cazul în care în timpul executării numărul normal de ori algoritmul este aplicat ∞ formula unkillable, algoritmul nu se aplică cuvânt de intrare procesată. Piesele din stânga și din dreapta pot conține cuvinte goale. Pentru a înregistra cuvântul gol nu are nevoie de nici o denumire specială, și de a converti cuvântul poate fi ușor de mutat în afară și pentru a muta.

Trecerea de la alte moduri de a descrie algoritmi pentru algoritmul normal de se numește o reprezentare în formă normală, sau normalizare.

Exemplu: Encoding 0 și 1 alfabet [a, b, c].

Prin definiție, există apariții de cuvinte goale de pe partea stângă și dreaptă a fiecărui cuvânt luat în considerare, atunci uite _ → o - va fi infinit atribui o literă la stânga cuvântului de intrare, care este, algoritmul nu poate fi aplicată, după caz.

Două indiciu suficient de simplu de aplicabilitate a algoritmului normal:

în toate formulele de substituire pe partea stângă nu este gol, iar partea dreaptă nu includ literele care apar pe laturile din stânga.
fiecare parte dreapta regula de substituție este mai scurtă decât stânga.

Algoritmul îndeplinește al doilea criteriu, formula nu conține piese de substituție rămas cu gol (goale, deoarece cuvinte mai scurte nimic, prin urmare, a doua caracteristică nu este executată).

Exemplu: construi un algoritm pentru atribuirea oricărui alfabet cuvânt [a, b, c] la scrisoarea dreapta. Spre deosebire de mașină Turing, algoritmul normal de nu are acces direct la capătul din dreapta al cuvântului de intrare. * Introducem pentru a marca locuri de interes în cuvântul. Vom implementa algoritmul în conformitate cu următoarea schemă:

* Atribuim stânga.
* Dacă nu este ultimul cuvânt, apoi schimba în locuri cu următoarea literă.
* Înlocuiți litera a, și a opri procesul.

Compararea diferitelor scheme algoritmice

În cazul în care este posibil să se reducă problema la unele probleme nerezolvate, ne arată că această problemă este de nerezolvat. Luați în considerare o auto-aplicabilitate pe schema Markov. Algoritmul se poate termina, dar poate - nu. Prin urmare Markov algoritm poate fi împărțit în două: auto-cererea pentru care există un algoritm pentru care nu există.

Algoritmul, care ar putea rezolva cu siguranță nici o problemă, și anume algoritmul de recunoaștere nu există, adică, aceasta înseamnă că problema de sine este insolubil. Dacă luăm algoritma → o, atunci nu samopimenim, a- samoprimenim. Pentru cazuri specifice, puteți identifica în mod specific, dar nu există nici un algoritm universal, adică, nu există nici un algoritm care ar rezolva toate problemele de auto-clasă.