Fondamenti di informatica

PROGRAMMA

Dato un algoritmo, una "la sua descrizione linguistica" in un particolare linguaggio di programmazione.

LINGUAGGIO DI PROGRAMMAZIONE

È una notazione formale che può essere usata per descrivere algoritmi. Ha due aspetti:

• SINTASSI
• SEMANTICA

La sintassi è una nozione di linguaggio più precisa, un sistema logico-formale. Il linguaggio deve rispondere a domande come:

• Quali sono le frasi lecite?
• Si può stabilire se una frase appartiene al linguaggio?
• Come si stabilisce il significato di una frase?
• Quali elementi linguistici sono primitivi?

La sintassi è l'insieme di regole formali (grammatica) per la scrittura di programmi in un linguaggio, che dettano le modalità per costruire frasi corrette nel linguaggio stesso.

La semantica è l'insieme dei significati da attribuire alle frasi (sintatticamente corrette) costruite nel linguaggio.

NB: una...

frase può essere sintatticamente corretta e tuttavia non avere significato! (vedi Umberto Eco)

Le regole sintattiche sono espresse attraverso notazioni formali:

• BNF (Backus-Naur Form)
• EBNF (Extended BNF)
• diagrammi sintattici

linguaggi di programmazione ad alto livello:

Si basano su una macchina virtuale che segue dei "passi" (o "mosse") che non sono quelle della macchina hardware (il calcolatore). "barriera" di astrazione

I linguaggi di programmazione permettono la creazione di una sintesi tra la "logica" del calcolatore e i domini dei problemi (classi di problemi) che possono essere trattati computazionalmente.

linguaggi di programmazione

Vengono suddivisi a seconda del modo in cui vengono descritti e risolti i problemi:

• imperativi (programmazione strutturata)
• funzionali (programmazione funzionale)
• ad oggetti (programmazione ad oggetti)
• dichiarativi (programmazione

ALGORITMI E DIAGRAMMI DI FLUSSO

algoritmo

Un un insieme ordinato di operazioni non ambigue ed e ettivamentecomputabili che, quando eseguito, produce un risultato osservabile e si arresta in untempo nito.

Un algoritmo deve avere le seguenti propriet :

• Finitezza: composto da un numero nito di passi elementari.
• Non ambiguità: (determinismo): i risultati non variano in funzione della macchina/persona che esegue l'algoritmo.
• Realizzabilità: deve essere eseguibile con le risorse a disposizione.

Per de nire un algoritmo necessario:

1. Condurre un'attenta analisi del problema ed eventualmente suddividere il problema in piccoli sottoproblemi.
2. Individuare i possibili ingressi e precisare le uscite (de nizione dei dati).
3. De nire completamente e dettagliatamente la sequenza dei passi che portano alla soluzione.

Per realizzare un algoritmo occorre rappresentare la ("azionielementari") che portano alla sua soluzione con

istruzioni di un linguaggio di programmazione.

Le azioni elementari (passi) di un algoritmo:

• devono dare un risultato
• certo
• unico
• ripetibile
• devono fornire il risultato in tempo finito
• devono essere interpretabili senza ambiguità dall'esecutore

Diagrammi di flusso (flowchart) sono un formalismo grafico per descrivere gli algoritmi.

Scompongono in passi successivi gli algoritmi, un diagramma di flusso è una descrizione più efficace e meno ambigua di una descrizione a parole.

Le operazioni su cui si basa un diagramma di flusso sono:

• Trasferimento di informazioni
• Esecuzione di calcoli
• Assunzione di decisioni
• Esecuzione di iterazioni

Nodi e Archi

Un diagramma di flusso è costituito da due tipi di entità:

• azioni elementari
• istruzioni primitive

Le istruzioni primitive eseguibili da un esecutore (calcolatore) sono:

• Operazioni aritmetiche
• Lettura di dati
• Scrittura di dati

dati sintattici”Nei linguaggi di programmazione i ”costrutti permettono di combinare opportunamente le azioni elementari.

Esistono diversi tipi di costrutti sintattici:

• Costrutto Sequenza– (eseguire un’azione dopo l’altra) —> “esegui A, poi B, poi C, ...”
• Costrutto Condizionale– (eseguire un’azione solamente se una certa condizione è verificata) —> “se X verificato allora esegui A”
• Costrutto Iterativo– (eseguire un’azione più volte finché non si verifica una condizione) —> “ripeti A finché X non verificato”

Ad ogni tipo di costrutto sintattico (linguistici) si associano delle strutture di controllo del flowchart.

Uso dei dati nei programmazione top-down

La una tecnica di programmazione per la realizzazione di programmi con la scomposizione iterativa di un problema in sotto problemi.

Si presta molto bene per la definizione di algoritmi con i diagrammi di flusso:

- All’inizio

1. Il diagramma di flusso rappresentato da un nodo che rappresenta la soluzione al problema. - Questo nodo viene scomposto in una rete di nodi in modo iterativo. - La scomposizione termina quando i singoli nodi possono essere rappresentati da semplici sequenze di istruzioni del linguaggio di programmazione scelto.
2. Fattoriale di un numero: Il in matematica si indica come n! ed è definito, se n è un intero positivo, come il prodotto dei primi n numeri interi positivi.
3. In Informatica l'algoritmo per il calcolo del fattoriale è definito in maniera ricorsiva.
4. A destra un possibile diagramma di flusso per rappresentarlo:

Esempio: massimo di 2 numeri

LINGUAGGI DI PROGRAMMAZIONE

Linguaggi macchina: I delle CPU forniscono solo le operazioni che l'elaboratore può eseguire:

• Operazioni molto elementari.
• Diverse per ogni processore.
• Scritte in linguaggio binario.

Sono più orientati alla macchina che ai

provvede le forme espressive appropriate per alcuni problemi speci ci.

linguaggio imperativo

Un legato all'architettura della macchina di Von Neumann, maad un livello di astrazione vicino a quello dei diagrammi di usso.

• Un programma una sequenza di istruzioni in cui:
• Le istruzioni vengono eseguite in sequenza.
• La sequenza pu essere alterata con istruzioni di salto.
• Le operazioni che e ettuano le istruzioni si basano sul concetto di variabile.
• Una variabile una astrazione del concetto di locazione di memoria in cui puessere assegnato, letto e modi cato un valore.
• Il C, Fortran, Pascal, Cobol e Basic sono i linguaggi imperativi pi di usi.

linguaggio logico

In un un programma composto da una base di conoscenzacontenente:

• Una descrizione del dominio del problema composta da un insieme di fatti.
• Un insieme di regole per manipolare l'insieme dei fatti.

ù è è ò ff è fi è à fi fl ù ff fi ò ò

L'esecuzione di un programma corrisponde all'applicazione delle regole sulla base di conoscenza:

• L'esecuzione guidata da un motore inferenziale.
• L'esecuzione attivata da una interrogazione dell'utente.
• Lo scopo dell'esecuzione verifica che l'interrogazione dell'utente sia vera o falsa.

Il linguaggio più conosciuto è il Prolog, un linguaggio funzionale in cui un programma è visto come una funzione matematica.

L'esecuzione di un programma corrisponde alla valutazione della funzione rispetto ai suoi argomenti.

Le differenze maggiori con un linguaggio imperativo sono:

• Non esiste il concetto di variabile.
• Sono adatti a elaborazioni simboliche.

Il Lisp è il linguaggio più conosciuto, ma non più molto usato.

Un linguaggio di programmazione orientato agli oggetti (OOP) consiste nella:

• Definizione di un insieme di classi.
• Creazione di un insieme di oggetti ed esecuzione dei