Programmazione I 2011/2012

Informatica, Verona

• Al Kelley, Ira Pohl: C, Didattica e Programmazione, Pearsons Education Italia (testo di riferimento)
• Wikipedia: Rappresentazioni numeriche in binario ed esadecimale

• Introduzione al corso
• La macchina di Von Neumann
• Codifica binaria dei numeri
• Calcoli in binario (addizioni, moltiplicazioni e divisioni per potenze del 2)
• Numerazione ottale ed esadecimale

• Codifica binaria in complemento a due
• Codifiche in virgola mobile (cenni)
• Problemi di approssimazione nelle codifiche in virgola mobile
• Algebra di Boole
• Operazioni bit a bit

• Funzione main(), direttiva di inclusione, printf() e scanf(), sequenze di escape, variabili, direttive di definizione (Sezione 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.10 del testo di riferimento)
• Primo esempio di programma C: ground.c
• Dichiarazioni senza o con inizializzazione
• Esempio di uso di variabili: miles2kilometers.c
• Token, commenti, parole chiave, identificatori, costanti intere, ottali, esadecimali, carattere
• Costanti stringa
• Distinzione fra espressioni e comandi (o istruzioni)
• Operatori aritmetici, priorità, associatività, uso delle parentesi
• Operatore di assegnamento semplice: leftvalue
• Sezioni 2.1, 2.3, 2.4, 2.5, 2.6, 2.7, 2.8, 2.9, 2.11

• Tipi di dato numerici: short, int, long, float, double
• Modificatori signed ed unsigned
• Limiti di rappresentazione: overflow
• Limiti di rappresentazione: underflow e approssimazioni sui valori in virgola mobile
• Esempio di approssimazioni su float e double: approximation.c
• Sezioni 3.1, 3.2, 3.4, 3.5, 3.6

• Funzioni matematiche sui double: sqrt(), pow(), exp(), log(), sin(), cos(), tan() e fabs()
• Esempio di uso dei formati di stampa in virgola mobile e delle funzioni matematiche: matematica.c. Con molti compilatori è necessario includere la libreria matematica!: cc matematica.c -lm
• Tipo char. Caratteri come valori numerici: tabella ASCII
• Funzioni di libreria getchar() e putchar()
• Esempio di uso di caratteri per input/output: io.c
• Formati di stampa in ottale ed esadecimale
• Esempio di uso dei formati di stampa in ottale ed esadecimale: esa_oct.c
• Sezioni 3.3, 3.9, 3.10, 3.12

• Istruzioni (comandi) ed espressioni
• Struttura dell'istruzione if
• Operatori relazionali, di uguaglianza e logici: precedenza, associatività
• Espressioni relazionali, di uguaglianza e logiche
• Espressione di assegnamento
• Istruzioni composte, istruzione espressione, istruzione vuota
• Sezioni 4.1, 4.2, 4.3, 4.4, 4.5, 4.6

• Istruzioni if ed if/else
• Associazione dell'else all'if più vicino
• Espressioni di assegnamento e operazione
• Pre e post incremento/decremento
• Sezioni 2.10 e 2.11. Sezione 4.7

• Valutazione lazy (cortocircuitata) di && e ||
• Operatore condizionale ternario ?: con valutazione lazy
• Istruzione while
• Esempi di uso del while: calcolo del fattoriale
• Sezioni 4.8 e 4.17

• Espressione virgola
• Istruzione for
• Esempi di utilizzo del ciclo for: stampa di una riga di asterischi: riga_di_asterischi.c, stampa di una riga di asterischi allineata a destra, con due cicli: riga_di_asterischi_destra.c, con un solo ciclo e un comando condizionale: riga_di_asterischi_destra2.c, con un solo ciclo e un'espressione condizionale: riga_di_asterischi_destra3.c. Stampa ciclica delle 26 lettere dell'alfabeto inglese: stampa_alfabeto.c.
• Ciclo for che stampa i numeri di Fibonacci: fibonacci.c
• Sezioni 4.9, 4.11 e 4.13

• L'istruzione do...while
• Richiesta di un input reiterata finché l'input non è valido: domanda_ripetuta.c
• Calcolo della radice quadrata con un ciclo do...while: radice.c
• Sezione 4.12

