Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Programacion Concurrente > Parcial 1 > Flashcards

Parcial 1 Flashcards

1
Q

Abstraccion

A

Acto mental en el que se aisla conceptualmente una propiedad o funcion concreta de un objeto, y se piensa que es, ignorando otras propiedades del objeto en cuestion. Me abstarigo de la implementacion.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Caracteristica reactiva de sistemas concurrentes

A

Sistema reactivo es aquel que reacciona permanentemente a cambios del ambiente y otros procesos.Suele no requerirse que terminen. Suelen no computar resultados.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Deadlock

A

Dos o mas procesos (o hilos) esperan mutuamente el avance del otro (o incluso el mismo hilo espera que avance el mismo).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Estados de un proceso

A

New: Proceso siendo creado.
Running: Proceso se esta ejecutando.
Waiting: Proceso esta esperando que se cumpla algun otro evento.
Ready: Proceso esta pronto para ejecutar, esperando por CPU.
Terminated: Proceso ha terminado.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Exclusión Mutua

A

Propiedad para controlar concurrencia, requisito de que un hilo en ejecución nunca entre en su sección crítica al mismo tiempo que otro hilo la esta ejecutando.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Interleaving

A

Intercalacion entre las acciones atomicas que componen un proceso concurrente, es decir entre las acciones atomicas que ejecutan los hilos.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Livelock

A

Dos o mas procesos no pueden avanzar en su ejecucion porque continuamente responden a los cambios en el estado de otros procesos. Los procesos se ejecutan simultaneamente sin realizar trabajo util, respondiendo a cambios de otros procesos. Esta es la diferencia con un deadlock, porque en este caso los procesos no estan en waiting, mientras que en deadlock los procesos estan en waiting.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Proceso

A

Unidad de actividad que se caracteriza por la ejecucion de una secuencia de instrucciones, un estado actual y un conjunto de recursos del sistema asociados.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Proceso vs programa

A

Un proceso es una actividad de cierto tipo que contiene un programa, entradas/salidas y estados.

Es una unidad de actividad que se caracteriza por la ejecución de
una secuencia de instrucciones, un estado actual, y un conjunto
de recursos del sistema asociados

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Sistemas críticos

A

Sistemas cuyas fallas pueden ocasionar daños de gran importancia.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Starvation (inanición)

A

Uno o mas procesos (o hilos) quedan esperando indefinidamente un mensaje o liberacion de un recurso.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Limitaciones del testing

A

El testing puede confirmar la presencia de errores pero
nunca garantizar su ausencia.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Control de procesos

A

Registro especial BCP (bloque de control de proceso) donde el OS agrupa toda la info que necesita conocer respecto a un proceso particular.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Info del control de procesos

A

Identificador del proceso (Process Identificator -PID-, de sus siglas en Inglés).
•Estado del proceso. Por ej. listo, en espera, bloqueado.
•Contador de Programa: Dirección de la próxima instrucción a ejecutar.
•Valores de registro de CPU. Se utilizan también en el cambio de contexto.
•Espacio de direcciones de memoria.
•Prioridad en caso de utilizarse dicho algoritmo para planificación de CPU.
•Lista de recursos asignados (incluyendo descriptores de archivos y sockets abiertos).
•Estadísticas del proceso.
•Datos del propietario (owner).
•Permisos asignados.
•Signals pendientes de ser servidos. (Almacenados en un mapa de bits)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Hilo

A

Permiten realizar varias tareas a la vez (concurrentemente). Distintos hilos comparten recursos entre si, como el espacio de memoria, archivos abiertos, etc.
Estos recursos que comparten los hilos son en conjunto conocidos como proceso.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Hilos vs procesos

A

Procesos son indep, llevan bastante info de estados, e interactuan solo por mecanismos del sistema. Cambiar de un proceso a otro es “costoso” ya que el sistema genera un tiempo desperdiciado para cambiar de proceso. El nucleo o kernel debe intervenir en la comunicacion entre procesos.
Los hilos en cambio comparten sus recursos de forma directa. Como pertenecen a un mismo proceso, cambiar de un hilo a otro es practicamente instantaneo. Son “baratos”. Su comunicacion no requiere invocar al nucleo.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Estados de un hilo

