Obiettivi Formativi

MODULO A Obiettivi formativi Fornire le conoscenze di base degli aspetti teorici e pratici dell'informatica moderna con particolare riferimento alle principali problematiche relative alla rappresentazione e alla elaborazione dell’informazione nei calcolatori elettronici. Trasmettere agli studenti una forma di pensiero computazionale ovvero la capacità di pensare in maniera algoritmica. Lo studente sarà reso in grado di analizzare un problema complesso, suddividerlo in sotto-problemi e progettare semplici algoritmi per la loro risoluzione. Favorire lo sviluppo dell’autonomia dello studente che sarà reso in grado di utilizzare in maniera consapevole i moderni strumenti informatici selezionando opportunamente tra quelli a disposizione i più adatti per la risoluzione del problema considerato. Far acquisire la terminologia di base dell’informatica moderna e la capacità di interloquire con linguaggio tecnico appropriato alla disciplina. Sviluppare nello studente un metodo di studio individuale adeguato a consentire l’approfondimento delle conoscenze acquisite e lo studio di altre discipline di base o specialistiche dell’ambito dell’ingegneria dell’informazione. MODULO B Obiettivi formativi Fornire le conoscenze di base dell’informatica moderna con particolare riferimento ai principali algoritmi e alle relative strutture dati presenti in letteratura. Introdurre la loro implementazione tramite un linguaggio di programmazione di alto livello. Trasmettere agli studenti la capacità di progettare algoritmi anche avanzati e di codificarli in programmi eseguibili da un calcolatore elettronico attraverso un linguaggio di programmazione di alto livello. Favorire lo sviluppo dell’autonomia dello studente che sarà reso in grado di selezionare opportunamente, tra gli algoritmi e le strutture dati noti, quelli più opportuni per giungere alla risoluzione dei problemi considerati con particolare attenzione all’ottimizzazione delle risorse di calcolo e di memoria richieste. Far acquisire la terminologia di base relativa alle tecniche di programmazione tramite linguaggi di alto livello. Lo studente sarà reso in grado di comunicare le motivazioni delle scelte tecniche adottate e di rappresentare adeguatamente i risultati ottenuti. Sviluppare nello studente una capacità di aggiornamento autonomo rispetto all’avanzamento delle tecnologie con particolare riferimento ai linguaggi di programmazione di alto livello, alle strutture dati avanzate e agli algoritmi correlati.

Learning Goals

MODULO A Obiettivi formativi Provide basic knowledge of the theoretical and practical aspects of modern computing with particular reference to the main problems related to the representation and processing of information in electronic computers. Transmit to students a form of computational thinking, i.e., the ability to think algorithmically. The student will be able to analyze a complex problem, divide it into sub-problems and design simple algorithms for their resolution. Encourage the development of the student's autonomy making them able to use modern IT tools in a conscious way, selecting appropriately, among those available, the most suitable for solving the problem under consideration. Acquire the basic terminology of modern information technology and the ability to speak with technical language appropriate to the discipline. Develop in the student an individual study method suitable to allow the deepening of the knowledge acquired and the study of other basic or specialist disciplines in the field of information engineering. MODULO B Provide basic knowledge of modern computing with particular reference to the main algorithms and related data structures present in the literature. Introduce their implementation through a high level programming language. Transmit to students the ability to design even advanced algorithms and to encode them in programs that can be executed by an electronic computer, through a high level programming language. Encourage the development of the student's autonomy making them able to appropriately select, among the ones already known, the most appropriate algorithms and data structures to reach the resolution of the considered problems, with particular attention to the optimization of the required computing and memory resources. Acquire the basic terminology related to programming techniques through high level languages. The student will be able to communicate the reasons for the technical choices made and to adequately represent the obtained results. Develop in the student an independent capacity of knowledge update with respect to the advancement of technologies and with particular reference to high-level programming languages, advanced data structures, and related algorithms.

Metodi didattici

Il corso, al fine di raggiungere gli obiettivi formativi previsti, si svolge prevalentemente attraverso lezioni frontali in aula. Sono inoltre previste esercitazioni in aula guidate dal docente, con lo scopo di stimolare la capacità di applicare la conoscenza acquisita durante le lezioni teoriche. In particolare le esercitazioni in aula consentiranno agli studenti di prendere manualità con i principi di base della programmazione. Tutte le attività sono svolte con supporto di slide delle lezioni.

Teaching Methods

The course, in order to achieve the expected training objectives, takes place mainly through classroom lectures. Classroom exercises led by the teacher are also provided, with the aim of stimulating the ability to apply the knowledge acquired during the theoretical lessons. In particular, the classroom exercises will allow students to learn the basic principles of programming. All activities are carried out with the support of lecture slides.

Prerequisiti

MODULO A Conoscenze di base di analisi matematica, geometria e logica matematica. MODULO B Sono richieste conoscenze di base di analisi matematica, geometria, logica matematica e informatica.

Prerequisites

MODULO A Basic knowledge of mathematical analysis, geometry and mathematical logic. MODULO B Basic knowledge of mathematical analysis, geometry, mathematical logic and computer science is required.

Verifiche dell'apprendimento

Il corso prevede due prove in itinere, un’attività di progettazione sotto forma di realizzazione di un programma in linguaggio C e una prova orale. La prima prova in itinere (con domande a risposta multipla e aperta) verterà sugli argomenti relativi alla prima parte del modulo A del corso e mirerà a verificare che gli studenti abbiano acquisito le conoscenze di base relative all’informatica moderna. La seconda prova in itinere (con domande a risposta multipla e aperta) verterà sugli argomenti relativi alla seconda parte del modulo A del corso e mirerà a verificare che gli studenti abbiano acquisito le conoscenze teoriche di base relative al linguaggio C. Per entrambe le prove la valutazione è espressa in trentesimi. Le due prove si tengono in date che vengono concordate durante le lezioni con gli studenti. Superate le prove in itinere, esse hanno validità per tutto l’anno accademico entro il quale dovrà essere sostenuta la prova finale ed ad ogni appello di esami gli studenti hanno la possibilità di recuperare eventuali prove in itinere non superate. L’attività di progettazione ha l’obiettivo di consentire agli studentidi dimostrare di aver acquisito la capacità di valutare e selezionare le alternative disponibili per la soluzione di un problema nonché la capacità di progettare e implementare un programma in linguaggio C mediante l’applicazione delle metodologie apprese. L'argomento dell’attività di progettazione viene concordato con il docente. L’attività viene sottoposta al giudizio del docente che potrà approvare o respingere il progetto. Gli studenti per i quali il progetto viene approvato sono ammessi alla prova orale che possono svolgere in un qualunque appello dell’anno accademico. L’obiettivo di tale prova è di verificare la capacità dello studente di comunicare le motivazioni delle scelte tecniche adottate durante l’attività di progettazione nonché il livello di conoscenza acquisito dallo studente sugli argomenti del modulo B del corso. In particolare, gli studenti saranno chiamati a dimostrare di conoscere e di sapere utilizzare le strutture dati e i relativi algoritmi mostrati a lezione. Il voto finale è espresso in trentesimi e tiene conto dei voti conseguiti durante le due prove in itinere, della complessità dell’attività di progettazione e della qualità della prova orale.

Assessment

