Programmazione 2 completa

PROGRAMMAZIONE 2 DIANA INGRID PUTELLI

INDICE

MODULO 1 – INTRODUZIONE AL CORSO E OOP

OBIETTIVI FORMATIVI

TESTI DI RIFERIMENTO

STRUMENTI (G++, WSL, VISUAL STUDIO CODE)

PERCHÉ LA PROGRAMMAZIONE ORIENTATA AGLI OGGETTI (INCAPSULAMENTO,

RIUTILIZZO, POLIMORFISMO, MANUTENIBILITÀ)

IL CONCETTO DI ASTRAZIONE (ESEMPI: PIANTINA STRADALE, CAFFÈ)

OGGETTI E CLASSI (ATTRIBUTI, OPERAZIONI, STATI)

PROGRAMMAZIONE PROCEDURALE VS OOP (ALGORITMO VS SISTEMA)

FASI OO: ANALISI (OOA), DESIGN (OOD), PROGRAMMAZIONE (OOP)

ESEMPIO DELL’AUTOMOBILE: AUTO_1.FERMATI(), AUTO_1.ACCELERA

SCAMBIO DI MESSAGGI

CONCETTI FONDAMENTALI: INCAPSULAMENTO/OCCULTAMENTO, EREDITARIETÀ,

POLIMORFISMO

BINDING DINAMICO (RUN-TIME)

ESERCIZI PRESENTI :

PROGETTARE UNA SOLUZIONE CHE SIMULI LA GESTIONE DI UNA BIBLIOTECA

(PRESTITO LIBRI).

PROGETTARE UNA SOLUZIONE CHE SIMULI IL FUNZIONAMENTO DI UNA FLOTTA DI

VEICOLI (NOLEGGIO AUTO, MOTO, CAMION).

PROGETTARE UNA SOLUZIONE CHE SIMULI IL FUNZIONAMENTO DI UN CONTO

BANCARIO (DEPOSITO, PRELIEVO, TRASFERIMENTO).

PROGETTARE UNA SOLUZIONE CHE SIMULI LA GESTIONE DELLE PRENOTAZIONI

DI UN HOTEL (AGGIUNTA CLIENTI, PRENOTAZIONE CAMERE, CHECK-IN, CHECK-

OUT).

MODULO 2 – C VS C++

SIMILARITÀ TRA C E C++ (SYNTAX, KEYWORDS, MEMORY MODEL)

ESTENSIONI DEL C++ RISPETTO AL C (OOP, TEMPLATE, OVERLOADING,

NEW/DELETE, NAMESPACE, 97 KEYWORD)

SOSTITUZIONI: .C VS .CPP, PRINTF/SCANF VS CIN/COUT, STDIO.H VS IOSTREAM

TIPI DI BASE C++ (INT, FLOAT, DOUBLE, CHAR, WCHAR_T, BOOL, VOID,

PUNTATORI)

TIPI NON DI BASE (ARRAY, OGGETTI, STRING)

TYPE MODIFIERS (SIGNED, UNSIGNED, SHORT, LONG)

CONSTANT/VOLATILE QUALIFICATION

TYPE CASTING: TYPE(VALUE), CONST_CAST, STATIC_CAST, DYNAMIC_CAST,

REINTERPRET_CAST

MODULO 3 – CLASSI E OGGETTI

DEFINIZIONE DI CLASSE (DICHIARAZIONE, ATTRIBUTI, METODI, INTERFACCIA)

SPECIFICATORI DI ACCESSO (PUBLIC, PROTECTED, PRIVATE)

INFORMATION HIDING / INCAPSULAMENTO

BUONE PRASSI (METODI PUBBLICI, DATI PRIVATI)

OGGETTI (ISTANZE DELLA CLASSE, OPERATORE .)

DATI MEMBRO (NON INIZIALIZZABILI DIRETTAMENTE)

FUNZIONI MEMBRO (DICHIARAZIONE E DEFINIZIONE)

FUNZIONI INLINE E OFFLINE (OPERATORE ::)

COSTRUTTORI (DEFAULT E CON PARAMETRI)

