Arturo Díaz Pérez

Análisis y Complejidad de Algoritmos

Modelos Computacionales Arturo Díaz Pérez ¬ ® ¯

El circuito lógico La máquina de estados finitos La máquina de acceso aleatorio La máquina de Turing

Models

Análisis y Diseño de Algoritmos

Compuertas Lógicas F Compuerta Lógica ß Un dispositivo físico que realiza una función booleana /f: N → { 0, 1 } /Frecuentemente n se codifica como una número en base 2 /n = xk-12k-1 + xk-22k-2 + ... + x121 + x020 +, xi= 0, 1 f

Las compuertas lógicas pueden ser construidas por tecnologías diferentes Se acostumbra utilizar un símbolo lógico para cada compuerta Los símbolos se utilizan para dibujar circuitos lógicos

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Models

1

Arturo Díaz Pérez

Circuitos Lógicos F Circuito Lógico ß Una DAG en la cual todos sus vértices, excepto los vértices de entrada y salida, están etiquetados con compuertas lógicas ß Los circuitos lógicos ejecutan programas estrictamente secuenciales, esto es, programas que consisten únicamente de asignmientos ß No contienen ciclos ni saltos ß Los circuitos lógicos constituyen los bloques básicos para la construcción de computadoras digitales. ß Cuando se combinan con celdas de memoria binarias, se pueden construir máquinas con memoria (máquinas de estados finitos)

Models

Análisis y Diseño de Algoritmos

Circuitos Lógicos x1

a

sum

b cin

x2 x3

cout x4

x1 := a xor b x2 := a nand cin x3 := b nand cin x4 := a nand b sum := x1 xor cin cout := (x2 nand x3) nand x4 Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Models

2

Arturo Díaz Pérez

Máquinas de Estados Finitos F Máquinas de estados finitos ß Es una máquina con memoria ß Ejecuta una serie de pasos en los cuales /toma su estado actual de un conjunto de estados Q /define su salida a partir de un conjunto de símbolos de entrada Σ ß FSM = < Σ, Ψ, Q, δ, λ> /Σ, alfabeto de símbolos de entrada /Ψ, alfabeto de símbolos de salida /Q, conjunto finito de estados /δ, función de transición 3 δ : Σ ×Q→ Q

/λ, función de transición 3 λ:Σ Análisis y Diseño de Algoritmos

× Q→ Ψ

Models

Máquinas de Estados Finitos Salida

Entrada

L

Memoria

Estado

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Models

3

Arturo Díaz Pérez

FSM: Ejemplo 0/0

1/0 0/0 1/0

a

b

1/0

c

0/(z_out := NOT y_in)

ESTADO a b c -

V0

V1

0 0 1 1

0 1 0 1

0

x_in

1 01,0 10,0 10, ¬yin --,-

00,0 00,0 00,¬yin --,-

Models

Análisis y Diseño de Algoritmos

FSM: Estructura General x d logic 0 D 0 Q CLK

d logic 1

D 1 Q CLK memory part

clk z logic

z logical part Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Models

4

Arturo Díaz Pérez

Autómata Finito F Autómata Finito ß AF = < Σ, Q, δ, q0, F> /Σ, alfabeto de símbolos de entrada /Q, conjunto finito de estados /δ, función de transición 3 δ : Σ ×Q→ Q

/q0, estado inicial /F ⊂ Q, conjunto0 de estados finales 0 1

q0/0

q1/1 1

Models

Análisis y Diseño de Algoritmos

Autómata de Pila F Autómata de Pila ß Consiste de /una cinta de entrada, /un control finito y / una pila Cinta de Entrada ß AF = < Σ, Γ, Q, δ, q0, Z0, F> /Σ, alfabeto de símbolos de entrada /Γ, alfabeto de símbolos de la pila /Q, conjunto finito de estados /δ, función de transición

Mecanismo de Control Pila

3 δ:Q×Σ×Γ→Q× Γ

/q0, estado inicial /Z0, símbolo inicial de la pila Análisis y Diseño de Algoritmos /F ⊂ Q, conjunto de estados finales

Análisis y Complejidad de Algoritmos

Models

5

Arturo Díaz Pérez

Autómata de Pila F Autómata de Pila ß Consiste de /una cinta de entrada, /un control finito y / una pila Cinta de Entrada

Mecanismo de Control Pila Análisis y Diseño de Algoritmos

Models

La Máquina de Acceso Aleatorio: RAM F RAM: Random Access Machine ß Es modelada como dos máquinas de estados finitos: /unidad central de procesamiento (CPU) /memoria de acceso aleatorio /cmd: READ, WRITE, NO-OP /instrucciones: 3 LOAD, STORE, ADD, SUB, MULT, DIV, 3 READ, WRITE, 3 JUMP, JZ, JNZ, HALT

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Models

6

Arturo Díaz Pérez

La Máquina de Acceso Aleatorio: RAM b

Decode

ALU

cmd

m-1 m-2

out_wrd rega

in_wrd

regb

addr

PC

Análisis y Diseño de Algoritmos

1 0

Models

Máquina de Turing

mecanismo de control

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Models

7

Arturo Díaz Pérez

Máquina de Turing F Máquina de Turing ß Cinta no acotada formada por casillas ß mecanismo de control, i. e., autómata con diversos estados ß cabeza de lectura con la que examina, en cada instante, una casilla en la cinta ß programa, lista de quíntuples de la forma /qs → ptm /q,p ∈ Q (estados), s,t ∈ Σ (símbolos del alfabeto), m ∈ { I, D, A} (movimiento) “Si en el estado q se lee en la cinta el símbolo s, entonces, cambia a s por t, luego pasa al estado p y pasa a examinar la casilla adyacenta en la dirección m”

Models

Análisis y Diseño de Algoritmos

Máquina de Turing: Ejemplo 1, 1, 1, 2, 2, 2, 3, 3, 3,

()(()) 1()(()) (1)(()) (2B(()) A1B(()) AB1(())

AB(1()) AB((1)) AB(2(B) AB(A1B) AB(AB1) AB(A2BB

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

x ) b y ( b x ( b

→ → → → → → → → →

1, 2, 3, 2, 1, 4, 3, 3, 3,

x, D B, I b, I y, I A, D No, H x, I No, H Si, H

AB(2ABB AB2(ABB ABA1ABB ABAA1BB ABAAB1B ABAABB1b

ABAAB3B ABAA3BB ABA3ABB AB3AABB A3BAABB 3ABAABB

3bABAABB [Si]ABAABB

Models

8

Arturo Díaz Pérez

Máquina de Turing: Ejemplo F Reconocimiento de cadenas equilibradas de paréntesis 1, x → 1, x, D 1, ) → 2, B, I 1, b → 3, b, I 2, y → 2, y, I 2, ( → 1, A, D 2, b → 4, No, H 3, x → 3, x, I 3, ( → 3, No, H 3, b → 3, Si, H Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

con cualquier cosa salvo “)”, aváncese a la derecha, x ∈ { (, A, B } con el primer “)”, márquese y retrocédase si la lista se acaba, revísese que todo haya quedado marcado con cualquier cosa salvo “(”, retrocédase a la izquierda, y ∈ { ), A, B } márquese el “(“ que empata y repítase el ciclo se termina la cadena y no existe el correspondiente “(”. No hay equilibrio. retrocédase ignorando las marcas, x ∈ { A, B } si quedara un “(”, éste ya no podrá empatarse. No hay equilibrio. acabó la cadena y todo quedó marcado. Si hay equilibrio. Models

9