CdSMATEMATICA
Codice017AA
CFU9
PeriodoPrimo semestre
LinguaItaliano
Lo studente che termina con successo il corso sarà in grado di dimostrare di conoscere i concetti basilari e i fondamenti dei linguaggi di programmazione. A questo scopo viene introdotto C come esempio di linguaggio di programmazione. Al termine del corso gli studenti devono essere in grado di tradurre un metodo astratto di risoluzione di un problema in un programma funzionante e di programmare in C ad un livello intermedio, elaborando algoritmi semplici.
Gli studenti devono inoltre dimostrare di aver acquisito una buona conoscenza di alcuni concetti relativi alla teoria dei linguaggi formali e alla teoria degli automi a stati finiti.
The student who successfully completes the course will be able to demonstrate knowledge of the basic concepts of language programming, by using C as example of programming languages; the student will have the ability to program in C language at an intermediate level, by elaborating simple algorithms.
Furthermore, the student will be able to demonstrate a good knowledge of the basic theory of automata and of formal languages.
La prova scritta serve a valutare l'apprendimento delle nozioni teoriche sulla parte di linguaggi e le capacità di risoluzione algoritmica e di programmazione in C.
La prova pratica di programmazione ha l'obiettivo di accertare le capacità di programmazione di algoritmi in C, con particolare riferimento alla gestione di sequenze, array, liste ed alberi.
Con la prova orale, facoltativa, si verificheranno le conoscenze sui principali contenuti del corso, e la loro assimilazione, l'uso della terminologia appropriata e infine la capacità di affrontare problemi sia di tipo teorico che pratico legati ai contenuti del corso.
The written exam is used to evaluate whether the student have learnt the theoretical notions on languages and automata; and the skills in solving algorithmic exercises and in programming their solutions.
The practical test assesses the skills in solving problems in an algorithmic way and in programming in C, in particular in managing sequences, arrays, lists and trees.
In the optional oral exam the student must be able to discuss the main course contents using the appropriate terminology and to demostrate her/his attitude to program and to solve exercises.
Al termine del corso lo studente sarà in grado di:
- risovere algoritmicamente un problema e di programmarne la soluzione in C, tenendo conto anche dell'efficienza delle soluzioni proposte
- programmare in C a livello intemedio
- affrontare piccoli problemi ed esercizi sia di tipo teorico che pratico legati ai contenuti del corso
At the end of the course the student will be able to
- algorithmically solve a problem and program the solution in C
- program at C at intermediate level
- to deal with small problems and exercises both theoretical and practical that are related to the content of the course
- Durante le prove scritte verranno richiesti esercizi per valutare l'apprendimento delle nozioni teoriche sulla parte di linguaggi e automi e di "problem solving" in C.
- Durante le prove pratiche di programmazione verranno richiesti esercizi per verificare la capacità di programmazione in C, con particolare riferimento alla gestione di sequenze array, liste ed alberi.
- Durante l'eventuale prova orale agli studenti verrà richiesto di saper presentare i principali contenuti del corso e di risolvere piccolo esercizi per dimostrare di saper utilizzare i principi appresi.
- During the written tests, exercises will be required to evaluate the theoretical knowledge of the part of languages and automata and of "problem solving" in C.
- During practical lab tests, exercises will be performed to verify the programming capacity.
- During the optional oral tests students will be required to present the main contents of the course and to solve small exercises to demonstrate their assimilation of the principles learned.
Lo studente potrà acquisire e/o sviluppare la capacità di pensare in modo algoritmico alla soluzione dei problemi.
The student will acquire and/or develop the ability to think in an algorithmic way to the solution of problems.
Durante le prove pratiche di laboratorio sarà anche valutata la modalità algoritmica di soluzione.
During the labtests, the algorithmic solution mode will also be evaluated.
Non sono richieste particolari conoscenze iniziali. Una conoscenza elementare della logica è certamente utile, così come una sufficiente familiarità con le tecniche di dimostrazione.
No particular initial knowledge is required. An elementary knowledge of logic is certainly useful, as well as a sufficient familiarity with the proof techniques.
La frequenza è fortemente consigliata.
- Le lezioni frontali si svolgono con uso di slide e della lavagna.
- Le esercitazioni si svolgono in aula: gli studenti svolgono degli esercizi, anche in gruppo, sotto la supervisione del docente.
- Le esercitazioni pratiche di programmazione si svolgono in aula/laboratorio con i computer dell'aula e/o con quelli degli studenti, sfruttando un'apposita piattaforma di autovalutazione degli esercizi, che fornisce una verifica automatica della correttezza dei programmi caricati, con l'ausilio dei docenti e del personale di supporto in laboratorio
- L'interazione con il docente avviene con colloqui (in orario di ricevimento o su appuntamento) e tramite posta elettronica.
- Il materiale didattico, gli esercizi e alcuni esempi di testi di esame sono accessibile sulla pagina web del corso.
- Il corso prevede una prova pratica intermedia il cui superamento esonera lo studente dalla prova pratica di esame.
Metodi di insegnamento:
- Lezioni
- Esercitazioni
- Laboratori
Attendance: strongly advised
- Frontal lessons are performed using slides and the blackboard.
- Exercises take place in the classroom: students practice exercises, even in groups, under the supervision of the lecturer.
- Lab lessons take place in the laboratiry: students practice exercises, under the supervision of the lecturer, by using an self-valutation platform
- Interaction with the teacher is done through interviews (on fixed office hours or by appointment) and by e-mail.
- On the web page of the course, the slides, the exercise and the course material presented in each lesson are published progressively on the course web page.
- The course provides a single intermediate test, the passing of which exempts the student from the student from the test of the exam.
Teaching methods:
- Lectures
- Laboratories
I parte Linguaggio C, come esempio di linguaggio di programmazione.
- Introduzione all'informatica con brevi cenni all'hardware e alla rappresentazione binaria.
- Introduzione ai principi della programmazione, attraverso la presentazione dei costrutti linguistici di base e attraverso qualche cenno alla semantica operazionale di un semplice linguaggio imperativo.
- Primi elementi del linguaggio: variabili ed espressioni aritmetiche.
- L'istruzione if e gli operatori logici.
- Variabili di tipo char, int, long int, float, double
- Istruzione switch-case.
- Istruzioni for, break, continue.
- Istruzioni while e do-while.
- Array e matrici.
- Stringhe.
- Defi nizione di nuove funzioni.
- Passaggio dei parametri e prototipi. Il tipo void.
- Funzioni ricorsive e loro uso.
- Algoritmi di ordinamento.
- Considerazioni sulle prestazioni degli algoritmi e cenne alla loro complessità.
- Puntatori e allocazione dinamica della memoria.
- Tipi fondamentali e tipi strutturati.
- Liste concatenate.
- Alberi binari e alberi binari di ricerca con strutture concatenate.
II parte Cenni di teoria degli automi e dei linguaggi.
- Classi cazione delle grammatiche e dei linguaggi formali.
- Automi a stati finiti.
- Linguaggio riconosciuto da un automa a stati fi niti
- Automi deterministici e non deterministici e loro equivalenza.
- Pumping Lemma per i linguaggi regolari.
- Proprieta dei linguaggi regolari rispetto alle operazioni di unione,
intersezione, complemento, prodotto e chiusura. - Grammatiche libere dal contesto e linguaggi liberi.
- Pumping Lemma per i linguaggi liberi
[Part I] C language, as an example of programming language.
- Introduction to the principles of programming.
- First elements: variables and arithmetic expressions and logical operators.
- Instructions if, switch-case, break, continue, while and for.
- Arrays and matrices.
- Strings.
- Definition of functions (also recursive), parameters and function prototypes.
- Sorting algorithms.
- Brief introduction to algorithmic complexity.
- Pointers and dynamic memory allocation.
- Basic types and structured types.
- Linked lists.
- Binary trees and Research binary trees with linked structures
[Part II] Introduction to automata theory and languages.
- Classification of grammars and formal languages.
- Language recognized by finite state automata.
- Deterministic and non-deterministic automata, regular expressions and their equivalences.
- Properties of regular languages with respect to the operations of union, intersection, complement, product and closure. Pumping Lemma.
- Context-free grammars and context-free languages. Pumping Lemma.
Slides presentate durante le lezioni.
TESTI DI RIFERIMENTO
- S. Ceri, D. Mandrioli, l. Sbattella. Informatica: programmazione McGraw-Hill. In alternativa: D. Mandrioli, G. Cugola, L. Sbattella, P. Cremonesi e S. Ceri. Informatica: arte e mestiere
- J. Hopcroft, J. Ullman. Automi, linguaggi e calcolabilità. Pearson. Addison-Wesley.
- B. W. Kerninghan, D. M. Ritchie. Linguaggio C Pearson.
- Cormen, Leiserson, Rivest, Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill
BIBLIOGRAFIA DI APPROFONDIMENTO
- A. Bellini, A. Guidi. Linguaggio C, guida alla programmazione. McGraw-Hill.
Slides presented during the lectures and lecture notes downloadable from the course's web page
Recommended reading parts of the following books:
- S. Ceri, D. Mandrioli, l. Sbattella. Informatica: programmazione McGraw-Hill. Alternatively: D. Mandrioli, G. Cugola, L. Sbattella, P. Cremonesi e S. Ceri. Informatica: arte e mestiere
- J. Hopcroft, J. Ullman. Automi, linguaggi e calcolabilità. Pearson. Addison-Wesley.
- B. W. Kerninghan, D. M. Ritchie. Linguaggio C Pearson.
- Cormen, Leiserson, Rivest, Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill
To go deeper:
- A. Bellini, A. Guidi. Linguaggio C, guida alla programmazione. McGraw-Hill.
Le modalità di esame per gli studenti non frequentanti sono identiche a quelle per gli studenti frequentanti.
Tutte le indicazioni su quanto fatto a lezione si trovano sulla pagina web del corso. Eventuale materiale sotto forma di lucidi o di esercizi è accessibile sempre a partire dalla pagina web del corso.
Examination methods for non-attending students are identical to those for attending students.
Non-attending students can find on the course web page the list of topics presented for each lesson,
with the projected slides, the assigned exercises and references to the relevant teaching mater.
L'esame è composto da:
- Prova scritta
- Prova pratica di programmazione in C
- Eventuale prova orale
La prova pratica consiste in un problema di programmazione da risolvere in circa due ore. Se superata, la prova rimane valida per tutti gli appelli dell'anno accademico.
Per accedere alla prova pratica e a quella orale occorre aver superato la prova scritta.
L'eventuale prova orale consiste in un colloquio tra il candidato e il docente, in cui vengono accertate le conoscenze del candidato sui principali argomenti del corso e le sue capacità nel risolvere problemi teorici e pratici.
The exam consists of:
- Written exam
- Practical programming test in C
- Optional oral exam
Practical testing consists of a programming problem to be solved in about two hours. If passed, the test remains valid for the whole academic year.
Passing the written exam is necessary to gain access to the practical and oral tests.
If the oral part is not overcome, it is possible to repeat it, without loosing the results of the written and practical parts of the exam.
The optional oral test consists of the teacher assesses the candidate's knowledge of the main subjects of the course and his / her abilities in solving theoretical and practical problems are ascertained.