logo sapienza

Fondamenti di Informatica, anno accademico 2008-2009
(Statistica Gestionale, 9 crediti)
Docente: Paolo Franciosa


Obiettivi Programma Materiale didattico
Orario delle lezioni Ricevimento studenti Modalità d'esame
Diario delle lezioni Prove d'esame

Per commenti e segnalazioni contatta il docente a


Obiettivi e contenuti del corso

Vengono illustrati i principi fondamentali della programmazione strutturata, con particolare riferimento alla programmazione orientata agli oggetti, utilizzando il linguaggio Java.

Vengono presentati alcuni algoritmi fondamentali per problemi di ordinamento, ricerca e selezione, alcuni problemi numerici, evidenziandone le caratteristiche di efficienza attraverso l'analisi di complessità asintotica.

Vengono descritti i principali metodi di codifica dell'informazione.

Alla fine del corso lo studente sarà in grado di:

torna all'inizio


Programma

Componenti di un sistema di elaborazione: hardware, software, principali unità periferiche. Interazione con un sistema operativo basato su finestre. Concetto di cartella, documento, applicazione. Il sistema operativo: funzioni principali, gestione dei processi, gestione della memoria, file system.

Rappresentazione dell'informazione: codifica di informazioni numeriche - sistemi di numerazione posizionali, codifica binaria, ottale, esadecimale, conversioni di base. Rappresentazione di numeri interi negativi. Rappresentazione in virgola mobile. Codifica di caratteri.

Concetto di algoritmo. Esempi di algoritmi in linguaggio naturale. Generalità sui linguaggi di programmazione, compilatori.

Programmazione in linguaggio Java: la Java Virtual Machine, ambienti di programmazione, compilazione ed esecuzione di programmi Java. Costrutti essenziali del linguaggio: variabili, espressioni, oggetti. Assegnazioni, metodi di input/output, istruzioni di selezione, ed iterazione. Uso di classi predefinite, invocazione di metodi. Consultazione della documentazione standard Java. Definizione di classi, principio della riutilizzazione del codice. Implementazione di vettori e matrici. Ereditarietà e polimorfismo.

Algoritmi fondamentali: Ricerca sequenziale, ricerca dicotomica su un vettore ordinato. Algoritmi di base su matrici. Ordinamento: selection sort, merge sort, quick sort, bubble sort. Algoritmo di Euclide per la ricerca del Massimo Comun Divisore (MCD).

Introduzione alla complessità computazionale: concetto di complessità di un algoritmo, notazioni asintotiche. Equazioni di ricorrenza e metodi per la loro soluzione. Complessità computazionale degli algoritmi studiati.

torna all'inizio


Materiale didattico

Testi consigliati

