Lezione 12

Algoritmi di Ordinamento cenni introduttivi:

  • Bubble Sort, Shell Sort.
  • Selection Sort: for all i, si seleziona il minimo in [i,N)  e lo si mette in v[i]
  • Insertion Sort: for all i, si estrae (la carta/il valore) v[i] e lo si mette nella sua corretta posizione nel sottovettore v[0..i-1] spostando verso destra fin quando necessario.

Implementazone in C:

#include <stdio.h>
#include <stdlib.h>

#define N 100

void insertion_sort(int v[N], int size)
{
    for (int i=1; i<size; i++)
    {
        int t = v[i];
        int j = i-1;
        while (j>=0 && v[j] > t) { v[j+1] = v[j]; j--; }
        v[j+1] = t;
    }
}

void vprint(int v[N], int size)
{
    for (int i=0; i<size; i++) {
        printf("%2d ",v[i]);
        if ((i+1) % 20 == 0)
            printf("\n");
    }
}

int main(void)
{
    int v[N];
    
    for (int i=0; i<N; i++)
        v[i] = rand() % 30 + 1;
    vprint(v,N);
    insertion_sort(v,N);
    printf("--------------------\n");
    vprint(v,N);
    return 0;
}

Ricorsione:

  • Funzioni Ricorsive, regole di visibilità
  • Funzioni Ricorsive come sostituto all'iterazione (Turing Equivalenza)
  • Ricorsione e Iterazione infinita: necessità del caso base.
  • Alcuni esempi:  fattoriale, fibonacci, mcd, potenza

Esercizi: scrivere tutte le funzioni sopra in modo ricorsivo.

  • Ordinamento Ricorsivo: merge / mergesort

 

Lezione 11

Esercizi su Vettori:

  • Ricerca di un elemento in un vettore, codice della ricerca lineare:
/*
 input: un vettore v di al massimo N elementi
        un intero x
        un intero n <=N.
 output:  k in [0,n) tale che v[k] = x 
         -1 se x non appartiene a v
*/
int linear_search(int v[N], int n, int x)
{
    for (int i=0; i<n; i++)
        if (v[i] == x) return i;
    return -1;
}

Algoritmo di ricerca binaria, o dicotomica (o metodo di bisezione):

/*
 input: un vettore v di al massimo N elementi
        v e' ordinato in modo crescente
        un intero x
        due interi low, hi, con low < hi <=N.
 output:  k in [low,hi) tale che v[k] = x 
         -1 se x non appartiene a v
*/
int binary_search(int v[N], int low, int hi, int x)
{
    if (x < v[low] || x > v[hi]) return -1;
    while (low < hi) {
        int mid = (low + hi)/2;
        // printf("debug: search in [%d,%d,%d)\n",low,mid,hi);
        if (v[mid] == x) return mid;
        else if (x > v[mid]) low = mid+1;
        else if (x < v[mid]) hi = mid;
    }
    return -1;
}

Lezione 10

 

  • Scope delle variabili, ambienti, visibilità di un nome.
  • Funzioni. Dichiarazione e uso.
  • Parametri Formali, Parametri Attuali
  • Passaggio di Parametri per valore.
  • Parametri array, semantica associata al passaggio del nome dell'array.
  • Dimensioni degli array/matrici nelle funzioni.

Lezione 9

Array e Matrici.

Creazione di un file di testo, con:

numero righe, numero colonne
matrice.

Lettura delle tre righe dentro tre vettori a,b,c, calcolo di a+b,a-b,etc. Costruzione di una matrice M con righe a,b,c. Calcolo e stampa di (prodotto tra matrici).

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define N 100

void vprint(double v[N], int s)
{
    putchar('[');
    for (int i=0; i<s ; i++) {
      char final_char = (i==s-1) ? ']' : ',';
      printf("%8.2f%c",v[i],final_char);
    }
    putchar('\n');
}

