Основы кибернетики МГУ Факультет вычислительной математики и кибернетики вопросы и ответы

Список вопросов с ответами по предмету «Основы кибернетики». Учебные материалы для подготовки к экзамену и зачёту.

Вопросы и ответы

  1. Сложность одновременного нахождения максимума и минимума в массиве 2 источника 2 источника
  2. Задача о минимальном остовном дереве и жадный алгоритм 1 источник 1 источник
  3. Тестирование линейности булевой функции и доказательство нелинейности 1 источник 1 источник
  4. Полиномиальные сведения между SAT, 3-SAT, CLIQUE и другими NP-полными задачами 1 источник 1 источник
  5. NP-полнота задачи РАСКРАСКА графа 1 источник 1 источник
  6. NP-полнота задачи ПОКРЫТИЕ МНОЖЕСТВА 1 источник 1 источник
  7. Минимальное вершинное покрытие и жадный алгоритм 2 источника 2 источника
  8. NP-полнота задачи ВЕРШИННОЕ ПОКРЫТИЕ 1 источник 1 источник
  9. NP-полнота задачи КЛИКА 1 источник 1 источник
  10. NP-полнота задачи 0–1 целочисленного программирования 1 источник 1 источник
  11. Задача 3-ВЫПОЛНИМОСТЬ и её NP-полнота 1 источник 1 источник
  12. Задача 2-ВЫПОЛНИМОСТЬ и полиномиальный алгоритм решения 1 источник 1 источник
  13. Задача ВЫПОЛНИМОСТЬ (SAT) и её принадлежность классу NP 1 источник 1 источник
  14. Теорема Кука—Левина 2 источника 2 источника
  15. NP-полнота: определение, свойства и значение 1 источник 1 источник
  16. Полиномиальная сводимость вычислительных задач 1 источник 1 источник
  17. Детерминированные и недетерминированные вычисления: классы P и NP 1 источник 1 источник
  18. Машины Тьюринга и временная сложность вычислений 1 источник 1 источник
  19. Аппаратная информационная безопасность в задачах синтеза схем 3 источника 3 источника
  20. Логический и топологический синтез СБИС: задачи, этапы и методы 2 источника 2 источника
  21. Схемы на КМОП-транзисторах как модель аппаратной реализации логики 1 источник 1 источник
  22. Схемы с мгновенными обратными связями 2 источника 2 источника
  23. Автоматные функции и их реализация схемами с элементами задержки 2 источника 2 источника
  24. Модифицированные классы схем для программно-аппаратной реализации ФАЛ: BDD и вычисляющие программы 2 источника 2 источника
  25. Длина диагностического теста: максимальные, типичные и почти-всюду оценки 1 источник 1 источник
  26. Алгоритм построения всех тупиковых тестов 1 источник 1 источник
  27. Задача контроля управляющих систем и тесты для таблиц 1 источник 1 источник
  28. Асимптотически оптимальный синтез КС, корректирующих один обрыв или одно замыкание 1 источник 1 источник
  29. Самокорректирующиеся контактные схемы и методы их построения 1 источник 1 источник
  30. Модели неисправностей и задача повышения надёжности управляющих систем 1 источник 1 источник
  31. Связь схемной и временной сложности вычислений: теорема Сэвиджа 1 источник 1 источник
  32. Основные классы дискретных управляющих систем и меры их сложности 1 источник 1 источник
  33. Локальные алгоритмы минимизации ДНФ и ограничения локальных методов 1 источник 1 источник
  34. Алгоритмические трудности синтеза минимальных схем: инвариантные классы и результат С. В. Яблонского 1 источник 1 источник
  35. Методы верхней и нижней оценки сложности конкретных ФАЛ и систем ФАЛ 1 источник 1 источник
  36. Асимптотически оптимальный синтез контактных схем 1 источник 1 источник
  37. Регулярные разбиения единичного куба и асимптотически оптимальный синтез формул 1 источник 1 источник
  38. Асимптотически оптимальный метод О. Б. Лупанова синтеза СФЭ 1 источник 1 источник
  39. Дизъюнктивно-универсальные множества функций алгебры логики 1 источник 1 источник
  40. Нижние мощностные оценки функций Шеннона 1 источник 1 источник
  41. Метод Шеннона синтеза схем 1 источник 1 источник
  42. Каскадные контактные схемы и СФЭ: метод каскадов и его применение 1 источник 1 источник
  43. Разложение ФАЛ и суперпозиция схем: корректность, разделительные КС и лемма Шеннона 1 источник 1 источник
  44. Методы синтеза схем на основе ДНФ и верхние оценки сложности 1 источник 1 источник
  45. Простейшие нижние оценки сложности функций алгебры логики 1 источник 1 источник
  46. Задача синтеза управляющих систем и сложность функций алгебры логики 1 источник 1 источник
  47. Функция Линдона: пример Линдона и решение уравнений 1 источник 1 источник
  48. Теоремы Янова—Мучника в теории управляющих систем 1 источник 1 источник
  49. Полнота системы основных тождеств для контактных схем и отсутствие конечной полной системы 1 источник 1 источник
  50. Эквивалентные преобразования контактных схем: основные, вспомогательные и обобщённые тождества 1 источник 1 источник