Funció llindar
En matemàtiques, una funció llindar (més coneguda en anglés com threshold function) és una funció booleana monòtona ƒ : {0,1}n → {0,1}, a on existixen n+1 reals no negatius w1, w2, ..., wn, t tals que:[1]
Per mig d'esta funció és possible definir un grafo llindar.
Història
Si be estes funcions varen ser definides per primera volta en la década de 1960[2] i desenrollades més extensament en 1971,[3] estan inspirades en el model matemàtic de neurona de McCulloch-Pitts, propost en 1943.[4]
En el context de la teoria de jocs, per la seua banda, estes funcions són ademés equivalents als jocs de majoria ponderada, sent estos mencionats per primera volta en 1944[5] i 1956.[6]
Complexitat computacional
Del punt de vista de la complexitat computacional, se sap que són computables en temps polinòmic. De fet corresponen a una subclasse (estricta[3]) de les funcions booleanas 2-monòtones, les quals també es poden computar eficientement.[1]
Referències
- ↑ 1,0 1,1 Erro en la seqüencia d'órdens: no existix el mòdul «Citas»..
- ↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- ↑ 3,0 3,1 Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- ↑ McCulloch, W.; Pitts, W.(1943).«A logical calculus of the idees immanent in nervous activity».Bulletin of Mathematical Biophysics.7: 115-133.(en anglés)
- ↑ von Neumann, J.; Morgenstern, O. (1944). Theory of Games and Economic Behavior (en anglés), Princeton University Press, NJ.
- ↑ Isbell, J.R.(1956).«A class of majority games».Ouart J. Math. Oxford Scr..7: 183-187.(en anglés)
Referències
- Este artícul conté una traducció derivada de «Función umbral» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.