
handle: 20.500.14352/10202
El objetivo de este trabajo consistió en desarrollar un experimento que permita analizar múltiples tipos de circuitos booleanos y las funciones que estos computan, de manera que podamos analizar las relaciones entre ambos conceptos. En el primer capítulo, se expone una definición formal del concepto archiconocido de circuito booleano, se analiza el crecimiento doblemente exponencial del conjunto de circuitos con m bits de entrada y se dota de un orden total a dicho conjunto. En el segundo capítulo, se demuestran una serie de resultados sobre vectores con determinadas propiedades que nos permiten recorrer de manera eficiente el conjunto de circuitos booleanos que tienen determinada profundidad y anchura. Este algoritmo se ha implementado en C++ utilizando técnicas de programación concurrente y estructuras de datos adecuadas para garantizar la eficiencia del mismo. A lo largo del tercer capítulo se exponen distintas métricas para medir la endogamia de los circuitos booleanos, así como intuiciones que justifican estas definiciones. Además, se incorpora un breve cuarto capítulo que versa sobre un tipo de gramática libre de contexto particular que genera funciones booleanas y su correspondencia con los circuitos booleanos. Finalmente, este trabajo concluye con un quinto y último capítulo en el que se analizan los resultados obtenidos en este experimento y se exponen las conclusiones consecuentes.
Informática, Complejidad de circuitos, Good prefix property, Clase de complejidad, Informática (Informática), Índice de un circuito, Correlation between functions and circuits, Circuit complexity, Propiedad del buen prefijo, P/poly, Circuito booleano, Complexity class, Endogamy of a circuit, Boolean function, Endogamia de un circuito, Correlación entre funciones y circuitos, 1203.17 Informática, 004(043.3), Función booleana, Boolean circuit, Algoritmo del índice, Index algorithm, Index of a circuit
Informática, Complejidad de circuitos, Good prefix property, Clase de complejidad, Informática (Informática), Índice de un circuito, Correlation between functions and circuits, Circuit complexity, Propiedad del buen prefijo, P/poly, Circuito booleano, Complexity class, Endogamy of a circuit, Boolean function, Endogamia de un circuito, Correlación entre funciones y circuitos, 1203.17 Informática, 004(043.3), Función booleana, Boolean circuit, Algoritmo del índice, Index algorithm, Index of a circuit
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