• Le istruzioni break e continue
• L'istruzione switch: stampa del nome e dei giorni di un mese: mesi.c.
• Cicli annidati.
• Stampa della tabella pitagorica: tabella_pitagorica.c; stampa di un triangolo di asterischi: triangolo.c; stampa di segmenti di numero e lunghezza variabili: segmenti.c.

• Stampa di una sinusoide: sinusoide.c
• Funzioni (e procedure)
• Definizione di funzione

• Chiamata di funzione: passaggio dei parametri per valore
• Ritorno di un risultato: l'istruzione return
• Record di attivazione
• Vincoli sulla return, con o senza argomenti
• Esempio di funzioni: giorni_sfigati.c
• Prototipo di funzione

• Uso di asserzioni
• File di intestazione .h
• Organizzazione di un programma in .h e .c
• Esempio di un programma strutturato in funzioni: prime.c, prime.h, fattorizzazione.c.

• Struttura a blocchi del codice
• Variabili locali e variabili globali
• Regole di visibilità
• Visibilità di variabili globali fra file sorgenti diversi: extern (quasi sempre sottointeso) e static: conta_chiamate.c, blocchi.c, blocchi2.c.
• Esempio di condivisione di una variabile fra due file: file1.c, file2.c.
• Tempo di vita delle variabili: classi di memorizzazione auto, register e static

• Il modificatore const
• Esempio di programma strutturato in funzioni: verifica parziale della congettura di Goldbach: tutti i numeri pari maggiori di 2 sono la somma di due numeri primi: prime.c, prime.h, goldbach.c, goldbach.h, main_goldbach.c. Da compilare con cc prime.c goldbach.c main_goldbach.c
• Esempio di programma strutturato in funzioni: il gioco delle torri di Hanoi: main_hanoi.c, hanoi.c, hanoi.h. Da compilare con cc main_hanoi.c hanoi.c

• Ricorsione
• Esempi di funzioni ricorsive: somma dei primi n numeri: somma.c, fattoriale: fattoriale.c, fibonacci: fibonacci.c.

• Si scriva un programma calcolatrice.c che opera come una semplice calcolatrice. Il programma deve consentire all'utente di digitare espressioni della seguente forma:

  numero operatore

  I seguenti operatori devono essere riconosciuti dal programma:

  + - * / S E

  La calcolatrice usa un accumulatore, inizialmente posto a 0. L'operatore S indica al programma di assegnare all'accumulatore il numero digitato. L'operatore E indica al programma di concludere l'esecuzione. Le operazioni aritmetiche sono svolte sul contenuto dell'accumulatore con il numero digitato che funge da secondo operando. Il programma deve controllare il caso della divisione per zero e verificare che l'operatore digitato sia ammesso.
  Per esempio, il programma dovrebbe comportarsi come segue:

  inizio dei calcoli
  10 S
  = 10.000000
  2.1 /
  = 4.761905
  0.0 /
  divisione per zero: impossibile
  = 4.761905
  0 /
  divisione per zero: impossibile
  = 4.761905
  1 +
  = 5.761905
  1.3 -
  = 4.461905
  -2.3 *
  = -10.262383
  8.1 S      
  = 8.100000
  0 E
  = 8.100000
  fine dei calcoli
       

• Un programma che dà il resto: resto.c
• Esempi di funzioni ricorsive: massimo comun divisore: gcd.c, funzione di Ackermann: ackermann.c, funzione 91 di McCarthy: mccarthy91.c
• Funzione ricorsiva che stampa le prime n lettere dell'alfabeto in ordine descrescente: prime_lettere_inverso.c
• Funzione ricorsiva che stampa le prime n lettere dell'alfabeto in ordine crescente: prime_lettere.c
• Ricorsione: il caso della torre di Hanoi: main_hanoi_automatico.c, hanoi.c, hanoi.h. Da compilare con cc main_hanoi_automatico.c hanoi.c

