Pensiero Computazionale, Ottimizzazione e Analisi Dati

Parte 1: Fondamenti Computazionali, Ottimizzazione e Modelli a Grafi

Questa prima parte del corso stabilisce le basi concettuali e metodologiche. Introdurremo il pensiero computazionale come approccio alla risoluzione dei problemi, definiremo formalmente i problemi di ottimizzazione che affronteremo, esploreremo le principali classi di algoritmi per risolverli e introdurremo i grafi come potente strumento di modellazione.

1. Introduzione al Pensiero Computazionale e ai Problemi di Ottimizzazione

1.1 Il Pensiero Computazionale: Oltre la Programmazione

Il Pensiero Computazionale (Computational Thinking) non è semplicemente saper programmare, ma un processo mentale per formulare problemi e le loro soluzioni in un modo che possa essere eseguito efficacemente da un "elaboratore" (umano o macchina). Si basa su alcuni pilastri fondamentali:

1. Decomposizione: Scomporre un problema complesso e difficile da gestire in sotto-problemi più piccoli, più semplici e gestibili individualmente.
2. Riconoscimento di Pattern (Pattern Recognition): Identificare somiglianze, regolarità, tendenze o strutture ripetitive all'interno dei problemi o tra problemi diversi. Questo permette di riutilizzare soluzioni o approcci noti.
3. Astrazione: Ignorare i dettagli irrilevanti o specifici di un problema per concentrarsi sugli aspetti essenziali. Questo processo porta alla creazione di modelli (matematici, logici, grafici) che catturano la struttura fondamentale del problema.
4. Progettazione Algoritmica: Sviluppare una sequenza logica e non ambigua di istruzioni (un algoritmo) che risolva il problema o uno dei suoi sottoproblemi, partendo da un input definito e producendo un output desiderato. Questo include considerare l'efficienza (tempo, spazio) e la correttezza della soluzione.

Questo approccio è applicabile in vasta gamma di discipline, non solo nell'informatica.

1.2 Classificazione dei Problemi Computazionali

Dal punto di vista computazionale, possiamo classificare i problemi in diverse categorie, tra cui:

• Problemi Decisionali: Richiedono una risposta binaria: Sì/No.
  • Esempio: Dato un grafo, esiste un percorso che visita ogni città esattamente una volta (Ciclo Hamiltoniano)? Dato un insieme di numeri, esiste un sottoinsieme la cui somma è zero?
• Problemi di Ricerca: Richiedono di trovare una soluzione che soddisfi determinati criteri, se ne esiste una.
  • Esempio: Trovare un percorso Hamiltoniano (non necessariamente il più corto). Trovare un sottoinsieme la cui somma è zero.
• Problemi di Ottimizzazione: Richiedono di trovare la migliore soluzione tra tutte quelle possibili (ammissibili), secondo un criterio quantitativo specificato.
  • Esempio: Trovare il percorso Hamiltoniano più corto (Problema del Commesso Viaggiatore - TSP). Trovare il sottoinsieme di oggetti che massimizza il valore totale rispettando un vincolo di peso (Problema dello Zaino - Knapsack). Questo corso si concentrerà principalmente sui problemi di ottimizzazione.

1.3 Formulazione Matematica di un Problema di Ottimizzazione

Un problema di ottimizzazione può essere formalizzato matematicamente identificando:

1. Variabili Decisionali: Un insieme di variabili x=(x1,x2,…,xn) i cui valori possono essere scelti o controllati. Definiscono una potenziale soluzione.