Aggregazione dei criteri
Esercizio 1 Scrivere un programma tabelline che invocato scrivendo
tabelline n1 n2 n2 ....
per ogni intero N sulla linea di comando crea il file N.tab contenente la tabellina (i multipli da 1 a 10) del numero N. Ad esempio scrivendo
tabelline 4 20
deve essere creato il file 4.tab contenente la sequenza
4
8
12
16
20
24
28
32
36
40
ed il file 20.tab contenente la sequenza
20
40
60
80
100
120
140
160
180
200
I file di output devono chiamarsi esattamente come indicato, e contenere esattamente i valori richiesti con un valore su ogni riga. Il programma deve accettare un qualsiasi numero di argomenti sulla linea di comando. Verificate con valgrind il corretto uso e deallocazione della memoria
Esercizio 2 Scrivere un programma triangolo che invocato scrivendo:
triangolo nomefile
legge da nomefile le stringhe contenute in esso e le salva in un array. Successivamente crea un file nomefile.triangolo contenente nella riga i-esima le parole dalla i-esima alla prima in ordine inverso. Ad esempio, se il file di input si chiama moria e contiene le parole dite amici ed entrate il file di output deve chiamarsi moria.triangolo e contentere le 4 righe:
dite
amici dite
ed amici dite
entrate ed amici dite
L'esercizio verrà considerato corretto solamente se la memoria verrà gestita in maniera dinamica e correttamente deallocata (verrà utilizzato valgrind per la verifica).
ATTENZIONE: i nome degli eseguibili (tabelline e triangolo) e i nomi dei file di output devono essere quelli indicati.
Testo Compito del 22/11
Aggregazione dei criteri
Si utilizzi la struttura
typedef struct terna {
int x,y,z;
struct terna *left, *right;
} terna;
per rappresentare il nodo di un albero binario di ricerca (ABR) contenente una terna di interi nei campi x, y, e z.
Importante: il vostro codice deve utilizzare le funzioni base per la manipolazione delle terne contenute in terne.c e terne.h. In particolare l'ABR deve usare come funzione di ordinamento terna_confronta che confronta gli elementi delle terne nell'ordine z, y, x. Quindi la terna 10 3 1 precede la terna 1 2 3 in quanto la componente z della prima terna è più piccola. Se le componenti z sono uguali si confronta la componente y (quindi 20 2 13 è minore di 2 3 13) e se anche le componenti y sono uguali si confronta la componente x (quindi 2 10 20 è minore di 3 10 20).
Non importa in quale modo organizzate i file sorgenti e il makefile ma è obbligatorio che usiate le funzioni definite in terne.c e non altre, e che la compilazione venga fatta con le opzioni std=c11 -Wall -O -g.
L'albero binario di ricerca per le terne deve supportare le funzioni di inserimento ricerca e visita in in-order più eventuali altre funzioni necessarie per lo svolgimento dell'esercizio. Dovete seguire la convenzione fatta a lezione che nell'abero non vengono mai inseriti elementi duplicati (cioè terne uguali).
Il makefile deve essere scritto in modo che scrivendo
makefile pitagora
venga generato l'eseguibile pitagora che svolge le seguenti operazioni. Scrivendo sulla linea di comando
pitagora nomefile s1 s2... sk
dove s1 s2... sk sono dei valori interi, il programma deve leggere le terne contenute in nomefile e memorizzarle nell'ABR. Successivamente deve: * stampare su stdout il numero di nodi dell'albero ottenuto * per i=1..k stampare su stdout il numero di terne nell'albero la cui somma è uguale all'intero si
Questi valori devono essere stampati uno per riga senza frasi esplicative; ad esempio se si esegue comando pitagora small 10 12 14 16 su stdout deve essere scritto
7
0
2
1
0
in quanto il file small contiene 7 terne distinte, di cui nessuna ha somma 10, due terne hanno somma 12, una terna ha somma 14 e nessuna ha somma 16.
Successivamente, il programma deve scrivere nel file nomefile.pit l'elenco delle terne dell'ABR che sono terne pitagoriche, cioè per cui vale
Importante: per calcolare il quadrato di una variabile x scrivete x*x, NON x**2 o x^2 (la seconda espressione compila ma calcola un'operazione bitwise che non c'entra con il quadrato).
Le terne devono essere stampate in ordine crescente: in pratica dovete fare una visita dell'albero in in-order e scrivere su file solo le terne pitagoriche. Anche in questo caso scrivete una terna per riga (usando la funzione terna_stampa in terne.c) senza commenti. Ad esempio, quando viene passato come argomento il file small il corrispondete file small.pit dovrebbe contenere solamente le due righe
3 4 5
12 5 13
che sono le terne pitagoriche contenute in small (si noti l'ordine: 3 4 5 precede 12 5 13 in quanto 5<13).
Il programma deve scrivere su stdout solamente i valori indicati sopra: ogni altra informazione e i messaggi di debug devono essere scritti su stderr. Prima di terminare il programma deve chiudere tutti i file e deallocare tutta la memoria utilizzata (usare valgrind, per la verifica).
Lettura delle terne. Le terne sono memorizzate in file di testo in un formato particolare:
ogni linea del file può memorizzare una singola terna
i valori delle terne sono espressi con sequenze del carattere - separate da un numero arbitrario di caratteri : o ; e tali caratteri possono apparire anche prima o dopo le sequenze di -. Ad esempio le linee :-:--:--:, -:;;:--;--:;, -;--;::-- sono tre modi possibili per esprimere la terna 1 2 2
se una linea contiene dei caratteri diversi da -, :, ;, e naturalmente \n, tale linea va ignorata
l'ultima regola è che se una linea contiene un numero di sequenze di - diverso da 3 (ad esempio :-;-- o -;-;-;-) tale linea va ignorata.
Tenuto conto di queste regole, consiglio di leggere le terne con la seguente procedura
usare getline per leggere una linea alla volta
eseguire una scansione della linea e se si trovano caratteri diversi da -:;\n passare alla linea successiva
utilizzare la funzione strtok per tokenizare la linea in modo che ogni token consista in una sequenza del solo carattere - e utilizzare strlen per ottenere il valore rappresentato da quella sequenza (si noti che i valori nelle terne saranno tutti positivi). Se effettuando la tokenizzazione risulta che ci sono meno un numero di sequenze diverso da 3, passare alla linea successiva.
Utilizzare i file small, t5, e t20 per testare il vostro codice. L'output che deve essere inviato su stdout si trova nei file con estensione .out e le terne pitagoriche da scrivere nei file .pit si trovano nei file .ris. Questi test vengono fatti automaticamente dando il comando python3 terne_test.py.
Testo compito del 20/2/25
Aggregazione dei criteri
Scrivere uno script python linee.py (deve chiamarsi così) che prende in input sulla linea di comando il nome di una directory dir, un intero positivo num, e una stringa pattern.
Lo script deve visitare tutti i file presenti nella directory dir e sue sottodirectory mettendoli in una lista di nome tutti utilizzando la metodologia vista a lezione. Per ogni file lo script deve memorizzare almeno il nome del file e le prime num linee di testo del file, dove num è il parametro intero positivo passato sulla linea di comando. Attenzione che il file potrebbe avere meno di num linee di testo, in tal caso memorizzate quelle che ci sono; il file potrebbe anche essere vuoto, in tal caso non deve essere memorizzata nessuna linea.
Successivamente, lo script deve creare una nuova lista di nome pochi contenente solamente i file tali che una delle righe memorizzate contiene la stringa pattern. Si noti che per verificare se una stringa è contenuta in un altra, si può usare la keyword in, ad esempio:
>>> "remo" in "saremo felici"
True
>>> "ramo" in "saremo felici"
False
Infine lo script deve stampare i file della lista pochi ordinati con il seguente criterio:
lessicograficamente rispetto alla linea contenente la stringa pattern; se ci sono più linee che contengono pattern si consideri quella che si trova prima nel file
a parità di linea contente la stringa pattern si consideri l'ordine lessicografico dei nomi
La stampa di ogni file deve consistere in almeno:
il nome del file
le massimo num linee memorizzate insieme al file
Obbligatorio:
chiamare lo script linee.py
memorizzare il nome del file e le linee di testo in una classe definita ad hoc
effettuare l'ordinamento della lista pochi definendo in maniera opportuna il metodo __lt__ dentro tale classe
effettuare la stampa dei file definendo in maniera opportuna il metodo __str__ dentro tale classe.
Esempio 1
Si supponga di avere il file pippo contenente le 2 linee
dolce a colazione
casa dolce casa
e il file zippo contente le 4 linee
xxx
yyy
dolce a colazione
andiamo a casa
Se si esegue
linee.py . 4 casa
l'ouput deve essere del tipo
### File: ./zippo
xxx
yyy
dolce a colazione
andiamo a casa
### File: ./pippo
dolce a colazione
casa dolce casa
infatti la parola casa è contenuta in zippo nella linea andiamo a casa che è lessicograficamente minore della linea casa dolce casa del file pippo. Se si esegue
linee.py . 2 casa
l'ouput deve essere del tipo
### File: ./pippo
dolce a colazione
casa dolce casa
in quanto le prime due linee di zippo non contengono casa e di conseguenza zippo non sarà nella lista pochi.
Se si esegue
linee.py . 3 dolce
l'ouput deve essere del tipo
### File: ./pippo
dolce a colazione
casa dolce casa
### File:./ zippo
xxx
yyy
dolce a colazione
in questo caso la linea che contiene dolce è la stessa nei due file (conta la prima occorrenza) quindi l'ordine dipende dall'ordinamento del nome del file (quindi se il primo file invece di pippo si chiamasse zitto allora andrebbe per secondo)
Esempio 2
Estraendo l'archivio esempio.zip si ottiene una cartella (con sottocartelle) di nome esempio. Invocando lo script su questa cartella dovreste ottenere i seguenti risultati (attenzione all'ordinamento dei file):
linee.py esempio 3 GNU
'pochi' contiene 1 file
### File: esempio/xerrori.h
#define _GNU_SOURCE // permette di usare estensioni GNU
#include <stdio.h> // permette di usare scanf printf etc ...
#include <stdlib.h> // conversioni stringa exit() etc ...
linee.py esempio 3 gcc
'pochi' contiene 2 file
### File: esempio/dir0_d1/dir1_d0/makefile
# definizione del compilatore e dei flag di compilazione
CC=gcc
CFLAGS=-std=c11 -Wall -O -g
### File: esempio/makefile
# definizione del compilatore e dei flag di compilazione
# che vengono usate dalle regole implicite
CC=gcc
linee.py esempio 1 del
'pochi' contiene 16 file
### File: esempio/dir0_d1/dir1_d0/makefile
# definizione del compilatore e dei flag di compilazione
### File: esempio/makefile
# definizione del compilatore e dei flag di compilazione
### File: esempio/dir0_d1/dir0_d0/file0.txt
Riga 0 del file file0.txt
### File: esempio/dir0_d1/file0.txt
Riga 0 del file file0.txt
### File: esempio/dir1_d1/dir0_d0/file0.txt
Riga 0 del file file0.txt
### File: esempio/dir1_d1/dir1_d0/file0.txt
Riga 0 del file file0.txt
### File: esempio/dir1_d1/file0.txt
Riga 0 del file file0.txt
### File: esempio/file0.txt
Riga 0 del file file0.txt
### File: esempio/dir0_d1/dir0_d0/file1.txt
Riga 0 del file file1.txt
### File: esempio/dir0_d1/dir1_d0/file1.txt
Riga 0 del file file1.txt
### File: esempio/dir1_d1/dir0_d0/file1.txt
Riga 0 del file file1.txt
### File: esempio/dir1_d1/dir1_d0/file1.txt
Riga 0 del file file1.txt
### File: esempio/dir1_d1/file1.txt
Riga 0 del file file1.txt
### File: esempio/file1.txt
Riga 0 del file file1.txt
### File: esempio/dir0_d1/file1.txt
aaa Riga 0 del file file1.txt
### File: esempio/dir0_d1/dir1_d0/file0.txt
bbb Riga 0 del file file0.txt
Testo compito del 10/4/25
Aggregazione dei criteri
Sequenze di Collatz
La trasformazione di Collatz dato un intero positivo n restituisce il valore n/2 se n è pari oppure 3*n+1 se n è dispari. E' stato osservato sperimentalmente che applicando ripetutamente questa trasformazione partendo da un qualsiasi intero positivo si finisce per ottenere sempre il valore 1. Ad esempio partendo da 13 raggiungiamo il valore 1 in 9 passi:
13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Scrivere un sorgente colla.c che generi l'eseguibile colla.out che invocato dalla linea di comando scrivendo:
colla.out nomefile soglia numt
legga gli interi positivi presenti nel file di testo nomefile e per ognuno di questi interi n generi un file di testo di nome n.txt contenente la sequenza di Collatz ottenuta partendo dal valore n e arrivando al valore 1. Se ad esempio si fornisce in input il file piccoli contenente i valori
5
3
16
devono essere creati rispettivamente i file: 5.txt contenente
5
16
8
4
2
1
il file 3.txt contenente
3
10
5
16
8
4
2
1
e il file 16.txt contenente
16
8
4
2
1
(questi file devono chiamarsi esattamente così e contenere esattamente un valore per ogni riga). Importante: usare il tipo long per gli elementi delle sequenze di Collatz in quanto anche partendo da valori iniziali piccoli si possono ottenere valori molto grandi.
La costruzione di questi file deve essere effettuata con il seguente procedimento: il thread principale deve creare numt (passato in argv[3]) thread secondari con i quali comunicherà con la tecnica produttore/consumatori utilizzando un buffer di dimensione 5. Il thread principale svolge il ruolo di unico produttore, mentre i thread secondari quello di consumatori.
Successivamente, il thread principale deve leggere gli interi positivi da nomefile (passato in argv[1]) e li deve mettere sul buffer (ricordate di leggerli come long con %ld). Ogni intero rappresenta una unità di lavoro per i consumatori.
Ogni thread consumatore deve ripetutamente:
leggere dal buffer un intero n
creare il relativo file n.txt con la corrispondente sequenza di Collatz come visto sopra.
Si può assumere che gli interi di nomefile siano tutti distinti e di conseguenza i file creati dai consumatori abbiano tutti nomi diversi.
In parallelo alla creazione dei file ogni thread consumatore deve contare quanti valori scritti nei file sono maggiori di soglia (passato in argv[2]) e al termine della computazione il thread principale deve sommare i parziali e scrivere su stdout il numero totale complessivo di valori maggiori di soglia. Su stdout non deve essere scritto altro, utilizzare eventualmente stderr per i messaggi di debug.
Esempi
Riprendendo l'esempio di prima, se il file piccoli contiene i valori 5, 3 e 16 scrivendo:
colla.out piccoli 8 2
devono essere usati 2 thread consumatori, devono essere creati i file 5.txt, 3.txt e 16.txt visti sopra e il programma deve terminare scrivendo su stdout:
Numero di valori maggiori di 8: 4
in quanto nei file sono scritti 4 valori maggiori di 8: 16, 16, 10, 16 (come vedete si contano anche le ripetizioni).
Scrivendo
colla.out piccoli 0 4
devono essere usati 4 thread consumatori e il programma deve terminare scrivendo su stdout:
Numero di valori maggiori di 0: 19
Scrivendo
colla.out numeri 100 3
devono essere usati 3 thread consumatori, devono essere generati 10 file .txt e il programma deve terminare scrivendo su stdout:
Numero di valori maggiori di 100: 647
Scrivendo
colla.out grandi 0 2
devono essere usati 2 thread consumatori, devono essere generati i file 999999.txt e 837799.txt e il programma deve terminare scrivendo su stdout:
Numero di valori maggiori di 0: 784
Ultima richiesta
Il programma deve creare un thread gestore di segnali che gestisca l'eventuale arrivo del segnale SIGINT utilizzando sigwait(3) (quindi non utilizzando un handler). All'arrivo di SIGINT il thread principale deve comportarsi come se il file di input non contenesse altri interi oltre a quelli già letti, deve far terminare normalmente i thread consumatori, stampare il messaggio che riporta il numero di valori maggiori di soglia (ovviamente contando solo quelli effettivamente scritti) e terminare lui stesso in maniera normale.
Ad esempio se viene eseguito il comando
colla.out piccoli 8 2
ma viene ricevuto SIGINT prima che il thread principale abbia letto il valore 16 dal file piccoli, devono essere creati solamente i file 3.txt e 5.txt e deve essere stampato su stdout:
Numero di valori maggiori di 8: 3
Per testare il funzionamento della gestione del segnale potete scrivere sulla linea di comando:
colla.out numeri & (sleep 0.5; pkill -INT colla.out)
dove al posto di 0.5 potete mettere un tempo di attesa (in secondi) a vostra scelta. Questo comando esegue colla.out in background e contemporaneamente esegue i comandi tra parentesi: quindi attende 0.5 secondi e poi invia il segnale SIGINT a colla.out.
Extra
Non è ammesso l'utilizzo di variabili globali.
Consegnare i file colla.c, makefile e altri file .c e .h che permettano di creare l'eseguibile colla.out semplicemente dando il comando make dalla linea di comando. Non consegnare altri file (eseguibili o di test).
Avete a disposizione i file piccoli numeri e grandi menzionati nel testo e una serie di file con estensione .sol contenente l'output che ci si aspetta nei file .txt. Per fare un confronto fra un .sol e un .txt scrivete ad esempio diff -b 16.txt 16.sol: se non viene generato output da diff il vostro file .txt è corretto.
Per ulteriori test potete usare il tool pycolla.py che prende in input un intero i e una soglia s , calcola la sequenza che parte da i e restituisce il numero di valori nella sequenza e il numero di tali valori sopra la soglia s.
Domande orale:
Chiede a tutti qualcosa sulla realizzazione del progetto, anche se è fatto bene chiede magari di spiegare meglio una parte, poi fa 4 domande estratte a caso
Domande Laboratorio2 Manzini
-differenza tra semafori con nome e senza nome
-il prof ha fatto vedere una struct e ha chiesto di scrivere (su un foglio) una funzione per cancellare tutti gli elementi di una lista di quella struct con un determinato valore
-parlare della funzione fork (senza avere il prototipo)
-thread in python
-broadcast e signal a confronto
-come leggere le linee da un file di testo in C
-funzione wait
-ha fatto vedere una pagina del man e chiesto di commentarla (mi pare di sigwaitinfo)
-barrier_init
-file oggetto e loro ruolo nella compilazione
-mkfifo (1) e (3)
-ha chiesto di scrivere una classe in python per salvare i dati di un file di testo che ha fatto vedere
-parlare di sem_post dato il prototipo
-tipo void *
-parlare della memoria condivisa
-metodo hash in python
-barrier_wait dato il prototipo
-strdup e strcpy a confronto
-pipe con e senza nome
-pagina del man di sigthread e sigmask
-thread_cond_wait dato il prototipo
-pagina man di unlink
-processi zombie
-come si realizza il thread gestore dei segnali
-thread_mutex_lock
-pagina man di scanf con una sezione particolare
-shm_open
-pagina man di pipe
-concetto di mt safe
-metodo eq in Python
-cosa sono le umask
-data una struct:
Codice: Seleziona tutto
typedef struct{
int x
int y
}coppia;-dato un file del tipo:
1 12 56 28 11 23 ….
…
dove: il primo valore è il nodo, il secondo il numero di archi uscenti e i successivi valori sono gli archi a cui si collega. Dire come rappresentare in Java un grafo di questo tipo è come scrivere una funzione per il calcolo del cammino minimo