int main(void)
{
    // creo un file con i dati.
    // matrice 3x5 con valori in [-20,20] casuali.

    seed = time(NULL);
    srand(seed);
    printf("3 5\n");
    for (int i=0; i<3; i++) {
        for (int j=0; j<5; j++) {
            printf("%.2f ", ((double)rand()/RAND_MAX)*20-10);
        }
        printf("\n");
    }

    /* adesso rileggo: assumo che la parte sopra venga
     * eseguita per generare un file matrice.dat tramite redirezione dell'output
     * il file verra poi letto tramite redirezione dell'input.
     */
    int n = 0; s = 0;
    scanf("%d %d",&n, &s);
    double a[N], b[N], c[N];

    for (int i=0; i<s; i++) scanf("%lf",&a[i]);
    for (int i=0; i<s; i++) scanf("%lf",&b[i]);
    for (int i=0; i<s; i++) scanf("%lf",&c[i]);

    printf("a = "); vprint(a,s);
    printf("a = "); vprint(b,s);
    printf("a = "); vprint(c,s);

    // ok, facciamo una somma:
    double z[N] = { 0 };
    for (int i=0; i<s; i++) z[i] = a[i] + b[i];
    vprint(z,s);
    double len = 0;
    for (int i=0; i<s; i++) len += z[i]*z[i];
    len = sqrt(len);
    printf("||z|| = %.2f\n",len);
    // normalize z
    for (int i=0; i<s; i++) z /= len;
    printf("z normalized: "); vprint(z,s);
    
    // ok, ora le matrici:
    double m[3][N];
    for (int i=0; i<s; i++)
        for(int j=0; j<s; j++)
           switch(i) {
           case 0: m[i][j] = a[j]; break;
           case 1: m[i][j] = b[j]; break;
           case 2: m[i][j] = c[j]; break;
           }
     mprint(m,3,s);  // scrivete voi la funzione.

     //scrivete il prodotto di m trasposto per m.

     return 0;
}

Esercizi:

  • dato un vettore, ed un valore x, trovare tutte le coppie del vettore che sommati fanno x. inserite un contatore dei controlli (if) svolti, e stampatelo alla fine, quanto può essere al massimo il valore di questo contatore? dipende dai dati? e nel caso peggiore?
  • dato un vettore di numeri interi, ordinarlo in modo crescente seguendo il seguente principio: il primo elemento del vettore ordinato è chiaramente il minimo di tutto il vettore, il resto del vettore rispetta lo stesso principio.
  • dato un vettore di interi ordinarlo in modo crescente seguendo questo principio: il vostro vettore è come un mazzo di carte da gioco, se è ordinato fino ad una certa carta (da sinistra a destra), la prima carta che non rispetta l'ordinamento viene inserita scorrendo dall'inizio della mano, cercando il punto in cui andrebbe inserita, e facendo poi scorrere le rimanenti carte per 'farle posto'. Formalizzate questa procedura e scrivete il codice C.

Lezione 8

Linguaggio C:

  • Stream standard per l'input output, stdin, stdout, stderr.
  • Redirezione degli stream da console, esempi:


$ programma > file.txt (redirezione dell'output)
$ programma < file.txt (redirezione dell'input)
$ programma < file1.txt > file2.txt (redirezione di entrambi)
$ programma1 | programma 2 (pipe (tubo): redirige l'output di programma1 sull'input di programma2)

  • Funzioni per la generazione di numeri pseudo-casuali: srand(seed), rand().
  • Funzioni per la lettura / scrittura di singoli caratteri getchar(), putchar(), la costante predefinita EOF.
  • Array: dichiarazione, utilizzo, esempio: lettura di 100000 interi tra 0 e 1000 generati da rand() e scritti in un file, e verifica che la distribuzione della rand() è
    uniforme. L'intervallo dei valori 0,1000 è suddiviso in 100 bin, associate alle variabili di un array.
  • Array come prodotto cartesiano su un tipo valido del linguaggio: ortogonalità del costrutto.
  • Array in memoria, rappresentazione.
  • Array di Array (matrici)

Lezione 7

C Tour de Force:

  • #define
  • passi del compilatore: preprocessore -> compilatore -> assembler -> linker
  • espressioni in C: assegnamento come espressione, pre-incremento / post-incremento (o decremento), (vedere su libro anche espressione condizionale e confrontare con il comando if).
  • espressioni booleane, tipo bool, include stdbool.h, operatori logici: && (and) || (or), ! (not).
  • comandi condizionali: switch, if, else pendente, iterazioni: while, do ..while, for.
  • iterazioni: uso del break, uso del continue.

Esempio: numeri primi:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void)
{
    int p = 0;
    // leggo p dall'input
    printf("Inserisci un intero: ");
    scanf("%d",&p);
    
    bool primo = true;
    int d = 0;

    // test di primalita' per p
    // p non e' primo se esiste un divisore, quindi
    // cerchiamolo: deve esistere in [2,sqrt(p)] 

    for (d = 2; d*d <= p; d++) {
        if (p % d == 0) { 
            primo = false;   // d e' un divisore di p
            break;           // posso terminare subito il ciclo
        }
    }

    if (primo) {
        printf("Ok, %d e' primo\n",p);
    } else {
        printf("Mi spiace, %d non e' primo, ",p);
        printf("infatti %d e' un suo fattore\n",d);
    }
    return 0;
}

Osservazione: Nel ciclo for, ho scritto come prima espressione d = 2. Notiamo che non è una dichiarazione, cioè non c'è scritto "int d = 2", le due istruzioni sono diverse, come vedremo in modo più approfondito questo ha a che fare con lo "spazio di visibilità dei nomi", un concetto importante nei linguaggi di programmazione: se mettevo la dichiarazione dentro il for, allora la variabile d esiste solo dentro il costrutto for.

Quindi all'uscita dal for essa cessa di esistere. Usarla nella printf subito sotto (riga 31) sarebbe sbagliato, ed il compilatore lo segnalerebbe (provate).

La dichiarazione fuori dal for invece, implica che la variabile è visibile fino alla fine del blocco corrispondente (la funzione main).

In generale quando si scrivono for, la pragmatica moderna ci dice che è preferibile limitare al massimo lo spazio di visibilità di una variabile e quindi, se non serve usarla 'fuori' dal ciclo, meglio inserire la dichiarazione nel for, ad esempio come in

for(int i=0; i<10; i++)...

Potete studiare il testo fino al capitolo sugli array incluso.

Lezione 6

Installazione di CodeBlock e uso dell'interfaccia.

Primo esercizio: Dato un intero in input, per ogni valore intero con stampare una riga con il valore di , quello di fattoriale e quello di .

Tipi nuovi: unsigned long long int.

Prima versione:


#include <stdio.h>
#include <math.h>

int main(void) 
{
    int n = 0;
    printf("Inserisci un intero: ");
    scanf("%d", &n);
    printf("Tabella dei fattoriali e loro radici quadrate");
    printf(" - n = %d\n",n);
    printf("-----------------\n");

    int i = 0;
    while (i <= n) {
        int k = 1; 
        unsigned long long f = 1;   // il fattoriale e' molto grande.
        while (k <= i) { f *= k; k++; }
        printf("%d\t %llu\t %10.3f\n",i,f,sqrt(f));
        i++;
    }
    return 0;
}

Definizione di Funzione in C:


#include <stdio.h>
// funzione fattoriale, iterativo
// calcola n! 
unsigned long long fact(int n)
{
    int k = 1; 
    unsigned long long f = 1;   // il fattoriale e' molto grande.
    while (k <= n) f *= k++;    // post-incremento, vedere libro.
    return f;
} 
// uso: printf("%llu \n",fact(4));

 

Seconda versione, con i for.


#include <stdio.h>

int main(void)
{
    int n = 0;
    printf("Inserisci un intero: ");
    scanf("%d", &n);
    printf("Tabella dei fattoriali e loro radici quadrate");
    printf(" - n = %d\n",n);
    printf("-----------------\n");
    unsigned long long f = 1; // il fattoriale e' molto grande. 
    for (int i = 1; i <=n; i++) {
        f *= i;
        printf("%d\t %llu\t %10.3f\n",i,f,sqrt(f));
    }
    return 0;
} 

Modificate il codice sopra: aggiungete una funzione che calcola la radice quadrata di un numero, e aggiungete un altra colonna, stampando la valutazione di tale funzione. Verificate che le ultime due colonne (quella della vostra radice e quella della sqrt corrispondano).

Esercizio: dato p intero, verificare se p è primo, scrivete un programma che legge n, e stampa 'primo' se lo è, oppure stampa un divisore di n (provando quindi che non è primo). Quando avete finito il programma, provate a modularizzare il codice, scrivendo una funzione:

Esercizio: I fattori primi di 13195 sono 5, 7, 13 and 29. Qual'è il fattore primo più grande di 600851475143 ? come scrivereste il codice? in C o in Python? perche? 

Iterazioni in C: ciclo while, ciclo for, ciclo do..while. Semantica.

Studiare dal Libro: capitolo 4, in particolare 4.2, riquadro Side Effects, Lvalue, assegnamento composto. 4.3 Operatori di Incremento/Decremento.

Nota: Dal punto di vista dei contenuti, potete procedere pian piano e svolgendo quanti più esercizi fino al Capitolo 8. Ricordate che il libro non è da usare come 'libro di corso' nel senso di procedere capitolo per capitolo 'esaustivamente' leggendo TUTTO, ma leggere, segnandosi man mano le cose importanti, e concentrandosi sugli esercizi. Il libro è un 'manuale di riferimento del linguaggio'. Per apprendere vanno fatti esercizi, quanti più ne fate, meglio vi troverete.

Lezione 5

Sommario del Programma svolto:

  1. Capitolo 1 delle note, svolgete esercizi di conversione tra diverse basi, con diversi formati (complemento a due, in scostamento)  e in virgola mobile. Provate semplici operazioni di somma/sottrazione o moltiplicazione in binario (ad esempio su 4 bit).
  2. Hardware del PC. Architettura di Von Neumann, CPU, RAM. bus. Periferiche. Struttura della CPU, ciclo di caricamento, decodifica, esecuzione (CPU come interprete del codice macchina).

Lezione:

  • Linguaggi Interpretati vs Compilati (script vs programmi binari).
  • Tipi di dato e loro uso nei linguaggi di programmazione: tipi dinamici (Python). Tipi statici (C). Uso dei tipi per effettuare controlli di correttezza semantica sulle operazioni svolte dal programma. Errori sintattici/semantici, semantica statica (C) o dinamica (Python).
  • Programmi svolti. Dato un intero , stampare il valore della somma dei primi numeri dispari.
#prima versione (non corretta)
n = int(input("Inserisci un intero: "))
somma = 0
i = 0
while i < n:
    if (i % 2 == 0):
        somma = somma + i
    i = i + 1

print("La somma dei numeri dispari da 1 a %d e' %d" % (n,somma))

La versione sopra non è corretta perche in realtà non sommiamo i primi numeri dispari, ma sommiamo i numeri dispari fino ad , il che è chiaramente diverso.
Invece dobbiamo svolgere la seguente sommatoria


Quindi:


n = int(input("Inserisci un intero: "))
somma = 0
i = 0
while i < n:
    somma = somma + (2*i+1)
    i = i + 1

print("La somma dei numeri dispari da 1 a %d e' %d" % (n,somma))

A parte osservare che il programma sopra può ridursi ad un semplice print(n**2) perche:


Quando diciamo che un linguaggio come Python è ad alto livello, lo facciamo perche ad esempio è possibile scrivere quel programma semplicemente con due righe di codice:

# leggo l'input   
n = int(input("Inserisci un intero"))

# calcolo la somma (advanced feature: list comprehension)
somma = sum( [ 2*i+1 for i in range(0,n)] )

# stampo
print("La somma dei numeri dispari da 1 a %d e' %d",(n,somma))

dove la funzione sum calcola ovviamente la somma di tutti i valori presenti nella lista di interi passata tra parentesi quadre, e l'espressione tra quadre è una "list comprehension" una delle caratteristiche più ad alto livello di Python, perche consente di generare insiemi di valori, esattamente come si fa in matematica, infatti in notazione matematica scriveremo:

Linguaggio C

Il primo programma:

#include <stdio.h>

int main(void)
{
    printf("Ciao Ragazzi\n");
    printf("Saluti dal C\n");
    return 0;
}

Osservazioni: la prima riga contiene una direttiva per il pre-compilatore, che si occupa di 'includere' le definizioni delle funzioni di libreria per l'I/O (input/output) tra cui quindi la printf (la scanf, ed altre).

Poi viene definita una funzione 'main', con dominio vuoto (void) e codominio un intero (il valore si vede subito è 0, sempre, e segnala il corretto svolgimento del programma, si restituisce un valore diverse se c'è stato un problema).

Le funzioni printf, servono per stampare una stringa formattata. Il codice Python è uno script, viene cioè eseguito tramite un interprete. Il codice C invece non è interpretato, ma va 'compilato'. Per compilare basta dare il comando dentro la console:

gcc -o nome sorgente.c
l'ordine del -o non è importante, quindi se il file sopra lo chiamiamo saluti.c, avremo:
gcc -Wall saluti.c -o saluti

vediamo il programma della somma:

#include <stdio.h>

int main(void)
{
    // questa riga e' un commento

    int n = 0;      // le variabili vanno tipate (int)
    int somma = 0;  // assegnate sempre un valore ad ogni variabile
    int i = 0;

    // ciclo while: come Python
    // la guardia del ciclo (predicato) va messo tra parentesi
    // i blocchi sono definiti tramite parentesi graffe
    // ogni istruzione viene terminata dal punto e virgola.

    while (i < n) {
        somma = somma + (2*i + 1);
        i = i + 1;
    }

    printf("La somma dei primi %d numeri dispari e' %d\n",n,somma);
    return 0;
}

Osservazione, lo stesso problema in matlab/octave:


n = input("Inserisci un intero:");
i = 0;
somma = 0;
while i < n
    somma = somma + (2*i + 1);
    i = i + 1;
end
fprintf('La somma dei primi %d numeri interi è %d\n',n,somma);

Lezione 4

  • Rappresentazione dell'Informazione, numeri negativi, rappresentazione con segno, in scostamento, modulo due.
    Numeri Floating-Point, virgola fissa, virgola mobile (IEEE-754).
    Caratteri: ASCII, UTF
    Segnali Audio, Immagini, Video (cenni a quantizzazione e campionamento).
  • Esercizi in Python, realizzazione dell'esercizio sulla successione di Collatz.
  • Liste in Python (senza formalizzazione), sintassi, uso. La funzione range(a,b).
  • Iterazione su contenitori: for x in range(a,b):

Esercizi:

  1. Scrivere una funzione Python che dato un intero p, restituisce True se p è primo.

Lezione 3

Rappresentazione degli interi in binario. Studiare il primo capitolo delle note.

Architettura della CPU, Ciclo di Caricamente-Decodifica-Esecuzione.
Componenti parte di controllo: PC, IR, SR (registro di stato), ruolo del PC
Componenti parte operativa: Registri, ALU.
Ciclo di clock.

Perche i computer sono sempre 'obsoleti' appena comprati? (detto in altri termini:
perche esce un nuovo telefonino ogni anno?)
Leggere: Legge di Moore


n = 10003
b = ''
while n>=1:
    d = n // 2
    r = r % 2
    b = str(r) + b
    print("%d\t%d\t%d\t%d",(n,d,r,b))
    n = d
print(b)