A

New: Hilo creado pero no inicializado. Le falta el start.
Running: Hilo en ejecución.
Blocked: Hilo blockeado, esperando por algun recurso para continuar.
Waiting: Similar al bloqueo, el hilo espera por la liberacion de un recurso para despertarse.
Terminated: Hilo terminó su ejecución.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Que tiene un hilo

A
  • Estado.
  • Contexto del procesador.
    * Punto en el que estamos ejecutando, la instrucción.
    * Se usa para reanudar un hilo que fue interrumpido con, para poder continuar la ejecución del hilo.
  • Pila de ejecución, donde se irá metiendo y sacando instrucciones. (Lugar donde almacenaremos las instrucciones que van a ser ejecutadas).
  • Espacio de almacenamiento estático donde almacenará las variables.
  • Acceso a los recursos de la tarea,
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Multiprogramación, Multiprocesamiento y procesamiento distribuido

A

Multiprogramacion:Gestion de varios procesos dentro de un sistema mono-procesador. No se logra procesamiento en paralelo y se produce sobrecarga en el intercambio de procesos, pero se eficientiza el utso del procesador en general.

Multiprocesamiento: Gestión de varios procesos dentro de un sistema multi-procesador.

Procesamiento distribuido: Gestion de varios procesos, ejecutandose en sistemas de computadores multiples y distribuidos.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Donde se puede presentar concurrencia?

A

Multiples aplicaciones
Apicaciones estructuradas: conjunto de hilos concurrentes
Estructura del sistema operativo: conjunto de procesos e hilos manejan el SO.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Tipos de interaccion entre procesos

A

Tres casos:
procesos no tienen conocimiento de los demas
procesos tienen conocimiento indirecto de los demas
procesos tienen conocimiento directo de los demas

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Competencia entre procesos por los recursos

A

Los procesos concurrentes entran en conflicto cuando
compiten por el uso del mismo recurso.

La ejecución de un proceso puede influir en el comportamiento
de los procesos que compiten.

Al haber procesos en competencia, surge la necesidad de la exclusion mutua, es decir que solo un procesos pueda acceder a una seccion critica en un momento dado.

Sin embargo, hacer cumplir la exclusion mutua puede llevar a interbloqueos.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Seccion critica

A

Parte de un programa que accede a un recurso critico, es decir un recurso no compartible, por lo que si se accediera en simultáneo por más de un hilo llevaría a problemas de concurrencia y por lo tanto fallas en la ejecucion.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Requisitos para exclusión mutua

A

Solo un hilo tiene permiso para entrar a seccion critica por vez.
Hilo (proceso) no puede solicitar acceso a seccion critica para luego demorarse indefinidamente.
No se debe suponer sobre velocidad relativa de los procesos o numero de procesadores.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Posibilidades al ejecutar primitiva SEND de un proceso

A

Proceso emisor se bloquea hasta que recibe el mensaje o no se bloquea.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Posibilidades al ejecutar primitiva RECEIVE en un proceso

A

Si previamente se envio un mensaje, este se recibe y continua la ejecucion.
Si esto no sucede, entonces el proceso se bloquea hasta que llegue un mensaje o continua, abandonando intento de recepcion.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Tipos de combinaciones de procesos

A

1) Envio y recepcion bloqueantes
2) Envio no bloqueante, recepcion bloqueante
3) Envio no bloqueante, recepcion no bloqueante

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Programacion paralela

A

Muchas instrucciones se ejecutan en simultaneo. Para problemas grandes, a menudo se pueden dividir en varios mas pequeños, que se resuelven en simultaneo.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Programacion concurrente

A

Composicion de computos que avanza colaborativamente para garantizar un resultado u operacion. Se deben coordinar las secuencias de las interacciones o comunicaciones entre diferentes computos, como asi tambien el acceso a los recursos que se comparten.

