Puteți ajuta adăugând referințe sau eliminând conținut nepublicat. Consultați pagina de discuții pentru mai multe detalii.
EXEL este un limbaj de descriere algoritmică proiectat în 1973 de informaticianul francez Jacques Arsac care a numit această limbă din cuvântul „excelent”.
Unul dintre obiectivele acestui limbaj este acela de a descrie un algoritm independent de limba în care va fi apoi implementat, care, în plus, poate fi EXEL însuși ... Limbajul EXEL face posibilă specificarea ambelor caracteristici ale datelor (matrice matricea arbitrară, triunghiularizată etc.) decât algoritmii înșiși (de exemplu produsul matricei ). Un algoritm de inversare a matricei pe care îl compunem cu caracteristicile unei matrice triunghiulare oferă automat prin simplificări algebrice un algoritm de inversare simplificat optimizat pentru matricile triunghiulare, de exemplu.
Autorul definește diagrama pașilor metodei computerului după cum urmează:
Situație concretă → Problemă → Algoritm → Program → Rezultate
La început, există o stare de fapt care generează o problemă: aceasta este ceea ce autorul desemnează printr-o situație concretă descrisă în limbaj natural. Prin abstractizare, este asociat cu o reprezentare formală. Aceasta definește problema.Pentru a rezolva această problemă, va fi necesar pe cât posibil (probleme NP-complete ...) să construim un algoritm. Traducerea acestui algoritm într-un limbaj de programare constituie Programul care va fi executat pe computer și va oferi rezultate. Interpretarea rezultatelor este lăsată în grija omului.
Ideea, implicită în proiectarea limbajului EXEL, este, pe cât posibil, de a construi un algoritm eficient într-un mod sistematic: toate transformările și simplificările vor fi îngrijite de mașină, în acest caz computerul, permițând rezultatele care trebuie atinse ...
EXEL este pentru algoritmi ceea ce este geometria analitică pentru geometrie: fie imediat se găsește o soluție geometrică, altfel poate relaționa întotdeauna ipotezele problemei cu geometria analitică (adică coordonatele carteziene ...). Cu limbajul EXEL, fie se găsește imediat un algoritm eficient, fie limbajul EXEL oferă posibilități pentru manipularea formală a programelor care fac posibilă construirea unui algoritm eficient ... Nu există o metodă generală pentru construirea unui algoritm nu mai mult decât există o metodă generală pentru rezolvarea vechilor probleme de construcție geometrică sau pentru găsirea unei dovezi a teoremei. Acesta este motivul pentru care prezentarea limbajului EXEL se va face folosind exemple.
Scrierea frecventă a programelor lungi cu limbi precum Fortran, Algol , Pascal ... este plictisitoare. Pentru a permite o scriere condensată a programelor, cum ar fi matematica unde există abrevieri ca , pentru a desemna orice element ,, pentru că există ... instrucțiunile limbajului EXEL au fost definite după cum urmează:
Fie t1, t2 două predicate, a1, a2, a3, a4 alternanții selectați conform indicației date în fața fiecăruia dintre ele:
prima literă se referă la primul predicat și a doua la a doua. F desemnează valoarea FALS și V valoarea ADEVĂRATĂ.
Se notează instrucțiunile de selecție multiplă:
(t1, t2) `? FF: a1 | FT: a2 | TF: a3 | TT: a4
astfel, a2 se execută dacă t1 este fals și t2 este adevărat ...
Limbajul EXEL constă din trei tipuri de instrucțiuni fundamentale:
Se notează instrucțiunea de atribuire:
< nom >< valeur >
<nume> este numele unei variabile, simple sau indexate.
<value> desemnează orice constantă, variabilă sau expresie care are o valoare.
Expresiile vor fi scrise urmând convențiile algebrei, folosind paranteze pentru a specifica prioritatea dintre operatori de îndată ce ne abatem de la cele mai obișnuite cazuri (de exemplu, ȘI, SAU ...).
Se notează selecția:
< test >?< suite d'instructions séparées par ; >|< suite d'instructions séparées par ; >¿
Dacă testul este ADEVĂRAT, executăm seria de instrucțiuni din dreapta barei, ELSE, executăm seria de instrucțiuni din stânga barei.
<secvența de instrucțiuni> este orice secvență de instrucțiuni, opțional poate fi redusă la o singură instrucțiune sau chiar goală.
<test> este o expresie booleană. Testul este evaluat: dacă valoarea sa este FALSĂ, se execută secvența de instrucțiuni din stânga barei și se termină instrucțiunea de selecție. Dacă valoarea este ADEVĂRATĂ, se execută secvența de instrucțiuni din dreapta barei și se termină instrucțiunea de selectare.
Există două forme de iterație:
Catarama cat mai multCea mai comună formă este iterația cu instrucțiunea TQ:
TQ <t> <suite d'instructions>
<t> est une expression booléenne.Lexecutarea este după cum urmează:
1) evaluează t
2) dacă t este ADEVĂRAT, executați secvența de instrucțiuni și reveniți la 1 altfel iterația este încheiată.
Buclă cu ieșire<suite d'instructions avec sortie de boucle notée !>
Secvența de instrucțiuni între acolade este executată atâta timp cât semnul! Nu este atins. Când este atins, ieșim din buclă și continuăm în secvență. EXIT ar trebui interpretat ca ieșind din iterația de închidere și continuând în ordine după ea. Prin extensie, putem indexa !. Astfel,! P indică ieșirea p iterațiilor care conțin, se notează! 1!, Indexul 1 este omis.
Sau pentru a schimba conținutul a două sloturi de memorie:
Se face distincția între adresa unei celule de memorie cu care este asociată variabila A și conținutul acesteia cu care este asociată o valoare, de exemplu a.
La fel și pentru o altă celulă de memorie cu care sunt asociate o variabilă B și o valoare b.
Fie C o variabilă intermediară care permite salvarea conținutului lui A.
Algoritm:
C←A; A←B; B←C
Nota 1:
De-a lungul celorlalte exemple prezentate, instrucțiunile de intrare / ieșire vor fi omise, conform definiției limbajului EXEL.
Valoarea absolută a unei variabile x, | x | = dacă x> 0 atunci x altfel -x. Ce este scris în limbajul EXEL:
|x| = x>=0 ? -x | x ¿
Nota 2:
Noțiunea de variabilă în informatică diferă de noțiunea de variabilă în matematică:
În matematică, conținutul unei variabile este constant, în informatică, conținutul unei variabile depinde de momentul în care variabila este luată în considerare.
Limita superioară Exemplul 1sup (a, b) = dacă a> = b atunci altceva b. Ce scrie în EXEL
sup(a,b) = a>=b ? b | a ¿
Exemplul 2sup (a, b, c) = sup (sup (a, b), c)
sup (a, b, c) = sup (a, b)> = c? c | sup (a, b)¿
sup (a, b, c) = (a> = b? b | a ¿)> = c? c | a> = b? b | La¿¿
În informatică, o operație repetitivă este menționată prin cuvântul iterație, în matematică prin recurență. Raționamentul prin inducție face posibilă construirea algoritmilor iterativi. Aceasta este o axiomă în teoria numerelor întregi pe care Peano o definește după cum urmează:
Fie P o proprietate verificată pentru valoarea 0, dacă această proprietate este, de îndată ce este adevărată pentru i, atunci este adevărată pentru i + 1, atunci această proprietate este adevărată indiferent de i. Cerere:
Consultație de masă liniarăFie a [1: n] o matrice de n elemente, de exemplu numărul de cărți de identitate.
Fie x un număr de căutat în tabel.
Fie t o variabilă booleană: dacă x se găsește în tabel, atunci t = Adevărat (adică V) altfel t = Fals (adică F)
Ipoteza recurenței:
Presupunem că am scanat tabelul până la rândul i și x nu a fost găsit.
Dacă i> n atunci x nu este în tabel, ieșiți din buclă altfel dacă se găsește a (i) = x, ieșiți din buclă altfel incrementăm i și restabilim ipoteza inducției.
inițializare: i ← 1
Algoritm în limbajul EXEL
I ← 1. t ← F;
i≤n? ! | a [i] = x? i ← i + 1 | t ← V!¿¿
Algoritm echivalent:
I ← 1. t ← F; i≤n? ! | a [i] ≠ x? t ← V! | i ← i + 1 ¿¿
Observație:
Utilizarea unei variabile booleene nu este necesară. Într-adevăr, conform definiției limbajului EXEL, la ieșirea dintr-o buclă, putem prelua valoarea unei variabile controlate. Prin urmare, dacă i≤n atunci x este în tabel. Cu toate acestea, este încă necesar ca compilatorul în care va fi implementat algoritmul să respecte această caracteristică, ceea ce este rar cazul. Cu toate acestea, luând în considerare această caracteristică, algoritmul anterior devine:
I ← 1. i≤n? ! | a [i] ≠ x? ! | i ← i + 1 ¿¿
dacă i≤n atunci x este în tabel în poziția i altfel x nu este în tabel.
Testele utilizează mai multe cicluri de ceas în funcție de mașini, această buclă poate fi accelerată:
Prin inserarea x în caseta n + 1, algoritmul devine:
i ← 1; a [n + 1] ← x;a[i]=x? i←i+1 | t←V !¿
Algoritm echivalent:
i ← 1; a [n + 1] ← x;a[i]≠x? t←V ! | i←i+1 ¿
Algoritm cu instrucțiunea TQ:
i ← 1; a [n + 1] ← x; TQ x a[i] i←i+1
Această adăugare de x la caseta n + 1 este posibilă numai dacă tabelul nu este saturat ...
Nota 1:
Ordinea elementelor din tabel este arbitrară. Cu toate acestea, tabelul poate fi sortat (vezi capitolul de sortare) în ordinea frecvenței de acces descrescătoare. Căutarea este mai scurtă, deoarece rangul elementului căutat este mai mic. Pe de altă parte, s-a admis implicit că elementul căutat era unic, nu este cazul general. pot exista mai multe elemente corespunzătoare elementului căutat; de aici importanța celui mai mic indice i astfel încât a [i] = x notat după cum urmează:
k = MU (i: a [i] = x), dacă k = n + 1, x nu este în tabel.
Nota 2:
Autorul avertizează împotriva utilizării buclei „WHILE”, care uneori este o sursă de erori de programare și complică dovezile programului ... În acest scop, el citează exemplul următorului algoritm care ar trebui să facă o căutare în tabel și care este greșit :
i ← 1; TQ i≤n et a [i] x DOi←i+1 FIN FAIRE
Dacă x nu este în tabel, indicele i atinge valoarea n + 1, iar compilatorul ar trebui să verifice a doua condiție a testului care este un [i] x, unde un [n + 1] nu este definit ce ar trebui să genereze un mesaj de eroare. Cu toate acestea, unii compilatori, imediat ce primul test este FALS, continuă în ordine și nu raportează o eroare.
ComplexitateEste nevoie de cel mult n operații pentru a găsi x, de aceea complexitatea unei căutări liniare a tabelului este de ordinul lui n.
consultarea la masă prin dihotomieUn alt exemplu pentru iterație: consultarea la masă prin dihotomie.
Consultarea tabelului prin hash (adică codificarea Hash)Un alt exemplu de iterație este căutarea tabelului prin hashing.
Comentariile vor fi inserate între ghilimele duble „...” vor fi auto-explicative sau se vor referi la comentariile detaliate plasate în afara programului (excesul de comentarii din program umbră instrucțiunile)