TEOREMA BOHM-JACOPPINI

-
TEOREMA BOHM-JACOPPINI

Importanţa acestei teoreme pentru programarea structurată este majoră deoarece ea stabileşte setul minim de instrucţiuni necesare pentru implementarea corectă a structurilor de bază ale algoritmilor.

Pentru descrierea oricărui algoritm sunt necesare următoarele instrucţiuni:
1. atribuire
2. decizie completă (structura alternativă cu două ramuri)
3. structura repetitivă cu test iniţial (CÂT_TIMP <>WHILE)

Importanţa acestei teoreme nu ne permită să o lăsăm nedemonstrată. Vom da o demonstraţie prin prezentarea modului de descriere a celorlalte structuri din aceeaşi categorie prin structurile menţionate în enunţ, renunţând la rigurozitatea matematică în favoarea conciziei.
Este important de reţinut că operaţiile I/O nu sunt esenţiale în descrierea algoritmului de rezolvare a unei probleme, rolul lor fiind de a asigura interacţiunea cu utilizatorul.
1. Pentru structura liniară, afirmaţia este evidentă.
2. Decizia simplă este un caz particular (trunchiat al deciziei complete).
Structura de selecţie cu n cazuri se poate descrie printr-o succesiune de n-1 decizii complete, fiecare testând în condiţia ei dacă valoarea evaluată a expresiei ordinale din capul structurii este sau nu egală cu una dintre constantele prezente în lista cazului respectiv. Dacă da (ramura THEN), atunci se execută instrucţiunea asociată, dacă nu (ramura ELSE) se face selectarea unui nou caz dintre cele rămase:
(A se vedea şi observaţia de la prezentarea schemelor logice pentru acest tip de structură alternativă).
3. Structura repetitivă cu test final se comută rapid la cea cu test iniţial prin utilizarea secvenţei înainte de intrarea în bucla cu test iniţial şi apoi implementarea buclei cu test iniţial care conţine condiţia negată.
Reprezentarea structurii cu număr determinat de paşi (PENTRU<>FOR) este chiar mai evidentă. O prezentăm în cele ce urmează;
var_c:=Li;
CÂT_TIMP var_c<>Lf EXECUTĂ
Secvenţa din FOR
var_c:=var_c+Pas
SFÂRŞIT_CÂT_TIMP.

Comentarii

Trimiteți un comentariu

Postări populare de pe acest blog

Alt set de probleme

-
Ne propunem in continuare sa adaugam un set nou de probleme pe blog, pentru ca elevii dornici sa munceasca sa aiba de unde alege probleme. I.Structura liniara si structura de selectie 1. Un bazin se umple cu apa prin intermediul a doua robinete.Daca lasam primul robinet deschis timp de h1 ore si al doilea robinet timp de h2 ore, in bazin vor fi p litri de apa. Daca primul robinet curge h1+1 ore iar al doilea h2-1 ore, in bazin vor fi o litri de apa. Scrieti un program care afiseaza cati litri de apa curg prin fiecare robinet timp de o ora. 2.Doua autobuze efectueaza curse regulate intre orasele O1 si O2. Primul autobuz pleaca din orasul O1 catre orasul O2 si circula cu viteza v1(kilometric/ora). Iar al doilea pleaca din orasul O2 catre orasul O1 si se deplaseaza cu v2 km/h. Stiind ca distanta dintre cele doua orase este d kilometric, scrieti un program care calculeaza dupa cat timp se intalnesc autobuzele si la ce distanta fata de orasul O1 are loc intalnirea. 3.Fiind date dou
Citiți mai multe

Obiecte cu care lucreaza algoritmii

-
OBIECTE CU CARE LUCREAZĂ ALGORITMII, OPERAŢII PERMISE: Algoritmii lucrează cu: date şi variabile. Algoritmii preiau datele de intrare asupra cărora acţionează pentru a obţine date de ieşire (rezultate). Datele se caracterizează prin tipul lor, valoarea pe care o conţin (corespunzătoare tipului) şi modul în care se tratează aceasta valoare (variabilă sau constantă). Datele pot fi: întregi, reale, logice, şir de caractere. Datele întregi şi reale poartă numele de date numerice. Datele reale sunt numere zecimale. Mulţimea numerelor reale este o reuniune între mulţimea numerelor raţionale şi mulţimea numerelor iraţionale. Deoarece calculatoarele nu pot reţine numere iraţionale, în informatică, printr-o dată reală înţelegem o valoare cu un număr finit de zecimale. Datele logice au două tipuri de valori: TRUE(adevărat) şi FALSE (fals). Datele de tip şir de caractere sunt reprezentate prin şiruri de caractere cuprinse între apostrofuri. Constantele sunt date care nu-şi modifică valoarea pe pa
Citiți mai multe

Caracteristicile unui algoritm

-
Fiecare propoziţie care face parte din descrierea unui algoritm este de fapt o comandă care trebuie executată de „cineva”. Comanda specifică o operaţie (acţiune) care se aplică datelor algoritmului determinând modificarea acestora. În ansamblu deci, algoritmul specifică posibilele succesiuni de transformări ale datelor, care conduc la aflarea rezultatelor. În consecinţă, caracteristicile unui algoritm sunt: • GENERALITATE: algoritmul trebuie să rezolve o clasă de probleme de acelaşi tip; • FINITUDINE: algoritmul trebuie să se termine pentru orice date de intrare; • UNICITATE: pentru aceleaşi date de intrare trebuie să se obţină aceleaşi date de ieşire în urma parcurgerii aceluiaşi algoritm.
Citiți mai multe