Testo di riferimento per il linguaggio Java:
Marco Bertacca, Andrea Guidi
Programmare in Java
McGraw-Hill, 2007.
Escludere 11.1, 11.4, 11.5, 11.7
13, 14, 15 (in programma solo classi e metodi utilizzati nelle esercitazioni per l'accesso a files di testo), 16, 17, 18, 19
Per approfondimenti:
Cay S. Horstmann.
Concetti di informatica e fondamenti di Java,
Edito da APOGEO, Terza Edizione, 2005.
Materale aggiuntivo è disponibile in http://www.apogeonline.com/libri, seguendo i link "Booksite" e poi "Area Studenti"", nell'area studenti.
Per gli argomenti di algoritmi e complessità, poche pagine dal testo seguente:
Cormen, Leiserson, Rivest: Introduzione agli algoritmi, volume 1, Jackson libri
Materiale di riferimento per la codifica dell'informazione:
Ceri, Mandrioli, Sbattella: Informatica arte e mestiere, McGraw-Hill.
Cap. 11, pagg. 243-255,
o in alternativa
Ceri, Mandrioli, Sbattella: Informatica istituzioni, McGraw-Hill.
Cap. 2 fino a 2.2.2 compreso e ad 2.3 alla fine del capitolo, pagg. 29-43

Strumenti di programmazione

Gli studenti che hanno difficoltà nel reperire il software possono rivolgersi al docente.

Altri link rilevanti

torna all'inizio


Modalità d'esame

L'esame consiste in una prova scritta e un colloquio. Nella prova scritta si richiede di scrivere o completare sorgenti Java e di rispondere a domande su argomenti teorici.

torna all'inizio


Diario delle lezioni

25 febbraio 2009
2 marzo 2009 3 marzo 2009 (lab) 4 marzo 2009: annullata
9 marzo 2009 10 marzo 2009 (lab) 11 marzo 2009
16 marzo 2009 17 marzo 2009 (lab) 18 marzo 2009
23 marzo 2009 24 marzo 2009 (lab) 25 marzo 2009
30 marzo 2009 31 marzo 2009 (lab) 1 aprile 2009
6 aprile 2009 7 aprile 2009 (lab) 8 aprile 2009
vacanze pasquali vacanze pasquali 15 aprile 2009
20 aprile 2009 21 aprile 2009 (lab) 22 aprile 2009
27 aprile 2009 28 aprile 2009 (lab) 29 aprile 2009
4 maggio 2009: annullata 5 maggio 2009 (lab) 6 maggio 2009
11 maggio 2009 12 maggio 2009 (lab) 13 maggio 2009
18 maggio 2009 19 maggio 2009 (lab) 20 maggio 2009
25 maggio 2009 26 maggio 2009 (lab) 27 maggio 2009: annullata causa commissione di laurea

Per commenti e segnalazioni, contatta il docente (paolo.franciosa@uniroma1.it)

torna all'inizio


25 febbraio 2009
Argomenti

Introduzione al corso

Concetto di algoritmo

Esempi di algoritmi:

  • risolvere una equazione di secondo grado;
  • verificare se tre numeri reali sono le misure dei lati di un triangolo rettangolo;
  • decidere se un numero naturale è primo o composto.

Riferimenti al testo Capitolo 1

torna all'elenco delle lezioni


2 marzo 2009
Argomenti

Architettura di un sistema di elaborazione

Origini del linguaggio Java

Compilazione e interpretazione di un programma in Java: codice sorgente, codice intermedio (bytecode); il ciclo di compilazione/esecuzione di programmi in Java; la Java Virtual Machine

Esempi di programmi Java

Tipi primitivi: aritmetici, carattere, boolean

Dichiarazione di variabili

Istruzione di assegnazione

Riferimenti al testo Capitolo 3

torna all'elenco delle lezioni


3 marzo 2009 (laboratorio)
Argomenti

Descrizione dei pacchetti JRE (Java Runtime Environment) e SDK (Software Development Kit)

Editing di programmi Java con Blocco Note

Compilazione ed esecuzione da "Prompt dei comandi" usando gli strumenti javac e java del SDK

Listati ed esercizi proposti Esercitazione 1

torna all'elenco delle lezioni

9 marzo 2009
Argomenti

Tipi primitivi: aritmetici, carattere, boolean

Dichiarazione di variabili

Uso di literal (costanti)

Operatori aritmetici

Costruzione di espressioni complesse

Precedenza tra operatori

Conversioni implicite ed esplicite, operatore cast

Assegnazioni tra tipi disomogenei

Riferimenti al testo Capitolo 3
Listati ed esercizi proposti

torna all'elenco delle lezioni


10 marzo 2009 (laboratorio)
Argomenti

Operatori relazionali:    >   >=   <    <=   ==   !=

Uso della istruzione if() ... else ...

Istruzioni if nidificate

Input/output attraverso metodi della classe JOptionPane

Esercizi proposti Esercitazione 2

torna all'elenco delle lezioni


11 marzo 2009
Argomenti

Istruzione composta { ... } e ambito di visibilità delle variabili

Espressioni booleane complesse: operatori && || !

Operatori di preincremento e postincremento ++, predecremento e postdecremento --

Istruzioni di ciclo: l'istruzione while

Uso di variabili boolean per il controllo di cicli

Istruzione break;

Istruzioni di assegnazione con modifica += -= *= /= %=

Riferimenti al testo Capitoli 4 e 5
Listati ed esercizi proposti
  • Ordina tre numeri: Ordina3.java
  • Verifica se tre interi sono i lati di un triangolo e individua il tipo di triangolo: Triangolo.java
  • Decidere se tre reali sono i lati di un triangolo rettangolo, acutangolo od ottusangolo
  • Dato capitale iniziale e interesse annuo, calcolare il capitale dopo un anno e dopo 3 anni
  • Date le coordinate di due punti trovare la loro distanza euclidea (usare il metodo Math.sqrt() per il calcolo della radice quadrata)
  • Calcola il numero di anni necessari per raggiungere un dato importo a partire da un capitale iniziale e un tasso di interesse annuo dati CapitaleObiettivo.java
  • Incremento di capitale con capitalizzazione degli interessi Capitale.java
  • Verifica se un naturale è primo
    • versione semplice Primalita.java
    • versione migliorata PrimalitaEfficiente.java
    • altri miglioramenti proposti:
      • terminare il ciclo appena trovato un divisore
      • evitare la divisione per numeri pari maggiori di 2
      • scrivere un programma che combina tutti i miglioramenti elencati
  • Stampa il numero di divisori di un naturale (si possono utilizzare alcune delle idee a proposito del test di primalità)

torna all'elenco delle l


16 marzo 2009
Argomenti

Esempi di semplici programmi con cicli e istruzioni di selezione

Riferimenti al testo Capitoli 4 e 5
Listati ed esercizi proposti

Vedi lezione precedente

torna all'elenco delle lezioni


17 marzo 2009 (laboratorio)
Argomenti Metodi di input/output della classe JOptionPane
Uso del ciclo while
Ricerca di massimo e minimo di un insieme
Riferimenti al testo Capitoli 4 e 5
Listati ed esercizi proposti Esercitazione 3

torna all'elenco delle lezioni


18 marzo 2009
Argomenti

Soluzione dell'esercizio proposto nella esercitazione precedente: stampa di un triangolo di asterischi di lato n con vari orientamenti StampaTriangolo.java

Istruzione di ciclo for, analogie con istruzione while

Istruzione di ciclo do ... while, differenze rispetto all'istruzione while

Esempi di programmi con cicli: verificare se un naturale è un numero perfetto

Sviluppo di algoritmi: approccio top-down

Algoritmo di bisezione per la soluzione di una equazione in una variabile, e sua implementazione BisezioneSemplice.java

Riferimenti al testo Capitolo 5
Listati ed esercizi proposti
  • Stampa della tavola pitagorica n per n TavolaPitagorica.java, assicurando che che l'input (n) sia compreso nell'intervallo [1,18]
  • Stampa di un albero di natale di altezza n (fornito in input) AlberoDiNatale.java. Ad esempio, per n=6 bisogna visualizzare il seguente disegno:
          *
         ***
        *****
       *******
      *********
     ***********
          *
          *
    

torna all'elenco delle lezioni


23 marzo 2009
Argomenti

Introduzione agli array monodimensionali: dichiarazione, allocazione ed uso

Inizializzazione di array

La proprietà .length di array

Input e output di array

Riferimenti al testo Capitolo 6
Listati ed esercizi proposti

  • Leggi da tastiera una sequenza di double, memorizzala in un array, stampa la somma degli elementi SommaArray.java
  • Leggi da tastiera una sequenza di double, memorizzala in un array, crea un array che contiene una copia degli elementi del primo array CopiaArray.java
  • Leggi da tastiera una sequenza di double, memorizzala in un array, crea un array che contiene una copia degli elementi del primo array, ma in ordine inverso CopiaOrdineInverso.java
  • Leggi da tastiera una sequenza di int che rappresenta delle frequenze, memorizzala in un array, crea un array che contiene le frequenze cumulate e stampa, in due colonne, la sequenza delle frequenze (sulla sinistra) e la sequenza delle frequenze cumulate (sulla destra) Cumula.java

Data in input una sequenza di interi, che rappresentano frequenze, stampare:

  • la frequenza massima e la frequenza minima;
  • calcolare l'array delle frequenze relative e stamparlo;
  • calcolare l'array delle frequenze relative cumulate e stamparlo;
  • stampare in quale posizione si trovano la frequenza massima e la frequenza minima.

torna all'elenco delle lezioni


24 marzo 2009 (laboratorio)
Argomenti Semplici esercizi su arrays
Listati ed esercizi proposti Esercitazione 4

torna all'elenco delle lezioni


25 marzo 2009
Argomenti

Variabili riferimento: il caso degli arrays

Assegnazione tra arrays

Arrays multidimensionali

Esempi di algoritmi su arrays

Riferimenti al testo Capitolo 6
Listati ed esercizi proposti
  • Ricerca sequenziale in un array disordinato RicercaValore.java
  • Ricerca sequenziale di più valori in un array disordinato RicercaRipetutaValore.java
  • Leggi da tastiera una sequenza di interi (la lunghezza è data anch'essa da tastiera), memorizzala in un array, verifica se la sequenza è in ordine non decrescente VerificaOrdine.java
  • Modificare il programma precedente per verificare se la sequenza è crescente, non decrescente, non crescente o decrescente
  • Leggi da tastiera una sequenza di interi (la lunghezza è data anch'essa da tastiera), memorizzala in un array, inverti l'array, stampa l'array ottenuto. Il problema deve essere risolto SENZA USARE ALTRI ARRAYS
  • Dato un array bidimensionale di int (preferibilmente inizializzato nel codice):
    • stamparlo in forma di tabella
    • stampare la somma di tutti gli elementi
    • costruire un array nel quale memorizzare la somma di ciascuna riga
    • trovare qual è la riga di somma massima (risolvere questo problema sia usando il risultato del punto precedente, sia senza utilizzare alcun altro array)
  • Dato un array bidimensionale che rappresenta una matrice quadrata, trovare il massimo elemento della diagonale
  • Dato un array di double, che rappresenta i valori di una funzione di due variabili calcolati sui punti di una griglia bidimensionale, individuare i punti in cui la funzione presenta un massimo locale (definiamo un punto di massimo locale come un punto interno alla griglia nel quale la funzione assume un valore strettamente maggiore di tutti gli otto punti adiacenti ad esso). I punti sul bordo della griglia non possono essere punti di massimo locale

torna all'elenco delle lezioni


30 marzo 2009
Argomenti

I metodi

Definizione e chiamata di metodi static

La signature di un metodo

I metodi void

Parametri formali e parametri attuali

Passaggio di parametri per valore

Passaggio di parametri array

Riferimenti al testo Capitolo 7
Listati ed esercizi proposti
  • Esempio di metodi con o senza parametri o valore di ritorno Metodi.java
  • Stampa i primi compresi tra 1 e un intero N fornito in input, utilizzando un metodo che verifica la primalità di un intero restituendo un boolean
  • Scrivere un metodo che trova la radice cubica di un intero (la soluzione sarà un intero che approssima la soluzione esatta)
  • Scrivere un metodo che trova la radice cubica di un double x, utilizzando un metodi di ricerca binaria. L'intervallo iniziale di ricerca sarà da 0 a x, il metodo si ferma appena viene raggiunta una approssimazione fissata a priori

torna all'elenco delle lezioni


31 marzo 2009
Argomenti

Esercitazione su metodi su arrays

Listati ed esercizi proposti

Esercitazione 5

Ecco un esempio di soluzione (da leggere solo dopo aver tentato a lungo di risolvere l'esercizio) Esercitazione 5 svolta

torna all'elenco delle lezioni


1 aprile 2009
Argomenti

L'algoritmo di ordinamento per selezione (selection sort)

Cenni alla complessità computazionale del selection sort

Calcolo del fattoriale

Riferimenti al testo Capitolo 7
Listati ed esercizi proposti
  • SelectionSort.java
  • Calcolo del fattoriale di un intero non negativo Fattoriale.java
  • Utilizzando i metodi definiti dei listati precedenti:
    • complessità del selection sort: stampare una tabella nella quale vengono mostrato il tempo impiegato per ordinare array random di double di dimensione crescente (199, 1000, 10000, 100000). I tempi possono essere calcolati attraverso la differenza tra i valori restituiti dal metodo System.currentTimeMillis(), immediatamente prima e immediatamente dopo l'ordinamento. È utile definire un metodo che alloca e restituisce un array random, la cui dimensione viene passata come parametro, e modificare il metodo ordinaConSelectionSort in modo che invece di essere void restituisca il numero di millisecondi impiegati
    • Come al punto precedente, ordinando però con il metodo Arrays.sort() (importare java.util.Arrays).
    • verificare qual è il massimo intero di cui è possibile calcolare il fattoriale in una variabile di tipo long

torna all'elenco delle lezioni


6 aprile 2009
Argomenti

Misure di complessità: la notazione asintotica O()

Esempi di classi di funzioni

Uso delle notazioni asintotiche per esprimere limitazioni superiori della complessità di algoritmi

L'algoritmo di ricerca binaria su array ordinati

Analisi della complessità dell'algoritmo di ricerca binaria

Riferimenti al testo Cormen, Leiserson, Rivest, pagg. 21-26
Listati ed esercizi proposti
  • Ricerca binaria in array ordinato RicercaBinaria.java
  • Scrivere un programma che:
    • genera un array di dimensione letta da tastiera
    • lo inizializza con interi random tra 0 e 1000000
    • lo ordina (usando un qualsiasi metodo di ordinamento)
    • chiede ripetutamente un intero da cercare nell'array e stampa ogni volta il numero di iterazioni eseguite dall'algoritmo di ricerca binaria per trovare l'elemento o per verificarne l'assenza
  • Valutare la complessità asintotica dell'algoritmo di ricerca binaria nel caso in cui l'intervallo di ricerca non fosse diviso ogni volta a metà, ma in due porzioni di lunghezza rispettivamente un terzo e due terzi della lunghezza dell'intervallo di ricerca precedente. Riferirsi al caso più sfavorevole.

torna all'elenco delle lezioni


7 aprile 2009 (lab)
Argomenti

Esercitazione su:

  • packages
  • parametri del main
  • Javadoc
  • calcolo del numero di elementi distinti in un array

Listati ed esercizi proposti Esercitazione 6

torna all'elenco delle lezioni


8 aprile 2009 (lab)
Argomenti

Esercizi di programmazione

torna all'elenco delle lezioni


15 aprile 2009
Argomenti

Introduzione alla programmazione a oggetti

Principio dell'information hiding

Da variabile-tipo a oggetto-classe

Variabili membro e metodi membro

Privatezza delle variabili membro

Definizione della classe Contatore

  • descrizione dei requisiti
    • creazione dell'oggetto
    • incremento
    • restituzione del valore
  • signature dei metodi membro
  • variabili membro
  • costruttori
  • implementazione dei metodi membro

Definizione della classe Osservazioni

  • descrizione dei requisiti
    • creazione dell'oggetto
    • aggiunta di un valore osservato
    • restituzione del numero di valori osservati
    • restituzione della media dei valori osservati

Riferimenti al testo Capitoli 8 e seguenti
Listati proposti
Esercizi proposti

torna all'elenco delle lezioni


20 aprile 2009
Argomenti

Esempio di definizione ed uso di una classe

Sovraccarico del costruttore: uso del this()

L'oggetto di invocazione: Uso del this nella disambiguazione dei riferimenti

Definizione ed invocazione di metodi static e metodi membro

Alcune classi predefinite: Arrays, StringTokenizer, Scanner, Random

Riferimenti al testo Capitoli 8 e seguenti
Listati proposti Soluzione dell'esercizio proposto il 15 aprile

torna all'elenco delle lezioni


21 aprile 2009 (laboratorio)
Argomenti Accesso a file di testo
Listati ed esercizi proposti

Esercitazione 7: accesso a file di testo. Nella stessa pagina è disponibile una soluzione alla esercitazione

torna all'elenco delle lezioni


22 aprile 2009
Argomenti

Eccezioni: eccezioni controllate e non controllate

Gestione delle eccezioni (costrutto try ... catch ... finally) e propagazione delle eccezioni (costrutto throws ...)

Posizionamento della gestione delle eccezioni

Introduzione alla ricorsione.

Esempio di algoritmo ricorsivo per il calcolo del fattoriale.

L'algoritmo di Euclide per il calcolo del Massimo Comun Divisore MassimoComunDivisore.java

Analisi di complessità dell'algoritmo MCD di Euclide.

Riferimenti al testo

Capitolo 12 e seguenti

Cormen, Leiserson, Rivest

torna all'elenco delle lezioni


27 aprile 2009
Argomenti

L'algoritmo di ordinamento per fusione (Merge Sort) MergeSort.java

Analisi di complessità del Merge Sort.

torna all'elenco delle lezioni


28 aprile 2009 (laboratorio)
Argomenti Filtraggio righe da file di testo
Listati ed esercizi proposti

Esercitazione 8

torna all'elenco delle lezioni


29 aprile 2009
Argomenti

Il paradigma divide et impera.

Analisi della complessità computazionale di algoritmi ricorsivi.

Soluzione di equazioni di ricorrenza attraverso il teorema principale (senza dimostrazione)

Esempi di applicazione del teorema principale:ricerca binaria, merge sort, algoritmo di Euclide per il MCD

L'algoritmo Quick sort (è disponibile una versione che mostra il funzionamento per ciascuna chiamata ricorsiva: QuickSort.java)

Riferimenti al testo Cormen, Leiserson, Rivest (pagine indicate)

torna all'elenco delle lezioni


5 maggio 2009 (laboratorio)
Argomenti Merge di file di testo: metodi della classe String e StringBuffer
Listati ed esercizi proposti

Esercitazione 9

Una soluzione è disponibile in MergeFiles.java o in MergeFiles1.java

torna all'elenco delle lezioni


6 maggio 2009
Argomenti

Algoritmo per il calcolo del k-esimo elemento: Selection.java

Algoritmo di ordinamento a bolle (Bubble sort) e suoi miglioramenti

torna all'elenco delle lezioni


11 maggio 2009
Argomenti

Codifica dell'informazione:

  • Generalità sulla notazione posizionale per numeri naturali, interpretazione di numeri espressi in base b
  • conversione da base b a base 10 e da base 10 a base b
  • rappresentazione di numeri interi in modulo e segno
  • rappresentazione di numeri interi in complemento a due

Riferimenti al testo appunti delle lezioni e testo di Ceri, Mandrioli, Sbattella

torna all'elenco delle lezioni


12 maggio 2009 (laboratorio)
Argomenti Scrittura di metodi su array bidimensionali, rappresentati in files di testo.
Listati ed esercizi proposti

Esercitazione 10

torna all'elenco delle lezioni


13 maggio 2009
Argomenti

Codifica dell'informazione:

  • Codifica ottale ed esadecimale, conversione da e verso la base 2
  • codifica di caratteri: ASCII, ASCII esteso, Unicode, codifica delle interruzioni di linea

Riferimenti al testo appunti delle lezioni e testo di Ceri, Mandrioli, Sbattella
Listati ed esercizi proposti

CodificaPosizionale.java

torna all'elenco delle lezioni


18 maggio 2009
Argomenti

Programmazione a oggetti:

  • Variabili membro e metodi membro
  • Costruttori
  • Sovraccaricamento di metodi

Riferimenti al testo

torna all'elenco delle lezioni


19 maggio 2009 (lab)
Argomenti

Completamento della classe UrnaInteri della lezione precedente

torna all'elenco delle lezioni


20 maggio 2009
Argomenti

Definizione di sottoclassi, ... extends ....
Chiamata del costruttore della superclasse super(...) e chiamata di metodi della superclasse super.nomeMetodo(...)

Ereditarietà di campi e metodi. Specializzazione di metodi per la sottoclasse attraverso la loro riscrittura (overriding).
La classe Object.

Il metodo toString() e sua ridefinizione (overriding). I metodi clone() e equals(Object)

Riferimenti al testo

torna all'elenco delle lezioni


25 maggio 2009
Argomenti

Classi astratte e totalmente astratte (interface). Implementazione di interface. Le interface Comparable e Serializable

Riferimenti al testo

torna all'elenco delle lezioni


Prove d'esame

Scritto del 4 Giugno 2009 Scritto2009-06-04.pdf

Scritto del 25 Giugno 2009 Scritto2009-06-25.pdf

Scritto dell'8 Settembre 2009 Scritto2009-09-08.pdf

torna all'inizio