Informatica: fondamenti, big data, algoritmi e algebra booleana

Informatica: Concetti Fondamentali

Pt.1 Informatica Informatica Il termine informatica (computer science in inglese) viene coniato negli anni 60 Philippe Dreyfus. E' la contrazione dei termini francesi "information" e "automatiqu'e" (informazione automatica). E' la disciplina preposta alla elaborazione dell'informazione in modo automatico. Lo strumento prepoposto a questa elaborazione automatica `e il calcolatore (o elaboratore elettronico o computer o suoi derivati quali, e.g., lo smartphone.)

Informazione e Dati

Informazione e dati Il termine informazione assume significati diversi a seconda dei contesti. Nell'informatica, l'informazione `e tipicamente codificata mediante dati. Un dato `e una rappresentazione di una o piu` propriet`a di un oggetto del mondo reale (che pu`o essere tangibile come una persona o astratto come una transazione bancaria). Sottoponendo i dati ad una elaborazione (e.g, il calcolo del volume di transazioni mensili) possiamo generare nuovi dati (e.g., capire se il nosto conto sta o meno crescendo).

Big Data e Crescita Esponenziale

Big Data: Conservazione e Analisi

Big data Modernamente, la vastissima mole di dati generata in e dall'Internet ha permesso la nascita di discipline il cui scopo 'e la conservazione (data storage) e l'analisi dei dati (data analytics). Un'dato (nel senso di fatto) forse sconcertante:

• Ogni mese l'uomo genera tanti dati (digitali) quanti ne sono stati generati dall'inizio dell'era digitale ad oggi.
• In altre parole, ogni mese la quantit a totale di dati digitali immagazzinati raddoppia.
• E' un fenomeno di crescita esponenziale (propriamente detta!).

Dati Digitali e Alfabeto Binario

Alfabeto Binario nell'Informatica

I dati digitali e alfabeto binario I dati digitali rappresentano l'informazione mediante dei simboli (differentemente da quelli analogici dove, e.g., il valore di un dato `e proporzionale all'intesit'a di una corrente elettrica). L'alfabeto usato nell'informatica di basso livello (*) `e un alfabeto estremamente ridotto: l'alfabeto binario. Contiene soltanto due simboli: 0 e 1. Ogni lettera di questo alfabeto e detta bit (contrazione di binary digit). (*) Per "basso livello" intendiamo che oggetti come, ad esempio, un'immagine digitale vengono rappresentati/memorizzati (a basso livello appunto) da sequenze di 0 e 1 - la trasformazione di queste sequenze in punti colorati (pixel) `e realizzata da un processo di rendering.

Motivazioni dell'Alfabeto Binario

perché l'alfabeto binario? La scelta di usare l'alfabeto binario 'e dettata dalla semplicit'a con cui i suoi simboli possono essere rappresentati da dispositivi bistabili: dispositivi fisici capaci di assumere e mantenere nel tempo (a meno di sollecitazioni esterne) due configurazioni alternative: 0 e 1. Esempi:

• Passaggio/non passaggio di luce da un cavo ottico
• Passaggio/non passaggio di corrente da un cavo elettrico
• Polarizzazione (= presenza/assenza di carica elettrica) di una sostanza
• Presenza di fori in una scheda forata

Elaborazione dell'Informazione

Attività di Elaborazione

Elaborazione dell'informazione L'elaborazione dell'informazione `e una qualsiasi attivita condotta sull'informazione/dati che comprenda:

• creazione
• modifica
• confronto
• memorizzazione (conservazione)
• trasmissione

L'informazione in ingresso viene denominata input; quella in uscita output. Il compito assolto dall'elaborazione viene spesso detto risoluzione di un problema. Ad esempio, addizionare 4 a 5 su una calcolatrice corrisponde a risolvere il problema della somma in una sua specifica istanza (l'input 4, 5). Dipendentemente dal tipo di calcolatore (si veda oltre), per elaborare l'informazione pu`o essere necessario fornire ad esso un insieme di istruzioni che descrivano come l'elaborazione va condotta. Questa descrizione `e comunemente detta algoritmo.

Problems and Algorithms

Problem Definition

Problems and algorithms 1/ A problem is a question that needs answering. For instance: "solve ax2 + bx + c = 0 for x over the complex numbers" Problems are general questions. When we face a specific one, we call it an instance. As an example: "solve 2x2 + 8x + 5 = 0 for x over the complex numbers" Our tasks is finding a procedure to solve every instance of a given problem, not just a specific one. We call such a procedure an algorithm. With a bit of extra detail, we call an algorithm a description (in some language) of a finite sequence of operations which, when carried out, lead to a solution our problem that is correct for all of its instances. Example: 2

Algorithm as an Operator

Algorithms 2/2 2 We can think an algorithm A for a problem P an an operator that transforms an instance I of P (every instance I of P, actually) into a (there may be more than one!) solution A(I) to P. Schematically: Instance I Algorithm A Solution A(I) We are not interested in what executes A (a human, a personal computer, the cloud, ... ) but, rather, in the sequence of operations A consists of. . We will not use any specific language/programming language to describe A . No knowledge of computer programming is required (although you should all know Python by now!)

Origin of the Term "Algorithm"

Origin of the name "algorithm"Muhammad ibn Mūsā al-Khwarizmī (780 AD - 850 AD), Mathematician at the House of Wisdom in Baghdad, Abbasid caliphate Strong contributions to algebra: The Compendious Book on Calculation by Completion and Balancing (al-Kitab al-mukhtaşar fī ķisāb al-jabr wal-muqābala) The term "algebra" is a corruption of al-jabr (restoration/completion: the operation of adding/subtracting the same quantity from the left- hand side and the right-hand side of an equation to cancel a term out) Also know for another book: On the Calculation with Hindu Numerals. The Latin name (Algoritmi de numero Indorum) translates into "Algorithmus's (book) on the Hindu number". Algorithmus is the latinized version of al-Khwarizmī. The first semantic connection to the modern meaning (sequence of operations) is recorded in the 13th century with the word algorism, from Old French.

Early Algorithms

First algorithms While the work of al-Khwarizmi did contain some algorithms, it is certaintly not the first scientific work featuring one. Algorithms date back to, at the very least, the Ancient Greeks: Euclid (~350 BC - ~ 250 BC) Euclidean algorithm for computing the greatest common divisor of a natural number Erathostenes (276 BC - 195/194 BC) Sieve of Erathostenes: algorithm for finding all prime numbers (up to a given one)

Calcolatori: Manuali, Semi-Automatici e Automatici

Tipologie di Calcolatori

Calcolatori manuali, semi-automatici e automatici Calcolatori manuali: permettono di codificare i dati in forma precisa, ma affidano all'uomo l'elaborazione. Esempio: l'abaco. Calcolatori semi-automatici: possono eseguire singole (semplici) elaborazioni sui dati senza intervento umano; per elaborazioni piu` complesse richiedono l'intervento (a volte per molte iterazioni) dell'uomo. Esempio: la calcolatrice tascabile (elaborazione semplice: una somma; elaborazione complessa: soluzione di un'equazione algebrica del secondo ordine) Calcolatori automatici: hanno una memoria (interna o esterna) su cui sono rappresentati sia i dati che le istruzioni (cio'e l'algoritmo); non richiedono l'intervento umano (a patto che abbiano ricevuto un input corretto). Esempio: il PC, lo smartphone.

