Algoritmi di ordinamento
Avete mai dovuto ordinare migliaia di parole in base all’alfabeto? No. Probabilmente perché in molti casi l’ordinamento viene effettuato dai computer. Per farlo, utilizzano programmi chiamati algoritmi di ordinamento.
In breve, un algoritmo di ordinamento confronta due valori e li scambia a seconda delle necessità. Si può immaginare come se si disponesse di una bilancia con la quale si dovessero ordinare delle palline esattamente uguali in base al loro peso.
A seconda di come si risolve il compito, l’ordinamento delle palline può richiedere più o meno tempo. Più sono le palline, più è importante avere il metodo più veloce possibile.
I metodi più lenti sono quelli che funzionano secondo il principio di casualità. Sono troppo inefficienti per un computer. Si utilizzano invece sofisticati algoritmi di ordinamento. Ad esempio, il bubble sort. In questo processo, un elemento viene sempre confrontato con l’elemento successivo e poi scambiato se l’elemento di sinistra è più grande di quello di destra. In questo modo, i numeri grandi si sollevano come bolle.
Ecco un esempio:
In primo luogo, si confronta il 3 con il 2. Poiché il 3 è più grande, i due numeri si scambiano di posto.
Poiché il 3 è più piccolo del 4, non c’è scambio. Tuttavia, il 4 è più grande dell’1 e i due numeri si scambiano di posto.
Ora inizia un nuovo ciclo. Poiché il 2 è più piccolo del 3, non succede nulla. Tuttavia, il 3 è maggiore dell’1, quindi i numeri vengono scambiati.
Il 3 è più piccolo del 4 e non cambia nulla. Si ricomincia un nuovo giro, in cui solo il 2 e l’1 devono scambiarsi di posto.
Anche questi semplici algoritmi di ordinamento possono essere esaminati con gli alunni. Potete trovare una sfida informatica sul sito web degli scout MIA.n. In tedesco Auf der MIA-Scouts Webseite findest du dazu ein Informatik-Challenge.
Naturalmente, esistono algoritmi di ordinamento ancora più efficienti. Tali algoritmi funzionano di solito secondo il principio del “divide et impera”, vale a dire che prevedono la divisione dell’elenco originale.
Se prendiamo ancora una volta come esempio le palline, le divideremo prima in gruppi più piccoli e poi ordineremo l’ordine all’interno del gruppo. Un metodo divide et impera chiamato “merge sort”, ad esempio, divide tutti i valori da ordinare in elenchi individuali e poi li riunisce passo dopo passo. Date un’occhiata a questo video sugli algoritmi e sul merge sort (YouTube, in inglese) di Crash Course Computer Science.
L’algoritmo di ordinamento rapido utilizza un perno per l’ordinamento. In primo luogo, un elemento viene collocato nella posizione corretta. Poi tutti gli elementi più piccoli vengono posizionati a sinistra del perno e tutti gli elementi più grandi a destra. Vengono quindi impostati altri perni finché l’elenco non è ordinato. Anche in questo caso, un elenco viene suddiviso in parti più piccole per risolvere il problema più rapidamente. Se siete interessati, potete trovare una spiegazione del Quick Sort sul sito web di Hack-Deck.
In generale, esistono molti algoritmi di ordinamento con velocità diverse. Nel video Cooding in pratica(YouTube) troverete altri algoritmi di ordinamento presentati graficamente.
Cifrario di Cesare
Oltre allo smistamento, un altro compito importante dei computer è quello di inviare i dati in modo che non possano essere intercettati da persone non autorizzate. Questo è importante, ad esempio, per l’online banking. Una forma molto semplice di crittografia è il cifrario di Cesare.
Il cifrario di Cesare è un modo per criptare un testo. Ad esempio, ogni lettera dell’alfabeto viene spostata di 3 posizioni. Ad esempio, la “A” diventa una “D”.
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C |
Sfida informatica in tedesco: In dieser Informatik-Challenge der MIA-Scouts erfährst du mehr zur Cäsar-Chiffre.
Naturalmente, le crittografie odierne non sono più così facili da risolvere come il cifrario di Cesare. Spesso si basano sull’esistenza di una chiave pubblica e di una privata, ma di questo non ci occuperemo in questa sede.
Il campo specialistico che si occupa dei metodi per criptare messaggi e dati si chiama crittografia. Se volete saperne di più sullo sviluppo della crittografia dei messaggi, potete guardare questo video di Crash Course Computer Science, che offre una buona panoramica della crittografia (YouTube).
Video in italiano
Il cifrario di Cesare è un modo per criptare un testo. Ad esempio, ogni lettera dell’alfabeto viene spostata di 3 posizioni. Ad esempio, la “A” diventa una “D”.
Testo del video Cifrario di cesare
Ciao e benvenuto in questo nuovo video di Hakuna MATH-ata! Oggi ti parlo del cifrario di Cesare.
Innanzitutto, vediamo cos’è: si tratta di un metodo usato per cifrare i messaggi. Si chiama così perché veniva utilizzato da Giulio Cesare per comunicare con le sue truppe. In realtà, si tratta di un metodo molto semplice che si basa sulla sostituzione delle lettere dell’alfabeto. In pratica ogni lettera è sostituita da quella che la segue dopo un numero fissato di posti.
Vediamo ora nel dettaglio come funziona il cifrario di Cesare attraverso un esempio. Supponiamo di voler cifrare il messaggio scritto alla lavagna.
Innanzitutto, possiamo eliminare gli spazi tra le parole in modo da rendere un po’ più difficile la decifrazione. Fatto ciò, andiamo a sostituire ogni lettera dell’alfabeto con quella che la segue dopo un certo numero di posizioni; ad esempio, con quella che la segue dopo tre posti.
In questo modo, la “a” verrà sostituita con la lettera “d”, la “b” con la lettera “e”, la “c” con la lettera “f” e così via.
In generale, ogni lettera dell’alfabeto viene sostituita da quella che la segue di tre posti. In questo caso abbiamo usato un alfabeto di 26 caratteri ma se anche decidessi di usare un alfabeto con un diverso numero di caratteri il ragionamento di fondo non cambierebbe. Bene, a questo punto non resta che sostituire a ciascuna lettera del messaggio originario la sua lettera corrispondente.
Ecco che il nostro messaggio assumerà la forma illeggibile scritta alla lavagna.
Tutto molto semplice, vero? Purtroppo però la semplicità ha un costo. Infatti, il cifrario di Cesare, oltre a essere eccessivamente semplice, è anche eccessivamente debole…e per debole intendo dire che un messaggio cifrato utilizzando questo metodo può essere decifrato in maniera altrettanto semplice. Ad esempio, attraverso quella che si chiama analisi delle frequenze ovvero lo studio delle frequenze con cui una data lettera compare all’interno delle parole di una certa lingua. Ad esempio, in italiano la lettera che ricorre più spesso è la “e”, seguita poi dalla “a”.
Ma anche senza ricorrere all’analisi delle frequenze, il Cifrario di Cesare può essere rotto usando la forza bruta. Basterà infatti ragionare a ritroso e provare a sostituire ogni lettera dell’alfabeto con quella che la precede di un
certo numero fissato di posti. In questo modo, dopo qualche tentativo infruttuoso, il messaggio tornerà a essere leggibile.
Ad esempio, se ti va puoi provare a decifrare il messaggio che scrivo alla lavagna. Buona fortuna!
In definitiva, quindi, ci tengo a ribadire questo concetto: se devi cifrare un messaggio supersegreto evita di usare il cifrario di Cesare o una delle sue varianti! Rischierebbe di essere scoperto in pochissimo tempo. Questo però non deve scoraggiarti. Puoi comunque ricorrere all’algoritmo RSA di cui abbiamo parlato in una precedente lezione oppure ad altri metodi che presenteremo nei prossimi video. A questo punto sicuramente ti starai chiedendo come fare per non perderti le prossime lezioni! La risposta è semplicissima: basta iscriversi al canale!
Bene, per oggi è tutto. Grazie per la visione e buona giornata!