Cos’è un calcolatore

Risoluzione di un problema

Algoritmo

Esempio MCD

Cifrario di cesare

Hardware e software

Sistemi operativi

Programmi

Astrazione

Linguaggio di programmazione

Compilatore

Programma

Es.: i blocchi

Dal Problema al Programma

Es.: somma primi 100 naturali

Tracciamento

Es.: somma numeri da N ad M

Processo risoluzione programma

Dati

Classi di istruzioni

Pseudo codice

Stampa di una linea di testo

Variabile

Assegnamento

Area di un rettangolo

Istruzioni di assegnazione

Istruzioni composta

Istruzioni condizionali

Istruzioni di controllo

Livelli di rappresentazione

Ciclo di vita di un programma

Storia del linguaggio C

Le funzioni

printf, include, scanf

Com’è fatto un programma in C

Quadrato di un numero

Somma di due numeri

Tipi di dati

Rappresentazione in memoria

Tavola ASCII

Operatori relazionali

Istruzioni if – else

Ramificazione del flusso

Esercizi

Soluzione esercizi del laboratorio

Il tipo di dato reale

Espressioni

Operatori matematici

Esercizi vari

Priorità degli operatori

Teorema di Bohm-Jacopini

Strutture di selezione

Esercizi vari

Scambio di due variabili

Es.: individuare il tipo di un triangolo

Strutture di selezione

Esercizi vari

Il mistero delle {}

System (“Pause”)

Printf e Scanf

if

Esercizi vari

Esercizi sugli operatori logici

IF equivalenti

Ricerca del MIN e MAX di una sequenza di numeri

Il calcolatore di Von Neumann: unità di I/O, Memoria, CPU

Cenni sulla rappresentazione delle informazioni

Informazioni rappresentabili

Esempi di rappresentazioni

Calcolatore elettronico: sottoinsiemi funzionali

Struttura di Von Neumann

Memoria principale

Interazione CPU-Memoria principale

Struttura della CPU

Esecuzione delle istruzioni: fetch. decode, execute

Linguaggi macchina

Dispositivi di I/O

Memoria secondaria

KByte, MByte, GByte, …

Sistemi operativi

Struttura del bus

Programmazione dei calcolatori

Linguaggi assemblativi

Assembler

CPU didattica: somma di due numeri

Linguaggi ad alto livello

Compilatori
Progetto:scrittura-> compilazione-> collegamento-> esecuzione

Istruzioni di trasferimento, aritmetiche di I/O e di salto e salto condizionato

Esempio di programma

Codici delle operazioni

Allocazione in memoria di programma e dati

Svantaggi del linguaggio assembler

Novità dell’assembler

codice-op mnemonici

Le etichette

Es. somma di due numeri con confronto finale

Cenni sulla complessità (approfonditi in seguito)

Comportamento della CPU nell’interpretazione dell’assembler

La SWITCH

Due possibili espressioni per la switch

Es. calcolare il giorno dopo di una determinata data considerando anche gli anni bisestili

La FUNCTION

Concetto di modulo di un programma

Funzioni in C

Es. cubo di un numero

Prototipo

Definizione

Chiamata

I commenti in C

Strutture di controllo

IF e ?

SWITCH

While

do-While

FOR

break e continue

Programma con funzioni

Passaggio di argomenti

Variabili locali

Es.: funzioni in un programma

Librerie matematiche

Funzioni come scatole nere

Le funzioni nel DevCpp

Es. 1: min e max di 3 numeri

Es. 2: semplice calcolatrice

Es. 3: somma tra frazioni

Analogico vs Digitale

Rappresentazione ed interpretazione

Valori numerici: numeri e numerali

BIT

Multipli del BIT

Numeri a precisione finita

Sistema di numerazione posizionale

Notazione

Esempi vari

Numerazione binaria

Conversione fra basi

Conversione da base 10 a base B

Algoritmo di conversione decimale -> binario

Esempi

Conversione fra basi:

— Binario -> Ottale

— Esadecimale -> Binario

— Decimale -> Binario (generico)

— Decimale -> Binario (solo per interi)

— Binario -> Decimale (2 metodi)