• Si scriva una funzione ricorsiva contiene9(int n) che riceve un numero non negativo n e restituisce vero se e solo se n contiene la cifra 9. Si scriva quindi un main() di prova che legge il numero da tastiera, lo richiede se è negativo e poi chiama la funzione contiene9() per dire se il numero contiene o no la cifra 9.

Prima prova parziale, senza nessuna iscrizione: 24 gennaio 2012, 8:30 - 10:30, aula Tessari

Fine prima parte del corso

• Array di valori primitivi: definizione, accesso agli elementi
• Iterazione come strumento tipico di elaborazione degli array
• Algoritmi sugli array: lettura di un array da tastiera elemento per elemento, scrittura di un array, somma degli elementi di un array, calcolo di massimo, minimo e media degli elementi di un array: array.c

• Passaggio di un array come parametro di una funzione: effetti collaterali (side-effects). passaggio.c
• Il modificatore const: per l'array e per gli elementi dell'array
• Determinare se un array è ordinato in senso non decrescente: non_decrescente.c
• Moltiplicazione fra due vettori di float: moltiplicazione.c

• Funzione che inizializza un array a numeri casuali
• Funzione che stampa un array
• Funzione che scambia due elementi di un array
• Funzione che determina la posizione in cui si trova l'elemento minimo in un array
• Ordinamento per ricerca iterata del minimo (MinSort)
• min_sort.c

• Ordinamento per ricerca iterata del minimo: versione ricorsiva
• Ordinamento per bolle (BubbleSort): bubble_sort.c
• Ordinamento per fusione (MergeSort): merge_sort.c
• Gara di velocità fra gli algoritmi di ordinamento: sorting.c

• Array bidimensionali
• Stampa della tabella pitagorica: tabella_pitagorica.c
• Creazione random, stampa e somma fra matrici: matrici.c

• Moltiplicazione fra matrici
• Uso dei vettori multidimensionali per l'implementazione del gioco del campo minato (o prato fiorito): campo_minato.c, grafica.c e campo_minato.h. Da compilare con

       cc campo_minato.c grafica.c
       

• Array di char: costanti stringhe come array di caratteri, formato %s di printf: array_di_caratteri.c.
• Funzioni sulle stringhe viste come array di caratteri: modifica_stringhe.c.
• Il concetto di puntatore a tipi primitivi
• Modifica di una variabile per side-effect tramite puntatore

• Passaggio dei parametri per riferimento: in C non esiste ma si simula con il passaggio per valore del puntatore
• Relazione fra array e puntatori: passa_array.c, pointers_arrays.c.
• Implementazione delle operazioni sugli array tramite puntatori
• Aritmetica dei puntatori
• Scorrimento di un array tramite incremento di un puntatore
• Cinque modi diversi di calcolare la lunghezza di una stringa: lunghezza.c.

• Funzioni che restituiscono un puntatore: massimo degli elementi di un array di interi
• Il puntatore NULL

• Esempi di funzioni con puntatori e incrementi di puntatori: vari modi di trovare l'ultimo carattere di una stringa: last.c; determinare se una stringa è palidroma: palindroma.c.

• Funzione che inverte una stringa in un buffer passato come argomento: reverse.c
• Esercizi su puntatori, array e stringhe: si completino le funzioni nel file strings.c in modo che siano corrette e, quindi, tutti i test passino. Soluzione: strings.c.

• Dangling pointers: dangling.c
• Puntatore a void
• Allocazione della memoria con malloc() e deallocazione con free(): reverse.c

• Funzioni della libreria standard string.h: esempio di utilizzo di strcat: concatena.c
• Il modificatore const per i puntatori
• Esempio di implementazione di strcpy(), strcat() ed strcmp(): strings.c

• Si implementino le funzioni di libreria strncmp(), strchr() ed strpbrk(), senza ovviamente cercare in internet una loro implementazione! Descrizione delle funzioni. Soluzione: strings.c

• Array di puntatori
• Argomenti della funzione main(): print_arguments.c
• Puntatore a puntatore
• Ordinamento alfabetico degli argomenti passati al main(): sort_arguments.c
• Determinare se un anno passato da linea di comando è bisestile: bisestile.c

