Che materia stai cercando?

Riepilogo di Metodi Matematici per Informatica Appunti scolastici Premium

Appunti di Metodi matematici per l'informatica basati su appunti personali del publisher presi alle lezioni della prof.ssa Mantaci dell’università degli Studi di Palermo - Unipa, facoltà di Scienze matematiche fisiche e naturali, Corso di laurea in informatica. Scarica il file in formato PDF!

Esame di Metodi Matematici per L'Informatica docente Prof. S. Mantaci

Anteprima

ESTRATTO DOCUMENTO

6.3: Per contrapposizione: dobbiamo negare la tesi e l'ipotesi e la negazione della tesi

diventa l'ipotesi e la negazione dell'ipotesi diventa la tesi

Es. P = x ≥ 9 e Q = x+3 ≥ 12 diventano P = x+3 ≥ 12 e Q = x ≥ 9

se poniamo per esempio x=10 diventa 10+3≥12 e 10≥9, P e Q sono vere;

7. Forma esplicita di un insieme: A={1,2,3,....n}1;

8. Forma implicita di un insieme: A = {P(x) | condizione di x }

n

9. I sottoinsiemi di un insieme sempre in numero 2 ed ogni insieme ha come

sottoinsieme l'insieme vuoto (0) e se stesso

10. Operazioni tra insiemi:

a. L'intersezione di due insiemi è data dagli elementi in comune dei due insiemi

presi sono una volta e si scrive A ;

∩B

b. L'unione di due insiemi è data dagli elementi sia di A che di B presi insieme e si

scrive A B c. La differenza A-B è data da tutti gli elementi di A non in comune con B

Esempio: nei numeri naturali IN

A=numeri dispari e B=numeri pari

A∩B=0, cioè insieme vuoto

A B= IN, cioè tutto l'insieme dei naturali

A-B=numeri dispari

B-A=numeri pari

A-B è detta anche complementare di B rispetto ad A

11. Prodotto cartesiano: dati due insieme A e B il prodotto cartesiano AXB è l'insieme

formato da tutte le coppie (a,b) con a€A e b€B

es: A = {5,6,4} B= {9,5}

AXB={(5,9),(5,5),(6,9),(6,5),(4,9),(4,5)}

12. Relazioni tra insiemi: la relazione R tra due insiemi A e B è un sottoinsieme del

prodotto cartesiano AXB.

Le relazioni possono essere d'equivalenza o d'ordine

Le relazioni sono d'equivalenza quando godono delle proprietà:

-Riflessiva: aRa (a è in relazione con a)

-Simmetrica: aRb => bRa (a è in rel con b e b è in rel con a)

-Transitiva: aRb e bRc => aRc (se aRb e bRc allora anche aRc)

Esempio: A = {1,2,3,4}

R1 = {(1,1),(2,2),(3,3),(4,4)} → riflessiva

R2 = {(1,2),(2,1),(1,3),(3,1)} → simmetrica

R3 = {(1,2),(2,4),(1,4)} → transitiva

Le relazioni d'ordine invece hanno queste tre proprietà

-Riflessiva: aRa (a è in relazione con a)

-Antisimmetrica: aRb e bRa <=> a=b(a è in rel con b e b è in rel con a solo se a=b)

-Transitiva: aRb e bRc => aRc (se aRb e bRc allora anche aRc)

Esempio: A = {1,2,3,4}

R1 = {(1,1),(2,2),(3,3),(4,4)} → riflessiva

R2 = {(2,2),(4,4)} → antisimmetrica

R3 = {(1,2),(2,4),(1,4)} → transitiva

Ordine parziale

{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(2,3),(1,3)}

riflessiva = si

antisimmetrica = si

transitiva = si (1,2),(2,3),(1,3)

Ordine totale

{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(1,3),(3,1),(1,4),(4,1),(2,3),(3,2),(2,4),(4,2),(3,4),

(4,3)} → tutte e tre le proprietà esistono e vengono presi tutti i valori

L'ordine si dice stretto nel caso in cui le proprietà di cui gode la R sono solo

asimmetrica cioè aRb => ¬ (bRa) e transitiva

es. {(1,3),(3,4),(1,4)}

| Preso un elemento a dell'insieme A, si definisce classe d'equivalenza un

sottoinsieme che contiene almeno l'elemento a stesso e si indica con [a] |

Le classi d'equivalenza devono

Essere dei sottoinsiemi non vuoti

Essere a 2 a 2 disgiunti, cioè devono dare un'intersezione vuota

La loro unione deve formare tutto l'insieme

13. Funzioni iniettive, suriettive e biunivoche.

I: quando ad ogni elemento di A corrisponde uno ed un solo elemento di B

S: quando ogni elemento di B è immagine di almeno un elemento di A

B: quando sono sia I che S

Condizioni

Iniettive |A|≤ |B| cioè cardinalità di A ≤ quella di B

Suriettive |A|≥|B| cioè cardinalità di A ≥ quella di B

Biunivoche |A|=|B| cioè cardinalità di A = quella di B

Cardinalità = numero degli elementi di un insieme

14. Principio di induzione e funzioni ricorsive:

Il principio di induzione serve a verificare che se per un determinato valore

assegnato ad n (per esempio 1) allora il predicato deve essere vero per (n+1)

Si dimostra ponendo due casi:

1. base dove, in genere, n=1, quindi basta sostituire 1 alla variabile n

2. per induzione, ponendo n=n+1

Esempio:

A = 5·3n + (−3)n.

n

per n=1 dimostrare che A =12

n

per n≥2 dimostrare che vale 9a n−2

quindi primo caso 5*3*1+(-3)*1 = 15-3 = 12

n n

secondo caso, aumentiamo di 1 la n in 5·3 + (−3) e diventa:

(n+1)

(n+1) (n+1) (n+1)

5*3 +(-3) = [3 ](5-1)= 4*3

aumentiamo di 1 la n in 9a e diventa 9a = 9a

n−2 n−2+1 n−1

n n (n-1) (n-1)

ci troviamo a da A = 5·3 + (−3) , quindi diventa 5*3 +(-3) =

n−1 n

(n-1) (n-1)

=3 (5-1)=4*3 (n-1)

ora sostituiamo in 9a il valore 4*3

n−1

(n-1) 2 2 (n-1) n-1+2 2 n+1

9(4*3 ) = 3 (2 *3 )=3 *2 =4*3

Nel secondo caso dell'induzione dobbiamo dimostrare che, oltre il caso base, il

nostro predicato sia vero per valori n-1 e n-2 (successioni ricorsive)

Una successione ricorsiva e una successione che ripete le operazioni precedenti per

ogni valori n e la più classica successione ricorsiva e la Successione di Fibonacci:

0 1 1 2 3 5 8 13 21 34 ….

dove fissati 0 e 1 come valori iniziali, gli altri valori vengono dati dalla somma dei

due precedenti

f(n)=0 se n = 0

f(n)=1 se n = 1

f(n)=(n-1)+(n-2) se n≥2 e ripetiamo sempre quest'operazione all'aumentare di n

Stesso discorso per la Torre di Hanoi dove noi dobbiamo ricorsivamente eseguire questi tre

passaggi:

Spostare n-1 dischi da A in B usando C come appoggio

Spostare il disco grande in C

Spostare n-1 dischi da B in C usando A come appoggio

e ripetere questi tre step fino al completamento del gioco


ACQUISTATO

1 volte

PAGINE

8

PESO

295.63 KB

AUTORE

astrex

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
Università: Palermo - Unipa
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher astrex di informazioni apprese con la frequenza delle lezioni di Metodi Matematici per L'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à Palermo - Unipa o del prof Mantaci Sabrina.

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 Corso di laurea in informatica

Informatica teorica: sintesi
Appunto
Sintesi basi dati
Appunto
Sintesi del Corso di Sistemi Operativi
Appunto
Riepilogo JAVA Prima Parte
Appunto