Che materia stai cercando?

Riassunto fondamenti di informatica

Appunti di Fondamenti di informatica basati su appunti personali del publisher presi alle lezioni del prof. Mosca dell’università degli Studi di Milano Bicocca - Unimib, facoltà di Scienze matematiche fisiche e naturali. Scarica il file in formato PDF!

Esame di Fondamenti di informatica docente Prof. U. Moscato

Anteprima

ESTRATTO DOCUMENTO

Funzioni

Funzione

: associazione di un insieme A a un insieme B tale che a ogni elemento di B

corrisponda​ al​ più​ un​ elemento​ di​ A.

​ ​ ​ ​ ​ ​

​ ​ ​ ​ ​

Dominio di R

: insieme​ degli​ oggetti​ x tale​ che​ <x,​ y>​ R per​ qualche​ y.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Codominio di R

: insieme degli oggetti y tale che <x, y> R per qualche x. La funzione

inversa del codominio corrisponde al dominio (esiste solo se la funzione è iniettiva, quindi

l’inversa​ è suriettiva).

​ ​ ​

​ ​ ​

Funzione iniettiva

: detta​ anche​ funzione​ ingettiva

​ ​ ​ ​ ​

oppure​ iniezione,​ è una​ funzione​ che​ associa​ ad

​ ​ ​ ​ ​ ​ ​ ​

elementi​ distinti​ del​ dominio,​ elementi​ distinti

​ ​ ​ ​ ​

del​ codominio​ (uno​ e uno​ solo).​ S T tale​ che​ a

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

ogni​ elemento​ di​ S corrisponde​ al​ più​ un

​ ​ ​ ​ ​ ​ ​ ​

elemento​ di​ T.

​ ​

​ ​ ​ ​

Funzione s

uriettiva

: ogni​ elemento​ del

​ ​ ​ ​

codominio​ è immagine​ di​ almeno​ un​ elemento

​ ​ ​ ​ ​ ​ ​

del​ dominio.​ In​ tal​ caso​ si​ ha​ che​ l'immagine

​ ​ ​ ​ ​ ​ ​ ​

coincide​ con​ il​ codominio.

​ ​ ​

​ ​ ​

Funzione biunivoca

: La​ funzione​ è sia​ iniettiva​ sia

​ ​ ​ ​ ​ ​ ​ ​

suriettiva​ (il​ dominio​ coincide​ con​ il​ codominio).

​ ​ ​ ​ ​ ​

​ ​ ​

Funzione totale

: definita​ su​ ogni​ elemento​ del

​ ​ ​ ​ ​ ​

dominio​ (es.​ sottrazione​ in​ Z).

​ ​ ​ ​

​ ​ ​

Funzione parziale

: non​ è definita​ su​ ogni​ elemento​ del​ codominio​ (es.​ divisione​ in​ N).

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​

Punto fisso

: ogni​ valore​ dato​ a quella​ funzione​ corrisponde​ a un​ unico​ valore,​ l’elemento

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

coincide​ con​ la​ sua​ immagine.

​ ​ ​ ​

​ ​ ​

Funzione composta

: f о g,​ applicazione​ di​ una​ funzione​ g a una​ funzione​ f.​ Se​ l’arietà​ della

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

funzione​ da​ applicare​ è maggiore,​ non​ è possibile​ applicarla.​ Quindi,​ se​ una​ funzione​ è in

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

NxN​ non​ va​ mai​ applicata​ a funzioni​ in​ N.

​ ​ ​ ​ ​ ​ ​ ​ ​

La​ funzione​ f deve​ avere​ come​ codominio​ un​ sottoinsieme​ del​ dominio​ di​ g.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Una​ funzione​ è invertibile solo​ se​ la​ sua​ inversa​ è una​ funzione,​ quindi​ se​ è iniettiva;​ l’inversa

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

è​ totale​ se​ f è suriettiva​ (e​ viceversa).

​ ​ ​ ​ ​ ​ ​ ​ ​

Principio della piccionaia

: se A e B sono due insiemi finiti e |A| > |B|, non esiste alcuna

funzione​ iniettiva​ totale​ da​ A a B.