The course includes two ongoing tests, a design activity in the form of the creation of a program in C language and an oral exam. The first ongoing test (with multiple choice and open questions) will focus on the topics related to the first part of module A of the course and will aim to verify that students have acquired basic knowledge relating to modern computer science. The second ongoing test (with multiple choice and open questions) will focus on the topics related to the second part of module A of the course and will aim to verify that the students have acquired the basic theoretical knowledge relating to the C language. evaluation is expressed out of thirty. The two tests are held respectively on dates that are agreed during the lessons with the students. Once the ongoing tests have been passed, they are valid for the entire academic year within which the final test must be taken and at each exam session students have the opportunity to recover any unsuccessful ongoing tests. The design activity aims to allow students to demonstrate that they have acquired the ability to evaluateand select the alternatives available for solving a problem as well as the ability to design and implement a program in C language by applying the methodologies learned. The topic of the design activity is agreed with the teacher. The activity is subjected to the judgment of the teacher who can approve or reject the project. Students for whom the project is approved are admitted to the oral exam which they can take in any session of the academic year. The objective of this test is to verify the student's ability to communicate the reasons for the technical choices made during the design activity as well as the level of knowledge acquired by the student on the topics of module B of the course. In particular, students will be asked to demonstrate that they know and know how to use the data structures and related algorithms shown in class. The final grade is expressed out of thirty and takes into account the marks obtained during the two ongoing tests, the complexity of the design activity and the quality of the oral exam.

Programma del Corso

------------------------------------------------------------ Modulo: 192/1 - FONDAMENTI DI INFORMATICA A ------------------------------------------------------------ - FONDAMENTI DELL’INFORMATICA MODERNA: Introduzione all'informatica. Il calcolatore elettronico, macchina di Von Neumann. Gerarchie di memorie. Sistemi numerici posizionali. Sistema binario. Conversioni di base. Operatori aritmetici nel sistema binario. Algoritmi, dati ed istruzioni, programmazione strutturata, Teorema di Böhm-Jacopini. Codifica degli algoritmi, linguaggio naturale, linguaggio di programmazione, pseudo-codice. Diagrammi di flusso. Algebra booleana. Linguaggi e grammatiche. Grammatiche formali. Backus-NaurForm (BNF). Linguaggi di programmazione: linguaggio macchina, Assembler, linguaggi di alto livello. Compilatori ed interpreti. Compilatori per linguaggio C, GCC. - IL LINGUAGGIO C: Caratteristiche del linguaggio C, struttura di un programma C, principali librerie. Tipi di dato, tipi elementari. Stringhe e I/O da terminale. Operatori ed espressioni, precedenza ed associatività, overloading degli operatori, conversioni di tipo. Istruzioni semplici, istruzioni di controllo, blocchi, regole di visibilità. Costrutto if e costrutto switch-case. Costrutti while, do-while e for. Tipi di dato strutturato in C. Array: definizione, operatori, inizializzazione. Gestione della memoria, Heap. Puntatori e loro operatori. Implementazione di array con puntatore. Le strutture. Tipi enumerativi. Le unioni. Tipi di dato definiti dall'utente. Le funzioni. Passaggio dei parametri per valore e per riferimento, utilizzo dei puntatori. Gestione dei file, file di testo e binari, canali standard, uso dei buffer. ------------------------------------------------------------ Modulo: 192/2 - FONDAMENTI DI INFORMATICA B ------------------------------------------------------------ - ALGORITMI AVANZATI: Algoritmi ricorsivi: funzioni ricorsive e parametri di funzioni ricorsive in C, condizione di terminazione, esempi di algoritmi ricorsivi e loro implementazione in C. Calcolo della complessità: introduzione alla valutazione della complessità di un algoritmo, utilizzo di espressioni asintotiche per esprimere la complessità computazionale di un algoritmo eloro proprietà e regole. Complessità computazionale di operazioni semplici, cicli e funzioni (ricorsive e non). Esempi di calcolo di complessità computazionale di programmi in C. Ricerca e ordinamento in strutture dati semplici. Algoritmi di ricerca: ricerca sequenziale e ricerca binaria. Loro implementazione in C e calcolo della loro complessità computazionale. Algoritmi di ordinamento semplici e evoluti: Bubble sort, Selection sort, Insertion sort, Shell sort, Quick sort, Merge sort. Loro implementazionein C e calcolo della relativa complessità computazionale. - STRUTTURE DATI ELEMENTARI E AVANZATE: Tipi di dato astratto: liste, pile e code. Liste concatenate: ricerca, inserimento in testa, in coda e ordinato, cancellazione. Liste doppiamente concatenate:ricerca, inserimento in testa, in coda e ordinato, cancellazione. Implementazione delle liste tramite array collegati e tramite allocazione dinamica della memoria e puntatori in C. Implementazione di pile e code con liste concatenate e con array monodimensionali in C. Code circolari. Operazioni di push, pop e peak. Operazioni di enqueue e dequeue. Strutture dati complesso: grafi e alberi. Definizione di grafo. Grafi orientati e non orientati. Rappresentazione dei grafi con matrici di adiacenza e liste di adiacenza in C. Algoritmi di attraversamento dei grafi: in ampiezza e in profondità. Loro implementazione in C. Definizione di albero come grafo aciclico. Definizione di albero binario, algoritmi di attraversamento e loro implementazione in C. Definizione di albero binario di ricerca. Algoritmi di creazione, inserimento ordinato, cancellazione, ricerca e loro implementazione in C.