VETTORE DI INIZIALIZZAZIONE DEI MEMBRI (PER ATTRIBUTI CONST E

RIFERIMENTI)

DISTRUTTORE (~NOMECLASSE)

ESEMPIO: CLASSE MIASTRINGA (ALLOCAZIONE DINAMICA, NEW[], DELETE[])

HEADER FILE (.H) E FILE DI IMPLEMENTAZIONE (.CPP)

MODULO 4 – EREDITARIETÀ E POLIMORFISMO

CLASSI DERIVATE: SINTASSI (CLASS DERIVATA : PUBLIC BASE)

TIPI DI EREDITARIETÀ: PUBLIC, PROTECTED, PRIVATE (TABELLA DI ACCESSO)

ESEMPI: PUBBLICAZIONE → RIVISTA, LIBRO

ESEMPIO: OGG_GEOM → CERCHIO, QUADRATO

EREDITARIETÀ PRIVATA (DEFAULT)

COSTRUTTORI ED EREDITARIETÀ (ORDINE DI CHIAMATA)

COSTRUTTORE DI UNA CLASSE DERIVATA (PASSAGGIO PARAMETRI ALLA BASE)

DISTRUTTORI ED EREDITARIETÀ (ORDINE INVERSO)

EREDITARIETÀ MULTIPLA (SINTASSI, PROBLEMA DELL’AMBIGUITÀ)

BINDING STATICO VS DINAMICO

FUNZIONI VIRTUALI (VIRTUAL)

ESEMPIO DI FUNZIONI VIRTUALI: FIGURA → CERCHIO, RETTANGOLO

POLIMORFISMO (STESSO MESSAGGIO A OGGETTI DIFFERENTI)

VANTAGGI DEL POLIMORFISMO

MODULO 5 – TEMPLATE

PARADIGMI DI PROGRAMMAZIONE (PROCEDURALE, MODULARE, OOP, GENERICA)

ALGORITMI INDIPENDENTI DAL TIPO (ES. SCAMBIA)

PROGRAMMAZIONE GENERICA (TEMPLATE)

TEMPLATE DI FUNZIONI (SINTASSI TEMPLATE <TYPENAME T>)

ESEMPIO COMPLETO: SCAMBIA, STAMPA, ORDINA

TEMPLATE DI CLASSI (SINTASSI, METODI ESTERNI, ISTANZIAZIONE)

ESEMPIO: CLASSE PILA<T, N> (PUSH, POP, QUANTI, VUOTA, PIENA)

