juaninf - notas de psudoprogramador

Tuesday, January 12, 2016

Problem "Marble Toy"

Consider the toy shown below. A marble is dropped in at A or B. Levers x, y, and z cause the marble to fall either to the left or right. Whenever a marble encounters a lever, it causes the lever to change state, so that the next marble to encounter the lever will take the opposite branch.

                  |A|          |B|
                  |    |       |    |
                  | x |       | y |
                 /  /  \      /  /  \
                /       \    /       \
               /   /\    \  /    /\   \
              /   /  \    \/    /  \   \
             /   /    \  z /   /    \   \
             \   \    /   /    \    /   /
              \   \  /    /\    \  /   /
               \   \/    /  \    \/   /
                \       /    \       /
                 \     /      \     /
                  |   |        |   |
                  |   |        |   |
                   |C|        |D|


Problem: Describe the set accepted by the DFA. Solution:


First the DFA solution is presented in the next table and his diagram in JFLAP in the next file.

To describe the set accepted by the DFA see that only the half of times that a ball falls in A affects x_2, the same happens for the case B. Then there are three cases to describe the set accepted by the DFA.

1.-If the word end in B and the numbers of Bs is even (par).
2.-If the word has the form XB where X is formed by As and Bs. The number of Bs on X is even and the half of the numbers of As and Bs is odd (impar) (exactly).
3.-If the word has the form XA where X is formed by As and Bs. The number of As on X is odd and the half of the numbers of As and Bs is odd.(exactly).

Friday, May 15, 2015

Building Simple Chat Client with Parse [Code]

I am learning android and I am following the tutorial Building Simple Chat Client with Parse. I am providing the source code in this link. Here you can find the code for that tutorial. Notice that the data type ParseObject of the variable message in line 76 from the source ChatActivity.java was changed by Message. I do not know why the author of that tutorial creates the object message of the class ParseObject. Case anybody know that, please comment this post.

Sunday, August 10, 2014

Compuscientia 2014: Cuarta Edición

Tenemos el agrado de invitar a la comunidad cientifica y empresarial a presentar trabajos para la cuarta edición de CompuScientia. CompuScientia es una revista de la Sociedad de Estudiantes de Ciencia de la Computación (SECC) que tiene por objetivo conectar a nuestros lectores con la realidad de la Computación en el Perú y el mundo. En el ámbito académico, se presentan oportunidades para hacer estudios de posgrado en varias universidades alrededor del mundo y muchos estudiantes peruanos han compartido y continuarán compartiendo sus experiencias en CompuScientia. De la misma manera, conferencias y eventos nacionales e internacionales relacionados a la computación merecen ser conocidos y difundidos. Trabajos teóricos, prácticos y aplicados en computación realizados por estudiantes de pregrado, posgrado y otros profesionales también tienen cabida en CompuScientia. En CompuScientia, también hay un gran interés por difundir experiencias académicas y logros de estudiantes y profesionales peruanos y latinoamericanos que son ejemplo para las nuevas generaciones. Análisis de noticias acerca de la realidad de la investigación en el Perú y en el mundo son de interés en CompuScientia. Un caso en el Perú, por ejemplo, es el análisis de la ley universitaria recientemente aprobada. En el ámbito laboral, startups, experiencias laborales en empresas reconocidas a nivel mundial como Facebook, Google, IBM también merecen ser difundidas. CompuScientia también tiene interés en difundir temas relacionados a la computación tales como: productos creados por jóvenes emprendedores, oportunidades para hacer internships, investigaciones en empresas, patentes y noticias relacionadas al enfoque empresarial.

Friday, March 07, 2014

Problema em Teoria dos Códigos

Neste post vou analisar o Problema MINIMUM DISTANCE (MD) (conjeturado NP-Completo em [1] e demostrado NP-Completo em [2])  para poder entender porque o problema computacional associado a este problema é NP-Hard

Problema de Decisão MINIMUM DISTANCE (MD)
Instancia : Uma matriz binária $H^{m\times n}$ e um $w > 0$.
Pregunta: Existe algum vector $x\in \mathbb{F}_2^n$ com peso de Hamming $\leq w$ tal que $Hx=0$?

