Fondamenti di Informatica
A.A. 2006-2007
Corsi di Laurea in Ingegneria Elettrotecnica ed Energetica
Docente: Laura Gilda Paccagnella
Dipartimento di Matematica Pura ed Applicata
Tel. 049-8271417
Email: laurap@math.unipd.it
Programma del corso
Argomenti di Informatica
Definizione di algoritmo; analisi e codifica; problemi primitivi e problemi terminali. Il metodo top-down; generalità della scomposizione. Il linguaggio di progetto: variabili e strutture di controllo.
Strutture dati. Astrazione sui dati e tipo di dato astratto. Astrazione sulle funzioni.
Ricerca lineare e dicotomica; ricerca hash.
Ordinamenti: lineare, bubble sort (e sue varianti), per inserimento; merge di dati ordinati.
La complessità degli algoritmi: definizione e calcolo per gli algoritmi svolti; ottimizzazioni.
La ricorsione: definizione ed esempi; il quicksort.
I record. I file sequenziali; operazioni sui file: unione, intersezione, differenza, gestione di archivi.
Allocazione statica e dinamica; puntatori e liste. Costruzione delle liste di tipo LIFO e FIFO; operazioni sulle liste: ricerca, inserimento, cancellazione di elementi.
Definizione di albero, alberi di decisione, limiti inferiori alla complessità; "divide et impera", alberi perfettamente bilanciati, bilanciati e di ricerca; il mergesort.
Confronto tra le varie strutture di dati (vettori, file, liste).
I sistemi di numerazione. I cambiamenti di base. Rappresentazione interna degli interi: complemento a due, con eccesso. Rappresentazione interna dei reali; errori di arrotondamento e troncamento; perdita di precisione nei calcoli.
La struttura del calcolatore: memoria centrale e memorie secondarie, CPU, dispositivi di I/O; modello di esecuzione.
Risorse software: il sistema operativo Linux; compilazione, link, esecuzione.
Facoltativo: La sintassi nei linguaggi di programmazione, backtracking e non determinismo.
Il linguaggio C++
La sintassi del linguaggio: alfabeto, definizioni di variabili e costanti; la struttura del file C++. I tipi standard, il tipo array, il tipo puntatore, il tipo record (struct). Regole per costruire espressioni. Azioni di ingresso/uscita, i file standard cin e cout; aggancio con i file fisici e file diversi da cin e cout. Le strutture di controllo: if, switch, while, for, do. Le funzioni; il passaggio dei parametri per valore e per riferimento. Applicazioni alla ricorsione. Puntatori e applicazioni alle liste concatenate. Liste lineari semplici: ricerca, inserimento, cancellazione di elementi in una lista; inserimento in ordine; fusione di liste. Esempi di alberi.
Orario delle lezioni
Le lezioni si tengono presso il plesso Paolotti.
Lu3:
Aula Taliercio (laboratorio didattico):
Sono a disposizione altre ore di laboratorio individuale facoltativo, presso il laboratorio didattico Aula Taliercio:
Orario di ricevimento
Giovedì 10.30 - 11.30 stanza n.702 Torre Archimede Via Trieste, 63 (settimo piano scale C D)
Venerdì Aula Taliercio durante il laboratorio facoltativo.
Libri di testo
Il testo adottato nel corso è : L.G.Paccagnella:
Fondamenti di Informatica , Ed. Libreria Progetto, Padova, 2002,
nel quale si trovano gli argomenti di teoria, una breve introduzione al
linguaggio C++, domande ed esercizi dati agli esami, esempi di programmi
in C++.
Testi di consultazione sono i seguenti:
A. Aho, I. Ullmann , Fondamenti di Informatica, Zanichelli, 1994.
D.M. Capper Introduzione al C++ per le scienze e l'ingegneria , McGraw-Hill, 1997
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e struttura dei dati, McGraw-Hill, 2005
D.P. Curtin, K, Foley, K. Sen, C. Morin, Informatica di base (con CD-ROM), Mc Graw-Hill, 2001.
C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e strutture dati, McGraw-Hill, 2004
M.R. Laganà, M. Righi, F. Romani, Informatica. Concetti e sperimentazioni, Apogeo, 2003
S.B. Lippman, C++ Corso di programmazione, Addison-Wesley 1993
F.Luccio, La struttura degli algoritmi, Boringhieri , Torino 1988
SSC Publisher, Le applicazioni di Linux. Guida all'uso, Mondadori, 2003
P. Tosoratti, Introduzione all’informatica, Ambrosiana, Milano, 1998
N.Wirth, Algoritmi + Strutture Dati = Programmi, Tecniche Nuove, Milano, 1987
Altro materiale didattico si può trovare presso il sito dell’Aula Taliercio www.adt.unipd.it. In particolare una simulazione del test a risposte multiple e altro materiale didattico che si utilizzerà durante le lezioni in laboratorio.
Obiettivi dell’insegnamento
Essendo questo l’unico corso di informatica nel corso di laurea triennale in ingegneria elettrotecnica ed energetica, si vogliono fornire allo studente i principi della programmazione in modo da acquisire autonomia nella progettazione degli algoritmi. L’acquisizione di tale capacità di programmare sarà importante per alcuni esami successivi. Allo stesso tempo si vuole dare allo studente una panoramica di teoria e tecniche proprie dell’informatica.
Modalità d’esame
L'esame è costituito da due prove: prova scritta e prova orale. Per accedere alla prova orale si deve aver superato la prova scritta.
Per accedere all’esame bisogna iscriversi nelle apposite liste di scritto ed orale presso il sistema informativo degli studenti.
La prova scritta è costituita da due parti: questionario e prova pratica.
Nel questionario lo studente dovrà rispondere a domande teoriche; nella seconda parte dovrà scrivere dei programmi in C++
funzionanti.
Tali prove si svolgeranno nel laboratorio didattico Aula Taliercio. Durante
la prova
scritta non si può uscire. Durante la prova scritta non
si può consultare alcun tipo di materiale.
Durante il corso verranno fatti due compitini che sostituiscono la prova scritta. Chi supera il primo compitino può presentarsi al secondo. Chi consegna il secondo compitino non può presentarsi allo scritto del primo appello. Chi si ritira dal secondo compitino (anche al termine della prova pratica) può presentarsi allo scritto del primo appello.
La prova orale consiste nella presentazione ed esposizione di programmi svolti durante il corso a scelta dello studente all'interno di un insieme di esercizi assegnati, che ricoprano i vari argomenti trattati.
Ciascun programma scritto in C++ dovrà essere
accompagnato dal file risultati, che dovrà contenere la stampa
dei dati e
più casi di prova.
Coloro che non superano la prova scritta non sono ammessi alla prova orale. Coloro che hanno un voto con * dovranno venire a prendere visione del compito prima di sostenere la prova orale che sarà subordinata alla risoluzione di esercizi attribuiti all’atto della visione del compito.
Chi ha superato una prova scritta può ripeterla in un appello successivo, ma mantiene il voto precedente solo se si ritira prima della scadenza del questionario.
Una volta superata la prova scritta, la prova orale potrà essere sostenuta in uno (ed uno solo ) degli appelli orali fissati entro e non oltre il 21/9/2007.
Chi non supera la prova scritta può ripeterla in qualsiasi altro appello.
Chi non supera la prova orale deve ripetere la prova scritta (in qualsiasi altro appello).