​ ​ ​ ​ ​ ​ ​ ​ ​

Arietà di una funzione o relazione

: numero degli insiemi su cui è definita la funzione o

relazione​ (unaria,​ binaria​ ecc.).

​ ​ ​

Strutture​ relazionali,​ grafi​ e ordinamenti

​ ​ ​ ​ ​

DAG

: grafo diretto (frecce) senza cicli, formato da coppie ordinate di punti. Il numero di archi

uscenti/entranti​ in​ un​ nodo​ è detto​ grado​ di​ ingresso/uscita.

​ ​ ​ ​ ​ ​ ​ ​ ​

Grafo connesso

: ogni coppia di vertici è connessa da un cammino, fortemente connesso se

esiste​ un​ cammino​ tra​ ogni​ coppia​ di​ vertici​ (quindi​ anche​ nel​ verso​ opposto).

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Cammino

: sequenza di frecce orientate per raggiungere un nodo a partire da un altro nodo.

La​ lunghezza​ è pari​ al​ numero​ di​ nodi​ - 1.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Semicammino

: cammino​ che​ non​ tiene​ conto​ della​ direzione​ delle​ frecce.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​

Ciclo (semiciclo)

: cammino​ (semicammino)​ dove​ il​ nodo​ di​ partenza​ è lo​ stesso​ di​ arrivo.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Albero

: un DAG con un nodo sorgente detto padre, e nodi figli. I nodi privi di figli sono detti

foglie. Un cammino è il percorso da un nodo per raggiungerne un altro, la lunghezza di un

cammino​ è detta​ profondità​ mentre​ la​ profondità​ massima​ è detta​ altezza.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Albero binario

: ogni nodo ha al massimo due figli. Può essere attraversato in profondità, in

ordine​ anticipato,​ simmetrico​ o posticipato.

​ ​ ​ ​ ​

Pre-ordine

: relazione​ binaria,​ riflessiva​ e transitiva.

​ ​ ​ ​ ​ ​ ​

Quasi-ordine

: relazione​ binaria,​ irriflessiva​ e transitiva.

​ ​ ​ ​ ​ ​ ​

Partially Ordered SET

: struttura relazionale (insieme di coppie) con relazione di ordine

parziale (transitivo, antisimmetrico e riflessivo). Il semiordinamento è anche un ordinamento

o​ ordine​ totale​ se​ x = y,​ oppure​ <x,​ y>​ R,​ oppure​ <y,​ x>​ R (tricotomia).

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

∈ ∈

- Riflessivo

: <x,​ x>​ R.

​ ​ ​ ​ ​ ​

- Ogni​ nodo​ ha​ un​ cappio,​ nella​ tabella​ le​ x sono​ sulla​ diagonale.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

- Antisimmetrico

: <x,​ y>​ R e <y,​ x>​ R (quindi​ x = y).

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

∈ ∈

- Ogni freccia ha solo una punta, e nella tabella non ci sono x simmetriche

rispetto​ alla​ diagonale.

​ ​

- Transitivo

: <x,​ y>​ R e <y,​ z>​ R quindi​ <x,​ z>​ R.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

∈ ∈ ∈

- Se​ s è collegato​ a t,​ t è collegato​ a r,​ allora​ s è collegato​ a r.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Copertura

: y è una copertura di x se non ci sono elementi che si frappongono nella relazione

di​ ordinamento.

​ ​ ​ ​

Elementi estremali

: ​

- Minimale/minimo

: non​ esiste​ un​ elemento​ minore​ di​ s.

​ ​ ​ ​ ​ ​ ​ ​

- Massimale/massimo

: non​ esiste​ un​ elemento​ maggiore​ di​ s.

​ ​ ​ ​ ​ ​ ​ ​

Nei​ sottoinsiemi​ di​ un​ grafo:

​ ​ ​ ​

- Minorante

: tutti​ gli​ altri​ elementi​ sono​ maggiori​ o uguali​ a s.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

- Maggiorante

: tutti​ gli​ altri​ elementi​ sono​ minori​ o uguali​ a s.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​

- Massimo minorante

: il​ maggiore​ tra​ i minoranti.

​ ​ ​ ​ ​ ​ ​

