Fondamenti di Informatica e Programmazione: Concetti Chiave e Strutture Dati

Tema 1: Introduzione all'Informatica

• Informatica: Un insieme di conoscenze scientifiche, tecniche e tecnologie che consentono l'elaborazione automatica delle informazioni.
• Sistema Informatico: Un sistema che elabora le informazioni. È composto da entità correlate: Hardware (processore), Software (programma), Peopleware (utenti).

Tema 2: Programmazione e Linguaggi

• Software: Un insieme di istruzioni che indicano al computer cosa fare in modo preciso e dettagliato.
  • I programmi non sono intelligenti.
  • Non hanno iniziativa.
  • Non hanno fantasia e inventiva.
• Modello: Una semplificazione della realtà che permette di astrarre i particolari superflui e concentrarsi su ciò che è veramente importante.
• Linguaggio di Programmazione:

  Sulla base del loro livello di astrazione:

  • Linguaggio macchina.
  • Linguaggio assembly.
  • Linguaggi di alto livello: C, C++...
  • Linguaggi di 4ª Generazione (4GL): SQL...
  • Linguaggi Component-based: NESC...
  • Linguaggi di Modellazione.

  Secondo lo stile di programmazione:

  • Dichiarativi (Prolog, LISP).
  • Imperativi (C, Java, C++).

  Secondo il processo di traduzione:

  • Compilati.
  • Interpretati.
• Un linguaggio di programmazione ha due componenti fondamentali:
  • Sintassi: Cosa e come si può scrivere? (Vocabolario e regole di scrittura).
  • Semantica: Che cosa significa ciò che scrivo?
• Errori in un Programma:
  • Impostare il codice in modo sistematico, ordinato e in base alle convenzioni riduce significativamente gli errori di semantica.
  • Progettare la programmazione prima, come regola. È molto importante.
• Tipi di Errori:
  • Errori rilevati al momento della compilazione: Sono sempre errori di sintassi. Il compilatore verifica la sintassi.
  • Errori rilevati in fase di esecuzione.
  • Errori non del programmatore.
  • Bug/Errori del programmatore.
  • Il meccanismo delle eccezioni in Java.
• Algoritmi: Studio delle procedure ottimali per la risoluzione di un problema.
• Algoritmo: Una "ricetta" per risolvere un problema.
• Efficienza: Non tutti gli algoritmi sono efficienti. L'efficienza è la capacità di svolgere un compito in modo ottimale. L'efficienza di un algoritmo si misura in termini di complessità (ordini di grandezza).
• Efficacia: Un algoritmo è efficace se risolve correttamente il problema per il quale è stato concepito.
• Ingegneria del Software: Principi e tecniche per lo sviluppo di software.
  • Fasi dell'Ingegneria del Software:
    • Analisi: Cattura e analisi dei requisiti.
      • Requisiti Funzionali.
      • Requisiti Non Funzionali: prezzo, tempi di sviluppo, modificabilità ed estendibilità, tempi di implementazione globali...
    • Progettazione (Design): Vengono realizzati vari design affinché il cliente possa decidere quale preferisce.
    • Implementazione: La parte meno creativa. Consiste nella codifica di un design.
    • Test o V&V (Validazione e Verifica):
    • Manutenzione del Software (80%):
      • Estensione e aggiornamenti (10%).
      • Risoluzione di problemi ed errori (60%).
      • Test di comportamento periodici (30%).

Tema 3: Introduzione alla Programmazione

Tema 4: Programmazione Strutturata

• Principi della Programmazione Strutturata:
  1. Ogni programma è una sequenza di istruzioni.
  2. Principio di Sequenza (Stacking): Ogni azione può essere sostituita da due o più azioni in sequenza.
  3. Principio di Annidamento (Nesting): Ogni azione può essere sostituita da una delle tre strutture di controllo valide esistenti, che sono:
     • Sequenza.
     • Selezione o Diramazione.
     • Iterazione o Ripetizione.
  • Tutte le strutture di controllo hanno un unico punto di ingresso e un unico punto di uscita.
  • Nota: Queste regole possono essere applicate con la necessaria frequenza.

Tema 5: Astrazione Procedurale e dei Dati

• Programmazione Strutturata (vedi Tema 4).
• Programmazione Modulare - il principio "divide et impera".
• Vantaggi della Programmazione Modulare:
  1. Incapsulamento Algoritmico: I moduli possono essere generalizzati come operatori che accettano parametri di input (0 o più) e producono risultati di output (0 o più).
     • Vantaggio Derivato: Se è necessario correggere, migliorare o cambiare un modulo, si deve modificare solo la sua implementazione.
     • Il codice di programmazione modulare diventa più facile da modificare e da sottoporre a debug.
  2. Astrazione Procedurale: Una volta creato un modulo, lo si può riutilizzare quante volte si vuole senza dover ripetere il codice. I moduli possono essere visti come "scatole nere" funzionali.
     • Vantaggio Derivato: Il codice si accorcia, senza duplicazioni e quindi più leggibile.
  • In Java, i moduli sono chiamati metodi.