• Funzioni della libreria standard ctype.h
• Funzioni atoi() e atol() di stdlib.h
• Implementazione di un programma che stampa il calendario di un mese di un anno, indicando mese e anno da linea di comando calendar.c. Utilizza l'algoritmo di Gauss per determinare il giorno della settimana di una data.
• Definizione di macro tramite #define. Ad esempio di IS_FEBRUARY e simili nel programma precedente
• Problemi legati all'uso delle macro (uso delle parentesi, valutazione ripetuta dei parametri)

• Strutture: il costrutto struct
• Definizione di variabili di tipo struttura
• Accesso ai campi di una espressione di tipo struttura: l'operatore punto
• Assegnamento fra espressioni di tipo struttura
• Passaggio e ritorno di strutture alle/dalle funzioni
• Passaggio delle strutture per valore
• Passaggio delle strutture per riferimento, usando i puntatori
• La notazione ->
• Riepilogo su tutti i leftvalue del C
• Esempio: programma per generare un mazzo di carte a caso: versione senza strutture: carte.c; versione con le strutture: carte_struct.c.

• Inizializzazione delle variabili di tipo struttura
• Uguaglianza nominale e non strutturale fra tipi struttura
• Organizzazione dei programmi:
  • un file .h definisce una struttura e le segnature delle funzioni sulla struttura
  • un file .c importa il .h e implementa le funzioni sulla struttura
  • chi usa la struttura, include il .h e compila il .c insieme agli altri sorgenti
• Esempio, le date del calendario: i file data.h e data.c definiscono e implementano una struttura data che rappresenta una data del calendario. Tali file definiscono e implementano, in particolare, le funzioni:
  • struct data *construct(int giorno, int mese, int anno), che costruisce una data rappresentante il giorno del mese dell'anno indicato. Se la data non è lecita, ritorna NULL
  • char *toString(struct data *this), che restituisce una stringa che descrive la data this in italiano, del tipo 13 gennaio 1973
  • int equals(struct data *this, struct data *other), che determina se le due date sono le stesse (stesso giorno, mese e anno)
  • int compareTo(struct data *this, struct data *other), che ritorna un numero negativo se this viene prima di other, 0 se sono uguali e un numero positivo se other viene prima di this
  • struct data *next(struct data *this), che ritorna la data successiva a this
  Tale programma può essere usato con il seguente main.c.

• Deallocazione delle strutture allocate da una malloc(): il distruttore di una struttura
• Esempio: data_loop.c, da compilare con i file per la data della lezione precedente
• Riorganizzazione del main dell'esempio delle date, in modo da effettuare le deallocazioni di memoria: main.c
• Programma che usa due strutture: gestione di una rubrica nome/cognome/telefono: voce.h, voce.c, rubrica.h, rubrica.c, main_rubrica.c
• Le direttive #ifdef, #ifndef e #endif del preprocessore C

• Strutture che contengono altre strutture
• Strutture che contengono puntatori ad altre strutture
• Il caso dello studente con una data di nascita
• Definizione di una struttura che rappresenta un orario della giornata (ora, minuti, secondi): orario.h e orario.c
• Definizione di una struttura che ingloba una data e un orario: clock.h e clock.c con una funzione che passa all'orario successivo e se passa la mezzanotte incrementa la data
• Che senso hanno le strutture ricorsive?

• La struttura ricorsiva per le liste
• Algoritmi ricorsivi sulle liste: traduzione in stringa, stampa, lunghezza, test di appartenenza: list.h, list.c, main.c.

• Algoritmi ricorsivi sulle: concatenazione, rimozione di un elemento, alternanza fra due liste, fusione di liste ordinate: list.h, list.c, main.c.
• Esercizi sulle liste

• Esercizi sulle liste

• Utilizzo delle liste per implementare le colonne della torre di Hanoi, di dimensione arbitraria: main_hanoi.c, hanoi.c, hanoi.h, list.h, list.c. Da compilare con cc main_hanoi.c hanoi.c list.c

• Esercizi di preparazione alla seconda prova parziale

• Esercizi di preparazione alla seconda prova parziale

Seconda prova parziale, senza nessuna iscrizione: 15 giugno 2012, 8:30 - 10:30

Fine del corso