Fondamenti di Informatica AFondamenti di Informatica AIntroduzione al corsoIntroduzione al corso

Moreno MarzollaDipartimento di Informatica—Scienza e Ingegneria (DISI)

Università di Bolognahttp://www.moreno.marzolla.name/

Introduzione 2

Introduzione 3

Ringraziamenti

● prof. Hany Farid, Dartmouth College– http://www.cs.dartmouth.edu/farid/

● prof. Simone Martini, Università di Bologna– http://www.cs.unibo.it/~martini/

Introduzione 4

Fondamenti di Informatica A

● http://www.moreno.marzolla.name/teaching/FINFA ● Orario

– Lunedì 10:00—13:00 GPT (teoria)– Martedì 14:00—16:00 G1P (teoria)– Mercoledì 13:00—15:30 (primo turno), 15:30—18:00

(secondo turno) VELA (laboratorio)● Prime due settimane: no laboratorio, mercoledì 12:00-14:00 G1P● Prestare attenzione ad eventuali variazioni d'orario

● Teoria– 60 ore

● Laboratorio– 30 ore (2 turni)

Introduzione 5

Libro di testo

● Facoltativo, ma fortemente consigliato per chi non segue le lezioni

● Uno a scelta tra:– J. Glenn Brookshear, “Informatica—una

panoramica generale”, 11/ed., Pearson 2012, ISBN 978-8871927671 (o edizione più recente)

– D. Sciuto, G. Buonanno, L. Mari, “Introduzione ai sistemi informatici”, 5/ed., McGraw-Hill, 2014, ISBN 978-8838668326 (o edizione più recente)

Introduzione 6

I docenti

● Moreno Marzolla (moreno.marzolla@unibo.it) – Teoria– Web: http://www.unibo.it/sitoweb/moreno.marzolla

● Sara Montagna (sara.montagna@unibo.it)– Laboratorio – linguaggio Java– Web: http://www.unibo.it/sitoweb/sara.montagna

● Raffaele Cappelli (raffaele.cappelli@unibo.it)– Laboratorio – linguaggio C– Web: http://www.unibo.it/sitoweb/raffaele.cappelli

● Michele Braccini (michele.braccini2@studio.unibo.it)– Tutor, principalmente per il laboratorio

Introduzione 7

Orario del corso

● Prime due settimane:– Lunedì 10—13 GPT– Martedì 14—16 G1P– Mercoledì 12—14 G1P

● A partire dalla terza settimana (7 marzo):– Lunedì 10—13 GPT– Martedì 14—16 G1P– Mercoledì 13:00—15:30 VELA (primo turno)– Mercoledì 15:30—18:00 VELA (secondo turno)

● Attenzione a cambi di orario in giorni specifici– Fare riferimento alla pagina del corso

Introduzione 8

Laboratori

● Suddivisione tra i due turni di laboratorio in base al cognome

● Primo laboratorio– Matricole pari: primo turno– Matricole dispari: secondo turno

● Ogni settimana i turni si scambiano– Fate riferimento alla pagina del corso per sapere a chi tocca

quale turno

Introduzione 9

A chi chiedere cosa

● Moreno Marzolla– Argomenti “teorici” svolti in aula– Questioni di carattere generale sul corso

● Sara Montagna– Laboratorio Java

● Raffaele Cappelli– Laboratorio C

Introduzione 10

Come chiedere

● E' sempre possibile (e incoraggiato!) fare domande durante le lezioni

● Domande “brevi”: via mail● Domande “non brevi”: a ricevimento, o dopo le lezioni

Introduzione 11

“Netiquette”ossia, le “buone maniere” nell'era di Internet

● Usare esclusivamente l'indirizzo istituzionale @studio.unibo.it

● Indicare sempre l'oggetto (subject) del messaggio● Firmare la mail con nome, cognome e matricola● Specificare che il messaggio è relativo al corso FINFA

– Ad esempio, iniziare il subject con “[FINF-A] ...”● La posta elettronica è un mezzo di comunicazione

asincrono– Non sempre siamo in grado di rispondere immediatamente– Non date per scontato che leggiamo la posta a mezzanotte

