RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискрет. матем., 2010, том 22, выпуск 1, страницы 50–57 (Mi dm1083)  

Об оценках сложности схем из многовходовых функциональных элементов

Н. П. Редькин


Аннотация: В работе представлен метод получения нижних оценок сложности схем из функциональных элементов, основанный на замене рассматриваемого, быть может, достаточно сложного базиса, содержащего многовходовые элементы, на более простой базис, например, из двухвходовых элементов, с последующим использованием уже известных нижних оценок сложности схем в простом базисе. Эффективность предлагаемого метода демонстрируется на конкретных примерах нахождения асимптотики, и, в некоторых случаях, и точного значения для сложности реализации конкретных булевых функций – монотонных симметрических функций и функций с малым числом единиц.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 08–01–00863, и Программы Президента Российской Федерации поддержки ведущих научных школ, проект НШ 4470.2008.1.

DOI: https://doi.org/10.4213/dm1083

Полный текст: PDF файл (124 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Discrete Mathematics and Applications, 2010, 20:1, 85–93

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.95
Статья поступила: 08.06.2009
Переработанный вариант поступил: 16.12.2009

Образец цитирования: Н. П. Редькин, “Об оценках сложности схем из многовходовых функциональных элементов”, Дискрет. матем., 22:1 (2010), 50–57; Discrete Math. Appl., 20:1 (2010), 85–93

Цитирование в формате AMSBIB
\RBibitem{Red10}
\by Н.~П.~Редькин
\paper Об оценках сложности схем из многовходовых функциональных элементов
\jour Дискрет. матем.
\yr 2010
\vol 22
\issue 1
\pages 50--57
\mathnet{http://mi.mathnet.ru/dm1083}
\crossref{https://doi.org/10.4213/dm1083}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2675430}
\zmath{https://zbmath.org/?q=an:05779534}
\elib{http://elibrary.ru/item.asp?id=20730323}
\transl
\jour Discrete Math. Appl.
\yr 2010
\vol 20
\issue 1
\pages 85--93
\crossref{https://doi.org/10.1515/DMA.2010.005}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1083
  • https://doi.org/10.4213/dm1083
  • http://mi.mathnet.ru/rus/dm/v22/i1/p50

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретная математика
    Просмотров:
    Эта страница:364
    Полный текст:113
    Литература:41
    Первая стр.:27
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020