Основы Кибернетики, экзаменационные вопросы 3 потока

Материал из eSyr's wiki.

(Различия между версиями)
Перейти к: навигация, поиск
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...»)
(Отмена правки № 1444 участника 216.224.124.124 (обсуждение))
Строка 1: Строка 1:
-
== From Ebaums Inc to MurkLoar. ==
+
== Информация о курсе ==
-
We at EbaumsWorld consider you as disgrace of human race.
+
*какого цвета учебник? — розового
-
Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
+
*как называется курс? — «Основы кибернетики»
-
Dig yourself a grave - you will need it.
+
*как зовут лектора? — профессор Сергей Андреевич Ложкин (http://mathcyb.cs.msu.su/staff/lozhkin.html)
 +
 
 +
== Вопросы к экзамену по курсу «Основы кибернетики» ==
 +
* [http://mathcyb.cs.msu.su/inf/oc3-3.doc взято] с [http://mathcyb.cs.msu.su/ сайта кафедры математической кибернетики] (весенний семестр 2006—2007 учебного года, 320-328, 341 группы)
 +
 
 +
*I. Представление функций с помощью дизъюнктивных нормальных форм и связанные с ним задачи.
 +
**1. Единичный куб и функции алгебры логики (ФАЛ). Дизъюнктивные (конъюнктивные) нормальные формы, связанные с ними представления и разложения ФАЛ ([1:гл.1,§2]).
 +
**2. Сокращенная дизъюнктивная нормальная форма (ДНФ) и способы ее построения ([1:гл.1,§3]).
 +
**3. Тупиковые и минимальные ДНФ, ядро и ДНФ Квайна. Критерий вхождения простых импликант в тупиковые ДНФ, его локальность ([1:гл.1,§4]).
 +
**4. Особенности ДНФ для ФАЛ из некоторых классов (линейных, монотонных и др.). Теорема Ю.И. Журавлева о ДНФ сумма минимальных ([1:гл.1,§5]).
 +
**5. Функция покрытия, таблица Квайна и построение всех тупиковых ДНФ. Градиентный алгоритм и оценка длины градиентного покрытия ([1:гл.1,§6]).
 +
**6. Задача минимизации ДНФ. Поведение функций Шеннона и оценки типичных значений для ранга и длины ДНФ ([1:гл.1,§7]).
 +
**7. Алгоритмические трудности минимизации ДНФ и оценки максимальных значений некоторых связанных с ней параметров ([1:гл.1,§§2,3,7]).
 +
**8. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста ([1:гл.1,§8]).
 +
*II. Основные классы дискретных управляющих систем. Оценка числа схем, их структурные представления и эквивалентные преобразования.
 +
**9. Задание формул деревьями, схемы из функциональных элементов (СФЭ). Оценка числа формул и СФЭ в базисе Б0={&,۷,ך} ([1:гл.2,§§2,3]).
 +
**10. Задача эквивалентных преобразований на примере формул ([1:гл.3,§1]). Оптимизация подобных формул по глубине ([1:гл.2§2]).
 +
**11. Полнота системы основных тождеств для эквивалентных преобразований формул базиса Б0 ([1:гл.3,§2]).
 +
**12. Эквивалентные преобразования СФЭ, моделирование эквивалентных преобразований формул в классе СФЭ. Моделирование эквивалентных преобразований в различных базисах, теорема перехода. ([1:гл.3,§1,3]).
 +
**13. Контактные схемы (КС) и π-схемы, оценка их числа. Особенности функционирования многополюсных КС ([1:гл.2,§§5,6]).
 +
**14. Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных и обобщенных тождеств ([1:гл.3,§4]).
 +
**15. Полнота системы основных тождеств. Отсутствие конечной полной системы тождеств в классе всех КС ([1:гл.3,§5]).
 +
**16. Операция суперпозиции и её корректность для некоторых типов схем. Разделительные КС, лемма Шеннона ([1:гл.2,§§1,3,6]).
 +
*III. Синтез, сложность и надежность управляющих систем.
 +
**17. Задача синтеза. Простейшие методы синтеза схем и оценки сложности функций ([1:гл.4,§§1,2]).
 +
**18. Метод каскадов для КС и СФЭ, примеры его применения ([1:гл.4,§3]).
 +
**19. Метод Шеннона и связанные с ним верхние оценки функций Шеннона ([1: гл.4,§3]).
 +
**20. Нижние мощностные оценки функций Шеннона ([1:гл.4,§4]).
 +
**21. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший метод О.Б. Лупанова для синтеза СФЭ в базисе Б0 ([1:гл.4,§5]).
 +
**22. Регулярные разбиения единичного куба и моделирование ФАЛ переменными. Оценки сложности некоторых дешифраторов и мультиплексоров ([1:гл.4,§§6,7]).
 +
**23. Асимптотически наилучший метод синтеза КС ([1:гл.4,§7]).
 +
**24. Асимптотически наилучший метод синтеза формул в базисе Б0, поведение функции Шеннона для глубины ФАЛ ([1:гл.4,§6]).
 +
**25. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание) ([2:§7], [11:§2.1]).
 +
**26. Задача синтеза схем для ФАЛ из специальных классов и индивидуальных ФАЛ. Методы получения верхних и нижних оценок сложности, минимальность некоторых схем ([8], [9:§2]).
 +
*IV. Некоторые прикладные вопросы теории сложности. Структурные модели высокого уровня.
 +
**27. Реализация автоматных функций схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями ([4:§8]). Схемы на КМОП-транзисторах и реализация ими простейших функций. ([1:гл.II,§7], [6]).
 +
**28. Вычисляющие и адресующие программы, представление о логических схемах программ. ([1:гл.2§§4,7].
 +
 
 +
 
 +
== [[Основы Кибернетики, Алгоритмы решения задач|Типовые задачи к экзамену]] ==
 +
# [[Основы Кибернетики, Алгоритмы решения задач/Задачи на ДНФ|Задачи на ДНФ]]
 +
## По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ.
 +
# [[Основы Кибернетики, Алгоритмы решения задач/Задачи на тесты|Задачи на тесты]]
 +
## По заданной таблице или КС и списку ее неисправностей построить все тупиковые проверяющие (диагностические) тесты.
 +
# [[Основы Кибернетики, Алгоритмы решения задач/Задачи на эквивалентные преобразования и структурное моделирование|Задачи на эквивалентные преобразования и структурное моделирование]]
 +
## По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств.
 +
## По заданной формуле построить подобную ей формулу минимальной глубины.
 +
## По заданной формуле с поднятыми отрицаниями построить моделирующую ее π-схему и обратно.
 +
# [[Основы Кибернетики, Алгоритмы решения задач/Задачи на синтез схем|Задачи на синтез схем]]
 +
## По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую ее СФЭ или КС.
 +
## Оценить сверху или снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем.
 +
## По заданной КС построить эквивалентную ей самокорректирующуюся КС.
 +
 
 +
{{Курс Основы Кибернетики}}

Версия 17:51, 3 февраля 2008

Информация о курсе

  • какого цвета учебник? — розового
  • как называется курс? — «Основы кибернетики»
  • как зовут лектора? — профессор Сергей Андреевич Ложкин (http://mathcyb.cs.msu.su/staff/lozhkin.html)

Вопросы к экзамену по курсу «Основы кибернетики»

  • I. Представление функций с помощью дизъюнктивных нормальных форм и связанные с ним задачи.
    • 1. Единичный куб и функции алгебры логики (ФАЛ). Дизъюнктивные (конъюнктивные) нормальные формы, связанные с ними представления и разложения ФАЛ ([1:гл.1,§2]).
    • 2. Сокращенная дизъюнктивная нормальная форма (ДНФ) и способы ее построения ([1:гл.1,§3]).
    • 3. Тупиковые и минимальные ДНФ, ядро и ДНФ Квайна. Критерий вхождения простых импликант в тупиковые ДНФ, его локальность ([1:гл.1,§4]).
    • 4. Особенности ДНФ для ФАЛ из некоторых классов (линейных, монотонных и др.). Теорема Ю.И. Журавлева о ДНФ сумма минимальных ([1:гл.1,§5]).
    • 5. Функция покрытия, таблица Квайна и построение всех тупиковых ДНФ. Градиентный алгоритм и оценка длины градиентного покрытия ([1:гл.1,§6]).
    • 6. Задача минимизации ДНФ. Поведение функций Шеннона и оценки типичных значений для ранга и длины ДНФ ([1:гл.1,§7]).
    • 7. Алгоритмические трудности минимизации ДНФ и оценки максимальных значений некоторых связанных с ней параметров ([1:гл.1,§§2,3,7]).
    • 8. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста ([1:гл.1,§8]).
  • II. Основные классы дискретных управляющих систем. Оценка числа схем, их структурные представления и эквивалентные преобразования.
    • 9. Задание формул деревьями, схемы из функциональных элементов (СФЭ). Оценка числа формул и СФЭ в базисе Б0={&,۷,ך} ([1:гл.2,§§2,3]).
    • 10. Задача эквивалентных преобразований на примере формул ([1:гл.3,§1]). Оптимизация подобных формул по глубине ([1:гл.2§2]).
    • 11. Полнота системы основных тождеств для эквивалентных преобразований формул базиса Б0 ([1:гл.3,§2]).
    • 12. Эквивалентные преобразования СФЭ, моделирование эквивалентных преобразований формул в классе СФЭ. Моделирование эквивалентных преобразований в различных базисах, теорема перехода. ([1:гл.3,§1,3]).
    • 13. Контактные схемы (КС) и π-схемы, оценка их числа. Особенности функционирования многополюсных КС ([1:гл.2,§§5,6]).
    • 14. Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных и обобщенных тождеств ([1:гл.3,§4]).
    • 15. Полнота системы основных тождеств. Отсутствие конечной полной системы тождеств в классе всех КС ([1:гл.3,§5]).
    • 16. Операция суперпозиции и её корректность для некоторых типов схем. Разделительные КС, лемма Шеннона ([1:гл.2,§§1,3,6]).
  • III. Синтез, сложность и надежность управляющих систем.
    • 17. Задача синтеза. Простейшие методы синтеза схем и оценки сложности функций ([1:гл.4,§§1,2]).
    • 18. Метод каскадов для КС и СФЭ, примеры его применения ([1:гл.4,§3]).
    • 19. Метод Шеннона и связанные с ним верхние оценки функций Шеннона ([1: гл.4,§3]).
    • 20. Нижние мощностные оценки функций Шеннона ([1:гл.4,§4]).
    • 21. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший метод О.Б. Лупанова для синтеза СФЭ в базисе Б0 ([1:гл.4,§5]).
    • 22. Регулярные разбиения единичного куба и моделирование ФАЛ переменными. Оценки сложности некоторых дешифраторов и мультиплексоров ([1:гл.4,§§6,7]).
    • 23. Асимптотически наилучший метод синтеза КС ([1:гл.4,§7]).
    • 24. Асимптотически наилучший метод синтеза формул в базисе Б0, поведение функции Шеннона для глубины ФАЛ ([1:гл.4,§6]).
    • 25. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание) ([2:§7], [11:§2.1]).
    • 26. Задача синтеза схем для ФАЛ из специальных классов и индивидуальных ФАЛ. Методы получения верхних и нижних оценок сложности, минимальность некоторых схем ([8], [9:§2]).
  • IV. Некоторые прикладные вопросы теории сложности. Структурные модели высокого уровня.
    • 27. Реализация автоматных функций схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями ([4:§8]). Схемы на КМОП-транзисторах и реализация ими простейших функций. ([1:гл.II,§7], [6]).
    • 28. Вычисляющие и адресующие программы, представление о логических схемах программ. ([1:гл.2§§4,7].


Типовые задачи к экзамену

  1. Задачи на ДНФ
    1. По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ.
  2. Задачи на тесты
    1. По заданной таблице или КС и списку ее неисправностей построить все тупиковые проверяющие (диагностические) тесты.
  3. Задачи на эквивалентные преобразования и структурное моделирование
    1. По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств.
    2. По заданной формуле построить подобную ей формулу минимальной глубины.
    3. По заданной формуле с поднятыми отрицаниями построить моделирующую ее π-схему и обратно.
  4. Задачи на синтез схем
    1. По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую ее СФЭ или КС.
    2. Оценить сверху или снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем.
    3. По заданной КС построить эквивалентную ей самокорректирующуюся КС.


Основы Кибернетики

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16

Календарь

пт пт пт пт пт
Февраль
 09 16 26
Март
02 09 16 23 30
Апрель
06 13 20 27
Май
04 11 18 25

Материалы к экзамену

Экзаменационные вопросы 3 потока 2007 (new!) | Алгоритмы решения задач | Теормин | Определения

Получено с http://esyr.us/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D1%8B_%D0%9A%D0%B8%D0%B1%D0%B5%D1%80%D0%BD%D0%B5%D1%82%D0%B8%D0%BA%D0%B8%2C_%D1%8D%D0%BA%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B2%D0%BE%D0%BF%D1%80%D0%BE%D1%81%D1%8B_3_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0
Личные инструменты
Разделы