Nozioni fondamentali programmazione C

Teoria dei linguaggi formali

Significato o semantica di un programma

«C'è modifica approfitto l'esecuzione del programma nel calcolatore???»

Secondo la teoria della calcolabilità non tutti i problemi si possono risolvere con l'informatica. Es: Non esiste un programma che, dato in input un codice e relativi dati, mi restituisca se il codice termina l'esecuzione o meno. Problema non calcolabile.

Paradigmi di programmazione

Modi diversi per risolvere lo stesso problema. I modi hanno la stessa potenza formale e possono risolvere le stesse classi di problemi.

Paradigma ricorsivo

I problemi vengono risolti attraverso la definizione e calcolo di funzioni ricorsive, ovvero definite in termini di se stesse. Es: funzione fattoriale ! : N -> N, n = n · (n - 1) · ... · 2, n ∈ N ovvero N - {0}.

Paradigma iterativo

I programmi vengono risolti attraverso trasformazione di stato. Stato iniziale → programma → Stato finale. Il programma prende lo Stato iniziale, opera su un insieme di problemi e produce lo Stato finale.

Teoria dei linguaggi formali

Significato o semantica di un programma

Che modifica apporta l'esecuzione del programma nel calcolatore?

Secondo la teoria della calcolabilità, non tutti i problemi si possono risolvere con l'informatica. Es: Non esiste un programma che, dato in input un codice, mi restituisca output, indicandomi se il codice termina l'esecuzione o meno. Problema non calcolabile.

Paradigmi di programmazione

Modi diversi per risolvere lo stesso problema. Due modi molto spesso per uno stesso problema possono risolverlo.

Paradigma ricorsivo

I problemi vengono risolti attraverso la definizione e calcolo con funzioni ricorsive, ovvero definite in termini di se stesse. Es: funzione fattoriale : -> Es: () = 2 + (). Definizione (come si comporta) 0! = 1, n! = n·(n-1)! ∈ N ovvero N - {0}. Nella definizione della funzione uso la definizione stessa. Uso (calcolo il valore) di 5!: 0! = 1, 1! = 1, 3! = 3·2·1 = 6, 4! = 4·3·2·1 = 24, 5! = 5·4! per n ∈ N⁺, 4·(3!) = 4·3·2·1 = 24.

Paradigma iterativo

I programmi vengono risolti attraverso trasformazione di stato. Stato iniziale ➔ Programma ➔ Stato finale. Il programma prende lo stato iniziale, opera su cui svolgere il problema il procedimento stato finale.

Il linguaggio C

Il linguaggio C è un linguaggio ad alto livello, cioè i costrutti del linguaggio sono comprensibili per il programmatore. Il calcolatore non esegue direttamente i programmi che noi scriviamo in linguaggio macchina. Tra il linguaggio e il calcolatore, c'è un programma particolare che traduce le istruzioni in linguaggio macchina.

Concetto di stato

Per spiegare il significato dei programmi, è necessario astrarre dal loro effetto sulla loro esecuzione a quel livello di astrazione. L'esecuzione consiste su una memoria astratta che si può definire mediante un multimi. di valori binari in notazione decimale.

Memoria fisica 1000... Sequenza di parole di memoria (celle) che vengono indirizzate 1000...0000. Tradurre le parole compreso anche basso lunghezza cost.

Stato composto da associazioni nome-valore: y 30, x 20, z 15. Con questo tipo di stato è veloce la rivalutazione del programma. Quindi, si necessita di uno stato composto da ambiente e memoria. Il valore della variabile al valore x lo trovi in memoria sull'indirizzo associato solo x nell'ambiente.

Ambiente

Associazione, nome-locazione

Memoria

Associazione, locazione-valore

Come si crea lo stato?

Nei linguaggi di programmazione esistono dei costrutti (strutture) delle dichiarazioni che hanno la funzione di creare lo stato. Effetto: Crea una nuova associazione sull'ambiente e sulla memoria. Esempio: int x = 12;

Come si modifica lo stato?

Attraverso costrutto del comando assegnamento. Nome ← espressione. Esempio: x ← 10+5. L'espressione ed il valore risultante vengono assegnati in memoria alla variabile.

Esempi: int x = 10, y ← 5, x = 3, i = 0, j=0, ← y+lex = x+y.

Comando condizionale

If (condizione) comando1; else comando2;

• Vero → Comando1
• Falso → Comando2

If annidato (NB: parentesi graffe!):

if (x > 0) {
    if (y > 0)
        x = x - 1;
    else
        y = y - 1;
} else {
    x = x + 2;
}

if (x > 0) {
    x = x + 1;
    y = y + 1;
}

Uguaglianza: ==

Assegnamento: =

Comando iterativo (iterazione indeterminata)

While (condizione) comando;

int x = 3;
int y = 0;
while (x > 0) {
    x = x - 1;
    y = y + 2;
}

Finché la condizione è vera, si esegue il comando; si rivaluta la condizione ad ogni "giro" di loop. Il comando permette di avere computazioni a infinito.

Comando iterativo (iterazione determinata)

For (int i = 0; i < N; i++) {...}

NB: la dichiarazione va deve avvenire fuori dal for e dentro al ciclo i non deve essere modificata.

Perché non definire un linguaggio con solamente iterazione determinata? Perché altrimenti si volerebbe la potenza di calcolo del linguaggio, quindi la possibilità di risolvere problemi.

int x = 24;
int y = 9;
while (x > y) {
    if (x > y)
        x = x - y;
    else
        y = y - x;
}

Es: - MCD (m, n) nel ciclo while; es: - MCD (n - m, m) nel ciclo for;

int x = 6;
int fact = 1;
for (int i = 1; i <= x; i++) {
    fact = fact * i;
}