Problema de Computación COMPUTATIONAL MINIMUM DISTANCE (CMD)
Instancia : Uma matriz binária $H^{m\times n}$ e um $w>0$.
Pregunta: Computar o vector $x\in \mathbb{F}_2^n$, com peso minimo, do código $C$ associado a $H$.

Veja que este é um problema de decisão porque as resposta possíveis são SIM ou NÃO. Que é NP-Completo esta demostrado em [2]. Que MD seja NP-Completo implica, neste caso, em que COMPUTING MINIMUM DISTANCE (CMD) é NP-Hard. Para demonstrar isto vamos a usar a definição informal que nos da o wikipedia.
Um problema $H$ é NP-difícil se e somente se (sse) existe um problema NP-completo L que é Turing-redutível em tempo polinomial para $H$. Em outras palavras, $L pode ser resolvido em tempo polinomial por umaMáquina de Turing Não Determinística com um oráculo para H. Informalmente, podemos pensar em um algoritmo que pode chamar tal Máquina de Turing Não-Determinística como uma sub-rotina para resolver H, e resolver L em tempo polinomial, se a chamada da sub-rotina leva apenas um passo para computar.
Então podemos usar como oraculo um algoritmo que resolve CMD para resolver em tempo polinomial, numa máquina de Turing Não Determinista, o problema MD. Para isto basta só comparar se o $w$ do problema MD é maior ou menor que o resultado retornado pelo oráculo. Se o $w$ fosse maior que o valor retornado pelo oraculo então a resposta do problema MD é SIM. Isto porque se fosse possível calcular a distancia minima do código, digamos $d$, então para qualquer $w\leq d$ a resposta é SIM. Se o $w$ fosse menor que o valor retornado pelo oraculo então a resposta do problema MD é NÃO dado que não pode existir $x$ com peso menor que $d$.

Referências
[1] Berlekamp, Elwyn R. and McEliece, Robert J. and van Tilborg, Henk C. A. (1978) On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24 (3). pp. 384-386. ISSN 0018-9448.
[2] The intractability of computing the minimum distance of a code - Vardy - 1997


Tuesday, February 04, 2014

Transformação Afim na Criptografia

Uma transformação afim é uma transformação entre dois espaços afins $A$ e $B$. Essa transformação, ou mapeamento, consiste numa transformação lineal em $A$ somado de um vetor $b \in B$. Ou seja: $$S(x)=Tx + b.$$ No campo da criptografia post-quântica as transformações afins são usadas para ocultar a chave pública dos sistemas de cifração baseados em multivariados.

Para os envolvidos na área é de importância saber lidar com as diferentes representações de uma transformação afim. Neste post apresentarei essas representações e mostrarei como converter uma para a outra. Seja $\mathbb{F}$ um corpo finito com $q$ elementos e $\mathbb{E}$ uma extensão de grau $n$ do corpo $\mathbb{F}$. Seja $S:\mathbb{F}^n\rightarrow \mathbb{F}^n$ uma transformação afim.

Definição 1: Seja $0\leq i < n$ e $A,B_i \in \mathbb{E}$. Então nós chamamos o polinômio $S(X)=\sum_{i=0}^{n-1}B_i X^{{q}^i}+A$ a representação de uma só variável da transformação afim $S$.

Definição 2: Seja $M_S \in \mathbb{F}^{n\times n}$ uma matriz e $v_s \in \mathbb{F}^n$ um vetor. Então nos chamamos $S(x):=M_Sx+v_s$, a representação matricial da transformação afim $S$ .

Definição 3: Seja o espaço vetorial $\mathbb{F}^n$. Então nós chamamos $\phi:\mathbb{E}\rightarrow \mathbb{F}^n$ com $\phi(a):=b$ e $b_i=a_{i-1}$ de bijeção canônica.

Teorema: Uma transformação afim, com $v=0$ na representação de uma só variável pode ser transformada eficientemente na sua representação matricial.

