DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Esercizi strutture e liste ======

===== Esercizio 1: L'insieme di Mandelbrot =====

L'[[http://it.wikipedia.org/wiki/Insieme_di_Mandelbrot|insieme di Mandelbrot]] e' un insieme frattale definito come l'insieme dei numeri complessi //c// per i quali la successione definita da:
<code>
z(0) = 0
z(n+1) = z(n)^2 + c
</code>
e' limitata, cioe' ''|z( n )|< 2'' per ogni ''n >=0''. 
Infatti al variare di ''c'', la sequenza puo' tendere
all’infinito o rimanere confinata in un disco di raggio 2 del piano complesso centrato
nell’origine.

L’algoritmo piu' semplice per visualizzare (una approssimazione de) l’insieme di Mandelbrot ´e l’//Escape Time Algorithm//. In questo algoritmo, dati ''A'' (l’area del piano complesso
da visualizzare) ed ''r'' (una precisione fissata) si effettuano i seguenti passi:
  - Si suddivide A in una griglia di punti a distanza uniforme (pixel) 
  - per ogni pixel (x, y) 
      - si calcolano r valori della sequenza con c=(x,y)
      - se dopo r iterazioni ''|z( r )|< = 2'' si considera c appartenente all'insieme e si assegna a c il colore NERO
  - altrimenti si assegna a c il colore j, che e' il minimo indice per cui ''| z(j) |>=2''


Utilizzare le strutture (struct) per rappresentare i numeri complessi come visto a lezione e
scrivere un programma C che calcola l'insieme di Mandelbrot per il rettangolo di estremi (-2,1) (1,-1) e stampando sullo standard output i colori dei pixel suppenendo di dividere il rettangolo di 300x200.
Per la stampa a colori in C consultare le [[fisica:informatica:201819:faq|FAQ]].




===== Esercizio 2: Sequenze di double  =====
Consideriamo il problema di leggere da standard input una sequenza di valori reali terminata da 0.0 creando la lista corrispondente di tipo
<code c>
typedef struct lista_d {
  double val;
  struct lista_d * next;
} lista_d_t ; 
</code>
  * sviluppare un programma C che legge un singolo elemento dallo standard input usando una funzione
<code c>
double leggi_nuovo_valore(void);
</code>
e utilizza le funzioni 
<code>
lista_d_t * inserisci_testa ( lista_d_t * l, double v);
lista_d_t * inserisci_coda ( lista_d_t * l, double v);
lista_d_t * inserisci_ord ( lista_d_t * l, double v);
</code>
per inserire nella lista. Ogni funzione prende come parametri (i) la lista l e (ii) il valore v da inserire (letto precedentemente con ''leggi_nuovo_valore(void)'', e restituisce la lista modificata (ovvero puntatore al primo elemento della lista, che potrebbe cambiato dopo l'inserzione).

La scelta della funzione per inserzione viene richiesta all'utente una volta per tutte prima di inserire i valori.
Inoltre, si utilizza una funzione ''stampa_lista()'' per stampare la lista inserita prima di terminare.



===== Esercizio 3: Altre funzioni su liste di double =====
Implementare le seguenti funzioni in modo iterativo e ricorsivo:
<code c>
/** calcola e restituisce il massimo della lista l */
double max ( lista_d_t * l);
/** calcola e restituisce la somma di tutti gli elementi della lista l*/
double somma ( lista_d_t * l);
/** libera la memoria occupata dalla lista */
void free_list( lista_d_t * l);
/** cancella, se presente, l'elemento che contiene la prima occorrenza 
del valore v dalla lista l (liberando la memoria) 
e restituisce la nuova lista */
lista_d_t * cancella_uno ( lista_d_t * l, double v);
/** cancella tutti gli elementi di valore
del valore v dalla lista l (liberando la memoria) 
e restituisce la nuova lista */
lista_d_t * cancella_tutti ( lista_d_t * l, double v);
</code>

e sviluppare un main() che ne testa il funzionamento.

===== Esercizio 4: Verifica di proprietà su liste (ricorsivamente)  =====
Definire una funzione ricorsiva che verifica che per ogni elemento di una lista valga la proprietà
\[
l(i + 1) = 2*l(i)
\]
dove $l(i)$ indica l'i-esimo elemento della lista a partire dalla testa. La funzione restituisce ''true'' se la proprietà è verificata e ''false'' altrimenti. I valori booleani sono definiti con una opportuna MACRO.

===== Esercizio 5: Liste con doppio puntatore  =====
Realizzare le funzioni dell'esercizio 1 utilizzando liste con puntatore al precedente e al successivo
<code>
typedef struct elem_d {
  double val;
  struct elem_d * prec;
  struct elem_d * next;
} elem_d_t ; 
</code>
in questo caso la lista complessiva puo' essere definita ad esempio come una struttura con due puntatori, uno alla testa ed uno alla coda 
<code>
typedef struct lista_d {
  struct elem_d * head;
  struct elem_d * tail;
} lista_d_t ;
</code>
come si modificano gli algoritmi sviluppati precedentemente ?

===== Esercizio 6: (avanzato) Array sparsi (//a la Python//) implementati come liste  =====
Vogliamo realizzare degli array di double di grandi dimensioni che contengono solo una piccola percentuale di elementi diversi da 0 come liste concatenate definite come
<code>
typedef struct sparse_d {
  double val;
  unsigned index;
  struct elem_d * next;
} sparse_d_t ; 
</code>
nella lista sono presenti solo gli elementi diversi da zero e per ogni elemento e' indicato l'indice a cui corrisponde. La Lista e' mantenuta ordinata rispetto al campo indice.
Realizzare le funzioni ''put'' e ''get'' che permettono di leggere il valore dell'elemento di un certo indice ''i'' (''get'') e di modificarne il valore (''put''), un possibile prototipo per queste funzioni e':
<code>
double get (sparse_d_T * a, unsigned indice);
sparse_d_t * put (sparse_d_T * a, double x, unsigned indice);
</code>


===== Esercizio 7: verificare gli accessi in memoria: valgrind =====

Verificare la correttezza degli accessi ai puntatori dello heap compiuti dalle funzioni su liste sviluppate negli esercizi precedenti utilizzando ''valgrind''. 
Questo strumento permette fra l'altro di capire se tutte le variabili sono inizializzate prima del loro uso, se accediamo a memoria gia' deallocata o mai allocata e situazioni similari


Per fare questo procedere come segue:  
  * compilare il file da verificare con opzione ''-g'' per includere le informazioni di debugging. Ad esempio se il mio file si chiama ''main.c'' posso compilare con
<code bash>
 gcc -Wall -pedantic -g -o prova main.c
</code>
  * eseguire
<code bash>
 valgrind ./prova
</code>
in questo modo, a schermo verranno riportare le infrazioni rilevate. Ad esempio, //invalid read// o //invalid write// sono accessi in lettura o scrittura a memoria non allocata o gia' deallocata.

''valgrind'' contiene moltissime opzioni, invitiamo gli studenti interessati ad esplorarle partendo dal[[http://valgrind.org/|sito]].