Corso Programmazione 2009-2010
(docente)
Fabio Aiolli
E-mail: aiolli@math.unipd.it
Web: www.math.unipd.it/~aiolli
(docenti laboratorio)
A. Burattin, E. Caniato, A. Ceccato
Dipartimento di Matematica Pura ed Applicata
Torre Archimede, Via Trieste 63
Corso Programmazione 2009-2010
(docente)
Fabio Aiolli
E-mail: aiolli@math.unipd.it
Web: www.math.unipd.it/~aiolli
(docenti laboratorio)
A. Burattin, E. Caniato, A. Ceccato
Dipartimento di Matematica Pura ed Applicata
Torre Archimede, Via Trieste 63
Fabio Aiolli PROGRAMMAZIONE
Introduzione al corso e Fondamenti * Orario delle lezioni e esercitazioni ~36 ore di lezioni in aula P200
Martedi’
Ore 11:30 - 13:15
Venerdi’
Ore 10:30 – 12:15
~32 ore di esercitazioni in laboratorio
Proposte.. Martedi’, Mercoledi’, ore 14:00 – 17:00
Aula Informatica C dell’ ex Dipartimento di Matematica Pura ed Applicata (Paolotti)
Prima esercitazione in laboratorio il 20/04/09
Fabio Aiolli * Kelley, I. Pohl. "C Didattica e programmazione", IV edizione, Pearson, 2004. Risorse per il corso Altri libri consigliati, slide ed esercizi saranno disponibili sul sito web del corso:
http://www.math.unipd.it/~aiolli/corsi/0910/prgxmat/prg.html Il GOOGLE GROUP del corso:
http://groups.google.it/group/prxmat10atunipd PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Fabio Aiolli * Il GOOGLE GROUP del corso:
http://groups.google.it/group/prxmat10atunipd ISTRUZIONI x GLI STUDENTI
Nickname: (per esempio, FabioA)
Inserire indirizzo di posta elettronica PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Fabio Aiolli * Prima Parte
Domande riguardanti la sintassi del linguaggio C e semplici programmi
Seconda Parte
Analisi e implementazione di algoritmi in C
Colloquio (per esame da 8 crediti)
Contenuti di Introduzione alla Programmazione
Esame Scritto PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Fabio Aiolli * Panoramica sul C
Strutture dati ed algoritmi
Programmi x il calcolo scientifico
Contenuti del corso PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Fabio Aiolli * Imparare a programmare NON e’ facile e NON si impara sui libri ma necessita di MOLTA pratica (e curiosita’)
RENDETEMI IL COMPITO + FACILE
Qualsiasi tipo di interazione con lo studente e’ ben accetta da parte mia
Richiedete spesso chiarimenti e partecipate attivamente alle lezioni e ai laboratori
Molto Importante PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Fabio Aiolli * Iniziamo.. PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Fabio Aiolli * PARTE 1
Definizioni Fondamentali PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Algoritmo
DEFINIZIONE
Insieme completo delle regole che permettono la soluzione di un determinato problema
DEFINIZIONE OPERATIVA
Procedura effettiva che indica le istruzioni (passi) da eseguire per ottenere i risultati voluti a partire dai dati di cui si dispone Fabio Aiolli * PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Algoritmo: Esempi
Esempio Culinario:
Ricetta x cucinare gli spaghetti
Esempi sui numeri:
Insieme di passi per verificare se un numero è dispari, pari, primo, ecc.
Altri esempi: MCD(a,b), mcm(a,b)
Per esempio l’algoritmo di Euclide per il calcolo del MCD (che può essere usato anche per il calcolo del mcm!) Fabio Aiolli * PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Algoritmo: Caratteristiche
Esprimibile con un numero finito di istruzioni
Istruzioni eseguibili da un elaboratore
Insieme di istruzioni di cardinalità finita
Tempo di esecuzione di ogni istruzione finito
Elaboratore ha una memoria
Calcolo per passi discreti
Non esiste limite alla lunghezza dei dati di ingresso
Non c’e’ un limite alla memoria disponibile
Numero di passi esecuzione eventualmente illimitato
Fabio Aiolli * PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Linguaggi
LINGUAGGI NON FORMALI (ambigui)
Linguaggio Naturale
Linguaggio della musica
Linguaggio del corpo
Ecc.
LINGUAGGI FORMALI (di programmazione)
Linguaggi NON ambigui, regolati da regole grammaticali precise
Possono essere classificati in base al loro livello di astrazione
Fabio Aiolli * PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Linguaggi di Alto Livello (LAL)
ESEMPI FAMOSI
Imperativi: PASCAL, FORTRAN,COBOL, C
Ad oggetti: CPP, JAVA
Appositi software (compilatori) si occupano di tradurre le istruzioni scritte in questi linguaggi (cosiddetto codice sorgente, un file di testo), nell’equivalente codice eseguibile dalla macchina (cosiddetto codice eseguibile, binario) Fabio Aiolli * PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Caratteristiche LAL strutturati
SEQUENZA
Le istruzioni vengono eseguite in sequenza nell’ordine in cui compaiono in un blocco di istruzioni
SELEZIONE
Strutture di controllo decisionali:
P.e. Se esegui
altrimenti esegui
ITERAZIONE
Strutture di controllo iterative:
P.e. Fintanto che esegui
Oppure, Esegui fintanto che Fabio Aiolli * PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Complessita’ degli Algoritmi
Complessita’ Polinomial (P) : Il numero di passi e’ proporzionale in modo polinomiale alla cardinalita’ dell’input
Complessita’ Non-Deterministic Polinomial (NP) : Sono noti algoritmi che terminano in un numero di passi polinomiale usando un numero indeterminato di macchine in parallelo, oppure utilizzando l’algoritmo di Gastone Fabio Aiolli * PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Algoritmi di Ricerca
Ricerca MIN e MAX
Ricerca di un valore in una collezione
Ricerca di un valore in una collezione ordinata
Ricerca degli zeri di una funzione Fabio Aiolli * PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Algoritmi di Ordinamento
Ordinamento degli elementi in una generica collezione
Fondere due collezioni ognuna di esse gia’ ordinata
Ordinare senza usare confronti Fabio Aiolli * PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Algoritmi di Ottimizzazione
Problema del Commesso Viaggiatore (TSP)
Problema dei Cammini Minimi (SP) Fabio Aiolli * PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Fabio Aiolli * PARTE 2
Il processo di programmazione PROGRAMMAZIONE
Introduzione al corso e Fondamenti
Comments