Programmazione I - Appunti

PROGRAMMAZIONE I & LABORATORIO

• Indice
1. Sintassi ................................................. pag. 1
2. Ricorsione .......................................... pag. 5
3. Programmazione Funzionale .................. pag. 10
4. Tipi Elementari ................................... pag. 13
5. Liste ..................................................... pag. 15
6. Tipi Derivati .......................................... pag. 19
7. Linguaggio C: Semantica ........................ pag. 20
8. Procedure ............................................ pag. 34

1. Sintassi

La sintassi di un linguaggio di programmazione si occupa della sua struttura, una volta che se ne è specificato il lessico, tracciate due linee:

• costruzione di stringhe (simboli - stati finiti)
• costruzione di stringhe grammaticali (struttura di frasi)

N.B. Concetti base della sintassi:

• alfabeto (A): insieme di simboli appartenenti al linguaggio
• stringhe (S): successione di simboli dello stesso alfabeto
• stringa vuota (ε): stringa che non contiene simboli
• insiemi (insiemi di stringhe)
• linguaggio (L): combinazione di possibilità di simboli di A
• teorici degli insiemistici

Due stringhe possono essere concatenate, cioè i simboli della prima stringa possono essere succeduti dai simboli di una seconda stringa, formando una stringa unica.

1.1 Automi a stati finiti (ASF)

Gli automi a stati finiti (ASF) sono un metodo di definizione dei linguaggi basato sul riconoscimento delle stringhe. Esso lavora su sequenze con una macchina a stati, con elementi comprovati con la quintuplice:

< A, Σ, S, F, δ >

in cui:

• A = alfabeto
• Σ = insieme degli stati
• S = stato iniziale (S ∈ Σ)
• F = insieme degli stati finali, o di accettazione (F ⊆ Σ)
• δ = relazione di transizione da uno stato all'altro, regola rappresentante casi:

< s_i, a_i, s_j > dove s_i e s_j sono stati, e a_i è un simbolo del carattere che percorrela la transizione.

1.1.1 Automi Deterministica (ASF)

Gli ASF si definiscono deterministici quando, per ogni simbolo di A, esiste solo un'esatta transazione possibile da ogni stato attuale a quello successivo. Si può usare domniae sgre ouvertes e perfetto quando si usano i sistemi studiati in precedenza.

1.1.2 Automi Non Deterministica (ASFN)

Gli ASF si definiscono non deterministici quando ci sono alcune elementi che si possono eseguire con più possibilità di transcompletezza degli stati.

N.B. Gli ASF si possono rappresentare con queste ASF.

2. Ricorsione

Si dice ricorsiva una funzione che all'interno della propria definizione, contiene una formulazione di se stessa.

dove

cioè

X è una funzione dei sistemi di insiemi

2.1 Punti Fissi

Una funzione ricorsiva è utile stabilire un insieme che sia invariante rispetto alla trasformazione, detto un punto fisso.

Se il punto fisso è presente, questa definizione che comparirà sempre, diventa utile nella formulazione.

Visto perché deve sempre esistere, esso sarà un insieme finito.

È il minimo punto fisso di una funzione e lo si indica punto fisso.

2.2 Monotonia

Una trasformazione si dice monotona se due insiemi X e Y e le loro trasformazioni sono corretti, cioè essi sono relazioni di inclusione:

X ⊆ Y ⟹ T(X) ⊆ T(Y)

2.3 Continuità

Una trasformazione si dice continua se una sequenza di insiemi X_i, X_i sono accrescate allo stesso modo:

X_i ⊆ X_i₊₁

oppure cioè

T(⋃ X_i) = ⋃ T(X_i)

2.4 Teorema 1

Se una funzione è continua, allora è anche crescente.

Dimostrazione:

T(X) ⋃ T(X_i)

= ⋃ T(X_i)

= continuità

= ⋃¹⁺∞ T(X_i)

T(X)

(N.B. Una funzione composta da due funzioni continue è essa stessa continua.)

3. PROGRAMMAZIONE FUNZIONALE

La programmazione funzionale si basa appunto sull'utilizzo di funzioni per il calcolo di valori. Lo scopo della programmazione è quello di definire funzioni che saranno eseguite per ottenere risultati.

NB: Si parla di forma canonica poiché, sebbene il valore della funzione sia lo stesso, le rappresentazioni possibili sono molteplici. Più variabili "Libere" e il linguaggio non può essere essere rappresentate in una situazione generica.

3.1 NOZIONI BASE SUL LINGUAGGIO CAML

Il linguaggio Caml è un linguaggio funzionale che utilizziamo per lo studio dei linguaggi.

Rispondere a domande che possono essere espresse evidenzia come le espressioni possono contenere ulteriori espressioni minantellini che siano valori al tipo che in generale possono contenere valore (es: _1/10)

3.2 ESPRESSIONI E VALORI

I valori possono essere i numeri, valori booleani, caratteri o semplici funzioni e più spesso cedere ai valors necessari a pratica di questi.

Le espressioni (hanno come significato un valore e possono dipendere dai suoi) significatoi valori adissesi le espressioni possono contenere singoli simboli; le strutture dati degli espressioni sono succiutevoli che genero dividere in base ai sistemi di calcolo in cui sono abluiti o servono tipo (INTEGRITÀ REFERENZIALE).

3.3 TIPI

I tipi sono collezioni di valori con diverse caratteristiche.

Ci sono due categorie di tipi:

• tipi primitivi
  • int
  • bool
• tipi derivati (cioè costruiti sulla base dei primitivi)
  • enumtype (es: int+int)
  • prodottto (es: int*bool)
  • pesata (es: char+float)

Il tipo di un'espressione dipende esclusivamente dai tipi delle sottoespressioni (DICHIARAZIONE FORTE, e STRONG TYPING).

Per esempio, dubto come un operatore sui valori reali, interamenti un sicuro in tipo.

5. Liste

Le liste sono collezioni ordinate di valori dello stesso tipo.

5.1 Operazioni su Liste

Le liste possono essere soggette a diverse interazioni con operatori.

5.1.1 Cons

Il cons (simbolo "::") aggiunge un elemento in cima alla lista:

• 1::[2,3];
• - : int list = [1;2;3]

5.1.2 Concatenazione

La concatenazione unisce in sequenza due liste fornendo una sola. L'operatore è "@":

• [1,2,3]@[4,5,6];
• - : int list = [1;2;3;4;5;6]

N.B.: In alcun casi l'operatore "::" e l'operatore "@" sono interscambiabili:

• [1;2;3] = [1]@[2;3]

5.1.2 Head e Tail

Le funzioni head e tail restituiscono, rispettivamente, il primo elemento di una lista e la lista senza il primo elemento.

Sono definite come segue:

N.B.: Si usi due (hd l); (tl l) = l.

5.1.3 Lunghezza di una Lista

La lunghezza conta il numero di elementi di una lista:

La lunghezza di due liste concatenate è data dalla somma delle due lunghezze:

Nell'immagine vediamo un esempio di albero binario che può produrre due ordini di una stessa lista. Seguendo due ordini diversi ma con lo stesso percorso: se l'elemento numero due è maggiore di quelli a sinistra e più piccoli di quelli a destra.

1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 11

Le tipi degli alberi binari le casi definiti:

# type la liste = Empty Node dei alberi

Le cifrature negli alberi possono essere effettuate tramite il parche mainstream.

# Let rec search x lot = match lot with Empty -> false Node(lg, lbt, rbt) -> if x = lg then true else (Search x lbt) or (Search x rbt)