- Oggetto:
- Oggetto:
Fondamenti dell'Informatica
- Oggetto:
Foundations of Computer Science
- Oggetto:
Anno accademico 2023/2024
- Codice dell'attività didattica
- INF0348
- Docenti
- Felice Cardone (Corso A)
Stefano Berardi (Corso B)
Luca Luigi Paolini (Corso C) - Corso di studi
- [008707] Laurea in Informatica
- Anno
- 1° anno
- Periodo didattico
- Primo semestre
- Tipologia
- Di base
- Crediti/Valenza
- 9 CFU - Numero di ore - Number of hours: 72 (in aula)
- SSD dell'attività didattica
- INF/01 - informatica
- Modalità di erogazione
- Tradizionale
- Lingua di insegnamento
- Italiano
- Modalità di frequenza
- Facoltativa
- Tipologia d'esame
- Scritto
- Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
L’insegnamento getta le basi di un approccio formale all’informatica, e costituisce il fondamento metodologico di tutto il successivo percorso formativo. I macro-argomenti dell’insegnamento:
- rappresentazione dei dati e loro codifica digitale e circuiti digitali;
- introduzione alle tecniche di dimostrazione e alla logica proposizionale e dei quantificatori;
- elementi di teoria dei linguaggi regolari e automi a stati finiti,
contengono un insieme di conoscenze e competenze richieste da tutti i successivi insegnamenti di settore informatico. Quindi l’insegnamento ha un carattere propedeutico e multidisciplinare.
The course lays the foundations for a formal approach to information technology, and constitutes the methodological foundation of all subsequent training courses. The macro-subjects of the teaching are the following:
- data representation and their digital coding and digital circuits;
- introduction to proof techniques and propositional logic and quantifiers;
- elements of the theory of regular languages and finite state automata.
These contain a set of knowledge and skills required by all subsequent courses in the IT sector. Therefore teaching has a preparatory and multidisciplinary character.
- Oggetto:
Risultati dell'apprendimento attesi
CONOSCENZA E CAPACITÀ DI COMPRENSIONE
Al termine dell’insegnamento saranno state acquisite:
- conoscenza delle tecniche di rappresentazione digitale dell’informazione
- conoscenza dei circuiti digitali
- conoscenza delle tavole di verità per i connettivi proposizionali, della deduzione naturale per la logica delle proposizioni e dei quantificatori
- conoscenza delle principali equivalenze relative ai connettivi proposizionali e ai quantificatori (leggi di de Morgan, dualità dei quantificatori)
- conoscenza delle principali costruzioni e dei principali teoremi sui linguaggi formali
CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE
Al termine dell’insegnamento si sarà in grado di:
- codificare e decodificare numeri con e senza segno, interi, frazionari, in virgola mobile;
- simulare il comportamento di circuiti combinatori e semplici circuiti sequenziali
- analizzare e sintetizzare di circuiti logici elementari per realizzare funzioni booleane
- formalizzare enunciati nel linguaggio naturale in termini di logica elementare
- riconoscere le principali forme di dimostrazione relative ai connettivi proposizionali e ai quantificatori
- seguire in dettaglio lo svolgersi delle dimostrazioni illustrate nell'ambito del corso, e produrre in autonomia semplici dimostrazioni, anche utilizzando le regole della deduzione naturale
- associare linguaggi regolari ad automi finiti e dimostrare la non regolarità di linguaggi
AUTONOMIA DI GIUDIZIO
Saper valutare la correttezza delle applicazione delle tecniche apprese. Saper scegliere le tecniche più adeguate in situazioni nuove.
ABILITÀ COMUNICATIVE
Saper descrivere sotto forma di testo scritto e con sufficienti dettagli le applicazioni delle tecniche apprese nel corso
CAPACITÀ DI APPRENDIMENTO
Sviluppo di capacità autonome di apprendimento e di autovalutazione della propria preparazione. Capacità di intraprendere gli studi successivi della propria carriera di studente con un alto grado di autonomia.
KNOWLEDGE AND UNDERSTANDING
By the end of the course the following will have been acquired: - knowledge of digital information representation techniques - knowledge of digital circuits - knowledge of truth tables for propositional connectives, natural deduction for the logic of propositions and quantifiers - knowledge of the main equivalences related to propositional connectives and quantifiers (de Morgan's laws, duality of quantifiers) - knowledge of the main constructions and the main theorems on formal languages
ABILITY TO APPLY KNOWLEDGE AND UNDERSTANDING
By the end of the course you will be able to: - encode and decode signed and unsigned, integer, fractional, floating point numbers; - simulate the behavior of combinatorial circuits and simple sequential circuits - analyze and synthesize elementary logic circuits to create boolean functions - formalize statements in natural language in terms of elementary logic - recognize the main forms of proof related to propositional connectives and quantifiers - follow in detail the unfolding of the demonstrations illustrated in the course, and independently produce simple demonstrations, also using the rules of natural deduction - associate regular languages to finite automata and prove the non-regularity of languages
AUTONOMY OF JUDGMENT
Knowing how to evaluate the correctness of the application of the learned techniques. Knowing how to choose the most appropriate techniques in new situations.
COMMUNICATION SKILLS
Being able to describe in the form of a written text and with sufficient detail the applications of the techniques learned in the course.
LEARNING ABILITY
Development of autonomous learning skills and self-assessment of one's preparation. Ability to undertake subsequent studies of one's student career with a high degree of autonomy.
- Oggetto:
Modalità di insegnamento
Lezioni frontali in presenza, ove possibile registrate. Le registrazioni verranno pubblicate sulla pagina Moodle del corso.
Class lectures, where possible recorded. Recordings will be published on the Moodle page of the course.
- Oggetto:
Modalità di verifica dell'apprendimento
Esame scritto costituito da domande ed esercizi erogati attraverso la piattaforma Moodle, e diviso in due parti, il superamento dalla prima parte è condizione necessaria per accedere alla seconda. Il punteggio della prova scritta, espresso in 30esimi, sarà dato dalla somma dei punteggi in 30esimi dei singoli esercizi. Il punteggio di ogni esercizio valuterà la conoscenza, la capacità di applicarla e di organizzarla in un discorso. Valuterà inoltre la capacità di ragionamento e la qualità dell’esposizione (competenza nell’impiego del lessico specialistico, efficacia, linearità).
Written exam consisting of questions and exercises delivered through the Moodle platform, and divided into two parts: passing the first part is a necessary condition to access the second. The score of the written test, expressed out of 30, will be given by the sum of the scores out of 30 of the individual exercises. The score of each exercise will evaluate the knowledge, the ability to apply it and to organize it in a speech. It will also evaluate the reasoning ability and the quality of the exposition (competence in the use of specialized vocabulary, effectiveness, linearity).- Oggetto:
Attività di supporto
Alcune delle lezioni saranno dedicate a esercitazioni mirate a consolidare l’acquisizione delle competenze in uscita.
Some of the lessons will be devoted to exercises aimed at consolidating the acquisition of skills.
- Oggetto:
Programma
Codifica digitale dell’informazione: bit, byte e suoi multipli.
Cenni riepilogativi sulla notazione posizionale
Codifica dei numeri naturali e interi: binario, ottale, esadecimale, complemento a 1 e a 2
Elementi di codifica dei numeri reali: virgola mobile, notazione esponenziale
Porte logiche, tavole di verità, espressioni Booleane e forme normali
Circuiti combinatori
Cenni sui circuiti sequenziali
La rappresentazione insiemistica di relazioni e funzioni, costruzioni su insiemi: insieme potenza, prodotto cartesiano, somma disgiunta e insieme delle funzioni di dominio e codominio dati.
Principali equivalenze relative a operazioni su insiemi e loro dimostrazione.
Tecniche di dimostrazione: dimostrazione diretta, per assurdo, per contrapposizione; dualità dei quantificatori.
Tavole di verità e nozione di conseguenza logica per la logica proposizionale.
Cenni sulla semantica dei quantificatori
Nozioni di base di linguaggi formali: alfabeto, parole su un alfabeto e operazione di concatenazione. L'insieme dei linguaggi e operazioni su linguaggi.
Automi a stati finiti e loro relazioni con i circuiti sequenziali; automi non deterministici con teorema di Rabin-Scott
Espressioni regolari e loro semantica: teorema di Kleene.
Proprietà dei linguaggi regolari, pumping lemma.
Digital coding of information: bit, byte and its multiples. Summary of positional notation Encoding of natural and integer numbers: binary, octal, hexadecimal, 1's and 2's complement Coding elements of real numbers: floating point, exponential notation.
Logic gates, truth tables, Boolean expressions and normal forms. Combinational circuits. Basic notions on sequential circuits.
The set-theoretic representation of relations and functions, constructions on sets: power set, cartesian product, disjoint sum and set of functions of the given domain and codomain. Main equivalences related to operations on sets and their proof.
Proof techniques: direct proof, by contradiction, by contrast; duality of quantifiers. Truth tables and notion of logical consequence for propositional logic. Basic notions of the semantics of quantifiers.
Basic notions of formal languages: alphabet, words on an alphabet and concatenation operation. The set of languages and operations on languages. Finite state automata and their relationship with sequential circuits; non-deterministic automata with Rabin-Scott theorem. Regular expressions and their semantics: Kleene's theorem. Properties of regular languages, pumping lemma.
Testi consigliati e bibliografia
- Oggetto:
- Libro
- Titolo:
- Fondamenti dell'Informatica
- Anno pubblicazione:
- 2023
- Editore:
- Pearson
- Autore:
- Richard Johnsonbaugh, J. Glenn Brookshear, Dennis Brylow
- ISBN
- Note testo:
- Maggiori dettagli alla pagina https://he.pearson.it/catalogo/1701
- Obbligatorio:
- Si
- Oggetto:
- Oggetto: