Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №2, Москва, 1989
Авторы: Карпова Н.А.
О вычислениях с ограниченной памятью
Аннотация:
Будем считать, что элементы схемы (из функциональных элементов) занумерованы в том порядке, в каком они срабатывают. Введем условие: значение (0 или 1), полученное на выходе элемента, должно храниться в регистре, т. е. ячейке памяти, до тех пор, пока не сработают все элементы, присоединенные к этому выходу. Исследовалась функция Шеннона при ограничении на t – число ячеек памяти. В качестве базиса выбрано множество всех p местных булевых функций. При t = 1 построение схем для всех булевых функций от n переменных возможно лишь при определенном росте p вместе с ростом n. В этом случае установлен порядок функции Шеннона. Для некоторого диапазона p порядок функции Шеннона установлен и при t = 2. При всех фиксированных t ≥ 3 и p ≥ 2 установлена асимптотика функции Шеннона.
Ключевые слова:
схема, регистр, функция Шеннона
Язык публикации: русский, страниц: 14 (с. 131-144)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Карпова Наталия Александровна,  ИПМ им. М.В. Келдыша РАН