Tipologia delle elaborazioni e delle procedure
Da Wikipedia, l'enciclopedia libera.
In questo articolo sono prese in considerazione le nozioni generali di elaborazione e di procedura (informatica) al fine di indicare una loro classificazione. Si vogliono dare indicazioni sulle elaborazioni di informazioni (e a un livello di maggiore complessità le elaborazioni di conoscenze) quale che sia la natura, umana o artificiale, dell'operatore che le esegue. Le procedure che controllano la esecuzione delle elaborazioni vengono esaminate senza entrare nei dettagli della loro costituzione: una procedura potrebbe ridursi ad istruzioni rivolte ad operatori umani ed essere scritta in un linguaggio naturale con tutta la precisione atta a garantire che gli operatori non incontrino richieste ambigue; in alternativa una procedura potrebbe ricondursi alle possibili esecuzioni di una macchina formale particolare (ad es. una macchina di Turing, un sistema di Thue o un computer idealizzato); come terza alternativa una procedura potrebbe essere rappresentata da un programma scritto in un linguaggio di programmazione di ampia popolarità (come C, Java o PHP) e dotato di una implementazione solidamente collaudata.
- Questo articolo vuole contribuire ad una presentazione che possa essere rivolta a persone che considerano la matematica esclusivamente in quanto contribuisce alla impostazione di calcoli effettivamente eseguibili per obiettivi concreti (persone con interessi esclusivamente computazionali), oppure a persone che, sul piano della filosofia della matematica aderiscono ad una visione finitista e costruttivista di questa disciplina.
Indice |
[modifica] Genere della tipologia
L'attendibilità delle conclusioni che raggiungiamo viene ricondotta, a un livello di tendenza astratta, alla fiducia nella possibilità di precisare tutti i dettagli inespressi che possono essere richiesti per rendere completa e rigorosa l'esposizione; a un livello di maggiore concretezza viene invece ricondotta alla coerenza con altri articoli che entrano in maggiori dettagli (v. ...).
Per contenere i discorsi nel presente articolo ci avvaliamo della possibilità di ricondurre tutte le elaborazioni ad analisi, trasformazioni e composizioni di stringhe, ricordando che con stringhe si possono rappresentare tutte le entità matematiche e informative che si possono elaborare senza ambiguità (in senso relativo) e tutte le trasformazioni che possono agire sopra queste entità.
[modifica] Elaborazioni e procedure su insiemi espliciti
Una prima distinzione riguarda da una parte le procedure ad esecuzione unica, che non richiedono dati in ingresso, e dall'altra le procedure con dati in ingresso, ciascuna istanza dei quali comporta una esecuzione potenzialmente diversa.
Al di là di questa distinzione, le prime elaborazioni e procedure che vanno prese in considerazione sono quelle che operano nell'ambito di insiemi espliciti (e quindi entro insiemi finiti). Inizialmente consideriamo solo elaborazioni per le quali si possa assicurare che giungano a termine dopo un numero finito di passi. Per una tale procedura usiamo il termine procedura terminante o procedura ad arresto assicurato. (A queste procedure si collega la nozione di algoritmo in senso stretto.)(br>
- Più avanti incontreremo procedure la cui esecuzione procede illimitatamente ed altre ancor più problematiche.
[modifica] Tipi di finalità
Un altro elemento di distinzione è costituito dalla finalità delle procedure e delle elaborazioni.
[modifica] Procedura elencativa
Serve a costruire un elenco comprendente tutte le stringhe che presentano determinate caratteristiche. Esempi ben concreti sono: la procedura che individua tutti i divisori di un numero intero positivo dato; la procedura che costruisce tutte le stringhe su un certo alfabeto e di una data lunghezza che sono palindromi.
[modifica] Procedura decisionale
Prevede una stringa w di ingresso e la sottopone ad una analisi al fine di decidere se soddisfa o meno a a certi requisiti concludendo con la sua accettazione o con il suo rifiuto; le due conclusioni si concretano nell'emissione di una informazione binaria, un sì o un no, un vero o un falso, un ok o un err, un 1 o uno 0. Una procedura di questo tipo stabilisce se w appartiene o meno ad un certo insieme; essa può anche servire a definire un insieme, quello delle stringhe accettate. Queste procedure sono collegate alla nozione di automa accettatore.
Esempi: procedura che decide se un intero positivo è un numero primo o al contrario un numero composito (v. test di primalità); la procedura che decide se una espressione costituisce una formula ben formata o se presenta qualche errore sintattico; la procedura che stabilisce se un punto del piano o di uno spazio appartiene ad un luogo geometrico oppure se è un punto interno ad una certa figura geometrica; se una certa equazione quadratica esprime una conica di un certo tipo, ad es. una ellisse.
[modifica] Procedura selettiva
Scorre un elenco esprimente un insieme esplicito e seleziona le stringhe che identificano gli elementi con determinate caratteristiche registrando queste, cioè gli elementi con particolari proprietà, sopra un nastro di uscita. Sostanzialmente individua un sottoinsieme dell'insieme esplicito
Esempi: Procedura che scorre un elenco di nomi e seleziona quelli che iniziano con una vocale; procedura che scorre un erlenco anagrafico e seleziona i records con i nati a Genova prima del 1950.
[modifica] Procedura di ricerca
Scorre un elenco dato per cercarvi una stringa con date caratteristiche; una elaborazione si potrebbe concludere con una risposta positiva ed una stringa trovata, o al contrario con una risposta negativa; nel primo caso la stringa trovata potrebbe essere l'unica oppure la prima di un sottoelenco. Con le espressioni insiemistiche si può dire che, nell'ambito di un universo U, dati un S sottoinsieme di U e un requisito per elementi di U, si chiede di cercare se esiste o meno un elemento x di S che soddisfa R. Si parla anche di problema della vacuità del sottoinsieme di S che soddisfi R.
Esempi: ricerca di un numero primo in un dato insieme di numeri dati; ricerca di una stringa priva di quadrati in un elenco dato.
Si osserva che procedure selettive, procedure decisionali e procedure di ricerca possono essere collegate in modi piuttosto precisi. Conoscendo una procedura decisionale D, si può costruire una procedura selettiva che organizzi lo scorrimento di un insieme U e, richiamando la D, proceda alla selezione. Una procedura decisionale può essere richiamata utilmente anche in una procedura di ricerca.
[modifica] Procedura trasformatrice o procedura trasduttrice
Trasforma un dato di ingresso particolare in un suo associato mediante un determinato meccanismo. Questo genere di procedura mette in atto una trasformazione, ovvero una funzione che ha come dominio l'insieme dei possibili dati di ingresso. Esempi: calcolo del quadrato di un numero intero (o razionale); calcolo di una qualsiasi espressione riguardante un numero intero (o razionale); applicazione di una sostituzione ad una stringa w data (cancellazione da w delle occorrenze di alcuni caratteri, sostituzione di tali occorrenze con stringhe date, ...).
Di questo genere di procedura si possono considerare molteplici varianti. Date due stringhe ottenere una loro composizione: questo genere di procedura realizza le leggi di composizione interna ed esterna delle strutture algebriche, a cominciare dalle operazioni aritmetiche su numeri interi e razionali. Combinando una procedura di scorrimento con una procedura di trasformazione ed una di confronto si può realizzare una procedura di ottimizzazione (e in particolare una ricerca di massimo o di minimo).