Prova: Definamos $e_i \in \mathbb{F}^n$ com $1\leq i \leq n$, com um $1$ no seu i-th coeficiente e zero no restante. Vamos a mostrar que a coluna $k$ dessa matriz é dada pela seguinte fórmula: $M_k=\phi(S(\phi^{-1}(e_k))).$ Vamos a definir $P(X):=\sum_{i=0}^{n-1}B_i X^{{q}^i}$. Da álgebra conhecemos que o corpo $\mathbb{F}^n$ é também um espaço vetorial sobre o corpo $\mathbb{F}$. Esse espaço vetorial tem a base $V=\{t^0, t^1, t^2,\ldots,t^{{n-1}}\}.$ Vamos a representar os coeficiente de $P(X)$ como  $B_i =\sum_{j=0}^{n-1}b_{ij} t^j$ e a variável $X=\sum_{k=0}^{n-1}X_{k}t^k$. Substituindo esses valores em $P(X)$ temos $$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} t^j(\sum_{k=0}^{n-1}X_{k}t^k)^{{q}^i},$$
Usando o teorema binomial e reduzindo temos
$$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}t^{j+k{{q}^i}},$$

Escrevendo $t^{j+k{{q}^i}}$ usando a base $V$ temos $t^{j+k{{q}^i}} = \sum_{m=0}^{n-1}c_{ijkm}t^m$. Por tanto:

$$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k} \sum_{m=0}^{n-1}c_{ijkm}t^m$$
$$P(X) =  \sum_{m=0}^{n-1}\underline{\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}c_{ijkm}}_{E}t^m$$
Por outro lado, escrevendo  $\phi(S(\phi^{-1}(e_k)))$ usando a base $V$ temos que esta é igual a: $\phi(S(\phi^{-1}(e_k)))=(\sum_{i,j}^{n-1}b_{i,j}c_{ijk0}, \cdots, \sum_{i,j}^{n-1}b_{i,j}c_{ijk(n-1)})$. Por fim, veja que $E_m = (\phi(S(\phi^{-1}(e_1)))[m],\cdots,\phi(S(\phi^{-1}(e_{n-1})))[m])^{T}*(X_1,\cdots, X_{n-1}).$

No caso de transformação afim com $v \neq 0$ então se tem que v:=$M_k=\phi(S(\phi^{-1}(0)))$ e as colunas de $M$ são $M_k=\phi(S(\phi^{-1}(e_k)))-v.$

Tuesday, December 17, 2013

Friday, December 06, 2013

El Faq de las Máquinas de Turing

Este post es sólo un oráculo de algunas preguntas frecuentes para quién ya estudió teoria de la computación y con el tiempo ha ido olvidando algunos conceptos.

Que es una máquina de Turing?
Un Dispositivo
Que es un problema?
Un conjunto de frases de longitud finita que esta asociada a un conjuto de frases también de longitud finita.
Que es un problema decidible?
Un problema que su conjunto asociado solo tiene las frases si y no, es decir existe un método que ya consigue definir esos: si y no. Los problemas decidibles tienen un método definido que consigue decir si el problema(la sentencia) es cierto o falso.
Que es un algoritmo?
No existe un consenso, pero se puede decir que es una máquina de Turing.
Todo método que resuelve un problema decidible puede ser implementado en una máquina de Turing?
no sé. Creo que si.
Que es un problema indecidible?
Un problema para el cual no existe un método tal que sea capaz de resolverlo con una respuesta si o no.
Cuantas programas puedo escribir en una máquina de Turing?
Si es universal muchos, recuerde que una máquina de Turing Universal permite simular cualquier máquina de Turing para cualquier entrada.
Que es PP?
Es la clase de problemas de decisión para los cuáles existe un algoritmo de Montecarlo bilateral que responde si cuando la respuesta correcta es si con probabilidad > 1/2 (idem para no) y el tiempo de ese algoritmo es es un polinómio en el tamaño de la entrada. Otra definición equivalente, es la clase de problemas resolubles por una MT probabilística en tiempo polinomial con probabilidad > 1/2 para todas sus instancias.
NP \in PP?
Si. El problema de la factoración esta en NP, por tanto en PP, entonces existe un algoritmo de montecarlo que consigue factorar como descrito en la pregunta anterior, sólo que máquinas de Turing probabilisticas no existen (en general las no deterministas no existen) y las que se simulan estas no son eficientes, es decir no consiguen factorar en tiempo polinomico.

Related Posts Plugin for WordPress, Blogger...