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)

Lezione II

Python:

  • Installazione ambiente su Windows:
    • Scaricare WinPython, una distribuzione 3.4. o 3.5 (non cambia molto), versione a 32/64 a seconda della vostra versione di Windows. Attenzione: seguite l'asterisco se installate la 3.5, e scaricate il pacchetto indicato in fondo alla pagina del sito, per windows 7 o 8, se ci sono problemi scaricatelo anche se avete windows 10. (Redistributable C++ Runtime).
      Eseguire l'installazione e specificare come posizione C:\WinPython (non installate sulla cartella Downloads. Subito dopo l'installazione, seguite le indicazioni del sito sopra, andate nella cartella C:\WinPython e eseguite il "WinPython Control Panel" ed eseguite la registrazione, a quel punto avete nel menu di Windows i link alle applicazioni.
      Quando eseguite Jupyter, la cartella di lavoro sarà: C:\WinPython\notebooks. Esplorate i vari elementi del menu. In particolare: Jupyter, Spyder.
    • Installate Notepad++ da qui.
    • Create una cartella C:\programmazione o come volete chiamarla voi. Scaricate "Console2". Potete cambiare la configurazione tramite i menu, per fare in modo che la console parta direttamente dentro la cartella di lavoro creata sopra. Nota: non potete eseguire python da console direttamente perche essa non troverà il comando, per farlo dovete prima eseguire c:\WinPython\script\env.bat, subito dopo potete eseguire ipython da console.
    • Se volete vedere cosa sia possibile fare con un linguaggio come Python, sopratutto in ambito scientifico, vi segnalo:
  • Installazione su Mac OS X (qualunque versione):
    1. Leggete prima questo. (Per fare la tilde ~ dovete premere Alt+5)
    2. Un editor che io uso regolarmente è TextMate.
    3. Installare HomeBrew. Potete comunque usare python da console, perche è già disponibile, ma attenzione è la versione 2.xx del linguaggio ed è in parte diversa dalla 3.xx (la print ad esempio non è una funzione e quindi non ha le parentesi attorno agli argomenti), vi consiglio di installare la 3, con "brew install python3", poi potete installare tramite "pip3 install ipython" e "pip3 install jupyter[all]" il resto, attenti a scrivere correttamente pip3 e non pip.
    4. Il compilatore C è già disponibile come vedremo. Guardatevi quando avete fatto, gli esempi dai link sopra.
  • Installazione su Linux: usate il gestore di pacchetti della vostra distribuzione.

Radice Quadrata:

# Questo è un commento
# Tutto quello che segue il cancelletto è un commento
# Radice Quadrata, Algoritmo dei Babilonesi (wikipedia)

# costanti

C = 3           # devo trovare radice quadrata di C
EPS = 0.000001  # precisione

# variabili

x = 1.5                 # stima iniziale 
e = x*x - C             # errore
if (e < 0): e = -e # modulo di |x^2 - c| i = 0 # contatore passi # iterazione: se l'errore è grande e non ho # eseguito almeno 10 passi allora continuo: while (e > EPS) and (i < 10):
     # metodo babilonese, media tra x e C/x
     x = (x + C/x) / 2.0
     # x è cambiato, aggiorno l'errore:
     e = x*x - C
     if (e < 0): e = -e # aumentiamo il numero di iterazioni i = i + 1 # se arrivo qui allora: # 1) il ciclo sopra è corretto, nel senso che non diverge # 2) la guardia del while è False, quindi vale # not (e > eps) and (i < 10) cioè
#    e <= eps or (i >= 10) 
# quindi: l'errore è minore di EPS, oppure ho fatto 
# già 10 iterazioni (da 0 a 9) e mi fermo

print("la radice quadrata di ", C, "è ", x)
print("Numero di iterazioni: ", i)

Esercizi:

  1. Modificate il codice sopra (in un altro file) e inserite la funzione input(), questa funzione del linguaggio ha come argomento una stringa che viene mostrata all'utente, tipicamente una domanda per spiegare cosa inserire, esempio: input("inserisci un intero: "), il risultato è una stringa. Per convertire la stringa in un intero, usare int(input(..)), mettete il risultato al posto della variabile C, e rieseguite il codice.
  2. Modificate il codice sopra, (in un altro file) e definite una funzione che calcola la radice, esempio di definizione di funzione:
    
    def f(x):
        return 2*x+1
    def cubo(c):
        return c*c*c
    # uso:
    print(f(4),cubo(3))
    
    
  3. Scrivere un programma Python che legge da input tre interi (a,b,c) e stampa il valore minimo e massimo.
  4. Scrivere un programma Python per l'algoritmo di Euclide, scrivete tre versioni: 1) definite prima due variabili m = 124422, n=23234 su cui volete calcolare mcd(m,n), e scrivete il codice che calcola il risultato nella variabile mcd. Alla fine stampate la variabile. 2) modificate il codice, e definite una funzione che prendere due parametri (m,n) e restituisce il massimo comune divisore, chiamate la funzione sui due valori precedenti e stampate il valore che ritorna. 3) modificate il programma precedente, prendendo, m,n in input usando input().
  5. Scrivete un programma che legge tre valori a,b,c (non interi) usate (float(input())) e calcola le soluzioni dell'equazione di secondo grado: . Usate la funzione del modulo math: math.sqrt() per il calcolo della radice.
  6. Advanced:  Leggete Collatz, scrivete la funzione che calcola Collatz, se è pari, se è dispari. Dato in intero ,   scrivere un ciclo che calcola i valori della funzione fino a quando essa non arriva a , stampando i valori per ogni iterazione. Mostrare la sequenza associata a , in quanti passi si arriva ad ?. Suggerimento: tra gli operatori del linguaggio c'è il 'a % b' che calcola il resto della divisione intera tra a e b.
  7. Advanced 2: Sempre con Collatz, usate il codice fatto sopra, per scrivere un ciclo che calcola la successione di Collatz per tutti gli interi . Non dovete stampare come fatto sopra l'intera successione, ma per ogni valore di dovete stampare il valore massimo presente nella sua successione di Collatz. Alla fine si avrà una tabella con i valori da con accanto il corrispondente massimo.

Hardware:

  • studiate le seguenti pagine di wikipedia,se fate fatica con l'inglese usate la versione italiana (fatta peggio):
    Algoritmi, Turing, Von Neumann, Radice Quadrata, Architettura di Von Neumann, Timeline, Memoria, RAM, CPU, Ciclo CPUALU, CPU CLock, Gigabyte, Data Size, Byte.Programmi.
  • Installate e Eseguite (su Windowz) il programma CPU-Z, cercate di capire il senso di ciò che mostra.
  • Importante: Guardare questo Video, (trascurate gli sproloqui finali sui fogli di calcolo). Leggete qui.
  • Ricapitolate con il fatto essenziale: la CPU è un interprete, quindi il suo programma è un ciclo in cui si legge un istruzione, si decodifica (si capisce cosa fare), se necessario si caricano i dati su cui l'istruzione deve agire (che devono essere in qualche modo specificati dall'istruzione stessa), si passa il tutto all'ALU e si esegue, infine si passa all'istruzione successiva. Semplice Pulito Efficiente.
  • Scaricate e iniziate a studiare le note sulla rappresentazione dell'informazione, disponibili sulla pagina del programma del corso.