— Altri

Esempi ed esercizi

Codice ASCII

Tipo char in C

La rappresentazione dei numeri negativi

Modulo e segno

Complemento a 2

Complemento alla base di un numero

Rappresentazione in complemento alla base

Utilità del complemento alla base

La rappresentazione in virgola fissa dei numeri razionali

Problema dell’overflow

Problema dello spreco di memoria

Rappresentazione in virgola mobile

Mantissa ed esponente

Notazione scientifica normalizzata

Problemi con l’uso della virgola mobile

Cause principali di errore nel calcolo in virgola mobile

Come ridurre l’overflow e l’underflow

Proprietà aritmetiche in virgola mobile

Somma in virgola mobile

Operazioni binarie

Istruzione for

Esempi ed esercizi

Calcolo del fattoriale

Stampa dei pari

Piramide di asterischi

Do While

Operatori unari di decremento e decremento

Operatori di assegnazione composta

Espressioni con side-effect ed istruzioni

Iterazione definita

Errore nelle iterazioni

Iterazione indefinita

Min e Max

Esempi ed esercizi

Tipi di dato primitivi

Tipo :: short int

Tipo :: int

Tipo :: long int

Tipo :: unsigned short int

Tipo :: short

Tipo :: unsigned long int

Tipo :: byte

Tipo :: float

Tipo :: double

Specifiche di conversione per tipi interi

Operandi interi

Tipo di una costante

Operandi aritmetici per interi

Operatori di assegnamento

Conversione di tipo

Espressioni che coinvolgono tipi di dato primitivi numerici diversi

Assegnazioni fra tipi di dato primitivi numerici diversi

Esempi ed esercizi

Operatori logici

Tabelle di verità

Variabili e parametri

Variabili globali

Variabili e memoria

Indirizzo

Numero di byte occupati

Il tipo puntatore

Operatore indirizzo

Dichiarazione e uso di puntatori

Operatore di indirezione *

Esempi ed esercizi

Esecuzione da cursore

Breakpoint

Ispezione delle variabili

getchar()

Break

Return

Exit

Soluzione per raffinamenti successivi

Struttura di un programma C

Funzione

Unità chiamante e chiamata

Parametri formali e attuali

Associazione tra parametri formali e attuali

Prototipo, definizione, chiamata

Definizione di una funzione :: tipo di ritorno, lista di parametri, variabili locali, istruzioni

Coercizione degli argomenti

Esempi ed esercizi

Legame per riferimento

Legami per riferimento e valore in C

Blocchi

Caratteristica delle variabili

Tipo

Valore

Ciclo di vita

Campo d’azione

Regole di visibilità

Formattazione dell’output

Visualizzazione interi

Visualizzazione numeri in virgola mobile

Visualizzazione stringhe e caratteri

Altri operatori di formattazione

Visualizzare con le dimensioni di campo e la precisione

Specifiche di precisione

Array

Inizializzazione Array

Stampa degli Array

Esempi ed esercizi

Ricerca indice di un valore

Area del rettangolo di punti P1, P2, P3, P4

Verifica della palindromia di una stringa

Trova le posizioni di un numero in un Array e trasferiscine gli indici in un altro array

Esercizi per casa

Modi alternativi per accedere agli elementi degli Array

Memorizzazione degli Array in memoria

Passare gli Array alle funzioni

Esercizio del DNA

Chiamata per indirizzo

Esercizi per casa

Caricamento di un Array

Es.: calcolo delle frequenze dei voti di una classe

Es.: Array passati per riferimento, elementi passati per valore

Qualificatore const

Array Multidimensionali

Inizializzazione

Array bidimensionali e puntatori

Array multidimensionale come argomento di funzione

Memorizzazione di una matrice leggendo i dati da un file

Esercizi per casa

-Memorizzazione

-Inizializzazione

-Lettura e scrittura

Es.: conta parole

Rappresentazione di dati eterogenei

Strutture

-Memorizzazione

-Accesso ai campi

Composizione di una struttura

Accesso diretto

Accesso indiretto tramite puntatore

Modi alternativi di definire una struttura

typedef

Inizializzazione

