Биологическая кибернетика представляет собой научное направление, в котором идеи, методы и технические средства кибернетики применяются к рассмотрению задач биологии и физиологии.

Биологическая кибернетика может быть представлена теоретической и практической частью. Основной задачей теоретической биологической кибернетики является изучение общих вопросов управления, хранения, переработки и передачи информации в живых системах. Одним из важнейших методов практической биологической кибернетики является метод моделирования - моделирование структуры и поведения биологических систем. В развитие этого метода биологическая кибернетика включает и вопросы конструирования искусственных систем, воспроизводящих деятельность отдельных органов, их внутренние связи и внешние взаимодействия. В этом направлении биологическая кибернетика смыкается с медицинской.

Медицинская кибернетика является научным направлением, связанным с использованием идей, методов и технических средств кибернетики в медицине и здравоохранении. Условно медицинскую кибернетику можно представить следующими группами.

1. Вычислительная диагностика заболеваний. Эта часть в основном связана с использованием вычислительных машин для постановки диагноза.

Структура любой диагностической системы состоит из медицинской памяти (совокупный медицинский опыт для данной группы заболеваний) и логического устройства, позволяющего сопоставить симптомы, обнаруженные у больного опросом и лабораторным обследованием, с имеющимся медицинским опытом. Этой же структуре следует и диагностическая вычислительная машина.

Первым шагом является разработка методик формального описания состояния здоровья пациента, проводят тщательный анализ по уточнению клинических параметров и признаков, используемых в диагностике. Отбирают главным образом те признаки, которые допускают количественную оценку.

Кроме количественного выражения физиологических, биохимических и других характеристик больного для вычислительной диагностики необходимы сведения о частоте (априорной вероятности) клинических синдромов и диагностических признаков, об их классификации, зависимости, об оценке диагностической эффективности признаков и т.п. Все эти данные хранятся в памяти машины.

Следующим шагом является выбор алгоритма. Машина сопоставляет симптомы больного с данными, заложенными у нее в памяти.

Логика вычислительной диагностики соответствует логике врача, устанавливающего диагноз: совокупность симптомов сопоставляется с предшествующим опытом медицины.

Новую (неизвестную) болезнь машина не установит. Врач, встретивший неизвестное заболевание, сможет описать его признаки. Подробности такого заболевания можно установить, лишь проводя специальные исследования. ЭВМ в таких исследованиях сможет играть вспомогательную роль.

2. Кибернетический подход к лечебному процессу. Установив диагноз, врач назначает и проводит лечение, которое, как правило, не сводится к одноразовому воздействию. Это сложный процесс, во время которого врач вновь и вновь получает медико-биологическую информацию о больном, анализирует эту информацию и в соответствии с ней уточняет, изменяет, прекращает или продолжает лечебное воздействие.

Для кибернетических систем характерно целенаправленное воздействие управляющей системы на объект управления (см. 4.4).

Врач управляет больным, система врач-больной является кибернетической, поэтому кибернетический подход возможен и к лечебному процессу. Однако, несмотря на такие возможности, пока еще проникновение идей, методов и технических средств кибернетики в эту, главнейшую, часть медицины достаточно скромно.

В настоящее время кибернетический подход к лечебному процессу облегчает работу врача, позволяет эффективнее проводить лечение тяжелобольных, своевременно принять меры при осложнениях во время операции, разработать и контролировать процесс лечения медикаментами, создавать биоуправляемые протезы.

Кратко остановимся на возможностях применения такого подхода.

Контроль за состоянием организма человека необходим во многих областях человеческой деятельности (спортивной, производственной, учебной, военной), но особенно важен он в стрессовых ситуациях или в таких лечебных условиях, как, например, хирургические вмешательства с применением искусственного кровообращения, дыхания, при реанимации, в состоянии наркоза и т.п.

Для этих целей создаются информационные системы оперативного врачебного контроля (ИСОВК), которые осуществляют съем медико-биологической информации, автоматическое распознавание функционального состояния пациента, фиксацию нарушений в деятельности организма, диагностирование заболевания, управление устройствами, регулирующими жизненно важные функции.