Course Syllabus

------------------------------------------------------------ Modulo: 192/1 - FONDAMENTI DI INFORMATICA A ------------------------------------------------------------ - FUNDAMENTALS OF MODERN COMPUTERS: Introduction to computer science. The electronic calculator, Von Neumann's machine. Memory hierarchies. Positional number systems. Binary system. Basic conversions. Arithmetic operators in the binary system. Algorithms, data and instructions, structured programming, Böhm-Jacopini theorem. Coding of algorithms, natural language, programming language, pseudo-code. Flowcharts. Boolean algebra. Languages ​​and grammars. Formal grammars. Backus-Naur Form (BNF). Programming languages: machine language, Assembler, high-level languages. Compilers and interpreters. Compilers for C language, GCC. - THE C LANGUAGE: Features of the C language, structure of a C program, main libraries. Types of data, elementary types. Strings and terminal I/O. Operators and expressions, precedence and associativity, operator overloading, type conversions. Simple instructions, control instructions, blocks, visibility rules. If construct and switch-case construct. While, do-while and for constructs. Types of structured data in C. Array: definition, operators, initialization. Memory Management, Heap. Pointers and their operators. Pointer array implementation. Structures. Enumerative types. Unions. User-defined data types. Functions. Passing parameters by value and by reference, using pointers. File management, text and binary files, standard channels, use of buffers. ------------------------------------------------------------ Modulo: 192/2 - FONDAMENTI DI INFORMATICA B ------------------------------------------------------------ - ADVANCED ALGORITHMS: Recursive algorithms: recursive functions and parameters of recursive functions in C, termination condition, examples of recursive algorithms and their implementation in C. Computation of complexity: introduction to the evaluation of the complexity of an algorithm, use of asymptotic expressions to express the computational complexity of an algorithm and their properties and rules. Computational complexity of simple operations, cycles and functions (recursive and otherwise). Examples of computational complexity calculations of C programs. Search and sorting in simple data structures. Search algorithms: sequential search and binary search. Their implementation in C and calculation of their computational complexity. Simple and advanced sorting algorithms: Bubble sort, Selection sort, Insertion sort, Shell sort, Quick sort, Merge sort. Their implementation in C and calculation of the relative computational complexity. - ELEMENTARY AND ADVANCED DATA STRUCTURES:Abstract data types: lists, stacks and queues. Linked lists: search, insertion at the top, in the queue and sorted, deletion. Lists doubly linked: search, insertion in the head, in the queue and sorted, deletion. Implementation of lists through linked arrays and through dynamic memory allocation and pointers in C. Implementation of stacks and queues with linked lists and one-dimensional arrays in C. Circular code. Push, pop and peak operations. Operations of enqueue and dequeue. Complex data structures: graphs and trees. Definition of graph. Directed and undirected graphs. Representation of graphs with adjacency matrices and adjacency lists in C. Algorithms for crossing graphs: in width and depth. Their implementation in C. Definition of tree as acyclic graph. Definition of binary tree, traversing algorithms and their implementation in C. Definition of binary search tree. Algorithms of creation, ordered insertion, deletion, search and their implementation in C.