мар 6
О диагностических тестах размыкания для контактных схем
К.А. Попков (ИПМ им. М.В.Келдыша)
6 мар 2019 в 10:30
комната 220, корпус В
6 мар 2019 в 10:30
комната 220, корпус В
Доказано, что при \(n\geqslant 2\) любую булеву функцию от n переменных можно реализовать двухполюсной контактной схемой, неизбыточной и допускающей диагностический тест, длина которого не превосходит \(n+k(n-2)\), относительно размыканий не более \(k\) контактов. Установлено, что при \(k=k(n)\leqslant 2^{n-4}\) для почти всех булевых функций от \(n\) переменных наименьшая возможная длина указанного теста не превосходит \(2k+2\).