В задачи оперативного врачебного контроля входят наблюдение за состоянием тяжелобольных с помощью систем слежения (мониторных систем), наблюдение за состоянием здоровых людей, находящихся в экстремальных условиях (стрессовые состояния, невесомость, гипербарические условия, среда с пониженным содержанием кислорода и т.п.).

Реализация принципа интенсивного ухода возможна в результате создания комплекса, позволяющего автоматически непрерывно контролировать состояние больного и сообщать о его изменениях.

Особенно важно получать быстрые и точные сведения о состоянии больного во время операции. В процессе операции фиксируется огромное количество (около 1000) различных параметров, характеризующих состояние больного. Проанализировать и проследить за таким количеством параметров в чрезвычайно короткие сроки для врача практически невозможно. В этих случаях на помощь приходит ЭВМ, тем более что при использовании ЭВМ в нее можно заранее вложить предшествующие

записи из истории болезни, сведения о наличии медикаментов, указания мер, которые необходимо предпринять в критических ситуациях.

Общие данные об оперируемых больных вводятся в ЭВМ заранее. Ввод данных о текущем состоянии производится с момента поступления больного в операционную. Кроме сведений о состоянии больного вводятся сведения о времени, виде и дозе анестезии и медикаментов и начинается непрерывная фиксация медико-биологических параметров. В результате, если какие-либо показатели будут выходить за критические значения, ЭВМ сообщит в виде звуковых или световых сигналов об опасности, выдаст на регистрирующее устройство информацию, объясняющую причины тревоги, и рекомендации по их устранению.

Еще одной возможностью применения кибернетики в медицине является математическое моделирование лечебного процесса, которое может служить основой для расчета оптимальных лечебных воздействий. Так, например, удается рассчитать процесс введения лекарственного препарата в организм больного, с тем чтобы вызвать наилучший лечебный эффект.

Кибернетический подход реализуется при создании сложных протезов, заменяющих некоторые органы. Поясним это примером.

Исследование биотоков мышц показало, что из-за возможности их съема непосредственно на мышцах удается определить информацию, посылаемую к мышцам (исполнительным, управляемым органам) центральной нервной системой (управляющей системой). Было установлено также, что биотоки могут возникать в мышце при команде центральной нервной системы и без выполнения команды, например в случае отсутствия конечности или ее части.

Эти свойства биотоков мышц позволили разработать активные протезы конечностей. Обычный протез, например ноги, восстанавливал лишь часть функции - опору, функция управления и координации в нем отсутствовала.

Разработаны протезы конечностей с биоэлектрическим управлением. Для управления такими конечностями разработаны специальные системы, в которые входят устройства съема биопотенциалов, усилитель и преобразователь, усиливающий сигнал и трансформирующий его в форму, пригодную для управления механической частью протеза (электродвигатели, редукторы и т.п.) и приведения в движение собственно протеза (кисть руки, пальцы, стопа ноги и т.д.).

С помощью преобразователей (датчиков), воспринимающих внешние воздействия на искусственный орган, осуществляется обратная связь: электрический сигнал с преобразователя трансформируется в сиг-

нал, подобный импульсам в воспринимающих нервах живого организма, и посылается от периферии к центру через неповрежденные участки кожи больной конечности.

3. Автоматизированные системы управления и возможности применения их для организации здравоохранения. В предыдущих разделах в основном делался акцент на процессы управления в биологических системах. Однако в своем первородном варианте термин «управление» больше си-нонимизировался с понятием «руководство» и относился к управлению хозяйством, предприятием, т.е. коллективом людей, выполняющих определенную цель. Такое понимание управления, разумеется, также является кибернетическим и, следовательно, процесс управление-руководство может быть оптимизирован с использованием методов и технических средств кибернетики.

Такая оптимизация привела к созданию в народном хозяйстве автоматизированных систем управления (АСУ). АСУ отличается от традиционных форм управления тем, что в них широко используют вычислительную технику для сбора и переработки информации, а также новые организационные принципы для реализации наиболее эффективного управления соответствующим объектом (системой).