● Queste regole valgono anche per me nei vs confronti!

Introduzione 12

Esempio di mail che viola tutte le regole

From: xxxx@yahoo.itDate: 20XX/XX/XX 23:47Subject:

Salve, volevo sapere se è disponibile domani per un ricevimento.

Introduzione 13

Esempio di mail che viola tutte le regole

From: xxxx@yahoo.itDate: 20XX/XX/XX 23:47Subject:

Salve, volevo sapere se è disponibile domani per un ricevimento.

Indirizzo non istituzionaleAssume che la mail venga letta a mezzanotte

Manca oggetto

Manca la firma e l'indicazione del corso cui si riferisce

Introduzione 14

Modalità d'esame

● Prova scritta sul programma svolto nell'ultimo anno accademico in cui si è svolto il corso

● Composta da domande (“a crocette” e a risposta aperta) ed esercizi di programmazione in Java e C

● Una unica prova: l'esame si supera o si fallisce per intero● Voti pubblicati su AlmaEsami

– Chi intende rifiutare il voto deve comunicarlo al docente entro la scadenza riportata nella mail di notifica; in tal caso verrà verbalizzato “Ritirato”

– Chi intende accettare il voto non deve fare nulla– Non si tengono voti in sospeso: chi intende migliorare il voto

deve rifiutare e ripresentarsi

Introduzione 15

Modalità d'esame

● Per gli iscritti ad anni precedenti che hanno superato la prova pratica ma non la prova teorica– Si puo' svolgere solo la parte teorica (sul nuovo programma

del corso) fino alla sessione di gen/feb 2017 compresa– Dopo tale data tutti i voti in sospeso (inclusi i voti finali non

ancora verbalizzati) saranno persi● Per gli iscritti ad anni precedenti che non hanno superato la

prova pratica– Esame con le nuove modalità e il nuovo programma

● Per chi deve sostenere il vecchio esame da 6 CFU– Contattare il docente per definire un programma ridotto,

comunque basato su quanto svolto a lezione nell'anno accademico più recente

Introduzione 16

Modalità d'esame

● Per partecipare allo scritto è obbligatorio iscriversi tramite AlmaEsami– La lista chiude 5-6 giorni prima dell'esame per darci il tempo

di predisporre gli aspetti logistici (aule, turni, ...)– Chi non si iscrive non viene ammesso

● Come da regolamento di Ateneo, verranno organizzati 6 appelli d'esame all'anno– 3 nella sessione estiva (giugno/luglio)– 1 nella sessione autunnale (settembre)– 2 nella sessione invernale (gennaio/febbraio)

● Non ci saranno altri appelli.

Introduzione 17

Per superare l'esame...

● “Spannometricamente”– 9 CFU = 9 25 = 225 ore di impegno totale– 90 ore in aula, il resto (135 ore) di studio individuale

● 135 ore = 16 giorni full time... solo per rendersi conto dell'impegno, SCONSIGLIO di affrontare qualunque materia chiudendosi in casa per 16 giorni!

● Come superare l'esame– Seguire le lezioni– Approfondire sul libro oppure su altro materiale che verrà

indicato dal docente– Chiedere in caso di dubbi (e venire a ricevimento)– Esercizi, esercizi, esercizi!!

● Sia sulla parte teorica che (soprattutto) di programmazione● L'informatica non è uno “sport” da praticare come spettatori

Introduzione 18

Questo corso

● Cosa imparerete– Principi generali– Metodi– Fondamenti di

programmazione

● Cosa non imparerete– Come si installa X– Come si usa Y– Riparare un PC– Scrivere una app

Introduzione 19

Cosa è l'informatica?

● Parole chiave– INFORMazione– Elaborazione automATICA

“Lo studio sistematico degli algoritmi che descrivono e trasformano l'informazione: la loro teoria, analisi, progetto,

efficienza, realizzazione e applicazione”

[Association for Computing Machinery (ACM)]

“La scienza della rappresentazione ed elaborazione [automatica] dell'informazione”

Introduzione 20

Informatica

● Costruzione di calcolatori efficienti

● Studio dei paradigmi di programmazione

