Lógica: Explorando las Reglas de Inferencia

Reglas de Inferencia

• Una regla de inferencia es un esquema para construir argumentos válidos, mostrando la forma lógica de pasar de las premisas a la conclusión.

Modus Ponens

• También conocido como Ley de Separación.
• Representación: $\qquad \begin{aligned} &p \rightarrow q \ &p \ \hline &q \end{aligned}$
• Ejemplo: Si está lloviendo, entonces hay nubes en el cielo. Está lloviendo. Por lo tanto, hay nubes en el cielo.

Modus Tollens

• Representación: $\qquad \begin{aligned} &p \rightarrow q \ &\neg q \ \hline &\neg p \end{aligned}$
• Ejemplo: Si está lloviendo, entonces hay nubes en el cielo. No hay nubes en el cielo. Por lo tanto, no está lloviendo.

Silogismo Hipotético

• Representación: $\qquad \begin{aligned} &p \rightarrow q \ &q \rightarrow r \ \hline &p \rightarrow r \end{aligned}$
• Ejemplo: Si termino mi tarea, entonces puedo ir al cine. Si voy al cine, entonces compraré palomitas de maíz. Por lo tanto, si termino mi tarea, entonces compraré palomitas de maíz.

Silogismo Disyuntivo

• Representación: $\qquad \begin{aligned} &p \lor q \ &\neg p \ \hline &q \end{aligned}$
• Ejemplo: Voy a estudiar o voy a dormir. No voy a estudiar. Por lo tanto, voy a dormir.

Adición

• Representación: $\qquad \begin{aligned} &p \ \hline &p \lor q \end{aligned}$
• Ejemplo: Estoy feliz. Por lo tanto, estoy feliz o está lloviendo.

Simplificación

• Representación: $\qquad \begin{aligned} &p \land q \ \hline &p \end{aligned}$
• Ejemplo: Estoy feliz y está soleado. Por lo tanto, estoy feliz.

Conjunción

• Representación: $\qquad \begin{aligned} &p \ &q \ \hline &p \land q \end{aligned}$
• Ejemplo: Estoy feliz. Está soleado. Por lo tanto, estoy feliz y está soleado.

Resolución

• Representación: $\qquad \begin{aligned} &p \lor q \ &\neg p \lor r \ \hline &q \lor r \end{aligned}$
• Ejemplo: Está lloviendo o está soleado. No está lloviendo o hace viento. Por lo tanto, está soleado o hace viento.

Fotodiodos Semiconductores

Fotodiodo ideal

• La absorción de un fotón con $hv > E_g$ genera un par electrón-hueco.
• Estos portadores son separados por el campo eléctrico en la región de agotamiento y son llevados a sus respectivos lados.
• Esto genera una corriente en el circuito externo que es proporcional a la potencia óptica incidente.

Responsividad

• La responsividad $\Re$ se define como $\qquad \Re = \frac{I_{ph}}{P_{opt}} = \frac{\eta q}{hv} = \frac{\eta \lambda}{1.24} \quad [A/W]$
  • Donde $I_{ph}$ es la fotocorriente generada, $P_{opt}$ es la potencia óptica incidente, y $\eta$ es la eficiencia cuántica (número de pares electrón-hueco generados por fotón incidente).

Fotodiodo PIN

• La absorción ocurre principalmente en la región intrínseca, donde cae la mayor parte del voltaje.
• W se hace lo suficientemente grande para absorber una gran fracción de la luz incidente, pero no tan grande como para que el tiempo de tránsito de los portadores a través de la región de agotamiento se alargue demasiado.

Fotodiodo de avalancha (APD)

• Polarización inversa alta para que los portadores puedan ganar suficiente energía para impactar ionizando otros pares electrón-hueco.
• Esto resulta en ganancia interna, lo que mejora la sensibilidad del detector.
• $I = M I_{ph}$, donde $M$ es el factor de multiplicación.
• Sin embargo, el proceso de avalancha añade ruido a la señal, lo que puede degradar la SNR.
• Hay un equilibrio entre ganancia y ruido.

Parámetros de Rendimiento del Fotodetector

Responsividad

• $\qquad \Re = \frac{I_{ph}}{P_{opt}} = \frac{\eta q}{hv} = \frac{\eta \lambda}{1.24} \quad [A/W]$

Eficiencia Cuántica

• $\qquad \eta = \frac{\text{Número de pares electrón-hueco generados}}{\text{Número de fotones incidentes}}$
• $\qquad \eta = (1 - r)(1 - e^{-\alpha W})$
  • Donde $r$ es el coeficiente de reflexión de Fresnel en la superficie, $\alpha$ es el coeficiente de absorción y $W$ es el grosor de la región de absorción.