Объекты управления АСУ различны как по своим масштабам, так и по назначению: участок цеха, кабинет врача, приемное отделение, предприятие, школа, больница, здравоохранение, отрасль промышленности, народное хозяйство страны и т.д.

В зависимости от уровня иерархии АСУ подразделяют на отдельные системы. Так, например, практически в любой отрасли хозяйства можно выделить отраслевую автоматизированную систему управления (ОАСУ).

Здравоохранение есть отрасль народного хозяйства, поэтому для управления этой отраслью была создана ОАСУ «Здравоохранение».

Не вдаваясь в детали такой ОАСУ, что является задачей специального курса в медицинском вузе, отметим лишь ее некоторые особенности.

Любые ОАСУ могут строиться на основе моделей, которые учитывают не только связи внутри данной отрасли, но и межотраслевые связи, т.е. взаимоотношение данной системы со всем народным хозяйством. Применительно к ОАСУ «3дравоохранение» модель должна включать как блок управления, так и другие элементы: профилактику, лечение (с диагностикой), медицинскую науку, кадры, материальное обеспечение.

Каждый из перечисленных элементов (блоков) ОАСУ связан как с элементами этой же системы, так и с другими системами. Проиллюстрируем это на примере профилактики заболеваний. Она включает иммунизацию населения, массовые медицинские осмотры, медицинское

просвещение и др. Массовые медицинские осмотры связаны с наличием подготовленных врачебных кадров, обеспеченностью аппаратурой и др. (внутренние связи и зависимости), состоянием и развитием промышленных предприятий, размещением населения по географическим зонам и др. (внешние связи, выходящие за пределы данной ОАСУ).

В первоочередные задачи ОАСУ «3дравоохранение» входят автоматизация процессов сбора и анализа статистической информации по основным направлениям медицинской деятельности и решение вопросов оптимизации некоторых процессов управления.

 

Оглавление

Аннотация рабочей программы дисциплины «Теоретические основы кибернетики» Учебная дисциплина «Теоретические основы кибернетики» относится к базовой части дисциплин специальности профессионального цикла подго- товки специалистов по направлению 060609 – медицинская кибернетика в медицинском институте ПГУ на кафедре «Медицинские информационные системы и технологии». Процесс изучения дисциплины «Теоретические основы кибернетики» направлен на формирование элементов следующих компетенций в соответст- вии с ФГОС ВПО по данной специальности: Код компе- тенции Наименование компетенции Структурные элементы компетенции ОК-7 Способен и готов к исполь- зованию методов управле- ния, к организации работы исполнителей, находить и принимать ответственные управленческие решения в условиях различных мнений Знать: модели формирования решений, основанных на знаниях Уметь: находить управленческие решения в условиях неоп- ределённости Владеть: навыками принятия компромиссных решений в ус- ловиях различных мнений ПК-15 Способен и готов разрабаты- вать и внедрять современные информационные техноло- гии в медицине и здраво- охранении, применять мате- матические методы и совре- менные программные сред- ства для обработки экспери- ментальных и клинико- диагностических данных, моделирования медико- биологических процессов Знать: автоматизацию ввода и обработки на ЭВМ физиоло- гических сигналов; методы гармонического анализа и преобразования сигналов для обработки медицинских данных на ЭВМ; методы распознавания образов, применяемые для анализа клинических данных, области их применения и ограничения; применение математических и информационных для решения задач дифференциальной диагностики Уметь: применять методы гармонического анализа и преоб- разования сигналов для обработки медицинских дан- ных на ЭВМ; применять методы распознавания образов и теории информации для решения задач медицинского диаг- ностирования Владеть: методами прикладной математики для решения за- дач диагностического моделирования физиологиче- ских систем и вычислительной диагностики Преподавание дисциплины предусматривает следующие формы орга- низации и технологии учебного процесса: лекции с применением мультимедийных технологий и проблемного обучения; практические занятия с использованием информационных технологий и анализом реальных проблемных ситуаций; индивидуальное обучение отлично успевающих студентов на основе формирования индивидуальной программы по дисциплине с учётом интере- сов студентов; самостоятельную работу студента с использованием электронных обра- зовательных ресурсов, компьютерных сетей; участие студентов в научно-исследовательских работах. Взаимосвязь учебной дисциплины «Теоретические основы кибернети- ки» с другими частями ОПОП: Учебные дисциплины, на которых основы- вается освоение теоретических основ ки- бернетики Учебные дисциплины, освоение которых основывается на изучении теоретических основ кибернетики Дифференциальное и интегральное исчис- ление. Математическая статистика. Инфор- матика, медицинская информатика. Компь- ютерный практикум по информатике. Био- логия. Общая биофизика. Физические осно- вы медицинских измерений. Вероятностные методы анализа и планирования медицин- ского эксперимента Физиологическая кибернетика. Медицин- ская биофизика. Клиническая кибернетика. Системный анализ и организация здраво- охранения. Информационные медицинские системы. Клиническая лабораторная диаг- ностика. Функциональная диагностика. Ви- зуализация и интерпретация сигналов в ме- дицинской диагностике. Планирование на- учных исследований в биологии и медици- не. Методы диагностики в клинике внут- ренних болезней. Методы диагностики в кардиологии. Компьютерные технологии в медико-биологических исследованиях. Ме- тоды обработки биомедицинских сигналов и данных Общая трудоёмкость освоения дисциплины составляет 9 зачетных еди- ницы. Продолжительность изучения дисциплины 2 семестра.

 