30
Q

Operacion atomica

A

Aquellas que siempre se ejecutan hasta terminar por completo. No pueden estas parcialmente completas

31
Q

Condicion de carrera

A

Cuando el resultado de la ejecucion de varios hilos concurrentes puede ser correcto o incorrecto dependiendo de como se entrelacen. Basicamente se cuando varios hilos leen, modifican y escriben una misma variable, probablemente la corrompan.

32
Q

Metodos y sentencias Synchronized

A

Todos los objetos tienen un lock asociado, que se puede adquirir o liberar con esta primitiva.
Se puede poner en el metodo (exclusion mutua), en este caso si se esta ejecutando el metodo sync, no se podra ejecutar ningun otro metodo sync del mismo objeto o clase (en caso metodo sync estatico).
O puede ponerse en bloque de codigo (seccion critica).
Si un thread ejecuta synchronized y el lock esta tomado, se suspende hasta que este se libera y puede continuar.

33
Q

Comunicacion entre hilos

A

Hay metodos que permiten esto, que si o si deben ejecutarse dentro de un bloque synchronized:

wait(): le dile al hilo de llamada que abandone el bloqueo y se vaya a dormir hasta que algun otro hilo ejecute notify().

notify(): Despierta a un hilo que invoco wait() en el mismo objeto. Cabe aclarar que notify() no abandona el lock, solo despierta al otro hilo.

notifyAll(): despierta a todos los hilos que llamaron a wait().

34
Q

Semaforo

A

Este objeto tiene un contador que protege el acceso a uno o mas recursos compartidos, no necesariamente en el mismo bloque. Tiene una lista/cola de procesos, en la que se incluyen los procesos suspendidos a la espera de su cambio de estado.

Pueden ser binarios, es decir solo toman valores 0 y 1, o no binarios, que pueden tomar cualquier valor Natural.

Semaforo=0 lock cerrado
Semaforo >0 lock abierto

Metodos basicos:
acquire() y release()

Si esta en 0 y aparece un acquire(), manda a ese hilo a dormir hasta que el semaforo sea mayor a 0.

A diferencia del lock, el semaforno no tiene owner (dueño), el contador va controlando si el semaforo permite pasar a un hilo o no.

35
Q

Reentrant lock

A

Esta clase provee bloqueo de exclusion mutua con el mismo comportamiento que synchronized, solo un hilo por vez puede tener el bloqueo en un momento dado.

Es importante envolver el bloque de codigo en try catch finally para asegurar que se libera el lock.

Metodos basicos:
lock(), unlock(), isLocked(), tryLock(), isLocked(), entre otros.

36
Q

ReadWriteLock

A

Es una interface, que me permite manejar dos bloqueos, uno de lectura y otro de escritura.

Es importante envolver el codigo en try-catch-notify para asegurar que se libere el lock.

La idea es que generalmente es seguro leer variables en simultaneo, siempre y cuando no se las modifique.

El bloqueo de lectura puede ser mantenido por varios hilos a la vez, pero cuando uno tiene el de escritura todos los demas esperan.

37
Q

CountDownLatch

A

Es una clase. Lo que hace es que uno o mas hilos esperen hasta que se realicen determinadas operaciones. Se inicializa con un valor entero que representa el numero de acciones a esperar.

Metodos basicos:

await(): hilo que lo ejecuta espera.

countDown(): hilo lo ejecuta al terminar una acción y decrementar el contador.

Cuando el contador llega a 0, la clase despierta a todos los hilos que ejecutaron await().

38
Q

CyclicBarrier

A

Es una clase. Se utiliza para sincronizar dos o mas hilos en un punto determinado, similar a CountDownLach, pero mas poderosa.
Se inicia con el numero de hilos que se sincronizaran en un punto determinado.

Cuando un hilo llegas a ese punto, llama al metodo await() para esperar a los demas. Cuando el ultimo hilo llama a await(), la clase despierta a todos los hilos y continuan su trabajo.