- Minimo maggiorante

: il minore tra i maggioranti. Un ordinamento è detto buono se ha

un​ minimo.

Reticolo

: poset in cui per ogni coppia ordinata esiste un massimo minorante (meet, e un

⊓)

minimo maggiorante (join Un reticolo è completo se ogni sottoinsieme ha un minimo e un

⊔).

massimo,​ è limitato se​ esistono​ massimo​ e minimo.

​ ​ ​ ​ ​ ​ ​ ​ ​

Proprietà​ di​ un​ reticolo​ distributivo (devono​ valere​ per​ tutte​ le​ coppie):

​ ​ ​ ​ ​ ​ ​ ​ ​ ​

- a​ (b​ c)​ = (a​ b)​ (a​ c)

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

⊔ ⊓ ⊔ ⊓ ⊔

- a​ (b​ c)​ = (a​ b)​ (a​ c)

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

⊓ ⊔ ⊓ ⊔ ⊓

- Se​ un​ reticolo​ ha​ un​ nodo​ in​ mezzo,​ non​ è mai​ distributivo.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​

Chiusura transitiva

: la​ più​ piccola​ relazione​ transitiva​ R’​ su​ S che​ contiene​ R.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Diagramma di Hasse

: rappresenta graficamente relazioni d’ordine su un poset. Un elemento

viene collocato sotto un altro solo se gli appartiene; ogni elemento avrebbe un cappio

(riflessività) ma può essere omesso, come gli archi dati dalle relazioni transitive; due

elementi​ sono​ uniti​ se​ uno​ è una​ copertura​ dell’altro.

​ ​ ​ ​ ​ ​ ​ ​ ​

Le relazioni possono essere rappresentate tramite grafo orientato, grafo bipartito e matrice

booleana. ​

Complemento

: un elemento è detto complemento se a a' = 1 e a a' = 0, cioè per la coppia

⊔ ⊓

elemento-complementare il join e il meet corrispondano al massimo e il minimo. Se non c’è

un​ massimo​ o un​ minimo​ nel​ grafo,​ gli​ elementi​ non​ hanno​ un​ complemento.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Induzione​ e ricorsione

​ ​ ​

Induzione

: serve per specificare procedimenti di calcolo su strutture, e per provare proprietà

matematiche​ su​ insiemi​ di​ numeri.

​ ​ ​ ​

Se la proprietà x è vera per un valore piccolo n, allora è vera anche per n + 1 e

conseguentemente​ per​ ogni​ n.

​ ​ ​

L’induzione si risolve dimostrando che la proprietà è vera per n, poi ponendo le stesse

condizioni a n + 1 (in caso di sommatoria, è sufficiente che arrivi a n + 1). Con le opportune

semplificazioni si torna alla proprietà di base, e sapendo che essa è verificata per n allora è

verificata​ per​ tutti​ i valori​ di​ n.

​ ​ ​ ​ ​ ​ ​

Ricorsione

: presuppone un caso base e un passo ricorsivo. Nel passo ricorsivo viene

chiamata la funzione finché non si raggiunge il caso base. Per esempio, il fattoriale di 100 è il

fattoriale​ di​ 99​ moltiplicato​ per​ 100;​ così​ via​ finché​ il​ numero​ non​ arriva​ a 1.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Esempi​ definizioni​ induttive​ e ricorsione:

​ ​ ​ ​ ​

- La lunghezza di una stringa vuota è 0; la lunghezza di una stringa non vuota (a+b) è

ε

1​ sommato​ alla​ lunghezza​ di​ b (a​ è un​ carattere).

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​


PAGINE

7

PESO

302.81 KB

AUTORE

skitos

PUBBLICATO

5 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
Docente: Moscato Ugo
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher skitos di informazioni apprese con la frequenza delle lezioni di Fondamenti di informatica e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Milano Bicocca - Unimib o del prof Moscato Ugo.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Fondamenti di informatica

Appunti logica proposizionale e predicativa
Appunto
Paradigmi Concorrenti - Appunti
Appunto
Algoritmi e Strutture Dati con domande riassuntive
Appunto
Appunti sulle matrici
Appunto