• Tipi di Classi in Java:
  • Classi.
  • Classi Libreria.
  • Metodi Statici (delle classi libreria): Metodi che non richiedono un oggetto per l'esecuzione. Vengono eseguiti utilizzando il nome della classe come destinatario del messaggio.
  • Classi che modellano oggetti.
    • Struttura (attributi).
    • Comportamento (metodi non statici).
• Parametri di Input dei Metodi:
  • Nel definire un metodo, questi parametri sono chiamati parametri formali (tipo + identificatore).
  • Quando si invoca un metodo, i parametri che vengono passati sono chiamati parametri attuali (valori letterali o variabili).
  • Modalità di Passaggio degli Argomenti:
    • Passaggio di argomenti per valore: si passa una copia.
    • Passaggio per riferimento: si passa l'indirizzo di memoria (puntatore).
• ATTENZIONE: In Java, TUTTO è passato per valore.
• I metodi accettano sempre zero o più parametri di input. Nel definire un metodo, questi argomenti sono chiamati parametri formali. Quando si invoca il metodo, i dati che vengono passati come argomento per i parametri di input sono noti come parametri attuali. In Java, i parametri formali sono sempre una copia dei parametri attuali. I parametri vengono passati al metodo per valore. Se si modifica un parametro formale all'interno di un metodo, ciò non ha impatto sul parametro attuale (ad esempio, per i tipi primitivi).
• Overload (Sovraccarico) dei Metodi: In Java è possibile definire diverse versioni dello stesso metodo con lo stesso nome all'interno della stessa classe. Quando ciò accade, si dice che il metodo è sovraccarico. Java determina quale versione di un metodo sovraccarico si sta chiamando verificando l'elenco dei parametri attuali che appaiono nella chiamata al metodo (numero, tipo e ordine dei parametri).
  • Due versioni di un metodo sovraccarico sono considerate corrette se e solo se hanno una firma diversa. Il tipo di ritorno non ha alcun significato per l'overload.
• Firma di un Metodo: Nome del metodo + lista dei parametri.
• Identificatore di un Metodo: Firma + tipo di ritorno.
• Astrazione:
  • Astrazione di Controllo (cicli).
  • Astrazione Procedurale (metodi).
  • Astrazione dei Dati.
  • Tabelle (insiemi).
  • Classi.
• Tipo di Dati Astratto (ADT): Un modello o una struttura astratta che definisce la struttura (attributi) e il comportamento (metodi) degli oggetti concreti che appartengono a quella classe.
• Classi Wrapper (o Involucro): Sono utilizzate quando è necessario un oggetto e non un tipo di dato primitivo. Ad esempio, in una coda, un elemento è legato al successivo.
• Metodi Non-Statici: Eseguiti su istanze di oggetti.
• Metodi Statici: Eseguiti a livello di classe.

Tema 6: Ricorsione (vs. Iterazione)

• Qualcosa di ricorsivo o ricorrente è qualcosa che chiama se stessa. Ha a che fare con il principio di induzione.
• La ricorsione può consumare molta memoria, perché mantiene le variabili durante l'esecuzione del metodo, e può essere lenta. La ricorsione è costosa in termini di risorse, ma è spesso più naturale per esprimere la soluzione di certi problemi, ed è quindi preferita in alcuni contesti. Ad esempio, in Java non è possibile implementare in modo ricorsivo il calcolo del fattoriale di un milione, poiché qualsiasi computer esaurirebbe la memoria; tuttavia, è fondamentale comprenderla per scrivere e analizzare alcuni programmi.
• Ricorsione vs. Iterazione:
  1. Entrambe eseguono una ripetizione:
     • a) La soluzione iterativa ripete il corpo del ciclo.
     • b) La soluzione ricorsiva ripete le chiamate al metodo ricorsivo.
  2. Entrambe hanno una condizione di terminazione:
     • a) Soluzione iterativa: termina quando la condizione di continuazione del ciclo non è più soddisfatta.
     • b) Soluzione ricorsiva: termina quando si raggiunge il caso base (induzione), innescando una sequenza di ritorni.
  3. Entrambe devono essere progettate per convergere alla soluzione (principio di convergenza, per non saltare la condizione di terminazione).
     • a) Soluzione iterativa: si deve garantire che si raggiunga la condizione di terminazione.
     • b) Soluzione ricorsiva: è necessario assicurarsi che si raggiunga il caso base.
• Backtracking (Tornando Indietro): La successione delle chiamate di ritorno.
• Principio Importante: Per qualsiasi soluzione iterativa è possibile trovare una soluzione ricorsiva equivalente, mentre il contrario non è sempre vero.

Teoria del Secondo Semestre

1. Incapsulamento in Fase di Sviluppo

Si definisce all'interno della classe quali dati le corrispondono e quali metodi e design.

2. Incapsulamento in Fase di Esecuzione