La ventaja es que le podemos pasar un Objeto ejecutable como parametro al inicializarla, entonces ejecutara este objeto como un hilo cuando todos los hilos hayan llegado al punto en comun.

39
Q

Sistemas reactivos

A

Sistemas informaticos que responden continuamente a su entorno a una velocidad determinada por este. Realizan procesos no terminados basados en estados que estan interactuando con el entorno para habilitar, aplicar o prevenir cierto comportamiento en el mismo. A menudo realizan procesos en paralelo. Se diferencian de los sistemas transformacionales, que no interactuan con el ambiente ni responden a estimulos.

40
Q

Arquitectura dirigida por eventos (EDA)

A

Es un patron de arquitectura de software impulsado por la produccion, deteccion, consumo y reaccion a eventos. Un sistema dirigido por eventos posee emisores y consumidores de eventos.
Sistemas EDA estan diseñados para entornos no predecibles y asincronos.

41
Q

Símbolo

A

Es una entidad abstracta, que no se va a definir, pues se toma como axioma. Puede ser una letra, numero, caracter, etc.

42
Q

Vocabulario o alfabeto

A

Es un conjunto finito de simbolos, no vacio. Se define por enumeracion de los simbolos que contienen.

43
Q

Cadena

A

Es una secuencia finita de simbolos de un determinado alfabeto.

Longitud de una cadena: numero de simbolos que contiene.

Existe la cadena vacia, se denota con lambda.

Se pueden concatenar cadenas, obviamente.

44
Q

Universo del discurso

A

El conjunto de todas las cadenas que se pueden formar con los simbolos de un alfabeto V se denomina universo del discurso de V y se representa W(V). Evidentemente este conjunto es infinito.

Clausura positiva de un alfabeto: esta formada por el universo del discurso del alfabeto sin contar la cadena vacia.

Clausura o cierre de un alfabeto: esta formada por el universo del discurso del alfabeto, incluyendo la cadena vacia.

45
Q

Lenguaje

A

Se denomina lenguaje sobre el alfabeto V a un subconjunto del universo del discurso.

Tambien se puede definir como un conjunto de cadenas de un determinado alfabeto.

Los lenguajes se definen por las propiedades que cumplen las cadenas contenidas en estos.

El lenguaje vacio existe y se denota con una fi.

46
Q

Gramática

A

Es un ente formal para especificar, de manera finita, el conjunto de cadenas de simbolos que constituyen un lenguaje.

Es una cuadrupla G=(VN,VT,P,S) donde:

VN=conjunto finito de simbolos no terminales (estados).
VT=conjunto finito de simbolos terminales (eventos).
P=conjunto de producciones o reglas de derivacion.
S=simbolo inicial y pertenece a VN.

Todas las cadenas del lenguaje definido por la gramatica estan formados con simbolos del VT.

El VN es el conjunto de simbolos introducidos como elementos auxiliares para la definicion de la gramatica, y que no figuran en las cadenas del lenguaje.

El simbolo inicial S es un simbolo no terminal a partir del cual se aplican las reglas de derivacion de la gramatica para obtener las distintas cadenas del lenguaje.

La producciones P son las reglas que se aplican desde S para obtener las cadenas del lenguaje.

47
Q

Autómata

A

Es una construccion logica que recibe una entrada y produce una salida en funcion de todo lo recibido hasta ese instante.

Es una quintupla A=(E,S,Q,f,g) donde:

E=conjunto de entradas o vocabulario de entrada.
S=conjunto de salidas o vocabulario de salida.
Q=conjunto de estados.
f: ExQ –> Q es la funcion de transicion o funcion del estado siguiente, y para un par del conjunto ExQ devuelve un estado Q.
g:ExQ–>S es la funcion de salida, y para un par del conjunto ExQ devuelve un simbolo de salida del conjunto S.

f y g pueden representarse mediante tablas:

https://drive.google.com/file/d/1AfTgKiYMvTIDV78dxJfvQ_8lXVn6_OcB/view?usp=sharing

