Algoritmo: differenze tra le versioni

Versione delle 14:05, 22 giu 2023

Versione delle 14:07, 22 giu 2023

Riga 92:

dove <math>D \pi</math> sono le istanze del problema e <math> S \pi </math> sono le soluzioni e <math>\forall x \in D \pi:f \pi (x) </math> sia una soluzione al problema per l'istanza x.

=== Studio della complessità computazionale di un algoritmo ===Esistono numerosi modelli matematici di algoritmo. In generale, un algoritmo riceve un insieme di valori (dati) in input e ne genera uno in output (chiamato soluzione). Dato dunque un algoritmo A si denota con fA la funzione che associa a ogni ingresso x di A la corrispondente uscita.

=== Studio della complessità computazionale di un algoritmo ===

Questa corrispondenza tra input e output non rappresenta il problema risolto dall'algoritmo. Formalmente, un problema è una funzione

�

(

�

�

)

→

�

�

f(D_{i})\to D_{s} definita su insieme Di di elementi che chiameremo restanze, a valori su un insieme Ds di risoluzioni.

Lo studio di un algoritmo viene suddiviso in due fasi:

sintesi (detta anche disegno o progetto): dato un problema A, costruire un algoritmo f per risolvere A, cioè tale che f=fa.

analisi: dato un algoritmo f e un problema A, dimostrare che f risolve A, cioè f=fa (correttezza) e valutare la quantità di risorse usate da f (complessità concreta).

{{vedi anche|Teoria della complessità computazionale}}