Quando la classe esiste già e si creano oggetti da essa, questi sono trattati come "scatole nere". I dati e i metodi sono incapsulati negli oggetti, di cui è necessario conoscere solo l'interfaccia per utilizzare i servizi offerti. Lo stato di un oggetto deve essere modificato solo attraverso i metodi dell'oggetto stesso.

3. Definizione di Interfaccia e Proprietà Associate

Un'interfaccia è una raccolta di costanti e metodi astratti. Le interfacce non vengono utilizzate da sole, a meno che non siano implementate in altre classi. La classe che implementa un'interfaccia fornisce le implementazioni dei metodi dichiarati nell'interfaccia. Una classe può implementare più di un'interfaccia, il che permette una certa capacità di ereditarietà multipla.

4. Astrazione

L'incapsulamento è una forma di astrazione. A un basso livello di astrazione, in una classe si manipolano i dati e i metodi singolarmente. A un elevato livello di astrazione, la classe è considerata un'unità e si utilizzano solo i suoi servizi.

5. Relazioni tra le Classi

• È-una (Generalizzazione/Ereditarietà):
• Associazione:
• Dipendenza (Usa):

6. Generalizzazione (È-una)

Questa relazione è tra un elemento generale (superclasse) e un caso specifico (sottoclasse/classe figlia). Si tratta di una relazione di ereditarietà. La classe figlia eredita gli attributi (dati) e le procedure (metodi) della classe padre e può aggiungere i propri.

7. Associazione

In un'associazione si indica che una classe è composta da altre classi. Questo si ottiene utilizzando un oggetto di una classe come attributo (dato) della classe composita. La molteplicità indica quanti oggetti sono collegati in un'associazione.

8. Dipendenza (Usa)

È una relazione di utilizzo (o impiego), in cui una variazione dello stato di un oggetto (l'indipendente) influisce sullo stato di un altro (il dipendente), ma non viceversa.

9. Costruttore

I costruttori sono uno o più metodi (sovraccarichi) utilizzati per creare oggetti di una classe. Hanno lo stesso nome della classe. Non hanno alcun tipo di ritorno, ma possono accettare parametri (per impostare le variabili dell'oggetto creato).

10. Riferimenti

Nell'assegnazione per riferimento, se i riferimenti puntano allo stesso oggetto, modificando il contenuto di un oggetto tramite un riferimento, si modifica il contenuto dell'oggetto accessibile anche tramite l'altro riferimento, perché in realtà si sta lavorando sullo stesso oggetto, anche se con riferimenti diversi.

11. Modificatori

• Di Visibilità:
  • public: accessibile da qualsiasi luogo.
  • protected: accessibile dalla classe, dalle classi nello stesso package o dalle sottoclassi.
  • private: accessibile solo dalla stessa classe.
• final: utilizzato per dichiarare costanti (variabili, metodi o classi che non possono essere modificati/sovrascritti).
• static: rende la variabile o il metodo appartenente alla classe stessa, non a una specifica istanza. Per le variabili, significa che è condivisa da tutti gli oggetti della classe. I metodi statici possono essere richiamati senza dover creare un oggetto di quella classe.

12. Tre Caratteristiche Fondamentali dell'OOP

• Incapsulamento
• Ereditarietà
• Polimorfismo

13. Polimorfismo

È la capacità di un riferimento di collegarsi a oggetti di varie classi correlate per via ereditaria. In pratica, significa che un riferimento può puntare a un oggetto di una classe o a un oggetto di una qualsiasi delle sue sottoclassi.

14. Utilità delle Classi Astratte

Le classi astratte non implementano tutti i loro metodi, il che costringe le classi figlie a fornire la propria implementazione. Se un metodo non fosse astratto, la classe figlia non sarebbe costretta a implementarlo e potrebbe utilizzare il metodo ereditato dalla sua classe padre.

15. Eccezioni

• Controllate (Checked): È obbligatorio gestirle con un blocco try-catch o dichiararle nella clausola throws, altrimenti possono produrre errori di compilazione.
• Non Controllate (Unchecked): Non è necessario dichiararle nella clausola throws. Sono errori che possono essere evitati durante la scrittura del codice, ad esempio divisione per zero, superamento della dimensione di un array, ecc.

16. Frameworks

Un framework è un'applicazione semi-completa, riutilizzabile e specializzabile mediante l'applicazione di specifici meccanismi di estensione o configurazione, per la produzione di applicazioni specifiche. Spesso include un'infrastruttura di implementazione.

Il punto chiave di un framework è la definizione dei punti che possono essere modificati o specializzati dal programmatore (hot spots) e quelli che non lo sono (codice stabile). I frameworks sono progettati utilizzando design patterns.

17. Alberi Binari

Sono strutture dati costituite da nodi, in cui esiste un primo nodo (radice o root) che ha al massimo due nodi discendenti. Da lì, ogni nodo ha a sua volta al massimo due nodi discendenti (figlio sinistro e figlio destro). Ogni nodo ha un valore "V" e un figlio sinistro e un figlio destro.