Il software
  • Un programma è una serie di istruzioni che il computer può eseguire in sequenza

  • Il software è l'insieme dei programmi e dei dati disponibili su di un calcolatore

  • Un calcolatore può eseguire direttamente (sull'hardware) solo i programmi che sono scritti in linguaggio macchina

  • In un calcolatore si distinguono vari "strati" di software. Per semplicità ne consideriamo due:

    • Il sistema operativo (come Linux, Windows, Mac Os, ...)

    • Le applicazioni (come editori di testo, sistemi di gestione di basi di dati, giochi,...)

La programmazione
La programmazione è l'attività di sviluppare programmi per un calcolatore. Lo scopo della scrittura di un programma è la risoluzione di un problema. Per risolvere un problema, bisogna:

  • Formulare il problema (specifica dei requisiti) in modo più o meno formale

  • Capire il problema e scomporlo in parti gestibili (analisi del problema)

  • Progettare una soluzione (algoritmo)

  • Implementare la soluzione (scrittura del codice)

  • Sottoporre la soluzione a test e correggere eventuali errori (verifica del programma, testing e debugging)

  • Tenere sempre aggiornato il programma (manutenzione)
Di tutte queste fasi vedremo nel corso principalmente quella di implementazione dell'algoritmo, e marginalmente quelle precedenti.

La specifica
La prima fase della programmazione consiste nel comprendere e definire (specificare) il problema che si vuole risolvere

La specifica del problema può essere fatta in maniera più o meno rigorosa, a seconda del formalismo descrittivo utilizzato

La specifica di un problema prevede la descrizione dello stato iniziale del problema (dati iniziali, input) e dello stato finale atteso (i risultati, output )

La caratterizzazione degli stati iniziale e finale dipende dal particolare problema in esame e dagli oggetti di interesse

Esempi:

  1. Dati due numeri, trovare il maggiore
  2. Dato un elenco di nomi e numeri di telefono (rubrica o elenco telefonico) e un nome, trovare il numero di telefono corrispondente
  3. Data la struttura di una rete stradale e le informazioni sui flussi dei veicoli, determinare il percorso più veloce da A a B
  4. Scrivere tutti i numeri pari che non sono ottenibili come somma di due numeri primi
  5. Decidere (in tempo finito) per ogni programma C e per ogni dato in ingresso, se il programma C termina quando viene eseguito su quel dato

Caratteristica comune ai problemi:

  • Informazioni in ingresso informazioni in uscita (stato iniziale) (stato finale)

Osservazioni sulla formulazione dei problemi:

  • La descrizione del problema è talvolta ambigua o imprecisa (esempio 2 con Mario Rossi che compare più volte)
  • La descrizione non fornisce un metodo risolutivo (si pensi all'esempio 3)
  • Per alcuni problemi non è noto un metodo risolutivo (nell'esempio 4, la congettura di Goldbach è che tutti i numeri pari siano esprimibili come somma di due primi)
  • Esistono problemi per i quali è stato dimostrato che non può esistere un metodo risolutivo (ad esempio 5)

Gli algoritmi
Una volta specificato il problema, si determina un procedimento risolutivo dello stesso (algoritmo), ovvero un insieme di azioni da intraprendere per ottenere i risultati attesi.

Un algoritmo è una sequenza di passi che, se intrapresa da un esecutore, permettono di ottenere i risultati attesi a partire dai dati forniti

La descrizione di un procedimento risolutivo può considerarsi un algoritmo se rispetta alcuni requisiti essenziali:

  • Finitezza: un algoritmo deve essere composto da una sequenza finita di passi elementari
    • Eseguibilità: il potenziale esecutore deve essere in grado di eseguire ogni singola azione in tempo finito con le risorse a disposizione
  • Non-ambiguità: l'esecutore deve poter interpretare in modo univoco ogni singola azione

Esempio di algoritmi:

  • procedimenti per calcolare il risultato di espressioni aritmetiche (operazioni elementari come addizione, sottrazione,...; o più complesse come radice quadrata,...) o algebriche (prodotti di polinomi, ...)
Non sono algoritmi...
  • le ricette di cucina
  • le istruzioni per la compilazione della dichiarazione dei redditi (!)

La codifica
Un linguaggio di programmazione definisce un insieme di parole e di simboli e un insieme di regole per combinarli

A differenza dei linguaggi naturali, le regole dei linguaggi di programmazione (che sono linguaggi formali) sono molto rigide, per garantire l'assenza di ambiguità

Ci sono centinaia di linguaggi di programmazione, divisi in varie categorie:

Linguaggi 
ad alto livello
Linguaggi 
assembly
Linguaggi 
macchina

Esempio:
Istruzioni C Istruzioni assembler Istruzioni macchina Significato
sum =0 LOAD R1 #0 1100 | 00000 Inizializzazione di SUM; metti 0 in R1
STORE R1 SUM 0010 | 10111 Metti il valore di R1 in SUM
sum = sum + x LOAD R1 SUM 0000 | 10111 Somma parziale; metti in R1 il valore di SUM
LOAD R2 X 0001 | 10101 Metti in R2 il valore di X
SUM R1 R2 0100 | ----- Metti in R1 la somma tra R1 ed R2
STORE R1 SUM 0010 | 10111 Metti il valore di R1 in SUM

La fase di codifica consiste nell'individuare una rappresentazione degli oggetti di interesse del problema ed una descrizione dell'algoritmo in un opportuno linguaggio noto all'esecutore

Poiché vogliamo far uso di un calcolatore per l'esecuzione dell'algoritmo, il risultato della fase di codifica dovrà essere un programma scritto in un linguaggio di programmazione comprensibile ad un calcolatore: il linguaggio macchina

Per raggiungere questo scopo abbiamo due alternative:

  • Tradurre (codificare) l'algorimo in linguaggio macchina

  • Tradurre (codificare) l'algorimo in un opportuno linguaggio di programmazione e poi usare un programma che traduca compili il programma in un programma scritto in linguaggio macchina, e quindi eseguibile su un calcolatore


Schema standard di compilazione/esecuzione
Tutto dipende dalla piattaforma

Ad esempio, se vogliamo eseguire un programma C su macchine che usano processori di famiglie differenti dobbiamo ricompilarlo su ogni macchina.