Pagina iniziale | Navigazione |
Google

Teoria della computazione

La Teoria della computazione Ť quella branca della matematica che si preoccupa di definire quali propriet√† possiede uno specifico linguaggio formale. Le principali propriet√† ricercate da un linguaggio formale sono:

  • La Correttezza
Ogni volta che un linguaggio formale definisce un enunciato come vere questo enunciato deve effettivamente essere vero.

  • La Completezza
Il linguaggio formale deve essere in grado di estrarre tutti gli enunciati veri, e solo quegli enunciati devono essere veri, se il linguaggio Ť completo non devono esistere altri enunciati veri ad di fuori di quelli precedentemente estratti

  • La Terminazione
Ogni algoritmo correttamente definito nel linguaggio formale deve terminare sempre in tempo finito.

Non tutte le propriet√† sono necessarie, spesso i linguaggi formali hanno solo la prima e la seconda propriet√†. In alcune applicazioni ci si accontenta di avere anche solo la prima propriet√† che chiaramente Ť irrinunciabile, senza la prima propriet√† si potrebbero avere enunciati chiaramente falsi ma che vengono dichiarati veri dal linguaggio formale generando contraddizioni.Nel caso si abbiano tutte le tre propriet√† e conveniente cercare di definire la complessit√† degli algoritmi definiti del linguaggio formale. La complessit√† Ť una funzione che stima il numero di passi necessari ad eseguire uno specifico algoritmo.


GNU Fdl - it.Wikipedia.org




Google | 

Enciclopedia |  La Divina Commedia di Dante |  Mappa | : A |  B |  C |  D |  E |  F |  G |  H |  I |  J |  K |  L |  M |  N |  O |  P |  Q |  R |  S |  T |  U |  V |  W |  X |  Y |  Z |