Flashcards
Mat Disc
Cards in this deck (38)
- 1Notação Big - Oh (O Grande)sejam C e k constantes, f(x) é O(g(x)) se:
|f(x)| ≤ C|g(x)|,
sempre que x > k. - 2As constantes C e k na definição da notação O grande são chamadas de:parâmetros da relação f(x) é O(g(x)).
- 3Há uma forte ligação entre O grande e Ômega grande. Particularmente, f(x) é Ω(g(x)) se, e somente se:g(x) for O(f(x)).
- 4Dizemos que f(x) é Ω(g(x)) se houver constantes positivas C e k tais que:|f(x)| ≥ C|g(x)|,
sempre que x > k. - 5Dizemos que f(x) é Θ(g(x)) quando (definição):f(x) é O(g(x)) e Ω(g(x)).
- 6Quando f é Teta grande de g(x), dizemos, também, que:f(x) é da ordem de g(x).
- 7Note que f(x) é Θ(g(x)) se, e somente se (2 opções):i) g(x) for Θ(f(x));
e
ii) f(x) for O(g(x)) e g(x) for O(f(x)) - 8Podemos mostrar que f(x) é Θ(g(x)) se conseguirmos encontrar números reais positivos C1 e C2 e um real positivo k tal que:C1|g(x)| ≤ |f(x)| ≤ C2|g(x)|,
sempre que x > k.
Isso mostra que f(x) é O(g(x)) e é Ω(g(x)). - 9Suponha que f¹(x) e f²(x) sejam O(g(x)), então (f¹ + f²)(x) é:(f¹ + f²)(x) é O(g(x)).
- 10Suponha que f¹(x) seja O(g¹(x)) e f²(x) seja O(g²(x)), então (f¹ + f²)(x) é:(f¹ + f²)(x) é O(max(|g¹(x)|, |g²(x)|).
- 11Suponha que f¹(x) seja O(g¹(x)) e f²(x) seja O(g²(x)), então (f¹.f²)(x) é:(f¹.f²)(x) é O(g¹(x).g²(x)).
- 12Uma relação em um conjunto A é um subconjunto de A x A. Quantas relações existem em um conjunto de n elementos?Como um conjunto de n elementos A x A tem n² elementos e um conjunto com m elementos tem 2^m subconjuntos, então um conjunto de n elementos A x A tem 2^n² relações.
- 13Uma relação R em um conjunto A é chamada de ________ se (a, a) ∈ R para todo elemento a ∈ R.reflexiva.
x R x para todo x. - 14Uma relação R em um conjunto A é chamada de _______ se (b, a) ∈ R sempre que (a, b) ∈ R para quaisquer a, b ∈ R.simétrica.
Uma relação é simétrica sse
∀a∀b. a R b -> b R a. - 15Uma relação R em um conjunto A tal que para quaisquer a, b ∈ R, se (b, a) ∈ R e (a, b) ∈ R, então a = b é chamada de _______.anti-simétrica.
Uma relação é anti-simétrica sse
∀a∀b. a R b ^ b R a -> a = b. - 16Para que uma relação seja anti-simétrica, é preciso que haja uma relação tal que a = b?não necessariamente uma relação anti-simétrica precisa que haja uma relação tal que a = b.
Só é necessário que não haja NENHUMA relação tal que (b, a) ∈ R e (a, b) ∈ R. - 17Para que uma relação seja simétrica, é necessário que haja pelo menos uma relação (a, b) ∈ R tal que a != b?Não.
Só é necessário que TODOS os elementos (b, a) ∈ R tenham a simetria (a, b) ∈ R. - 18Uma relação R em um conjunto A é chamada de _______ se, sempre que (a, b) ∈ R e (b, c) ∈ R, então (a, c) ∈ R para todo a, b, c ∈ R.transitiva.
∀a∀b∀c. (a, b) ∈ R ^ (b, c) ∈ R -> (a, c) ∈ R - 19Reflexividade na matriz de relação:A relação é reflexiva se
𝑀[𝑖][𝑖] = 1 para todos os 𝑖. - 20Simetria na matriz de relação:Uma relação é simétrica se, sempre que
(𝑎, 𝑏) está na relação (𝑀[𝑖][𝑗] = 1),
também está (𝑏, 𝑎) (𝑀[𝑗][𝑖] = 1).
Verifique se 𝑀[𝑖][𝑗] = 𝑀[𝑗][𝑖] para todos os pares. - 21Antissimetria na matriz de relação:Uma relação é antissimétrica se, sempre que (𝑎, 𝑏) e (𝑏, 𝑎) estão na relação
(𝑀[𝑖][𝑗] = 1 e 𝑀[𝑗][𝑖] = 1), então 𝑎 = 𝑏 (𝑖 = 𝑗).
Verifique se 𝑀[𝑖][𝑗] = 1 e 𝑀[𝑗][𝑖] = 1 ocorre somente para 𝑖 = 𝑗. - 22Transitividade na matriz de relação:Uma relação é transitiva se, sempre que (𝑎, 𝑏) e (𝑏, 𝑐) estão na relação, (𝑎, 𝑐) também está.
Verifique se, para cada 𝑖, 𝑗, 𝑘,
se 𝑀[𝑖][𝑗] = 1 e 𝑀[𝑗][𝑘] = 1, então 𝑀[𝑖][𝑘] = 1 - 23Sera R a relação de um conjunto A em um conjunto B e S a relação de B em um conjunto C, a COMPOSTA de R e S (R ° S) é:a relação que consiste dos pares ordenados (a, c), nos quais a ∈ A e c ∈ C, e para os quais exista um elemento b ∈ B, tal que (a, b) ∈ R e (b, c) ∈ S.
Informal: é tipo uma relação transitiva mas entre dois conjuntos diferentes. EX:
R = {(1, 2), (2, 3), (4, 2), (3, 3), (1, 4)}
S = {(2, 3), (4 ,4), (3, 4), (1, 1)}
R ° S = {()} - 24Definição recursiva das potências de R (composta):- R¹ = R ;
- R^n+1 = R^n ° R;
exemplo:
R³ = R² ° R = (R ° R) ° R; - 25A relação R em um conjunto A é transitiva sse:R^n ⊆ R para n = 1, 2, 3...
- 26Definição de relações n-árias:Sejam A¹, A², A³, ..., An conjuntos. Uma relação n-ária desses conjuntos é um subconjunto de A¹ x A² x A³ x ... x An. os conjuntos A¹, A², A³, ..., An são chamados de domínios da relação e n é chamado de seu grau.
- 27Operador de seleção:Seja R uma relação n-ária e C uma condição que os elementos em R podem satisfazer. Então, o operador de seleção Sc leva a relação n-ária R à relação n-ária de todas as n-uplas de R que satisfaze à condição C.
- 28Dada uma relação R no conjunto A, seu Fecho Reflexivo é:Uma relação que contém R, é reflexiva e está contida em qualquer relação reflexiva que contenha R.
Ou seja, pode ser formada acrescentando todos os pares (a, a), com a ∈ A, que ainda não estejam em R.
R ∪ △,
em que △ = {(a, a) | a ∈ A} - 29Dada uma relação R no conjunto A, seu Fecho Simétrico é:A menor relação possível que contém R, é simétrica e está contida em qualquer relação simétrica que contenha R.
O fecho simétrico de uma relação pode ser construindo adicionando-se todos os pares ordenados da forma (b, a), em que (a, b) está na relação, e que ainda não estejam em R.
R ∪ R‾¹,
em que R‾¹ = {(b, a) | (a, b) ∈ R} - 30Dada uma relação R no conjunto A, seu Fecho Transitivo pode ser obtido (+ definição com grafo orientado):adicionando-se todos os pares ordenados que devam estar presentes e repetindo-se esse processo até que nenhum novo par seja necessário.
DEFINIÇÃO:
Seja R uma relação em um conjunto A. A relação de conectividade R* consiste nos pares (a, b), tal que existe um caminho de comprimento pelo menos um, de a a b em R. - 31Relações de Equivalência são:relações que são reflexivas, simétricas e transitivas.
- 32As relações de equivalência dividem conjuntos em:Classes disjuntas de elementos equivalentes.
- 33A notação a~b é frequentemente usada para indicar:que a e b são elementos equivalentes com referência a uma relação de equivalência particular.
- 34Seja R uma relação de equivalência em A. É chamado de classe de equivalência de a:o conjunto de todos os elementos que estão relacionados a um elemento a de A, indicada por [a].
[a] = {s | (a, s) ∈ R} - 35Uma relação R em um conjunto S é chamada de ordem parcial se for:reflexiva, anti-simétrica e transivita.
É chamado de poset e é indicado por
(S, R).
Os membros de S são chamados de elementos do poset. - 36Sobre os elementos em um poset e suas comparações:nem todo elemento de um poset é comparável.
Por exemplo no poset (Z+, |), os inteiros 3 e 9 são comparáveis, pois 3|9, mas os inteiros 5 e 7 são incomparáveis, pois 5 não divide 7, nem vice-versa. - 37O termo "ordem parcial" é usado quando (a)_________ O termo "ordem total" é usado quando (b)_________(a) há elementos no poset que são incomparáveis
(b) quaisquer dois elementos do conjunto são comparáveis. - 38(S, ≤) é um conjunto bem-ordenado se:se for um poset tal que ≤ seja uma ordem total e todo subconjunto não-vazio de S tenha um menor elemento.
Information
- Description
- 1º ano Matemática Flashcards on Mat Disc, created by Raiza Wunsch on 01/12/2024.
- Created by
- Raiza Wunsch
- Views
- 0
- Rating