Concepte de bază ale teoriei algoritmilor - studopediya

algoritmi puse numit corespondență constructivă între cuvinte în alfabete abstracte.

alfabet Abstract - orice set finit de obiecte, numite litere sau caractere ale alfabetului. Orice alfabet este dată o listă a simbolurilor sale: A =.

Cuvântul sau un șir de alfabet definit ca orice alfabet finit de secvențe ordonate: aa, ABC, ABB.

Lungimea cuvânt este numărul de caractere ale unui cuvânt.

cuvânt gol - un cuvânt de lungime zero.

Word P - sub-cuvânt cuvânt cuvânt Q dacă Q pot fi reprezentate sub forma: q = pr. Operatorul alfabetice (cartografiere) este orice cuvinte corespondență care asociază alfabet Un cuvânt cu același sau un alfabet diferit. În acest caz, primul alfabet cunoscut sub numele de intrare și de ieșire al doilea operator.

Operatorul alfabetice - funcție care definește hectare de relații = c.

Operatorul alfabetice este dat de:

Figura 1 - Stabilirea operatorului alfabetic grafic.

Distinge operatori alfabetice lipsite de ambiguitate și multi-evaluate.

Sub operatorul alfabetic simplu se referă la un operator care fiecare cuvânt de intrare este pus sub nici un cuvânt mai mult de o ieșire (figura 2).

alfabetic operatorul multivaloare folosit înțelege un operator, astfel încât fiecare cuvânt de intrare este plasat sub unul sau mai multe cuvinte de ieșire (figura 1).

Figura 2 - unic Operatorul alfabetic.

Operatorul alfabetice nu se asociază cu un cuvânt dat alfabet Ai nici un cuvânt de ieșire Bj, inclusiv un gol, nedefinit la Ai cuvânt.

Colectarea tuturor cuvintelor, care este definit operatorul alfabetice se numește domeniul de definiție.

Cartografierea fiecare caracter de intrare de caractere de caractere alfabet în cuvintele de ieșire alfabet numit de cartografiere de codificare.

Procesul de codificare inversă - decodificare.

Decodificarea operatorul T -1 B = a.

aabacd → kkklkmlll

Pentru reversibilitatea de codificare trebuie îndeplinite două condiții:

1. Codurile de intrare diferite caractere ale alfabetului trebuie să fie diferite;

2. Codul cu privire la orice intrare de caractere alfabet nu ar trebui să coincidă cu oricare dintre sub-cuvinte inițiale alte coduri de caractere.

Codificare, în care toate codurile sunt de aceeași lungime, a declarat a fi normal.

Cel mai adesea ca codificarea de intrare a alfabetului folosind sistemul binar.

Pentru a determina lungimea cuvântului de cod se utilizează formula:

m - numărul de caractere din alfabetul de ieșire;

l - lungimea cuvântului de cod,

n - numărul simbolurilor de intrare alfabetului.

Operatorii alfabetice date printr-un sistem finit de reguli numite algoritmi.

Doi algoritmi sunt considerate egale, dacă acestea sunt egale cu operatorii alfabetice corespunzătoare și același sistem de reguli care definește acțiunea algoritmului.

Doi operatorul alfabetice sunt considerate egale dacă au același domeniu și în comparație cu orice rezultate identice cuvânt de intrare.

Cele două afirmații sunt echivalente în cazul în care au aceleași operatori alfabetice, dar nu la fel ca regulile sistemului.

Algoritmi bazate pe operatorul alfabetic de o cifră numit determinist.

Un algoritm numit masa, în cazul în care se aplică o multitudine de cuvinte de intrare.

În cazul în care algoritmul oferă un rezultat după un număr finit de pași, este numit eficient.

Pe baza impactului proprietății urmează conceptul de domeniul algoritmului.

Intervalul de aplicabilitate a algoritmului - o pluralitate de linii de intrare pentru care rezultativen algoritm. Apoi, doi algoritmi sunt considerate echivalente în cazul în care același interval de aplicabilitate și prelucrarea rezultatelor oricăror cuvinte din acest domeniu.

Algoritmii se numesc aleator în cazul în care sistemul de norme prevede posibilitatea unei selecții aleatorii a cuvintelor de intrare sau reguli de conversie.

Algoritmul se numește auto-modificatoare, în cazul în care procesele nu numai cuvinte de intrare, dar, de asemenea, schimbările în procesul.

Orice modalitate de a specifica algoritmi numit sistem algoritmică.

Sistemele algoritmice sunt împărțite în:

Un sistem algebric este construit într-un anumit simbolism, în care algoritmii prezentate sub forma unor texte liniare:

Funcții recursive Ø;

mașină de Ø Turing;

operator de sistem Ø Wang Hao;

Ø circuit logic solstițiului de vară.

În sistemul geometric al algoritmilor construite sub formă de seturi între care a intrat comunicarea cu hărțile de caracter sau relațiile binare. Algoritmii sunt prezentate ca scheme grafic:

Mașini de stat; Ø

Ø Markov algoritm normale;