Cunoștințe, prelegere, algoritmi de program structurat

Adnotare: Algoritmi și modele de calcul. Programe structurate: sintaxă și semantică. Funcții aritmetice calculate prin programe structurate

Ce este un algoritm?

Scopul inițial al teoriei algoritmilor este de a clasifica toate sarcinile pe algoritmic rezolvabilă și de nerezolvat, și anume, pe cele pentru care există algoritmi decisivi. și cele pentru care nu există astfel de algoritmi. Informal de algoritmul poate fi înțeleasă așa cum este exprimat într-un limbaj, un set de reguli (prescripție, prescripție, modul), care permite să se aplice la sursa (de intrare) de date X a unui set de serii de date X valabil de acțiuni discrete (operațiunile de echipe), ceea ce duce la un anumit rezultat - datele de ieșire a unui Y. set, în acest caz, se spune că algoritmul calculează o funcție de tipul X -> Y. această definiție laxe este foarte potrivit în cazurile în care, pentru anumite funcții, am prezentat „obiect“, numit și goritmom calculele sale (de exemplu, algoritmul lui Euclid pentru calculul celui mai mare divizor comun a două numere întregi), și este posibil să se verifice cu ușurință dacă el într-adevăr permite să se calculeze funcția dorită. Totuși, este complet inadecvat să se demonstreze că pentru o funcție dată nu există un algoritm.

Deși algoritmii în diferite domenii de aplicare a face cu obiecte discrete de diferite tipuri :. numere întregi și numere raționale, siruri de caractere, formule, tot felul de expresii, grafice, matrici, tabele, bitmap-uri, etc suntem în această parte a cursului vom lua în considerare doar problema de calcul a funcțiilor argumente naturale care iau în considerare valorile naturale. Astfel de funcții sunt adesea numite funcții aritmetice. Faptul este că pentru orice număr natural de obiecte discrete (în special, pentru toate cele de mai sus), există o simplă codificare a numerelor întregi sale elemente. Prin urmare, problemele de calculare a funcțiilor pe aceste seturi se transformă în probleme de calcul al funcțiilor aritmetice.

Ne amintim că N denotă setul de numere naturale, adică N =. Pentru o funcție aritmetică parțială n-locală f: N n → N, desemnează domeniul definiției sale. Pentru a indica faptul că f nu este definită pe un anumit set de numere a1. o scriem și dacă f este definită pe acest set, atunci scriem. Astfel.

Programe structurate

În această secțiune vom analiza programele structurate ca mijloc de descriere a algoritmilor. Ei calculează funcțiile utilizând mijloace minime: asignări elementare. declarații condiționale și bucle.

Mai întâi, definim sintaxa programelor structurate. Pentru aceasta vom repara un set numar variabil de variabile Var. care vor fi folosite în programe. Ca de obicei, presupunem că include numele x, x1, x2. y, y1. z, z1. și altele asemenea. În următoarele definiții, x, y, z sunt variabile arbitrare de la Var.

Definiție 7.1. Operator de atribuire. Asignarea este o expresie a unuia dintre următoarele trei tipuri:

Definiția 7.2. Condiții. O condiție este o expresie a unuia dintre cele două tipuri:

totul este un program structurat.

Construcția din (b) se numește o aplicație secvențială sau o compoziție a programelor, iar construcția din (c) este numită operator condițional; Construcția în n. (R) este operatorul ciclului. starea ciclului. a este corpul ciclului.

Cu ajutorul programelor structurate (denumite în continuare pur și simplu ca programe), funcțiile (parțiale) sunt calculate din argumente naturale care iau în considerare valorile naturale. Cu fiecare program, asociază în mod natural setul de variabile incluse în el (definiți acest set prin inducție la construirea programului). În procesul de lucru, programul modifică valorile acestor variabile. Semantica operațională stabilește regulile pentru această schimbare.

Definiția 7.4. Statul este o mapare din setul de variabile Var la mulțimea N. Pentru că vom denumi valoarea variabilei x în stare. Fie S să denumească setul tuturor stărilor.

Desigur, atunci când analizăm un anumit program, vom fi interesați de valorile variabilelor de la.

Definiția 7.5. Semantica operațională a unui program este o selecție (în general, parțială) de tip S -> S. Programul induce pe setul de toate stările. Prin denumirea statului - rezultatul aplicării programului către stat. Se determină prin inducție la construirea programului.

• , unde, și.
• , unde, și.
• , unde, și
• Lasă-l să fie. Apoi, în acest caz, dacă și apoi.

Să presupunem că dacă x = y atunci sfârșitul. atunci

Să presupunem că dacă x