Tiempo de Tránsito

• El tiempo de tránsito es el tiempo que tardan los portadores en desplazarse a través de la región de agotamiento.
• Esto limita el ancho de banda del fotodiodo.
• $\qquad t_t = \frac{W}{v_d}$, donde $v_d$ es la velocidad de deriva del portador.

Ancho de Banda

• $\qquad BW \approx \frac{0.37}{t_t}$

Ruido

• El ruido es cualquier corriente o voltaje no deseado que interfiere con la señal.
• Las principales fuentes de ruido en los fotodiodos son:
  • Ruido de disparo: debido a la llegada aleatoria de fotones y a la generación aleatoria de pares electrón-hueco.
  • Ruido térmico: debido al movimiento aleatorio de electrones en la resistencia.

Relación Señal a Ruido (SNR)

• $\qquad SNR = \frac{I_{sig}^2}{\sigma_N^2}$
  • Donde $I_{sig}$ es la corriente de señal y $\sigma_N^2$ es la varianza del ruido.

Fotoconductores

• Material semiconductor en el que la conductividad aumenta cuando se expone a la luz.
• Cuando se absorbe un fotón, genera un par electrón-hueco, lo que aumenta la conductividad del material.
• El cambio en la conductividad es proporcional a la potencia óptica incidente.

Ventajas

• Alta ganancia
• Estructura simple

Desventajas

• Tiempo de respuesta lento
• Alta corriente oscura

Tablas Hash

Motivación

• Admite operaciones de conjunto dinámico en tiempo $O(1)$
  • INSERTAR, BUSCAR, ELIMINAR
• Matrices vs. Tablas Hash
  • Matrices: las claves son índices, deben conocerse las claves de antemano
  • Tablas Hash: las claves no son índices, se pueden insertar claves sobre la marcha

Direccionamiento Directo

• Caso simple: la clave es igual a la dirección
• Es trivial cuando podemos permitirnos asignar una dirección de memoria para cada clave posible.

Funciones Hash

• ¿Qué ocurre si no es práctico asignar una dirección de memoria para cada clave posible?
  • Por ejemplo, |universo de claves| >> |claves reales|
  • Por ejemplo, claves de 64 bits pero solo se quieren almacenar 1000 elementos
• Use una función hash para asignar varias claves a la misma ranura

Colisiones

• Cuando dos claves se hash a la misma ranura
• ¿Qué probabilidad hay de que esto ocurra?
  • Paradoja del cumpleaños: en una sala de 23 personas, hay > 50% de probabilidad de que dos personas compartan el mismo cumpleaños.

Encadenamiento

• Cada ranura en la tabla hash almacena una lista enlazada de elementos que se hash a esa ranura

Hashing Uniforme Simple

• Es igualmente probable que cada clave se hash a cualquiera de las ranuras $m$
• Sea $n$ el número de claves
• Factor de carga $\alpha = \frac{n}{m}$
• Tiempo esperado para una búsqueda sin éxito = $O(1 + \alpha)$
• Tiempo esperado para una búsqueda con éxito = $O(1 + \frac{\alpha}{2}) = O(1 + \alpha)$
• Si $n = O(m)$, entonces $\alpha$ es constante, por lo que el tiempo de búsqueda es $O(1)$

Funciones Hash

• Queremos que nuestra función hash satisfaga el supuesto de hashing uniforme simple
• Pero no conocemos la distribución de probabilidad de la que se extraen las claves
• Heurísticas
  • Hashing por división
    • $h(k) = k \mod m$
    • Evite $m = 2^p$
    • Buena elección: primo no demasiado cercano a la potencia exacta de 2
  • Hashing por multiplicación
    • $h(k) = \lfloor m(kA \mod 1) \rfloor$
    • $0 < A < 1$
    • $m$ no es crítico, elija una potencia de 2
    • Buena elección: $A = (\sqrt{5} - 1) / 2$
• Ejemplo
  • Claves: 101, 1000, 10000, 90000
  • $h(k) = k \mod 7$
  • $h(101) = 3$
  • $h(1000) = 6$
  • $h(10000) = 5$
  • $h(90000) = 4$

Resumen

• Las tablas hash son una estructura de datos poderosa que puede admitir operaciones rápidas de INSERTAR, BUSCAR y ELIMINAR
• Las funciones hash se utilizan para asignar claves a ranuras en la tabla hash
• Las colisiones ocurren cuando dos claves se hash a la misma ranura
• El encadenamiento es una forma sencilla y eficaz de resolver las colisiones
• El supuesto de hashing uniforme simple es importante para un buen rendimiento
• Las funciones hash deben elegirse cuidadosamente para evitar colisiones