Ojo: En las diapositivas siguientes, donde se hacen ejercicios de obtener la gramatica a partir de un autómata, se utiliza esta forma para definir al automata (similar pero no es exactamente la misma):

Quintupla A = (Q, V, δ, q0, F) donde:

Q: Conjunto de estados
V: Vocabulario o alfabeto de entrada
δ: Q x V -> Q funcion de transicion
q0: Estado inicial
F: Conjunto de estados finales.

Esta segunda definicion es mas facil de entender, y es la que se aplica en los ejercicios.

48
Q

Notacion de elementos (VT,VN,V,Cadenas terminales, Cadenas)

A

VT: sus elementos se representan por letras minusculas de comienzo de abecedario, operadores, caracteres, digitos del 0 al 9, palabras reservadas de programacion.

VN: sus elementos se representan por letras mayusculas de comienzo de abecedario, excepto el simbolo inicial que va con S. Tambien por nombres en minuscula, pero entre parentesis angulares.

Vocabulario: elementos indiferenciados de VT yVN se denotan con letras mayusculas del final del alfabeto.

Cadenas terminales: cadenas compuestas unicamente por simbolos terminales se representan con letras minusculas del final del alfabeto.

Cadenas: las cadenas que contienen simbolos terminales y no terminales indiferenciados se representan con letras minusculas griegas.

49
Q

Algoritmo para obtener gramatica regular desde automata finito

A

1) Asociar a estado incial del automata el simbolo S.

2) Asociar a cada estado del automata un simbolo no terminal (A,B,C).

3) Para cada transicion definida en el automata δ (ei , a) = ej, agregar un elemento al conjunto de producciones, la producción A → 1B, siendo A y B los símbolos no terminales asociados a ei y ej respectivamente. Si ej es un estado final, agregar también la producción A → a.

4) Si el estado inicial es tambien final, agregar la produccion S → ε.

50
Q

Jerarquia de gramaticas

A

•Gramáticas de tipo 0:
También llamadas gramáticas no restringidas o gramáticas con estructura de frase.

•Gramáticas de tipo 1:
También llamadas gramáticas sensibles al contexto

•Gramáticas de tipo 2:
También se denominan gramáticas de contexto libre o libres de contexto

•Gramáticas de tipo 3

También denominadas regulares o gramáticas lineales a la derecha comienzan sus reglas de producción por un símbolo terminal, que puede ser seguido o no por un símbolo no terminal

51
Q

Correspondencia entre lenguajes y gramaticas

A

Gramatica tipo 0 genera lenguaje tipo 0.

Gramatica tipo 1 genera lenguaje tipo 1.

Gramatica tipo 2 genera lenguaje tipo 2.

Gramatica tipo 3 genera lenguaje tipo 3.

52
Q

Expresiones regulares

A

Es una herramienta para describir lenguajes de tipo 3 o regulares.
Son metalenguajes para describir lenguajes regulares.

53
Q

Operaciones con lenguajes regulares

A

Union o alternativa:
L1 U L2 = {x/x ∈ L1 🇻 x ∈ L2}

Concatenacion:
L1L2={x1x2/x1 ∈ L1 ∧ x2 ∈ L2}

Potencia de un lenguaje: caso particular de la anterior, concatenas un lenguaje consigo mismo.

Cierre u operacion estrella:
L*={Φ} U {L} U {LL}….

Cierre positivo:
L+={L} U {LL} …..

54
Q

Operaciones con expresiones regulares

A

Si ∝ es una expresion regular, entonces {∝} es el conjunto descrito por esa expresion regular.

Union o alternativa:
∝|β es uan exp. reg. tal que {∝|β} = {∝} U {β}.

Concatenacion:
∝β esuna exp. reg. tal que {∝β} = {∝} {β}

Cierre u op. estrella:
∝* es exp. reg que denota {∝}*

Cierre positivo:
∝+ es exp. reg. que denota {∝}+

55
Q

Propiedades de exp regulares

A

Asociatividad.

Distributividad respecto a la concatenacion.

