Zusammenfassung der Ressource
Conceptos
preeliminares
- Cadenas, alfabetos
y lenguajes
- Simbolo
- Entidad
abstracta. (Letras,
símbolos)
- Cadena: secuencia finita
de simbolos yuxtapuestos
- Longitud: # de
símbolos que la
componen
- Cadena
vacía (E)
- Prefijos:
primeros
símbolos.
Sufijos: últimos
símbolos
- Concatenación: 1a
cadena seguida de
la 2a cadena sin
espacios
- Alfabeto:
conjunto
finito de
símbolos
- Lenguaje formal:
conjunto finito de
cadenas de símbolos
tomados de algun
alfabeto
- Grafos y árboles
- Grafo: G=(V,E)
- V= conjunto finito
de vértices (nodos)
- E= conjunto
de pares de
vértices
(aristas)
- Grafo dirigido
(digrafo) G=(V,E)
- V= conjunto finito de
vértices (nodos)
- E= conjunto de
pares
ordenados de
vértices
- Arbol: digrafo con:
- Existe un vértice
(raiz) sin
predecesores
- De ahi sale una
trayectoria a
cada vértice
- Cada vértice
(menos la raiz)
tienen un predesor
- Los sucesores de cada
vértice están ordenados (a
partir de la izquierda)
- Hijo: Sucesor
de un vértice
- Padre:
precesor de un
vértice
- Notación de
conjuntos
- Conjunto:
colección de
objetos sin
repetirse
- Especificando
sus
elementos
{0,1}
- Formador de
conjuntos
- {x|P(x)}, {x en A| P(x)}
- Operaciones
- unión: (AuB)
{x|x está en A o
está en B}
- intersección: {x|x
está en A y está en
B}
- Diferencia: (A-B) :
{x|x esta en A y no
está en B}
- Producto Cartesiano:
conjunto de pares
ordenados (a,b) | a está en
A y b en B
- Conjunto potencia de A.
(2^A): Todos los
subconjuntos de A.
- Pruebas
inductivas
- Sirve para
comprobar
teoremas
- Su principio:
- a) P(0), y. (se le
llama base)
- b) Paso
inductivo:
P(n-1) implica
que P(n) vale
para n>=1
- Relaciones
- binaria:
conjunto de
pares
- Primer componente
pertenece al dominio
- Segundo
componente
pertenece al
contradominio
- Propiedades
- 1. Reflexiva si aRa
para toda a en S
- 2. Irreflexiva si aRa es falsa
para toda a en S
- 3. Transitiva si aRb y
bRc implican aRc
- 4. Simétrica si aRb
implica bRa
- Asimétrica si aRb
implica que bRa es
falsa