Riassunto esame Fondamenti di informatica, prof. Vittorini, libro consigliato Fondamenti di Informatica, Fadini Savy

Parte prima: Fondamenti teorici

Capitolo primo: I modelli fondamentali

1. Informatica: approcci teorico e tecnico

Si può dire che la base teorica dell'Informatica sia il concetto di Calcolo Automatico, per il quale occorrono:

• Dati Iniziali.
• Insieme di regole (Programma).
• Macchina che esegue il Programma producendo, attraverso Dati Intermedi, i Dati Finali richiesti.

Da un punto di vista Teorico, ci si interessa dei Modelli Matematici che, anche storicamente, hanno contribuito a chiarire l'entità dei vari problemi da risolvere formalizzandoli in maniera rigorosa; dal lato più pratico e Tecnico invece, è importante la comprensione dei meccanismi e dei componenti sui quali si basa l'Elaborazione Elettronica e lo Sviluppo del Software necessario.

Nell'Informatica è essenziale il ricorso a Modelli. Un Modello rappresenta un' Astrazione della Realtà, effettuata allo scopo di analizzarla e studiarla, che conserva di essa però solo i tratti essenziali, prescindendo da ogni singolo esemplare. I Modelli che ci interessano in Informatica sono fondamentalmente i Modelli Matematici o Modelli Formali, che riconducono una realtà a Formule, Equazioni e Procedimenti matematici.

2. Il concetto di elaborazione

Il concetto astratto di Elaborazione è quello di "Trasformazione di Dati", indicata dalla notazione Y=F(X), dove X è l'insieme dei Dati Iniziali in Ingresso, Y è l'insieme dei Dati Finali in Uscita, F è una Regola o Funzione (intesa nel senso più ampio possibile) che associa un Y ad ogni X.

Si noti comunque che solo in rari casi e per problemi molto semplici F consiste in una sola Operazione, e che invece, quasi sempre, essa si compone di più Operazioni in sequenza.

3. Il concetto di algoritmo

Altro concetto fondamentale dell'Informatica, anche se preesistente ad essa, è quello di Algoritmo: un Algoritmo è, matematicamente, un Procedimento Matematico per risolvere un problema. In realtà, più in generale, un Algoritmo non si applica solo a numeri, ma a qualsiasi forma di Dato (espresso da Simboli o Sequenze di simboli) e attraverso una serie di Azioni Elaborative (ciascuna di esse è una semplice Trasformazione dei Dati Iniziali in Dati Intermedi) produce la suddetta trasformazione da X a Y, dunque la risoluzione del problema proposto.

Possiamo quindi dire che:

• L'Algoritmo è una Sequenza di Azioni Elaborative (dove il concetto di Sequenza è fondamentale).
• L'Algoritmo è una Sequenza Finita.
• L'Algoritmo è Deterministico (e non soggetto a regole probabilistiche).
• L'Algoritmo risolve automaticamente un problema, sempre che:
• esso sia formalizzato (cioè si consideri l'insieme delle Azioni Elaborative Possibili).
• esista un Linguaggio in cui esprimerlo con rigore e senza ambiguità.
• esista una Macchina che, comprendendo il Linguaggio, esegua l'Algoritmo.

4. Il modello di automa

Un modello fondamentale dell'informatica è quello di "Automa a stati finiti", un modello matematico che fornisce una prima Astrazione della Macchina risolutrice di Algoritmi. Concetto importante è quello di "Stato" che suggerisce intuitivamente una certa "Condizione" di funzionamento della Macchina che reagisce ad un certo Ingresso con una ben precisa Uscita.

Il modello è così definito:

• Sia M l'automa.
• Sia Q l'insieme finito di Stati Interni q.
• Sia I l'insieme finito di Ingressi i.
• Sia U l'insieme finito di Uscite u.
• Sia "t" la Funzione di Transizione che trasforma un sottoinsieme di (Q x I) in Q.
• Sia "w" la Funzione di Uscita che trasforma un sottoinsieme di (Q x I) in U.

Allora M = (Q, I, U, t, w) è il nostro "Automa a Stati Finiti" o "Macchina Sequenziale" e si dice "Completo" se i suddetti sottoinsiemi coincidono con (Q x I).

Due sono i modelli fondamentali:

• Modello di Mealy, che concettualmente consta di una parte che Calcola le funzioni "t" e "w" ed un'altra che, come elemento di Ritardo, ripropone lo stato seguente q' in entrata: questo è importante perché l'Uscita sarà funzione sia dell'Ingresso che dello Stato.
• Modello di Moore, che si distingue dal precedente essenzialmente per il fatto che la funzione "w" ha come dominio solo Q, e quindi le Uscite sono funzioni solo dello Stato e non dell'Ingresso.

In ogni caso, sebbene diversi, è stata dimostrata l'equivalenza tra i due modelli, per cui è sempre possibile convertire una Macchina di un tipo nell'altro tipo.

Per spiegare meglio i due modelli, si possono utilizzare:

• Diagrammi degli Stati, in cui ogni Stato è indicato da un Cerchio, i Segmenti Orientati che collegano i Cerchi sono determinati dalla funzione "t", l'Ingresso è indicata sul segmento orientato che essa stessa determina, l'Uscita è indicata nel Cerchio separata dal nome dello stato da uno slash (in Moore), sul segmento orientato che la determina separata dall'Ingresso da uno slash (in Mealy).
• Tabelle, in cui sulle colonne ci sono gli Ingressi, sulle righe ci sono gli Stati (e le Uscite per Moore), mentre nelle caselle corrispondenti ci sono gli Stati Successivi (e le Uscite per Mealy).

6. Le macchine di Turing

Se il modello di automa fornisce il concetto di "Sequenza di Azioni" e "Stato", esso è troppo generico, non precisando la natura degli Ingressi o delle Uscite, e quindi quali siano le "Possibili Azioni Elaborative": dunque non aiuta a chiarire il concetto di Algoritmo.

Il modello della "Macchina di Turing" viceversa è stata intesa come modello ideale di Macchina in grado di risolvere Algoritmi, e quindi ha permesso di raggiungere importanti risultati teorici sulla Calcolabilità (cosa una macchina automatica può fare o meno) sulla Complessità (cosa si deve intendere per algoritmo più o meno complesso), sull'Equivalenza tra algoritmi, e così via.

**La Macchina di Turing è un particolare automa, per il quale sono definiti:

• L'insieme degli Ingressi e delle Uscite come insiemi di Simboli noti (in generale 0,1).
• Un meccanismo ideale di Scrittura e Lettura.
• Uno speciale Nastro continuo su cui la testina opera.

**La Macchina di Turing è composta:

• Una Memoria, costituita dal Nastro.
• Una Testina, posizionata in ogni istante su una casella del Nastro, capace di spostarsi a Destra, Sinistra o stare ferma, leggere il contenuto della casella, scrivere in essa uno dei Simboli noti sostituendo la precedente scrittura.
• Un Dispositivo di Controllo che ad ogni coppia (Stato, Simbolo letto) associa la coppia di azioni (Cambia Stato, esegui una delle Azioni Elaborative).

**L'elaborazione della Macchina di Turing:

• Avviene su un qualunque Tipo di Dato opportunamente codificato con un numero qualsiasi di Simboli scelti.
• Si compone di attività elementari (leggi, scrivi, sposta) che però in sequenza producono un'operazione complessa.
• Si rifà ad un Input, un Output e una Memoria (coincidono nel Nastro).

**Una Macchina di Turing è totalmente identificata da:

• Il Contenuto "t" del suo Nastro.
• La Posizione iniziale della testina.
• Lo Stato iniziale della macchina.
• La Tabella delle transizioni.

Se quindi si pone "t" il contenuto del Nastro, e "d( T )" la descrizione della Macchina di Turing, possiamo affermare che "d ( T )", composta magari di una serie di quintuple del tipo "(Stato attuale, Simbolo letto, Stato seguente, Movimento testina, Simbolo scritto)" è quella funzione che associa a "t" un Nastro opportunamente modificato " t' ", e può essere essa stessa, opportunamente tradotta in sequenza di "1" e "0", oggetto dell'elaborazione di un'altra Macchina di Turing: questo è fondamentale, perché da qui discende la possibilità di scrivere un Programma e di poterlo tradurre in un altro Linguaggio.

7. Calcolabilità e tesi di Church

Partendo dall'affermazione che una Macchina di Turing che non si arresta mai, non realizza un Algoritmo, diciamo che:

<< Non esiste un formalismo né una macchina concreta che possa calcolare una funzione non calcolabile secondo Turing >> (tesi di Church o di Turing).

Essa discende da considerazioni intuitive sugli Algoritmi e non è stata mai dimostrata, tuttavia il fatto non essere mai stata smentita dal momento della sua formulazione (1936) finora le ha conferito grande importanza.

Da essa si può affermare che: << un Algoritmo è ciò che può essere realizzato con una macchina di Turing >>.

9. Modelli avanzati di automi e macchine di Turing

Oltre ai modelli fondamentali di automa trattati finora, ve ne sono degli altri, tra i quali i più importanti sono gli "Automi a pila" e gli "Automi non deterministici".

L'Automa a pila possiede un Nastro di Ingresso, un Dispositivo di Lettura che avanza solo da sinistra a destra e una Memoria denominata "a pila" o "stack": esso adotta una speciale strategia di accesso ai dati, simulando il deposito e il prelievo di elementi da una pila, la cosiddetta LIFO (Last In, First Out).

Le Operazioni possibili per questo Automa agiscono tutte sulla "testa" della pila (l'elemento in cima) e sono:

• Push = un elemento viene scritto in memoria.
• Top = la testa della pila viene letta.
• Pop = la testa della pila è eliminata.

Le Macchine di Turing "Non Deterministiche" agiscono diversamente da quelle comunemente dette deterministiche, giacché la funzione di transizione "t" può associare ad ogni coppia, una o più azioni diverse in alternativa: essa preleva Dati da più Nastri di Ingresso e Uscita e dà luogo a computazioni che possono diramarsi ad albero seguendo modalità esplorative e non prefissate. Esse forniscono modelli astratti di alcuni algoritmi legati alla Teoria della Complessità.

10. Algoritmi, linguaggi e programmi

Abbiamo visto finora i concetti di Algoritmo, di Modello di Automa a Stati finiti, di Modello di Turing e il suo legame con quello di Algoritmo. Questo spiana la strada alla definizione di Calcolatore, una speciale Macchina con un Programma registrato in Memoria (cioè un Algoritmo formalizzato in un certo Linguaggio), tale da determinare, al suo variare, il variare delle Azioni Elaborative della Macchina.

11. Modello "penna e carta"

In realtà l'esempio che viene più spesso fatto per spiegare il concetto di Algoritmo è il cosiddetto "Modello penna e carta", così riassumibile: sia un operatore (anche umano) dalle limitate capacità elaborative, capace di poche e semplicissime azioni elementari; sia altresì un documento che descrive una sequenza di queste semplici azioni allo scopo di risolvere un problema anche di una certa complessità; sia inoltre un tabulato, dal quale è possibile estrarre Dati Iniziali, sul quale è possibile memorizzare Dati Intermedi, e in funzione del quale è possibile ricavare i Dati Finali. Si avrà dunque che, con semplici operazioni di Ingresso Dati, Trasferimento dei Dati ai Registri di una macchina calcolatrice, Assegnazione dei Dati a Variabili del Tabulato, ... l'operatore arriverà, seguendo scrupolosamente il Documento descrittivo, risolverà il problema in maniera "automatica".

12. Modello di Von Neumann

Il Modello di Von Neumann è il più vicino alla struttura dei moderni elaboratori, ed in realtà è stato usato come modello costruttivo dei primi calcolatori ed è interessante notare che esso semplicemente traspone in termini di componenti elettronici ed elettro-meccanici il Modello "penna e carta" esposto precedentemente.

Esso si compone delle seguenti Unità:

• Unità di Ingresso, tramite cui viene Caricato il Programma ed Inseriti i Dati Iniziali.
• Unità di Memoria, nella quale vanno memorizzati il Programma, Dati Iniziali, Intermedi e Finali (il Tabulato).
• Unità di Controllo (CU) o Processore, che interpreta le singole istruzioni del programma e aziona le varie Unità.
• Unità Logico-Aritmetica (ALU), in grado di eseguire a richiesta le operazioni aritmetiche e logiche.
• Unità di Uscita, tramite cui i Dati vengono Salvati o messi in Chiaro per l'utente.

Tale Macchina, dopo aver Caricato il Programma (Load-Time), lo Esegue (Run-Time) alternando all'Accesso alla prossima Istruzione (Fetch) l'esecuzione della stessa (Execute), e scambiando con la Memoria i Dati aziona di volta in volta le Unità Periferiche.

Capitolo secondo: La macchina astratta generalizzata

1. Valore, tipo e attributo di un'informazione

Il concetto di Informazione è legato al concetto di Scelta, poiché un Informazione tende ad eliminare l'incertezza scegliendo uno tra i Valori possibili di un insieme. In Informatica l'Informazione è studiata in funzione della sua elaborazione e risulta composta di un Valore, un Tipo e di un Attributo. [vedere Parte II, Capitolo II, Paragrafo 1]

2. Informazione e dati. Il bit

Possiamo dare 3 definizioni distinte di "bit":

1. "Dicesi bit un tipo di dato di cardinalità 2" = infatti la minima Scelta che si può fare, quindi il presupposto minimale per l'esistenza di una Informazione è un insieme di Cardinalità 2; comunque, il bit può essere usato per rappresentare insiemi di Cardinalità > 2, tramite una apposita rappresentazione convenzionale (tramite sequenza o stringa di bit) che associa ad ogni elemento dell'insieme una delle N=2^k disposizioni con ripetizione dei simboli "1" e "0".
2. "Dicesi bit l'unità di misura dell'informazione" = infatti, volendo assegnare un Peso all'informazione (questo è intuitivamente importante se si pensa che al crescere dei valori su cui si può effettuare la scelta, aumenta anche la dimensione dello "spazio fisico" su cui tale Dato potrà essere memorizzato) si associa l'Unità di Misura alla scelta tra 2 soli elementi.
3. "Dicesi bit la cifra dell'aritmetica binaria" = infatti, come il nome stesso suggerisce (Bit = BInary digiT = cifra binaria), "1" e "0" sono i simboli dell'aritmetica binaria, ed ogni valore in "base decimale" può essere convertito proprio tramite una stringa di bit in un valore in "base binaria".

3. Tipi semplici e strutturati

Un Tipo si dice Semplice se non è suddivisibile in Tipi più elementari (es.: il numero Intero), Strutturato se invece è composto da altri Tipi (semplici o strutturati). È evidente comunque che se un Tipo è strutturato, lo è anche il Valore in esso memorizzato, e così l'Attributo assegnato (es.: il tipo Complesso). [vedere Parte II, Capitolo III, Paragrafo 1]

4. Le azioni elaborative nella macchina di Von Neumann

Un Dato può essere agevolmente rappresentato nella forma (A,V) cioè (Attributo, Valore) dove A={a1, a2, ... aN} e V={v1, v2 ... vN}. L'Azione Elaborativa considerata nel modello di Von Neumann ha l'effetto di alterare lo stato dei Dati, e, in generale, ciò accade tramite il meccanismo dell'Assegnazione (che avviene in un tempo Finito, in base alla Velocità della Macchina) che ha come Oggetto una Variabile (dunque il Valore di un Attributo) e può avere come "Soggetto":

• Valore derivante da Operazioni su valori Disponibili (assegnati ad Attributi) e/o Noti (Costanti).
• Valore già assegnato ad altri Attributi.
• Valore Noto.
• Valore derivato da Ingresso Dati.

Una Elaborazione Y=F(X) ha l'effetto di assegnare a ciascun attributo "Ay" i valori degli attributi "Ax" passati per la regola "F": l'elaborazione si decompone in azioni elementari che costituiscono l'Algoritmo di Calcolo o Processo di Elaborazione. Tale elaborazione viene eseguita dal Processore sulla base di un Algoritmo scritto sotto forma di Programma in un Linguaggio di Programmazione sintetico, comprensibile, formale, non ambiguo e non ridondante.

6. La macchina astratta generalizzata

Ciascun tipo di Linguaggio di Programmazione, sulla base anche delle potenzialità del Processore della Macchina in uso, definisce Tipi e Operazioni su di essi propri: ciascuno di essi opera su una diversa Macchina Astratta o Virtuale che è una Macchina di Von Neumann (Macchina-COBOL, Macchina-Pascal, Macchina-C++, e così via.). Definiremo Macchina Astratta Generalizzata o MAG come modello del quale le Macchine Virtuali suddette possono ritenersi casi particolari.

**La MAG è costituita da:

• Un insieme di Registri di Memoria.
• Un Registro speciale detto PI, prossima istruzione, che contiene una informazione del tipo "puntatore ad un'istruzione".
• Un Processore.

**Nella MAG è definita una famiglia T di Tipi (Atomici e Strutturati) così articolata:

• Dati.
• Istruzioni.
• Puntatori a Dati (assumono come valore l'Attributo del Dato).
• Puntatori ad Istruzioni (assumono come valore il nome di un'istruzione, l'Etichetta o Label).

**Ogni Azione Elaborativa della MAG può essere schematizzata come "i = (f, P1, P2)", dove:

• "i" è l'Istruzione da compiere.
• "f" è la Funzione (un Operatore o una Combinazione di operatori) da applicare a P1.
• "P1" è un insieme di Puntatori a Dati e/o Istruzioni.
• "P2" è un insieme di Puntatori a Dati (modificati da "f") più il registro PI (che rimanderà alla prossima istruzione).

**Il Processore della MAG agisce secondo i seguenti passi:

• Prelievo dalla Memoria dell'Istruzione puntata dal PI e spostamento nel Processore.
• Prelievo diretto e/o indiretto dei Dati presenti in P1.
• Calcolo della "f".
• Memorizzazione dei dati elaborati.