Appunti di Programmazione

APPUNTI DI PROGRAMMAZIONE A

INFORMATICA = informazione automatica, elaborazione automatica

dell’informazione.

L’ informatica si occupa di una disciplina chiamata linguistica computazionale.

Claude Shannon ha descritto la teoria dell’informazione che sta alla base della

trasmissione dell’informazione, delle telecomunicazioni.

DEFINIZIONI DI BASE

Sia un alfabeto di simboli:

A ≠∅ , finito

{ }

0 ℇ ℇ∉

=

A , A

1 =

A A ;

k ( )

=

A A × A ×… × A k volte con k ≥ 2

Definiamo chiusura di Kleene l’insieme (infinito contabile) i cui

¿ k

∈

=¿

A k N A

elementi sono detti stringhe ed prende il nome di stringa vuota.

ℇ

Sulle stringhe è possibile definire un’operazione chiamata concatenazione:

¿ ¿

Sia allora ∈più

u=s∗t → posso spezzare stringa parti

∈ ∈

s A , t A

PROPRIETÁ DELLA CONCATENAZIONE:

 Associatività: ( )∗u=s∗( )=s∗t∗u

s∗t t∗u

 Non commutatività: s∗t ≠t∗s

 Identità: s∗ℇ=ℇ∗s=s

 ¿ k

∀ ∈ ∃! ∈

s A k : s A | |

posso definire lunghezza della stringa

⟹ =k

s

 ¿ ¿

| | | | | |

∀ ∈ ∈ = +

s A , t A s∗t s t

Altre definizioni:

Sia diciamo che t è una sottostringa di s (fattore) se

¿

o ∈

s ,t A

¿

∃u ∈

, v A : s=u∗t∗v

Se u, v esistono, cioè sono allora s viene detta sottostringa propria.

≠ℇ

viene dette prefisso di s, se

¿ ¿

o ∈ ∃ ∈

t A s A : s=t∗v

viene dette suffisso di s, se

¿ ¿

o ∈ ∃ ∈

t A s A : s=v∗t

IL LINGUAGGIO ¿

Dato un alfabeto di simboli chiamiamo linguaggio il sottoinsieme

L⊆ A

dell’insieme di tutte le possibili stringhe.

Possiamo definire un linguaggio o più in generale un qualunque insieme

solitamente in due modi:

 Caso estensionale: enumerazione di tutti gli elementi di un insieme (perfetto

nel caso di insieme finiti);

 Caso intensionale: definisco gli insiemi per proprietà (perfetto nel caso di

linguaggi).

{ }

¿

Es. ∈ (s )

L= s A : p 1 2

NB: p(s) viene definita tramite la morfologia e la grammatica della lingua.

C’è un terzo modo per esprimere la struttura dei linguaggi nel caso dei

linguaggi di espressioni caratterizzati da:

 3

Insieme finito K di costanti zeroari (arità 0);

 Insieme finito L di operatori unari postfissi (es. 0!);

 Insieme finito R di operatori unari prefissi (es. -0);

 Insieme finito B di operatori binari (es. 0+0);

 Insieme di simboli (es. parentesi tonde).

L’unione di questi insiemi e simboli forma l’ALFABETO.

NB: le parentesi devono essere bilanciate, cioè ad ogni parentesi aperta deve

corrispondere una parentesi chiusa. Inoltre, devono avere al loro interno una

stringa non vuota, così come a sinistra (risp. destra) di un operatore postfisso

(risp. prefisso) non ci può essere una stringa vuota.

SEMANTICA DEL LINGUAGGIO

DEF

Dato un linguaggio L chiamiamo formula ben formata una qualsiasi stringa di

L: ∈

WFF di L⟶ s L 4

Noi, finora, abbiamo costruito la sintassi sulla base della morfologia e della

grammatica; ora, dobbiamo definire la semantica del linguaggio.

La semantica si basa sul dominio di interpretazione sul quale trasferisco le

π

WFF:

Sia chiamiamo funzione di interpretazione :

π ≠ 0, σ

¿ ⟶

σ : L⊆ A π

1 Parte della linguistica che studia come le parole si possono modificare e come da una parola se ne ottiene un’altra.

2 Complesso di regole di una lingua.

3 N° di argomenti del singolo operatore.

4 Lo studio delle funzioni proprie della struttura della frase.

Questa funzione mi permette di dare una semantica al mio linguaggio.

Esempio:

( )

3 8

5 ,

=

I =Z

π

↓ ↓

+ ↓

A Z

A

Trasformiamo la stringa in qualcos’altro, che non appartiene all’insieme di

partenza

Per ogni operatore dobbiamo specificare precedenza e associatività (non è parte

della grammatica ma della semantica) per dare un ordine e definire in modo

univoco l’interpretazione del linguaggio:

 Precedenza più basso è l’indice di precedenza e prima deve

p∈ N , p ≥ 0 :

essere svolto. Le costanti e le parentesi hanno precedenza 0.

xf , yf → L

 Associatività di operatori: fx , fy → R

xfx , xfy , yfy , yfx → B

x, y sono gli argomenti che hanno rispettivamente precedenza e .

≤

¿

Esempio:

{ }

K= 0,1, … , 1000

¿

p : 4

+¿ , p :3

yfx yfx

¿

¿

B=¿

Es.

1) 3+2+5

2) 3+2*5

ESPANSIONE DEL LINGUAGGIO C

Chiamiamo espansione del linguaggio C, , la struttura così definita:

E C

{ A ≠∅ , finito

¿

A

=

E ¿

C ⊆

L A

σ : L → π , funzione diinterpretazione astratta

Sia l’insieme degli interi macchina il quale dipende appunto dalla

⊆

I Z

macchina, in quanto il computer è un oggetto finito che non può manipolare

tutti i numeri.

{ }

=

E sia un insieme finito in cui è il valore

k

K k ,… ,−2 ,−1, 0,1, 2 , … , k i

i i i

minimo e il valore massimo.

k i −1

Possiamo definire una relazione biunivoca tra questi due

ρ : I → K , p : K → I

i i

insiemi tale che:

−1

( ) ( )

=ρ

σ k k se k è un elemento di K i

OPERATORI

 Prefissi: + - fy 2

 Binari: + - yfx 4

* / % yfx 3

Esempio:

3+5*2

Applico formula delle parentesi complete ovvero ogni costante, letterale ha

attorno due parentesi e ogni operazione ha due operandi racchiusi tra le

parentesi.

(3)+(5)*(2)

((3)+((5)*(2)))

0 4 0 perché tra parentesi

→

PROPRIETÁ DI σ

è una funzione ricorsiva perché il valore della funzione dipende dalle sue

σ

sottoparti; trasforma la nostra stringa in qualcosa di più semplice,

σ

l’accorcia.

( )

1) ( ) ( )

=σ

σ E E

2) −1

( )= (K )

σ K ρ

3) ( )=σ ( )

+E

σ E

4) (−E )=−σ ( )

σ E

5) ( ) ( ) ( )

=σ

σ A ± B A ± σ B

6) ( )=σ ( ) ( )

σ A∗B A ∙ σ B

( )

A ( ) ( )

7) =σ ÷σ

σ A B

B

Dove è la divisione intera tra interi tale che:

2

¿ :Z → Z

{ a

⌊ ⌋ seab>0

b

a

a÷b= ⌈ ⌉ seab<0

b

0 se b ≠ 0, a=0

IMP. se b=0

8) ( ) ( )

=σ (

σ A %B A mod σ B)

Dove è il resto della divisione intera.

%

Questa operazione assume un senso preciso solo se ; se

( ) >0 (

σ B σ B)<0

dipende, perché non è standardizzato in C.

( )

σ B

Esempio: [ ]

( )

( )

( ) ( )∗( )

⟹ +

3+2∗5 σ 3 2 5

¿ ¿¿

σ

¿ ¿¿

σ [ ] ( )∗( )

¿ + [( )]

σ 3 σ 2 5

[ ]

( )∗( )

¿ 3+σ 2 5

(2)

¿

( )

5

¿ ¿

3+σ [ ]

[ ] ( )

¿ 3+σ 2 ∙ σ 5

[ ]

( )

¿ 3+2 ∙σ 5

[ ]

¿ 3+2 ∙σ 5

¿ 3+2 ∙5=13

Analogamente, possiamo estendere queste funzioni a un sottoinsieme di numeri

razionali. =∅

Sia e consideriamo l’insieme tale che .

K K K

D⊆Q D D i

Possiamo definire una relazione biunivoca tra questi due insiemi tale

−1

ρ ↓, p ↑

che: −1

( ) ( )

=ρ

σ k k