lambda es el elemento neutro en concatenacion.

56
Q

Estado de un automata

A

Toda la info necesaria en un momento dado para poder deducir, dado un simbolo de entrada en ese momento, cual sera el simblo de salida.

57
Q

Configuracion y movimiento de un automata

A

Configuracion: su situacion en un instante dado.

Movimiento: el transito entre dos configuraciones. Se representa con el operador binario –>

58
Q

Diagramas de Mealy/Moore

A

Son otra forma de representar las funciones de transicion y saida de un automata (ademas de las tablas).
Son grafos dirigidos en los que:
Cada nodo corresponde a un estado.
Cada transicion se corresponde a un evento.
Por lo tanto, hay una relacion donde para cada par se obtiene el siguiente estado:
(evento, estado actual)–>estado siguiente.
Para la salida:

Maquina de Mealy: la salida esta expresada en los arcos junto al evento. La salida depende del estado y de donde se viene.

Maquina de Moore: la salida esta expresada en los estados. La salida solo depende del estado.

59
Q

Definicion formal Mealy-Moore

A

Mealy: 6tupla =(E,S,Q,q0,f,g)
E=vocabulario de entrada
S=vocabulario de salida
Q=conjunto de estados
f: ExQ–>Q mapeo de pares de un estado y simbolo de entrada para el siguiente estado.
g:ExQ–>S mapeo de pares de un estado y simbolo de entrada para el simbolo de salida correspondiente

El de moore es igual, la diferencia esta en g
g(Moore)=Q–>S en este caso solo se mapea el estado al simbolo de salida correspondiente.

60
Q

Moore vs Mealy

A

Moore es mas segura de usar, ya que las salidas cambian siempre en el clock, ademas, no todos los circuitos secuenciales se pueden implementar con Mealy, pero si con Moore.

Mealy reacciona mas rapido, ya que las entradas se conectan al combinacional de salida directamente, entonces no espera el clock para cambiar de estado, ademas tienden a tener menos estados justamente por esto.

61
Q

Automatas conexos, deterministas y no deterministas

A

Un automata es conexo si todos los estados de Q son accesibles desde el estado inicial q0.

Automata determinista es aquel en el que la funcion de cambio de estafo f es determinista. En caso contrario es no determinista.

62
Q

Correspondencia entre gramaticas, lenguajes y automatas

A

Automata tipo 0: maquina de turing. Se corresponde con gramatica y lenguaje (recursivamente enumerable) de tipo 0.

Automata tipo 1: automatas limitados linealmente. Se corresponde con una gramatica y lenguaje (dependiente del contexto) de tipo 1.

Automata tipo 2: automata de pila. Se corresponde con gramatica y lenguaje (libres de contexto) de tipo 2.

Automata tipo 3: automatas finitos. Se corresponde con gramatica y lenguaje (regulares) de tipo 3.

63
Q

Distintos tipos de automatas

A

Maquina de Turing: es el mas complejo y potente, se puede ver como una cinta con un cabezal que lee y escribe En el cabezal tenemos los estados, y en la cinta los distintos simbolos. En este caso la cinta se puede mover a izq. o derecha.

Automatas linealmente acotados: Similar a maquina de Turing, pero en este caso la cinta es acotada, no infinita, tiene simbolos # y $ que delimitan a izq. y derecha el limite de la cinta.

Automatas de pila: En este caso la cinta solo se mueve hacia la izquierda, pero el cabezal solo puede leer e ir guardando valores en una pila.

Automatas finitos: los mas simples, en este caso el cabezal solo lee, y la cinta se mueve solo hacia la izquierda.

64
Q

Maquina de Turing

A

Cinta infinita con cabezal de lectura escritura. La cinta se puede mover a der. o izq.
En un movimiento puede realizar distintas acciones:
1) cambio de estado
2) imprime simbolo en la sinta reemplazando el simbolo leido
3) se mueve la cabeza en la cinta, o bien se detiene.
Todo esto puede ocurrir de manera conjunta o no.

