Книги сотрудников ИСИ

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

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

Издание осуществлено при частичной финансовой поддержке Российского фонда фундаментальных исследований (гранты РФФИ № 09-07-00012 и № 08-01-00673).

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

В книге представлены следующие результаты.

• На СП с видимыми и невидимыми переходами и их подклассах введен и изучен большой набор базисных, обратных-прямых и учитывающих места поведенческих эквивалентностей в семантиках от интерливинговой до истинного параллелизма и от линейного до ветвистого времени.
• На временных сетях Петри с видимыми и невидимыми переходами и их подклассах разработан и исследован ряд временных, не-временных и региональных интерливинговых эквивалентностей в следовой и бисимуляционной семантиках.
• На стохастических сетях Петри с невидимыми переходами определен и изучен ряд базисных, обратных и обратных-прямых эквивалентностей в интерливинговой и шаговой, а также в следовой и бисимуляционной семантиках.
• Исследованы семантические эквивалентности стандартных и стохастических ПА, а также их связь с сетевыми эквивалентностными отношениями. Разработан и реализован алгоритм автоматической проверки семантической эквивалентности формул.

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

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

Книгу можно приобрести в интернет-магазине Издательства СО РАН или в книжном магазине Академкнига (г. Новосибирск, Морской пр-т, д. 22, телефон: (383) 330-0922).

Книга посвящена разработке адаптивных методов и средств поддержки дистанционного обучения программированию в рамках проблемного подхода и является четырнадцатой в серии, издаваемой Институтом систем информатики имени А.П. Ершова СО РАН по проблемам конструирования и оптимизации программ. Рассмотрены вопросы дистанционного и проблемного обучения. Исследованы методы и средства адаптации и интеллектуализации дистанционного обучения. Описана адаптивная среда WAPE поддержки дистанционного обучения программированию в рамках проблемного подхода. Представлен вводный курс программирования на базе нового языка Zonnon, недавно пополнившего известное семейство Цюрихских языков: Паскаль, Модула-2 и Оберон.

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

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

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

Настоящая работа посвящена исследованию проблемы автоматического построения сетевых моделей Estelle-спецификаций распределенных систем и развития средств верификации этих моделей. Язык выполнимых спецификаций Estelle принят в качестве международного стандарта. Рассматриваются Estelle-спецификации с задержками и приоритетами, но без динамических конструкций, позволяющие адекватно представлять значительный класс коммуникационных протоколов. В качестве моделей выбраны раскрашенные сети Петри, предложенные Йенсеном, которые расширяются посредством семантик времени в смысле Мерлина и приоритетов. В работе представлен метод трансляции Estelle-спецификаций в данной сетевой модели, описана его реализация, а также система NetCalc, предназначенная для редактирования и симуляции таких моделей. Кроме того, представлены результаты экспериментов по сетевому моделированию и поиску семантических ошибок для версий четырех известных протоколов: со скользящим окном, кольцевого, соединений, InRes.

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

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

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

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

Словарь доступен по следующему адресу http://pco.iis.nsk.su/grapp/.

• Объектно-ориентированное программирование (С++)
• Объектно-ориентированное программирование (С++, Ява и C#)
• Языки спецификаций

Кроме того, здесь же вы найдете домашнее задание.