Alan Turing e la Macchina di Turing

Alan Turing: Padre dell'Informatica

Alan Turing Il matematico, logico, crittografo e filosofo britannico Alan Turing `e considerato il padre dell'informatica. E` famoso per aver ideato la Macchina di Turing (MdT), un modello matematico del moderno calcolatore. La MdT `e costituita da

• Un alfabeto (un insieme finito di simboli)
• Un nastro per lettura/scrittura
• Una testina posizionata su una cella del nastro (pu`o leggere e scrivere)
• Un insieme di stati (tra cui quello iniziale e quello finale)
• Una tabella delle azioni o funzione di transizione

Tesi della Computabilità di Church-Turing

Tesi (o congettura) della computabilità Una funzione (matematica) dei numeri naturali è detta computabile se esiste un algoritmo che può calcolare l'output per ogni possibile valore (lecito) dell'input. Esempio: la funzione che calcola la somma di due numeri 'e computabile (ne vedremo un esempio dopo). Tesi (congettura) di Church-Turing: se una funzione matematica `e computabile esiste allora almeno una macchina di Turing in grado di implementarla (cio'e di eseguire un insieme di operazioni che portino al calcolo della funzione richiesta qualsiasi sia il valore del suo input). Secondo questa tesi, la MdT `e il modello di calcolo "piu` potente" che abbiamo. Ad oggi, tutti i calcolatori in uso sono potenti (*) quanto la MdT. (*) Per potenza intendiamo la capacità di portare a compimento un algoritmo, non la rapidità nel farlo (che chiamiamo efficienza)! Diverse MdT hanno efficienza diversa!

Utilità della Tesi di Church-Turing

Utilità della tesi La tesi di Church-Turing permette di confrontare un nuovo modello di calcolo e/o un nuovo "tipo di computer" con tutti gli altri verificando (formalmente) se sia o meno potente come la MdT: basta un solo confronto con la MdT. (Diversamente, un nuovo modello/computer dovrebbe essere confrontato con tutti quelli che l'uomo ha inventato.) Grazie a questa tesi, le propriet'a di un algoritmo possono essere studiate (matematicamente) analizzandone il comportamento su una MdT che ben rappresenti l'elaboratore (fisico) che verr'a effetivamente utilizzato.

Architettura di von Neumann

Componenti dell'Architettura

Architettura di von Neumann Il matematico ungherese (nazionalizzato americano) John von Neumann (uno dei genii, seppur guerrafondaio, del secolo scorso) ide`o la cosiddetta architettura di von Neumann nei primi del '900. Questa architettura coincide con lo schema "hardware", cio'e fisico (a differenza della MdT, che 'e un modello matematico e quindi astratto - potremmo dire "software"), di un calcolatore universale (capace cio'e di calcolare qualsiasi funzione computabile). E` lo schema base del computer moderno. L'architettura prevede:

• memoria: un dispositivo di memorizzazione (un insieme di "celle" contenenti dati o istruzioni) - un computer che segua questa architettura 'e detto programmabile
• central processing unit (CPU): un dispositivo di elaborazione per la lettura ed esecuzione delle istruzioni; l'insieme di istruzioni disponibili `e detto Instruction Set Architecture (ISA)
• interfaccia di input/output (I/O)
• bus: un canale di comunicazione tra le varie componenti

Software, Hardware e PC

Definizioni di Software e Hardware

Software, hardware e il PC Il software (dall'inglese soft = morbido e ware = manufatto) `e un insieme di istruzioni. Possiamo immaginarlo come un complesso insieme di algoritmi. L'hardware `e l'insieme delle componenti tangibili del computer. E` la realizzazione (implementazione) dell'architettura di von Neumann in un calcolatore specifico.