Definicion formal:
una quintupla MT=(E,S,Q,f,g) (def de automata) o bien la definicion equivalente:

MT=(Q,Σ,Г,δ,q0,B,F) donde:

Q={conjunto de estados}
Г={conj. de simbolos permitidos en la cinta}
B ∈ Г es simbolo blanco
Σ ∈ Г es el subconjunto de simbolos de entrada no incluyendo el blanco
δ: QxГ–>QxГx{I,D,S} es la funcion del siguiente movimiento (Izquierda, derecha, stop).
q0 ∈ Q es el estado inicial
F ⊂ Q es el subconjunto de estados finales.

Una transicion se define como:
r;w,d
donde r es el simbolo que se lee en la cinta
w es el simbolo a escribir sobre la cinta donde esta r.
d es la direccion para mover la cinta luego de escribir w.

65
Q

Lenguaje aceptado por maquina de Turing

A

L(MT) es el conjunto de palabras formadas con el alfabeto Σ*. Existe una correspondencia entre gramaticas, lenguajes y automatas de tipo 0 (Maquina de Turing)

66
Q

Importancia de maquina de Turing

A

Segun Church:
Algoritmo=Maquina de Turing
Todo algoritmo es equivalente a una maquina de Turing.

67
Q

Automatas linealmente acotados

A

Es una maquina de Turing con las siguientes condiciones:

1) el alfabeto de entrada incluye los simbolos # y $ que son las marcas de fin de la cinta.
2) La cabeza del automata no puede desplazarse fuera de esos simbolos, y no puede escribir sobre ellos.

Definicion formal:
ALA=(Q,Σ,Г,δ,q0,#,$,F)
Q=conjunto de estados
Г=Conjunto de simbolos permitidos en la cinta
Σ ∈ Г es el subconjunto de simbolos de entrada no incluyendo el blanco.
δ: QxГ-->QxГx{I,D,S} es la funcion del siguiente movimiento (Izquierda, derecha, stop).
q0 ∈ Q es el estado inicial
F ⊂ Q es el subconjunto de estados finales
# y $ ∈ Σ corresponden a la amrca izq. y der. de la cinta.
68
Q

Lenguaje aceptado por ALA

A

Hay correspondencia entre gramaticas de tipo 1, lenguajes de tipo 1 y automatas de tipo 1 (ALA)

69
Q

Automatas de pila (pushdown automata)

A

Operaciones elementales:
1)Dependientes de la entrada: se lee un simbolo, y en funcion de este, el estado, y el valor en la pila, el control pasa a otro estado, y en la pila se introduce otro valor, o se extrae el que estaba, o no se hace nada.

2) Independientes de la entrada: si el simbolo que se lee no interviene, la cinta no se mueve, lo que permite amnejar la pila sin la info de entrada.

Definicion formal:

AP=(Q,Σ,Г,δ,q0,Z0,F)
Q=conjunto de estados
Σ=alfabeto de entrada
Г=alfabeto de pila
δ=funcion de transicion, de la forma:
δ: Qx{Σ U {λ}} x Г --> QxГ*
q0 es el estado inicial
Z0 es el simbolo incial de la pila
F es el conjunto de estados finales.

En general este automata es no determinista, es decir que el resultado de la funcion de transicion no esta determinado, pueden resultar dos o mas valores.

Configutacion del automata: situacion en un instante dado, se puede representar por el terceto:
(q,W,∝)
q representa estado actual del automata.
W es la cadena de entrada que resta por analizar.
∝ es el contenido de la pila en ese instante.

En el jflap para describir transiciones:
a,Z;aZ

a es la entrada a procesar
Z es el valor actual en la parte superior de la pila
aZ representa el nuevo valor a empujar en la pila, luego de sacar el valor en la parte superior de esta.

70
Q

Lenguaje reconocido por automata de pila

A

Reconocen lenguajes de tipo 2. Existe correspondencia entre gramaticas, lenguajes y automatas de tipo 2 (de pila).

Programacion Concurrente (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions