Appunti Fondamenti di informatica

●​ Array: collezione ordinata di elementi dello stesso tipo.

●​ Liste: sequenze dinamiche di elementi.

●​ Stack e Queue: strutture dati LIFO (Last In, First Out) e FIFO (First In, First

Out).

●​ Alberi e Grafi: strutture dati avanzate per rappresentare relazioni complesse.

Programmazione e Linguaggi

I linguaggi di programmazione si dividono in:

●​ Linguaggi di basso livello: come Assembly, vicini al linguaggio macchina.

●​ Linguaggi di alto livello: come Python, Java, C++.

Paradigmi di programmazione

●​ Imperativo: sequenza di istruzioni (C, Pascal).

●​ Orientato agli oggetti: utilizza classi e oggetti (Java, Python, C++).

●​ Funzionale: basa la computazione su funzioni matematiche (Haskell, Lisp).

Basi di Dati

Le basi di dati servono per archiviare e gestire informazioni in modo efficiente.

●​ Modelli di database:

○​ Relazionale (SQL): dati organizzati in tabelle.

○​ NoSQL: dati non tabellari, utilizzati per big data e applicazioni web.

●​ Operazioni SQL principali:

○​ SELECT, INSERT, UPDATE, DELETE.

Reti di Computer

Le reti permettono la comunicazione tra dispositivi. Si classificano in:

●​ LAN (Local Area Network): rete locale, connette dispositivi in un'area ristretta.

●​ WAN (Wide Area Network): rete geografica, connette più LAN tra loro.

●​ Internet: rete globale basata sul protocollo TCP/IP.

Protocolli di rete

●​ HTTP/HTTPS: protocollo per la comunicazione web.

●​ FTP: protocollo per il trasferimento di file.

●​ DNS: sistema per la risoluzione dei nomi di dominio.

Sicurezza Informatica

La sicurezza informatica è fondamentale per proteggere i dati. Include:

●​ Crittografia: protezione dei dati con algoritmi di cifratura.

●​ Firewall: software/hardware che filtra il traffico di rete.

●​ Autenticazione: verifica dell'identità di un utente tramite password o biometria.

Intelligenza Artificiale e Machine Learning

L'IA è la simulazione dell'intelligenza umana attraverso software e hardware.

●​ Apprendimento supervisionato: il modello viene addestrato con dati etichettati.

●​ Apprendimento non supervisionato: il modello rileva pattern nei dati senza

supervisione.

●​ Reti neurali artificiali: sistemi ispirati al cervello umano per il riconoscimento di

pattern complessi.

Algoritmi ■​ Approccio algoritmico. Metodo risolutivo, semialgoritmo, algoritmo.

Proprietà. Tipologia dei problemi. Strategia vincente dei giochi finiti.

Macchina di Turing

■​ Funzionamento e struttura, matrice funzionale, applicabilità.

Composizione di matrici. Ipotesi fondamentale degli algoritmi. Algoritmo

di imitazione. Problema della codifica. Insieme semidecidibile e

decidibile. Indecidibilità della terminazione.

■​ Struttura e funzionamento della macchina di Von Neumann.

Grafi e alberi

■​ Grafo e grafo diretto. Cammino e sua lunghezza, ciclo. Grafo connesso,

fortemente e debolmente. Albero e albero diretto. Implementazioni

(plessi, liste multiple, matrici di adiacenza, liste di adiacenza).

Attraversamenti (breadth-first e depth-first). Grafo pesato. Algoritmo di

Dijkstra. Chiusura transitiva. Algoritmo a matrice di adiacenza.

Algoritmo di Warshall. Albero ricoprente e minimo albero ricoprente.

Algoritmo di Prim. Algoritmo di Kruskal.

Metodi di ricerca

■​ Ricerca lineare: tabella ordinata e non ordinata, costro con

equiprobabilità, distribuzione di Ziff, legge di Helsing.

■​ Ricerca logaritmica: metodo standard, metodo con interpolazione.

■​ Albero binario di ricerca: albero bilanciato (AVL), perfettamente

bilanciato, quasi perfettamente bilanciato, fattore di bilanciamento,

teorema AVL, algoritmi di bilanciamento.

■​ Ricerca hash: concetto di funzione hash, hash perfetto e non perfetto,

hash per chiavi alfanumeriche, risoluzione delle collisioni (catene

interne ed esterne), risoluzione collisioni "open" (scansione lineare,

scansione quadratica normale e pesata, scansione random), double

hashing, strategie di cancellazione, valutazione metodi hash.

Modelli per memoria secondaria

■​ Memorie secondarie: unità a nastro, unità a disco, metodi di accesso,

organizzazione sequenziale e ad accesso mirato (ordinamento per

posizione, per chiave, struttura sequenziale ordinata e non).

■​ File Hash: funzionamento a blocchi, recupero overflow, hash dinamico.

■​ File indicizzati: organizzazione secondaria, concetto di indice e

principio di guadagno, ISAM (overflow interno ed esterno).

■​ B-alberi: alberi AVL in memoria secondaria (strategia lineare,

raggruppata e ottima), definizione di B-albero, criterio di ricerca,

evoluzione di un B-albero, esplorazione ordinata, gestione di overflow,

analisi delle prestazioni, costo di inserzione, pregi e difetti, albero B+ e

B*.

Complessità

■​ Tipologia di macchine di Turing. Macchina di Turing non deterministica.

Definizione di complessità in tempo. Macchina Ram e formato delle

istruzioni.

■​ Complessità computazionale: criterio del costo uniforme e logaritmico,

ipotesi della teoria della complessità e teorema di Ram-Turing,

operazione dominante, complessità asintotica e regole di composizione.

■​ Modelli per linguaggi di alto livello: regole dei costi (I/O, cicli, test,

sequenze), valore di taglio e tirannia della crescita, formule di ricorrenza

(selection sort, ricerca binaria, quicksort perfetto e medio).