MODELLI DI COMPILAZIONE: COMPILAZIONE PER INCLUSIONE (#INCLUDE

"PILA.CPP" NELL'HEADER)

COMPILAZIONE SEPARATA (EXPORT – NON PIÙ SUPPORTATA IN C++11)

TEMPLATE E POLIMORFISMO (DIFFERENZE)

MODULO 6 – COMPLESSITÀ COMPUTAZIONALE

COSTO DI UN ALGORITMO (TEMPO E SPAZIO) IN FUNZIONE DI N

COSTO DI ISTRUZIONI CONDIZIONALI (IF-ELSE), CICLI (FOR, WHILE), SEQUENZE

CASO PESSIMO E CASO MEDIO

COMPLESSITÀ TEMPORALE (OPERAZIONI A COSTO UNITARIO)

NOTAZIONE ASINTOTICA: O-GRANDE (LIMITE SUPERIORE)

NOTAZIONE ASINTOTICA: Ω-GRANDE (LIMITE INFERIORE)

NOTAZIONE ASINTOTICA: Θ-GRANDE (LIMITE STRETTO)

PROPRIETÀ DI O, Ω, Θ

DELIMITAZIONI ALLA COMPLESSITÀ DI UN PROBLEMA (LIMITE SUPERIORE E

INFERIORE)

ANALISI DI ALGORITMI: ESEMPI PRATICI (O(1), O(N), O(N²), O(LOG N), O(LOG LOG

N))

ESEMPIO COMPLESSO CON CICLI ANNIDATI

ESERCIZI PRESENTI (DA ESERCIZI_COMPLESSITA.PDF):

19 DOMANDE SU O-GRANDE (F(N) = N² + N⁴ APPARTIENE A O(N³)? ...)

7 DOMANDE SU Ω-GRANDE

8 DOMANDE SU Θ-GRANDE

ESERCIZIO 1: CALCOLO COMPLESSITÀ DEL FATTORIALE ITERATIVO (PASSAGGI)

ESERCIZIO 2: CALCOLO COMPLESSITÀ CASO PESSIMO DELLA RICERCA

SEQUENZIALE

ESERCIZIO 3: CALCOLO COMPLESSITÀ CASO PESSIMO DI INSERTION SORT

MODULO 7 – RICORSIONE

DEFINIZIONE DI FUNZIONE RICORSIVA

ESEMPIO: FATTORIALE (RICORSIVO VS ITERATIVO)

PRODOTTO DI DUE NUMERI NATURALI (RICORSIVO)

INDUZIONE MATEMATICA E CORRETTEZZA

ESEMPIO: FUNZIONE PUZZLE (PROBLEMA DELLA TERMINAZIONE)

RICORSIONE VS ITERAZIONE (VANTAGGI E SVANTAGGI: SPRECO DI TEMPO E

MEMORIA)

ESEMPIO: SOMMA ELEMENTI DI UNA LISTA (RICORSIVA)

ESEMPIO: ELEVAMENTO A POTENZA (RICORSIVO VS ITERATIVO, COSTO)

SERIE DI FIBONACCI (RICORSIVO E ITERATIVO

RICORSIONE INDIRETTA

ESERCIZIO: MASSIMO COMUNE DIVISORE (MCD)

ESERCIZIO: SOMMATORIA

ESERCIZIO: SOMMA DEI QUADRATI

ESERCIZIO: MASSIMO IN UN ARRAY (DIVIDE ET IMPERA)

TORRI DI HANOI (STRATEGIA RICORSIVA)

ESERCIZI PRESENTI :

SOMMARE GLI ELEMENTI DI UNA LISTA (RICORSIVO)

TROVARE IL MASSIMO IN UNA LISTA (RICORSIVO)

GENERARE L’N-ESIMO NUMERO DI FIBONACCI E STAMPARE LA SEQUENZA FINO

AD N

CALCOLARE IL MCD TRA DUE INTERI

CALCOLARE IL NUMERO DI OCCORRENZE DI UN CARATTERE C IN UNA STRINGA S

DATO IL NUMERO DI DISCHI N, RISOLVERE IL PROBLEMA DELLE TORRI DI HANOI

ELENCANDO LE MOSSE

MODULO 8 – ORDINAMENTO E RICERCA

RICERCA SEQUENZIALE (CODICE E COMPLESSITÀ)

RICERCA BINARIA (CODICE E COMPLESSITÀ)

TABELLA COMPARATIVA: CASO MIGLIORE, MEDIO, PEGGIORE PER SEQUENZIALE

E BINARIA

INSERTION SORT (IDEA, CODICE, COMPLESSITÀ O(N²))

MIGLIORAMENTO CON RICERCA BINARIA (RIDUCE I CONFRONTI MA NON GLI

SPOSTAMENTI)

SELECTION SORT (IDEA, CODICE, COMPLESSITÀ)

BUBBLE SORT (IDEA, CODICE, VERSIONE CON FLAG, COMPLESSITÀ)

MERGE SORT (DIVIDE ET IMPERA, CODICE, COMPLESSITÀ O(N LOG N))

QUICK SORT (PIVOT, PARTIZIONE, CODICE, COMPLESSITÀ: CASO MIGLIORE O(N

LOG N), PEGGIORE O(N²))

ESERCIZI PRESENTI:

IMPLEMENTARE L’ALGORITMO INSERTION SORT

MIGLIORARE L’ALGORITMO PRECEDENTE SFRUTTANDO LA RICERCA BINARIA

IMPLEMENTARE L’ALGORITMO SELECTION SORT

APPLICARE LA RICERCA SEQUENZIALE PER CONTARE IL NUMERO DI VOLTE CHE

UN ELEMENTO COMPARE IN UN ARRAY

MODULO 9 – ALBERI BINARI DI RICERCA (BST)

DEFINIZIONE DI ALBERO (GRAFO DIRETTO, RADICE, FOGLIE)

ALBERI E STRUTTURE GERARCHICHE (PADRE, FIGLIO, FRATELLI, ASCENDENTI,

DISCENDENTI)

DEFINIZIONE RICORSIVA DI ALBERO

PROFONDITÀ DI UN NODO

CAMMINI E LIVELLI

ALBERI BILANCIATI

ALBERO BINARIO (FIGLIO SINISTRO E DESTRO)

ALBERO BINARIO DI RICERCA (PROPRIETÀ: CHIAVI A SINISTRA MINORI, A DESTRA

MAGGIORI)

INSERIMENTO IN UN BST (CODICE)

VISITE: PREORDER, INORDER, POSTORDER (CODICE C++)

COSTO DELLA VISITA: Θ(N)

RICERCA IN UN BST (RICORSIVA E ITERATIVA, COMPLESSITÀ O(H))

MASSIMO E MINIMO (O(H))

SUCCESSORE DI UN NODO (DUE CASI, CODICE)

CANCELLAZIONE DI UN NODO (TRE CASI: FOGLIA, UN FIGLIO, DUE FIGLI) –

PROCEDURA TRAPIANTA

ESERCIZI: NON PRESENTI ESPLICITAMENTE IN QUESTA LEZIONE, MA LE

OPERAZIONI DI INSERIMENTO, CANCELLAZIONE E VISITE SONO GLI ESERCIZI

TIPICI.

MODULO 10 – GRAFI

DEFINIZIONE DI GRAFO (V, E), ARCHI DIREZIONATI/NON DIREZIONATI

GRADO DI UN VERTICE (ENTRANTE + USCENTE)

CAMMINO (LUNGHEZZA, CAMMINO SEMPLICE), CICLO

GRAFO CONNESSO, COMPONENTI CONNESSE

COMPONENTI FORTEMENTE CONNESSE (GRAFI ORIENTATI)

SOTTOGRAFO, GRAFO COMPLETO

RAPPRESENTAZIONE: LISTE DI ADIACENZA (O(V+E)), MATRICI DI ADIACENZA

(O(V²))

RICERCA IN AMPIEZZA (BFS): CODICE, COLORI (BIANCO, GRIGIO, NERO),

DISTANZE, PREDECESSORE, COMPLESSITÀ O(V+E)

STAMPA DEL CAMMINO MINIMO (PRINT-PATH)

RICERCA IN PROFONDITÀ (DFS): CODICE, TIMESTAMPS (D[V], F[V]), FORESTE,

COMPLESSITÀ Θ(V+E)

ESERCIZI: NON PRESENTI ESPLICITAMENTE IN QUESTA LEZIONE.

MODULO 11 – CENNI DI SOFTWARE SECURITY

SLIDEPRINCIPISOFTWARESECURITY.PDF

LINGUAGGI COMPILATI VS INTERPRETATI

GESTIONE DELLA MEMORIA (STACK FRAME)

BUFFER OVERFLOW (BOF): STACK BASED, HEAP BASED

PROTEZIONI PER BINARI: NX, STACK CANARY, PIE, ASLR

Capitolo 1 – Introduzione al corso e alla

Programmazione Orientata agli Oggetti

1.1 OBIETTIVI FORMATIVI

1.2 "Consolidare il pensiero computazionale"

"Acquisire e sviluppare capacità di:"

"Risolvere problemi semplici utilizzando gli strumenti della OOP"

 "Comprendere le proprietà fondamentali di diversi algoritmi e strutture dati"

 "Implementare gli algoritmi studiati in C++ attraverso soluzioni affidabili ed

 efficienti"

1.2 TESTI DI RIFERIMENTO

Testo principale:

"Luis Joyanes Aguilar - Fondamenti di Programmazione in C++ - McGrawHill"

Testo secondario:

"T. H. Cormen - Introduction to Algorithms - The MIT Press"

Testi consigliati:

"C++ Tecniche avanzate di programmazione - Apogeo"

"Algoritmi in C++ (terza edizione) - Pearson Education Italia"

"Effective C++ e More Effective C++ - Addison Wesley"

"The C++ Programming Language, Book by Bjarne Stroustrup"

1.3 STRUMENTI

"G++ 12.x.x o superiore (non C++) su Linux"

"Editor qualsiasi (e.g. Visual Studio Code, no DevC++)"

Per chi usa Windows:

"Windows Subsystem for Linux (WSL)"

"Si può usare Visual Studio con supporto WSL"

Istruzioni:

" https://learn.microsoft.com/en-us/cpp/build/walkthrough-build-debug-wsl2?view=msvc-

170 "

1.4 PERCHÉ LA PROGRAMMAZIONE ORIENTATA AGLI

OGGETTI

"Incapsulamento: implementare elementi specifici nascondendo i dettagli implementativi

interni"

"Riutilizzo del codice: Creare nuovi elementi estendendo elementi esistenti"

"Polimorfismo: trattare oggetti differenti che condividono caratteristiche come se fossero

dello stesso tipo"

"Manutenibilità: Le modifiche a una parte specifica del sistema possono essere effettuate

con un impatto minimo sulle altre parti"

1.5 IL CONCETTO DI ASTRAZIONE

"Il mondo in cui viviamo è costituito da sistemi molto complessi, in cui oggetti diversi

interagiscono tra loro e cambiano il loro modo di agire in funzione di quello che accade."

"È difficile gestire una realtà complessa, allo stesso modo è difficile costruire sistemi

complessi come ad esempio software di grandi dimensioni."

"Un modo per gestire la complessità è l'astrazione."

1.5.1 Esempio 1: Piantina stradale

"Una piantina stradale rappresenta un'astrazione di una città."

Spiegazione implicita nella slide: La piantina mostra solo le strade e i punti di interesse,

non tutti i dettagli fisici della città (alberi, tombini, singoli edifici). Si concentra sugli

elementi utili per orientarsi.

1.5.2 Esempio 2: Come fare per avere un caffè

Testo nella slide:

"Come faccio per avere un caffe ?"

"I need Coffee"

Spiegazione implicita nella slide: L'astrazione consiste nel richiedere il servizio senza

conoscere i dettagli implementativi (come la macchina del caffè funziona internamente,

come viene macinato il caffè, ecc.). L'utente interagisce solo con l'interfaccia del servizio.

1.5.3 Definizione di Astrazione

"L'astrazione è un procedimento che consente di semplificare la realtà che vogliamo

modellare."

"La semplificazione avviene concentrando l'attenzione solo sugli elementi importanti del

sistema complesso che stiamo considerando."

1.6 OGGETTI E CLASSI

1.6.1 Definizione di Oggetto

"L'oggetto è il core della programmazione orientata agli oggetti."

"Gli oggetti in un linguaggio OOP forniscono la funzionalità di astrarre, cioè di nascondere

i dettagli implementativi interni."

"Quando si creano dei programmi mediante un linguaggio ad oggetti, la capacità di

astrarre, cioè la capacità di semplificare delle entità complesse in oggetti caratterizzati dalle

caratteristiche e dalle funzionalità essenziali per gli scopi preposti, può risultare

determinante."

1.6.2 Caratteristiche degli Oggetti

"Gli oggetti rappresentano modelli concettuali del mondo reale."

"Gli oggetti possono esibire attributi (caratteristiche), come size, name, shape, e via

dicendo (stati dell'oggetto)."

"Gli oggetti possono esibire operazioni (ovvero le operazioni che essi possono compiere),

come ad esempio settare un valore (cambiare stato), mostrare a screen un risultato, oppure

incrementare il valore di una variabile come ad esempio la velocità."

1.6.3 Definizione di Classe

"Gli oggetti vengono costruiti a partire dalle 'classi', i modelli che descrivono le

caratteristiche che gli oggetti devono possedere."

"Le classi sono organizzabili in gerarchie che determinano quali caratteristiche devono

essere passate da classi genitrici (base) a classi figlie (derivate). Tale meccanismo viene

chiamato 'ereditarietà'."

1.6.4 Attributi e Metodi (schema concettuale)

"Un oggetto può essere definito elencando sia le sue caratteristiche, sia il modo con cui

interagisce con l'ambiente esterno, cioè i suoi comportamenti."

"Le caratteristiche rappresentano gli elementi che caratterizzano l'oggetto,

o utili per descrivere le sue proprietà e definirne lo stato."

"I comportamenti rappresentano le funzionalità che l'oggetto mette a

o disposizione: chi intende utilizzare l'oggetto deve attivare i comportamenti

dell'oggetto stesso."

"Una classe incapsula sia le caratteristiche (attributi) sia i comportamenti (metodi) degli

oggetti che rappresenta."

"Inoltre fornisce una interfaccia pubblica per poter utilizzare (interagire con) gli oggetti

definiti dalla classe."

"In altre parole, la OOP combina strutture dati e algoritmi in entità software 'impacchettate'

dalla definizione di una classe."

1.7 PROGRAMMAZIONE PROCEDURALE VS OOP

1.7.1 Definizione di Programmazione Procedurale

"Nello sviluppo software, usando la metodologia della programmazione procedurale,

l'interesse principale è rivolto alla sequenza di operazioni da svolgere: si crea un modello

indicando le procedure da eseguire in maniera sequenziale per arrivare alla soluzione."

"Lo spostamento di attenzione dalle procedure agli oggetti ha portato all'introduzione

della programmazione ad oggetti. Gli oggetti sono intesi come entità che hanno un loro

stato e che possono eseguire certe operazioni."

"L'algoritmo fa spazio al concetto di sistema."

1.7.2 Definizione di Algoritmo vs Sistema

"Un algoritmo è un insieme di istruzioni che a partire dai dati di input permettono di

ottenere i risultati di output."

"Un algoritmo deve essere riproducibile, deve avere una durata finita e non deve essere

ambiguo."

"Il modo di programmare pone attenzione sulla sequenza di esecuzione."

"Un sistema è una parte del mondo che si sceglie di considerare come un intero,

composto da componenti."

"Ogni componente è caratterizzata da proprietà rilevanti, e da azioni che creano interazioni

tra le proprietà e le altre componenti."

1.7.3 Limiti dei Linguaggi Procedurali

"I linguaggi procedurali hanno dei limiti nel creare componenti software riutilizzabili."

"I programmi sono fatti da funzioni, che rappresentano codice riutilizzabile, ma che spesso

fanno riferimento a headers e/o variabili globali che devono essere importate insieme al

codice delle funzioni."

"I linguaggi procedurali non si prestano bene alla modellazione di concetti ad alti livelli di

astrazione, utili per rappresentare entità complesse che interagiscono in un sistema reale."

Schema nella slide:

Headers Variabili globali

f() g()

h() ...

x()

"In altre parole, i linguaggi procedurali separano le strutture dati e gli algoritmi."

1.7.4 Esempio: Interfaccia Grafica (GUI) di un PC

"Componenti:

Finestre (proprietà: dimensione, posizione)

 Bottoni (proprietà: colore, testo)"



"Interazioni:

Premendo un bottone si può aprire una finestra (e quindi definire la sua posizione e

 la sua dimensione)"

1.8 FASI OO: ANALISI, DESIGN, PROGRAMMAZIONE

"Possiamo individuare tre fasi 'Object-Oriented' (OO):"

"Analisi (OOA): identificazione dei requisiti funzionali, dei componenti e delle loro

 relazioni logiche."

"Design (OOD): specifica delle gerarchie tra classi, e delle loro interfacce e

 comportamenti."

"Programmazione (OOP): implementazione del design, test ed integrazione."



"La OOP è il momento in cui si scrive effettivamente il codice."

1.8.1 Approfondimento: Fase di Analisi