Esercizi per casa

Es.: trovare i contribuenti aventi una età compresa in un certo intervallo

Utilizzo di strutture con funzioni

Strutture nidificate

Generazione di numeri casuali: rand, srand e time

Esercizi per casa

Esercizio Filtra

I/O in C

Stream

File

printf / frprintf – scanf / fscanf a confronto

Descrittore di file

Connessione

Modalità d’uso

Chiusura della connessione

Eccezioni

EOF

Esempi

Esercizi per casa

I/O su stdin e stdout

I/O su file

Esempio: scrivere caratteri su file

Esempio: conteggio caratteri di un file

Esempio: copia di un file

Esempi: acquisizione array da file

Esempio: acquisizione array bidimensionale

Norme di leggibilità del linguaggio

Commenti

Nomi di variabili e funzioni

Costanti

Spaziatura

Disposizione sottoprogrammi

Variabili globali

Uscita da una funzione

Allineamento e Indentazione

Esercizi per casa

Funzioni di gestione degli errori su file: errno, feof, ferror, perror

File speciali: stdin, stdout, stderr

Accesso casuale

fread

fwrite

fseek

ftell

Modalità operative di fseek

Funzioni di posizionamento nel file fsetpos, fgetpos

Esempio: stampare i mesi contenuti in file con 31 giorni

Esempio: lettura di un file e memorizzazione in una struttura in memoria centrale

Esempio: aggiornamento del file degli esami svolti da uno studente

Esercizi per casa :: file di CD

Espansione in linea delle Macro

Macro in forma parametrica
Definizione della macro

Macro VS Funzioni

Gestione dinamica della memoria

malloc, calloc, free

Funzioni della libreria standard di Input : getchar, gets, getc, fgetc, fgets, scanf, fscanf, sscanf

Funzioni della libreria standard di Output : putchar, puts, putc, fputc, fputs, printf, fprintf

Visualizzazione degli interi

Visualizzazione in virgola mobile

Visualizzazione di stringhe e caratteri

Dimensione di campo e precisione

Funzioni per la conversione delle stringhe : atof, atoi, atol, strtod, strtol, strtoul

Funzioni per la manipolazione delle stringhe : strcpy, strncpy, strcat, strncat, strcmp, strncmp

Esercizio :: playlist

Teoria della complessità

Misurazione delle risorse

Determinazione della complessità

Ipotesi semplificativa

Complessità in tempo, in spazio e asintotica

Complessità del caso peggiore, medio e ottimo

Notazioni: O, sigma e teta

Esempi e proprietà

Esercizi per casa

Classi principali: costante, sottolineari, nlogn, polinomiali, esponenziali

Esempio: ordinare un array

Esempio: Selection Sort

Calcolo dell complessità del Selection Sort

Quando un algoritmo ha buona complessità?

Esercizi per casa

Selection Sort

Complessità del Selection Sort

Bubble Sort

Bubble Sort ottimizzato

Complessità del Bubble Sort

Algoritmi di ricerca

Ricerca Sequenziale

Ricerca Binaria

Calcolo e confronto delle complessità
Esercizi per casa

Definizione: il caso base e il passo induttivo

Es. fattoriale

Definizioni ricorsive

Definizione ricorsiva dell’ordine lessicografico

Definizione ricorsiva di espressioni aritmetiche

Funzioni ricorsive

Selection Sort ricorsivo

Numeri di Fibonacci

Meccanismo delle chiamate a funzioni

Iterazione vs ricorsione

Eliminazione della ricorsione

Eliminazione della ricorsione in coda

Induzione completa

Validità delle dimostrazioni per induzione completa

Mergesort ricorsivo

Esercizi svolti sulla ricorsione: calcolo dei coefficienti binomiali, le torri di Hanoi, le curve di Koch

Esercizi per casa

Esercizi per casa

Esercizi per casa

Rappresentazione dei colori

Formato del file BMP

Esercizi sui FILE e Array

Lettura file BMP

Scrittura file BMP

Stampa header file BMP

Elaborazione

Funzione di elaborazione

Esercizi sui FILE e Array

Attenzione: alcuni potrebbero non funzionare.