Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на синтез схем
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 73: | Строка 73: | ||
# Посчитать число функций в заданном классе ''Q''(''n''). | # Посчитать число функций в заданном классе ''Q''(''n''). | ||
# Сразу же из этого получить асимптотически нижнюю оценку функции Шеннона, связанной с классом ''Q''(''n''): | # Сразу же из этого получить асимптотически нижнюю оценку функции Шеннона, связанной с классом ''Q''(''n''): | ||
- | #* ''L''<sup>''K''</sup>(''Q''(''n'')) ≳ log(|''Q''(''n'')|) / | + | #* ''L''<sup>''K''</sup>(''Q''(''n'')) ≳ log(|''Q''(''n'')|) / ''n'' |
- | #* L<sup>C</sup>(''Q''(''n'')) ≳ log(|''Q''(''n'')|) / | + | #* L<sup>C</sup>(''Q''(''n'')) ≳ log(|''Q''(''n'')|) / ''n'' |
# Показать, как для любой функции из данного класса построить схему из класса U, реализующую данную функцию и имеющую сложность, асимптотически равную вычисленной нижней оценке. Из этого будет следовать, что полученная асимптотически нижняя оценка является и асимптотически верхней оценкой, а из этого, в свою очередь, будет следовать, что функция Шеннона для заданного класса ''U''(''n'') будет просто асимптотически равна полученной нижней оценке. | # Показать, как для любой функции из данного класса построить схему из класса U, реализующую данную функцию и имеющую сложность, асимптотически равную вычисленной нижней оценке. Из этого будет следовать, что полученная асимптотически нижняя оценка является и асимптотически верхней оценкой, а из этого, в свою очередь, будет следовать, что функция Шеннона для заданного класса ''U''(''n'') будет просто асимптотически равна полученной нижней оценке. | ||
#* В пункте 3 всегда пригождается следующее: для любой функции от ''n'' переменных можно построить, реализующую её СФЭ и КС со сложностью, асимптотически не превосходящей 2<sup>n</sup> / ''n'' | #* В пункте 3 всегда пригождается следующее: для любой функции от ''n'' переменных можно построить, реализующую её СФЭ и КС со сложностью, асимптотически не превосходящей 2<sup>n</sup> / ''n'' |