● Sviluppo di algoritmi efficienti per risolvere problemi

● Studio dei limiti teorici della risoluzione meccanica di problemi

– Tutti i problemi sono risolubili “meccanicamente”?

– Esistono problemi “troppo difficili” per essere risolti meccanicamente?

Ling

uagg

i di

prog

ram

maz

ione

Alg

oritm

i

Fo

ndam

enti

teor

ici

dell'

info

rmat

ica

Har

dwar

e

Informatica

Introduzione 21

Perché studiare informatica?Il Therac-25

● Dispositivo computerizzato per la radioterapia di pazienti affetti da cancro

● Terza generazione (Therac-6, Therac-20)● I modelli precedenti disponevano di

controlli hardware per impedire il sovradosaggio

● I controlli hardware sono stati rimpiazzati da controlli software per ridurre i costi

● Nel funzionamento nominale eroga 6000 rad complessive in 3 settimane di utilizzo

● A causa di grossolani errori di programmazione, ha erogato fino a 60000 rad in una singola sessione

● Tra giugno 1985 e gennaio 1987 sei pazienti sono morti o seriamente feriti da dosi eccessive di radiazioni

● http://www.computer.org/computer/homepage/misc/Leveson/index.htm

Perché studiare informatica?Ariane 5

Perché studiare informatica?Lo scandalo Wolkswagen sulle emissioni

Introduzione 24

Informatica e computer

“Computer Science is no more about computers than astronomy is about

telescopes, biology is about microscopes or chemistry is about beakers and test tubes.”

Michael R. Fellows and Ian ParberryComputing Research News, vol. 5, n. 1, 1993

Introduzione 25

Cosa è un computer?

"Human computers - Dryden" by NACA (NASA) - Dryden Flight Research Center Photo Collection - http://www.dfrc.nasa.gov/Gallery/Photo/Places/HTML/E49-54.html. Licensed under Public Domain via Commons - https://commons.wikimedia.org/wiki/File:Human_computers_-_Dryden.jpg#/media/File:Human_computers_-_Dryden.jpg

Introduzione 26

Cosa è un computer?

● Un computer è un dispositivo programmabile in grado di svolgere in modo automatico una sequenza di operazioni aritmetiche o logiche

● In altre parole, è uno strumento per la rappresentazione, memorizzazione ed elaborazione di informazioni

Introduzione 27

Conoscenza

● Dichiarativa– Consiste nella descrizione

di fatti o proprietà

● Imperativa– Consiste nella descrizione

di regole o procedure che consentono di ottenere determinati risultati

“La radice quadrata di x è il numero non negativo y tale che y2 = x”

Trova una stima G della radice quadrata di xRipeti Se G2 ≈ x allora il risultato è G; stop altrimenti G ← (G + x/G) / 2

L'informatica si occupa di questo

Introduzione 28

Conoscenza Imperativa

● Come possiamo descrivere la conoscenza imperativa?● Fixed program computer

– Dispositivi specializzati per risolvere un tipo specifico di problema

● Stored program computer– Dispositivi che ricevono in ingresso una sequenza di

istruzioni che descrivono i passi da eseguire per risolvere un certo problema

– Possono risolvere problemi diversi, ricevendo sequenze di istruzioni specializzate per il problema da risolvere

– Esistono molti linguaggi di programmazione che possono essere usati per descrivere le istruzioni da eseguire

Introduzione 29

Conoscenza imperativa e algoritmi● Un algoritmo è un procedimento per

risolvere un problema mediante una sequenza finita di passi elementari– Descritto in modo preciso allo scopo di

automatizzarne l'esecuzione● Il termine deriva dal nome del