Список вопросов и типовых задач к экзамену по курсу «Основы кибернетики» (весенний семестр 2014-2015 уч. г.; 320-328 гр.) I. Основные вопросы, входящие в экзаменационные билеты 1. Представление функций алгебры логики (ФАЛ) дизъюнктивными нормальными формами (ДНФ) и его «геометрическая» интерпретация. Совершенная ДНФ и критерий единственности ДНФ. См. [1:гл.1,§§2,5]. 2. Сокращённая ДНФ и способы её построения [1:гл.1,§3]. 3. Тупиковая ДНФ, ядро и ДНФ пересечение тупиковых. ДНФ Квайна, критерий вхождения простых импликант в тупиковые ДНФ и его локальность. См. [1:гл.1,§4]. 4. Особенности ДНФ линейных и монотонных ФАЛ. Функция покрытия, таблица Квайна и построение всех тупиковых ДНФ. См. [1:гл.1,§§5,6]. 5. Градиентный алгоритм и оценка длины градиентного покрытия, лемма о «протыкающих» наборах. Использование градиентного алгоритма для построения ДНФ. См. [1:гл.1,§6]. 6. Задача минимизации ДНФ. Поведение функции Шеннона и оценки типичных значений для ранга и длины ДНФ [1:гл.1,§7]. 7. Алгоритмические трудности минимизации ДНФ и оценки максимальных значений некоторых связанных с ней параметров [1:гл.1,§§1,3,7]. Теорема Ю.И. Журавлёва о ДНФ сумма минимальных [1:гл.1,§5]. 8. Формулы и способы их задания, эквивалентность формул и функционалы их сложности [1:гл.1,§1, гл.3,§1]. Оптимизация подобных формул по глубине [1:гл.2,§2]. 9. Схемы из функциональных элементов (СФЭ) и операции их приведения. Оценка числа формул и СФЭ в базисе Б0={&,۷,ך}. См. [1:гл.2,§§2,3]. 10. Контактные схемы (КС) и π-схемы, моделирование формул и π-схем. Оценки числа КС и числа π-схем, особенности функционирования многополюсных КС. См. [1:гл.2,§§5,6]. 11. Эквивалентные преобразования формул с помощью тождеств. Полнота системы основных тождеств для эквивалентных преобразований формул базиса Б0. См. [1:гл.3,§2]. 12. Эквивалентные преобразования СФЭ и моделирование с их помощью формульных преобразований. Моделирование эквивалентных преобразований формул и схем в различных базисах, теорема перехода. См. [1:гл.3,§§1,3]. 13. Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных и обобщённых тождеств. См. [1:гл.3,§4]. 14. Полнота системы основных тождеств. Отсутствие конечной полной системы тождеств в классе всех КС. См. [1:гл.3,§5]. 15. Задача синтеза. Методы синтеза схем на основе ДНФ и связанные с ними верхние оценки сложности функций. См. [1:гл.4,§1]. 16. Нижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальность некоторых схем. См. [1:гл.4,§2], [7:§7]. 17. Разложение ФАЛ и операция суперпозиции схем. Корректность суперпозиции для некоторых типов схем, разделительные КС и лемма Шеннона. См. [1:гл.2,§§6,7]. 18. Каскадные КС и СФЭ. Метод каскадов и примеры его применения, метод Шеннона. См. [1:гл.4,§3]. 19. Нижние мощностные оценки функций Шеннона, их обобщение на случай синтеза схем для ФАЛ из специальных классов [1:гл.4,§4]. 20. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший метод О.Б. Лупанова для синтеза СФЭ в базисе Б0. См. [1:гл.4,§5]. 21. Регулярные разбиения единичного куба и моделирование ФАЛ переменными. Асимптотически наилучший метод синтеза формул в базисе Б0. См. [1:гл.4,§6]. 22. Асимптотически наилучший метод синтеза КС. Синтез схем для ФАЛ из некоторых специальных классов. См. [1:гл.4, §§7,5]. 23. Синтез схем для некоторых дешифраторов и мультиплексоров. Поведение функции Шеннона для глубины ФАЛ [1:гл.4,§6]. 24. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста. См. [1:гл.1,§8]. 25. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание). См. [4:§7], [2: ч. III, р. 2, §1]. 2 II. Дополнительные вопросы 26. Полиномиальная сводимость языков. Классы P и NP, NP-полнота, формулировка теоремы Кука. Примеры NP-полных проблем. См. [6:§§4.1,4.5-4.8]. 27. Некоторые модификации основных классов схем (BDD, вычисляющие программы, схемы на КМОП-транзисторах и др.), связанные с программно-аппаратной реализацией ФАЛ. См. [1:гл.2,§§4,6,7]. 28. Реализация автоматных функций схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями. См. [7:§8], [2: ч. I, р. I, гл. 3, §§2-3]. III. Типовые задачи к экзамену 1. По заданной ФАЛ построить её сокращённую ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ. 2. По заданной формуле построить подобную ей формулу минимальной глубины. 3. По заданной формуле с поднятыми отрицаниями построить моделирующую её π-схему и обратно. 4. По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств. 5. По данной каскадной КС построить инверсную каскадную КС. 6. По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую её СФЭ или КС. 7. Оценить сверху и снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем. 8. По заданной КС построить эквивалентную ей самокорректирующуюся КС. 9. По заданной таблице или КС и списку её неисправностей построить все тупиковые проверяющие (диагностические) тесты. IV. Литература Основная: 1. Ложкин С.А. Лекции по основам кибернетики. – М.: МГУ, 2004. (Электронные версии лекций последних лет можно найти по адресу http://mk.cs.msu.ru/index.php/Основы_кибернетики_(3-й_поток) ) 2. Яблонский С.В. Элементы математической кибернетики. – М.: Высшая школа, 2007. 3. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986. 4. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнёва С.Н. Задачи по курсу «Основы кибернетики». – М.: МГУ, 2011. 5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2004. 6. Алексеев В.Б. Введение в теорию сложности алгоритмов. – М.: Изд-во МГУ, 2002. Дополнительная: 7. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов. – М.: МГУ, 2000. 8. Дискретная математика и математические вопросы кибернетики. – М.: Наука, 1974. 9. Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС. (http://mk.cs.msu.ru/images/8/87/Lozhkin-Marchenko-VSLI-models.pdf) 10. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. – М.: МГУ, 1984. 11. Нигматулин Р.Г. Сложность булевых функций. – М.: Наука, 1991. 3 Порядок проведения экзамена по курсу «Основы кибернетики» В соответствии с объявленными в начале семестра правилами, по результатам контрольных работ с учётом посещаемости студентов, их работы на лекциях и семинарах, а также самостоятельной работы каждому из них выставляется предварительная оценка. Для студентов, имеющих предварительную оценку «5», экзамен проводится в форме общего собеседования по программе курса на определения, формулировки утверждений и идеи их доказательства, методы решения задач. Для студентов, имеющих предварительную оценку «2», экзамен представляет собой письменный тест-контрольную из 9-10 вопросов и задач продолжительностью 2 астрономических часа. Данный тест могут по желанию писать и студенты, имеющие оценку «3-», но их итоговая оценка в этом случае будет не больше «3». Все остальные студенты (с предварительной оценкой «3-», «3» и «4») получают билет с двумя вопросами и одной задачей и после 15-20 минутной подготовки отвечают на него сначала на уровне определений, формулировок утверждений и идей их доказательства, а также методов решения задач. Затем студент, по усмотрению экзаменатора, должен раскрыть те или иные детали доказательства утверждений из вопросов билета по конспектам или иным источникам, а также полностью или частично решить задачу билета в течение выделенного специально для этого времени. Студенты, набравшие не менее 80% от суммы баллов по задачам тестов-контрольных соответствующего раздела, то есть получившие по ним оценку «5», от решения билетной задачи данного типа освобождаются. Последний этап экзамена представляет собой описанное выше общее собеседование по другим вопросам или задачам программы. В соответствии с принятыми правилами итоговая экзаменационная оценка не может превосходить предварительную оценку больше, чем на один балл. Студент, который имеет предварительную оценку «3» или «4» и не претендует на более высокую итог

 

 

«Синтез и сложность управляющих систем» Решения задач присылать по адресу [email protected]. Каждая задача засчитыва- ется первому приславшему её правильное решение. Задача 1. Определим понятие коммуникативной сложности ФАЛ 𝑓, 𝑓 ∈ 𝑃2(𝑛). Пусть Алисе да- ется некоторый набор 𝛼˜ = (𝛼1, . . . , 𝛼𝑛), а Бобу — некоторый набор 𝛽˜ = (𝛽1, . . . , 𝛽𝑛) значений БП 𝑥1, . . . , 𝑥𝑛, причем 𝑓(˜𝛼) ̸= 𝑓(𝛽˜), Алиса не знает 𝛽, ˜ а Боб не знает 𝛼, ˜ но оба знают ФАЛ 𝑓. Обмениваясь информацией (битовыми сообщениями), каждый из них должен найти такой (один и тот же) разряд 𝑗, в котором наборы 𝛼˜ и 𝛽˜ от- личаются. Коммуникативной сложностью ФАЛ 𝑓 называется минимальное число необходимых битовых сообщений, при котором Алиса и Боб гарантированно найдут искомый разряд. Доказать, что при условии нулевой глубины элемента отрицания глубина любой ФАЛ в стандартном базисе совпадает с коммуникативной сложностью этой ФАЛ. Задача 2. Доказать, что для любой ФАЛ 𝑓, 𝑓 ∈ 𝑃2(𝑛), существует (1, 2)-КС Σ𝑓 , реализующая систему (𝑓, ¯𝑓) и такая, что 𝐿(Σ𝑓 ) . 2 𝑛 𝑛 . Задача 3. Для линейной ФАЛ 𝑙8 = 𝑥1 ⊕ 𝑥2 ⊕ . . . ⊕ 𝑥8 построить реализующую её минимальную КС сложности 28, отличную по структуре от схемы Кардо. Задача 4. Пусть 𝑄(𝑛) – множество ФАЛ 𝑓, 𝑓 ∈ 𝑃2(𝑛), столбец значений которых имеет префикс вида {(001); (010); (100)} ⌊ 2 𝑛 3 ⌋ . Найти асимптотику функции Шеннона 𝐿 𝐾(𝑄(𝑛)) для сложности реализаций функций из этого множества в классе контактных схем.

 

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