Assegnamenti per l' Esame

di Programmazione II

(anno 2002/2003)

Un elenco ancora parziale di esercizi:

1) Grafici di Funzione.

    Il programma deve permettere di fare il grafico di una o piu' serie di dati.
Le serie di dati saranno lette da un file di testo.
Il programma dovra' automaticamente calcolare delle scale, disegnare gli assi, mettere delle etichette  sulle suddivisioni etc.

2) Analisi di espressioni aritmetiche.

     Una espressione  come (3+2)*7/(4-5) deve essere letta come una stringa dall' input e si deve costruire un albero binario che la rappresenta. Una volta ottenuto l'albero si dovra' calcolare il valore dell'espressione.

3) Simulazione del moto

    Si dovra' simulare il moto di una pallina sparata da un cannoncino con una certa velocita' iniziale.
La pallina rimbalzera' sul pavimento con un certo coefficiente di anelasticita'.
Si dovranno leggere dall' input i parametri e rappresentare graficamente la simulazione.

4) Analisi di testi.

    Si devono poter leggere dei testi da uno o piu' file  e calcolare la frequenza delle parole che vi compaiono.
    Interpretando le parole come assi in uno spazio a n dimensioni (n=numero di parole diverse) si potra' anche calcolare la distanza fra due testi (distanza Euclidea) da usare come grado di somiglianza fra i testi stessi.

5) Simulazione discreta.

    Si simuli una agenzia bancaria. Ci sono n sportelli. Casualmente (con una certa probabilita') entrano i clienti. Ogni cliente si mette in coda (in quella piu corta). Il primo cliente di ciascuna coda viene servito dall' impiegato e impiega un tempo (anche questo calcolato casualmente in un certo intervallo) a compiere l' operazione.
Il tempo procede per "tic" discreti.
La simulazione deve far vedere (potendo cambiare i vari parametri: numero di sportelli, probabilita di ingresso dei clienti, distribuzione dei tempi impiegati per le singole operazioni) come si evolvono le code.

6) Tokenizer.

Il tokenizer e' una componente dei compilatori che analizza il testo del programma con il comp[ito di classificarlo il:
Esempio:
ingresso (leggendo un file che contergga un programma c c++)
if (alfa>8.75)
{ x=x1+x2;}
else .....
uscita (su terminale o su di un file)
parola_chiave(if) identificatore(alfa) operatore(>) costante (8.75) altro({) identificatore(x)  operatore(=) identificatore(x1) operatore(+) identificatore(x2) altro(;) altro(}) parola_chiave(else) ...

7) Biblioteca

Creare una struttura dati opportina per rappresentare il catalogo di una biblioteca.
Ogni libro dovra` essere rappresentato da autore, casa editrice, anno di edizione, collocazione, un insieme di parole chiave.
Scrivere un programma che permetta di inserire dei dasti di prova (ad esempio leggendoli da un file di testo) e che permetta di fare delle ricerche secondo vari criteri

8) Conversione da notazione infissa a notazione postfissa

La notazione comune per le espressioni aritmetiche e' quella infissa
            (6+2)*5-8/4
La notazione postfissa e' piu' facile da calcolare (usata spesso dai compilatori) e' piu' facile da calcolare.
L' operatore e' scritto dopo gli operandi (non servono parentesi ne conoscere la precedenza ed associativita` degli operatori )
L' espressione precedente puo` essere scritta come:
   3 4 + 5 * 8 4 / -
e puo` essere facilmente calcolata per mezzo di uno stack usando l'algoritmo che segue.
Algoritmo.
Supporre che infix sia un vettore di caratteri che contiene l'espressione infissa e chwe p[ostfix sia un vettore di caratteri che contiene l' espressione postfissa di uscita. Stack e' uno stack di caratteri.
  1. Ponete nello stack una parentesi aperta '(' .
  2. Accodate alla fine di infix una parentesi chiusa '('.
  3. Finche' lo stack non e' vuoto leggete infix da sinistra a destra ed eseguite le seguenti operazioni:
    1. Nel caso in cui il carattere corrente di infix sia un numero  copiatelo nel prossimo elemento di postfix.
    2. Nel caso in cui il carattere corrente di infix sia una parentesi aperta  deponetela nello stack.
    3. Nel caso in cui il carattere corrente di infix sia un operatore :
      1. estrarre gli operatori (se ce ne sono) dal;la sommita' dello stack, finche' hanno una priorita` maggiore o uguale di quella corrente e inserirli in postfix.
      2. ponete sullo stack il carattere corrente di infix .
    4. Nel caso che il carattere corrente di infix sia una parentesi chiusa
      1. Estrarre gli operatori dalla sommita` dello stack e inseriteli in postfix, fin quando non ci sia una parentesi aperta sulla sommita` dello stack.
      2. Estrarre dallo stack ed eliminare la parentesi aperta.
Le operazioni consentite sono + - * /  % ^ (addizione, sottrazione, moltiplicazione, divisione, modulo, elevamento a potenza).
I numeri sono formati da una sola cifra.

9) Calcolo di espressioni postfisse

Una espressione postfissa puo' facilmente essere calcolata usando uno stack.
  1. Finche ci sono numeri od operatori in ingresso: 
    1. nel caso in cui ci sia un numero deporre il suo valore sullo stack.
    2. nel caso sia un operatore estrarre due numeri dallo stack e calcolare il risultato dell' operazione. Mettere il risultato nello stack. (fare attenzione all' ordine degli operandi).
  2. Quando l' input e' finito lo stack deve contenere un singolo dato che e' il risultato del calcolo dell' espressione.
Utilizzare delle classi con template per poter analizzare sia espressioni intere che float che double.
Le operazioni consentite sono + - * /  % ^ (addizione, sottrazione, moltiplicazione, divisione, modulo, elevamento a potenza). I numeri sono ovviamente costituiti da piu' cifre. L' espressione e' terminata da un END OF FILE. (CTRL Z).

10) Memorie associative

In una memoria associativa si memorizzano delle coppie chiave/valore. I dati vengono recuperati in base alla chiave (che puo` essere unica o duplicata). Esempi di strutture dati di questo genere sono le map e le  multimap delle Standard Template Library.
Senza usare le STL ma utilizzando degli alberi binari, realizzare una memoria associativa con le seguenti funzionalita`:
  1. Inserimento di una coppia chiave/valore (se la chiave esiste gia' segnalarte un errore)
  2. Ricerca per chiave 
  3. Esame sequenziale della memoria (da realizzare mediante un iteratore).
I tipi della chiave e del valore sono generici (template). Le chiavi devono essere confrontabili con gli operatori <  e = .

Istruzioni.

Ogni studente dovra' scegliere un esercizio e comunicarmi quale per e-mail: bianchi@CE.UniPR.IT
A lezione, venendo nel mio studio o per e-mail potra' chiedermi ulteriori spiegazioni o suggerimenti.
Per l' esame dovra' presentare e discutere l' esercizio fatto.
Al programma dovra essere allegata una relazione che illustri quali classi si sono usate (dando una motivazione), che spieghi la struttura generale del programma,  le sue modalita` d' uso ed i risultati ottenuti.  Il codice andra opportunamente commentato.