matematico persiano Muhḥammad ibn Mūsā al-Khwārizmī (نب دمحمحمد بن (نب دمحموسى الخوارزنب دمحمی– Autore di un primo fondamentale

trattato di algebra– Un cratere lunare porta il suo nome Muhḥammad ibn Mūsā al-Khwārizmī (c. 

780 – c. 850) (francobollo sovietico  commemorativo; Fonte: Wikipedia)

30

Gli algoritmi sono ovunque!

Introduzione 31

Gli algoritmi sono ovunque!

● Le proteine assumono una ben precisa struttura tridimensionale a causa dell'interazione degli aminoacidi che le compongono

● Si ritiene che certe malattie neurodegenerative siano causate dall'accumulo di proteine che si ripiegano in maniera “scorretta”

http://en.wikipedia.org/wiki/Protein_folding

Introduzione 32

Algoritmo vs Programma

● Un algoritmo è una sequenza finita di passi elementari per risolvere un problema dato– Solitamente espresso in

modo informale, ad es., in linguaggio naturale oppure mediante diagrammi

● Un programma è l'implementazione di un algoritmo mediante un linguaggio di programmazione– Espresso formalmente nel

linguaggio adottato

Introduzione 33

I passi per risolvere un problema

Problema

Algoritmo

Programma

Risultati

Analisi

Implementazione

●Diagramma a blocchi●Pseudocodice●Descrizione testuale

Linguaggio di programmazione(C, Java, Matlab, Python, ...)

Esecuzione

Introduzione 34

Valutare un algoritmo

● Correttezza– Se l'algoritmo fornisce un risultato, è sempre quello corretto?

● Completezza– L'algoritmo fornisce sempre un risultato, quando ne esiste

uno?● Efficienza

– Quanto tempo richiede per calcolare il risultato? Nel caso migliore? Nel caso peggiore?

● Realizzabilità– L'algoritmo è descritto in modo non ambiguo? Siamo in

grado di implementarlo?

Introduzione 35

Esempio

● Ricerca sull'elenco del telefono– Input: un cognome e nome qualsiasi– Output: numero di telefono dell'abbonato

Introduzione 36

Esempio

Parti dal primo abbonato sull'elenco

Il nome è quello cercato?

Passa all'abbonatosuccessivo

SìNo

Stampa num.di telefono

● Ricerca del numero di telefono consultando l'elenco– Input: cognome e nome di

un individuo qualsiasi– Output: numero di

telefono

Inizio

Introduzione 37

EsempioParti dal primo abbonato

sull'elenco

Il nome è quello cercato?

Passa all'abbonatosuccessivo

SìNo

Sei arrivatoalla fine?

Sì

No “non trovato”

Stampa num.di telefono

● Ricerca del numero di telefono consultando l'elenco– Input: cognome e nome di

un individuo qualsiasi– Output: numero di

telefono, oppure “non trovato”

Inizio

Introduzione 38

EsempioParti dal primo abbonato

sull'elenco

Il nome è quello cercato?

Passa all'abbonatosuccessivo

SìNo

Sei arrivatoalla fine?

Sì

No “non trovato”

Stampa num.di telefono

● Corretto?● Completo?● Efficiente?

– Quante pagine dell'elenco devo esaminare nel caso migliore?

– Quante pagine dell'elenco devo esaminare nel caso peggiore?

Inizio

Introduzione 39

Ricerca binaria

1.Dividi la pila di pagine in due parti uguali composte da circa metà delle pagine ciascuna

2.Scarta la metà che sicuramente non contiene il nome che stai cercando

3.Se la parte che rimane è costituita da una singola pagina, cerca il nome su quella pagina

4.Se la parte che rimane è più di una pagina, vai al passo 1

Introduzione 40

Esempiocerchiamo “Marzolla”

Viesti …... 7746734

Zulian ….... 7716632

Soru ….. 3763343

Tancredi …. 91874363

Rossi … 3764634

Serafini ….. 37465374

Nicoletti …. 2873643

Pasquini … 34676473

Ligure ….. 277382

Marotta ….. 7365263

Franchini ….. 63343

Gaiardo ... 7632554

Derossi ….. 219387

Fortunati ….. 348726

Albano …... 1312412

Cadorna ….. 13123412

Introduzione 41

Esempiocerchiamo “Marzolla”

Viesti …... 7746734

Zulian ….... 7716632

Soru ….. 3763343

Tancredi …. 91874363

Rossi … 3764634

Serafini ….. 37465374

Nicoletti …. 2873643

Pasquini … 34676473

Ligure ….. 277382

Marotta ….. 7365263

Franchini ….. 63343

Gaiardo ... 7632554

Derossi ….. 219387

Fortunati ….. 348726

Albano …... 1312412

Cadorna ….. 13123412

Prima divisione

Introduzione 42

Esempiocerchiamo “Marzolla”

Ligure ….. 277382

Marotta ….. 7365263

Franchini ….. 63343

Gaiardo ... 7632554

Derossi ….. 219387

Fortunati ….. 348726

Albano …... 1312412

Cadorna ….. 13123412

Introduzione 43

Esempiocerchiamo “Marzolla”

Ligure ….. 277382

Marotta ….. 7365263

Franchini ….. 63343

Gaiardo ... 7632554

Derossi ….. 219387

Fortunati ….. 348726

Albano …... 1312412

Cadorna ….. 13123412

Seconda divisione

Introduzione 44

Esempiocerchiamo “Marzolla”

Ligure ….. 277382

Marotta ….. 7365263

Franchini ….. 63343

Gaiardo ... 7632554

Introduzione 45

Esempiocerchiamo “Marzolla”

Ligure ….. 277382

Marotta ….. 7365263

Franchini ….. 63343

Gaiardo ... 7632554

Terza divisione

Introduzione 46

Esempiocerchiamo “Marzolla”

Ligure ….. 277382

Marotta ….. 7365263

Introduzione 47

Esempiocerchiamo “Marzolla”

Ligure ….. 277382

Marotta ….. 7365263

Non trovato

Introduzione 48

Analisi della ricerca binaria

● Corretto?– Quale proprietà dell'elenco telefonico è fondamentale per

garantire la correttezza dell'algoritmo?● Completo?● Efficiente?

– Quante divisioni devo fare nel caso migliore?– Quante divisioni devo fare nel caso peggiore?

Introduzione 49

I limiti dell'informatica

● Fino ad ora abbiamo considerato una definizione “intuitiva” di algoritmo

● Ma, precisamente, che significa “calcolare”?● E' possibile calcolare il valore di qualsiasi funzione,

oppure esistono funzioni il cui valore “non è calcolabile”?

Introduzione 50

Alan Mathison Turing

● Nato il 23 giugno 1912● OBE (Order of the British

Empire), FRS (Fellow of the Royal Society)

● Morto il 7 giugno 1954 per avvelenamento da cianuro

Introduzione 51

Alan Mathison Turing

● Criptanalisi● Macchine per il calcolo● Gioco dell'imitazione● Morfogenesi

Introduzione 52

Criptanalisi

Introduzione 53

www.turingsunflowers.com

Introduzione 54

Il gioco dell'imitazione

● Tenta di dare una risposta pragmatica alla domanda “cos'è l'intelligenza?”

● Un interrogante è collegato mediante un terminale con due stanze: in una di esse si trova una persona, nell'altra un computer

● Ponendo domande tramite il terminale, l'interrogante deve decidere chi è l'essere umano e chi la macchina

Introduzione 55

Introduzione 56

Cosa significa calcolare?

1 79

2 6

+5=2

7

Introduzione 57

Macchina di Turing

● Dispositivo astratto che contiene tutti gli elementi essenziali per “calcolare” una qualsiasi funzione– Un supporto su cui scrivere: un nastro infinito, diviso in

caselle– Un insieme finito di simboli che possono comparire sul

nastro– Un dispositivo di lettura/scrittura– Un insieme finito di “stati” in cui la macchina si può trovare in

ogni istante– Una “tavola di istruzioni” finita, che dice alla macchina cosa

fare in base al simbolo che si trova in quel momento sotto la testina di lettura/scrittura

Introduzione 58

Macchina di Turing

● Un insieme finito di stati in cui la macchina può trovarsi– q0 è lo stato iniziale, in cui la macchina si trova quando viene fatta

partire– halt è lo stato finale: se la macchina raggiunge tale stato, si ferma.– Nota: gli stati possono avere nomi arbitrari; “q0” e “halt” sono solo una

nostra convenzione che useremo qui● Un nastro infinito diviso in celle● Un alfabeto finito (insieme di simboli che possono comparire

sulle celle del nastro)– L'alfabeto include un simbolo “spazio” (blank) che compare su tutte le

(infinite) celle non inizializzate del nastro.– Un insieme finito di celle puo' contenere inizialmente simboli diversi da

blank, e rappresentano l'input iniziale della macchina di Turing● Una funzione di transizione che determina il comportamento

della macchina

Introduzione 59

Funzione di transizione

● Una lista di regole che indicano, per ogni possibile simbolo X che si trovi al momento sotto la testina e per ogni possibile stato P della macchina:– quale simbolo Y scrivere al posto di X (è possibile riscrivere

nuovamente X);– quale è il nuovo stato Q della macchina (è possibile che lo

stato rimanga sempre P);– se la testina deve essere spostata a destra oppure a sinistra

di una casella;● Inizialmente la macchina si trova nello stato iniziale, e

la testina è posizionata su una data cella del nastro (che di solito dipende dal problema da risolvere)

Introduzione 60

Esempio

1 1 1 1

Testina di lettura/scritturacon indicato lo stato corrente

Contenuto iniziale del nastro

● Alfabeto: {1, blank}● Stati: {q0, halt}

Stato corrente

Simbolo corrente

Nuovo Simbolo

Nuovo Stato

Spostamento

q0 1 1 q0 right

q0 blank 1 halt right

q0

Introduzione 61

Esempio

● Calcolare il “complemento a uno” di un numero espresso in base 2– In pratica, cambiare gli '1' con '0' e viceversa– 10010001 → 01101110

● Inizialmente sul nastro viene scritta la cifra binaria● Al termine il nastro deve contenere il risultato al posto

degli input● Esercizio: come definiamo la funzione di transizione?

1 0 0 0 10 0 1

q0

Introduzione 62

Esempio

● Calcolare la somma di due numeri in base 1– 111 + 1111 = 1111111

● Inizialmente sul nastro vengono scritti i due numeri da sommare, separati da un blank

● Al termine il nastro deve contenere il risultato al posto degli input

● Esercizio: come definiamo la funzione di transizione?

1 1 1 1 11 1

q0

Introduzione 63

LEGO Turing Machinehttp://www.legoturingmachine.org/

Introduzione 64

Funzioni calcolabili eTuring-Completezza

● Tesi di Church-Turing: le funzioni calcolabili sono tutte e sole le funzioni calcolabili da una qualche macchina di Turing

● Qualsiasi formalismo mediante il quale sia possibile simulare una macchina di Turing si dice Turing-Completo– Tutti i moderni linguaggi di programmazione sono Turing-

completi– Questo significa che nessuno di loro è più “potente” degli

altri, nel senso che non esistono funzioni che possono essere codificate in un linguaggio ma non negli altri

Introduzione 65

Funzioni non calcolabili:Halting Problem

● Esistono funzioni che NON sono calcolabili● Esempio (Halting Problem)

“Scrivere una funzione Termina(P, I) che accetta in input (1) la descrizione di un programma P, e (2) l'input I da passare a P. La funzione Termina(P, I) deve restituire TRUE se e solo se il programma P applicato all'input I termina, FALSE altrimenti”

Introduzione 66

Funzioni non calcolabili:Tassellatura di Wang

● Dato un insieme di piastrelle di Wang, decidere se esse possono ricoprire il piano– Esempio: le piastrelle seguenti possono ricoprire il piano (in

modo non periodico)

● E' stato dimostrato che è impossibile definire un algoritmo per decidere se un insieme dato di piastrelle può ricoprire il piano

Introduzione 67https://en.wikipedia.org/wiki/Wang_tile

Introduzione 68

...e poi dicono che l'informatica teorica non serve

Michael F. Cohen, Jonathan Shade, Stefan Hiller, and Oliver Deussen. 2003. Wang Tiles for image and texture generation. In ACM SIGGRAPH 2003 Papers (SIGGRAPH '03). ACM, New York, NY, USA, 287-294. DOI http://dx.doi.org/10.1145/1201775.882265

Introduzione 69

Idee chiave

● Cos'è l'informatica● Il concetto di algoritmo● Algoritmo vs programma● Macchina di Turing● Funzioni non calcolabili