Программа дисциплины «Теоретические основы информатики»

Программа дисциплины

«Теоретические основы информатики»

для направления 080700.62 – «Бизнес-информатика»

Утверждена Учебно-методическим Советом ПФ ГУ-ВШЭ Председатель____________ «_______»__________________________2010 г.

Одобрена на заседании кафедры Информационных технологий в бизнесе протокол __________ Зав. кафедрой________________ «______»__________________________2010 г.

Пермь 2010

I.  Обязательный минимум содержания дисциплины по ГОС

Программа разработана в соответствии государственным образовательным стандартом высшего профессионального образования по направлению подготовки 080500 «Бизнес-информатика (квалификация (степень) "бакалавр")», утвержденным приказом Министерства образования и науки РФ от 14 января 2010 г. № 27. Государственный образовательный стандарт высшего профессионального образования определяет совокупность требований, обязательных при реализации основных образовательных программ бакалавриата по направлению подготовки 080500 «Бизнес-информатика» образовательными учреждениями высшего профессионального образования на территории Российской Федерации.

Выпускник должен обладать следующими общекультурными компетенциями (ОК):

-  осознает сущность и значение информации в развитии современного общества; владеет основными методами, способами и средствами получения, хранения, переработки информации (ОК-12);

-  имеет навыки работы с компьютером как средством управления информацией, способен работать с информацией в глобальных компьютерных сетях (ОК-13);

-  способен работать с информацией из различных источников (ОК-16);

-  способен к организованному подходу к освоению и приобретению новых навыков и компетенций (ОК-17);

Выпускник должен обладать следующими профессиональными компетенциями (ПК):

-  использовать основные методы естественнонаучных дисциплин в профессиональной деятельности для теоретического и экспериментального исследования (ПК-19);

-  использовать соответствующий математический аппарат и инструментальные средства для обработки, анализа и систематизации информации по теме исследования (ПК-20);

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

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

Изучение курса «Теоретические основы информатики» на первом курсе обеспечивает получение следующих основных знаний, навыков и умений, определяемых ГОС ВПО:

Бакалавр бизнес-информатики должен

-  знать:

×  теоретические основы информатики;

-  уметь:

×  применять математические методы и инструментальные средства для исследования объектов профессиональной деятельности;

×  строить математические модели объектов профессиональной деятельности;

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

×  систематизировать и обобщать информацию;

-  владеть:

×  основами математического моделирования прикладных задач, решаемых аналитическими методами;

×  навыками решения задач дискретной математики;

×  навыками решения оптимизационных задач с ограничениями;

×  методами поиска, хранения и обработки информации.

II.  Пояснительная записка

1.  Автор программы: , к. ф.-м. н., доцент

2.  Требования к студентам:

Приступая к изучению данной дисциплины, студент должен обладать знаниями информатики в объеме общеобразовательной школы, а также знаниями, полученными при изучении курсов «Программирование», «Программирование на языке Pascal», «Геометрия и алгебра», «Информационные процессы, системы и сети».

3.  Аннотация:

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

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

Задачи:

-  познакомить студентов с базовыми понятиями в области современных информационных технологий;

-  познакомить с теоретическими основами создания и функционирования информационных систем различного назначения;

-  познакомить с различными методологическими подходами к моделированию и проектированию информационных систем;

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

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

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

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

4.  Учебная задача курса:

В результате изучения курса студент должен:

·  Иметь представление:

-  об эволюции информационных технологий и современных тенденциях развития средств ИКТ;

-  о типовой структуре информационных систем и о существующих подходах к моделированию информационных систем, различных классах моделей, применяемых в области ИТ;

-  о методах теории множеств, теории графов и конечных автоматов, математической логики и неклассических логик, алгебры, применяемых при проектировании и анализе информационных систем, их компонентов;

-  о проблемах, возникающих при создании сложных ИС различного назначения и подходах к их решению;

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

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

·  Знать:

-  основные термины, применяемые при описании моделей, анализе и проектировании ИС, оценке их эффективности;

-  определения и основные характеристики различных классов информационных систем;

-  общие теоретические основы и математические методы, применяемые при создании сложных программных систем;

-  особенности применения моделей различных типов для решения типовых задач моделирования бизнес-систем и проектирования ИС.

·  Уметь:

-  решать задачи, связанные с проблемами разработки сложных ИС в различных предметных областях, и выбирать средства их решения;

-  выбирать эффективные методы создания и исследования моделей ИС.

·  Обладать навыками:

-  навыками применения математического аппарата для решения задач, связанных и моделированием бизнес-систем, анализом и проектированием ИС;

-  создания простейших моделей систем;

-  анализа проблем, связанных с проектированием программных систем.

Студенты после изучения курса должны иметь представление о возможностях различных подходов к созданию моделей сложных систем и уметь самостоятельно выбирать математический аппарат для решения задач моделирования.

5.  Формы контроля:

·  Текущий контроль: согласно графику контрольных мероприятий выполняются контрольные работы и домашнее задание.

Тематика домашних заданий:

×  Модели данных, индексация данных.

Тематика контрольных работ:

×  Проблемы взаимного исключения.

×  Проблема тупика.

·  Итоговый контроль: экзамен проводится в соответствии с учебным планом в конце четвертого модуля. Итоговая оценка: складывается в соответствии с «Положением о рейтинге», принятом в ПФ ГУ ВШЭ. Формы проведения определяются учебным планом.

III.  Содержание программы

Тема 1. Информационные системы и информационные технологии

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

Тема 2. Понятие модели и моделирование информационных систем

Понятие модели. Основные принципы моделирования. Классификация моделей, аналитическое, численное и имитационное моделирование. Особенности моделирования информационных систем. Модели данных, сравнение. Моделирование предметных областей. Понятие о языках моделирования. Понятие о метамоделировании.

Тема 3. Математическая теория систем и математические
основы информационных технологий

Подходы к построению общей теории систем. Задачи математической теории систем. Математические основания теории систем. Основные определения: понятие системы и временной системы, понятие алгебраической системы. Теоретико-множественные понятия общей теории систем. Формализованное понятие информационной системы. Модели программ и их применение для решения задач разработки программного обеспечения.

Теория множеств в моделировании и исследовании сложных систем.

Теория графов и модели данных, алгоритмов и программ. Графовые модели информационных систем, представление структуры, поведения во времени объектов и пользователей. Многоуровневые модели информационных систем.

Математическая логика и неклассические логики и разработка систем искусственного интеллекта.

Модели данных: «дореляционные» модели (иерархическая, сетевая), реляционная модель. Сравнение моделей. Реляционная алгебра, реляционное исчисление и базы данных.

Тема 4. Проблемы создания сложных программных систем и
математические методы решения

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

Тема 5. Методы и средства создания информационных систем

Понятие жизненного цикла (ЖЦ) информационных систем. Этапы ЖЦ. Модели ЖЦ. Методологии анализа и проектирования ИС, структурные методы и объектно-ориентированный подход, основные отличия. Понятие о шаблонах проектирования. Понятие программной инженерии. Инструментальные средства поддержания жизненного цикла ИС, CASE-инструментарий. Понятие адаптируемых информационных систем. Технологии создания адаптируемых ИС, понятие DSD (Domain Specific Design) и DSM (Domain Specific Modeling), языки моделирования и предметно-ориентированные языки (DSL, Domain Specific Languages), метамоделирование и метаязыки, языковые инструментарии.

IV.  Учебно-методическое обеспечение дисциплины

1.  Литература:

Базовые учебники:

1.  Лядова Л. Н., Мызникова Б. И., Фролова Н. В. Основы информатики и информационных технологий. Пермь: Перм. ун‑т, 2004.

2.  Лядова Л.Н. Теория информационных систем. Пермь: Пермский филиал ГУ-ВШЭ, 2009.

3.  Шаврин С. М. Моделирование и проектирование информационных систем: учеб.-метод. пособие / , , ; Перм. гос. ун‑т.– Пермь, 2007.

Основная:

1.  Лядова Л. Н. Стандарты и технологии создания открытых инфор­ма­цион­­ных систем: учеб.-метод. пособие / , , ; Перм. ун-т. – Пермь, 2007.

2.  Замятина Е. Б. Системы имитационного моделирования и машинная имитация: теоретические основы и реализация: метод. пособие/ , В. В. Ланин, , ; Перм. гос. ун-т.– Пермь, 2007.

3.  Замятина Е. Б. Современные теории и системы имитационного моделирования: учеб.-метод. пособие / , , ; Перм. ун-т.– Пермь, 2007.

4.  Юрков К. А. Технологии создания систем электронной коммерции: учеб.-метод. пособие / , , ; Перм. ун‑т. – Пермь, 2007.

Дополнительная:

1.  Е. Теория информационных систем: Курс лекций [Электронный ресурс]. Екатеринбург: УГТУ, 1999.

2.  , «Эквивалентность ресурсов в сетях Петри». Москва, Научный мир, 2008.

3.  Джекобсон А. Язык UML. Руководство пользователя: Пер. с англ. – М.: ДМК Пресс; СПб.: Питер, 2004. – 432 с.: ил. – (Серия «Объектно-ориентированные технологии в программировании»).

4.  М. Проектирование программного обеспечения экономических информационных систем. М.: Финансы и статистика, 2000.

5.  , В. Пример описания предметной области с использованием Unified Modeling Language (UML) при разработке программных систем // Interface Ltd., 2001.

6.  Н. CASE структурный системный анализ (автоматизация и применение). М.: Изд-во «Лори», 1996.

7.  Н. Методы и средства системного структурного анализа и проектирования. М.: НИВЦ МГУ, 1996.

8.  Кумсков М. Унифицированный язык моделирования (UML) и его поддержка в Rational Rose 98i – CASE-средстве визуального моделирования // //www. *****/public/990804/uml4b. htm.

9.  Ларман К. Применение UML и шаблонов проектирования: Пер. с англ.: Уч. пос. – М.: Издательский дом «Вильямс», 2001. – 496 с.: ил.

10.  В. BPwin и ERwin. CASE-средства разработки информационных систем. М.: ДИАЛОГ-МИФИ, 2000.

11.  Материалы сайтов www. *****, www. *****, www. *****, www. *****, www. *****.

12.  UML – новый стандарт языка объектно-ориентированного моделирования. Квинтэссенция успешного опыта // SoftScribe International, http://www. *****/inform22_97/sscrb. htm.

13.  UML. Мета-язык проектирования и моделирования программного обеспечения // http://it. *****/reviews/UML.

2.  Тематика заданий по различным формам текущего контроля:

Тематика домашних заданий:

1.  Математическая теория информационных систем и информационных технологий:

-  модели данных, индексация данных.

Тематика контрольных работ:

1.  Управление ресурсами и процессами: проблема взаимного исключения.

2.  Управление ресурсами и процессами: проблема тупика.

Перечень вопросов для самоконтроля студентов:

  1.  Дайте определение информационной технологии, приведите примеры.

  2.  Дайте определение информационной системы и приведите классификацию ИС. Каковы основные характеристики систем различных классов? Какие технологии используются для их создания.

  3.  Опишите основные компоненты, типовую архитектуру корпоративной информационной системы.

  4.  Дайте определение модели. Приведите общую классификацию математических моделей.

  5.  В чем суть математического моделирования? Сравните различные методы. Приведите примеры применения различных методов и подходов к моделированию.

  6.  Дайте определение языка моделирования. Что такое метаязык? Каковы основные особенности метамоделирования и его применение к созданию ИС.

  7.  Дайте формальное определение системы. Приведите классификацию систем.

  8.  Дайте определение модели данных. Сравните различные модели. Каковы преимущества и недостатки каждой модели? Приведите примеры.

  9.  Назовите графовые модели систем, известные вам. Каково их применение?

  10.  Дайте определение сети Петри. Приведите пример использования для исследования систем.

  11.  Определите понятие ресурса и процесса. Дайте классификацию. Какие отношения могут возникать между процессами?

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

  13.  Какие методы решения проблемы взаимного исключения вы знаете? Сравните их.

  14.  Дайте определение тупика. Сформулируйте задачи, связанные с проблемой тупика. Сравните подходы к решению. Какие возможности обеспечивают для разработки параллельных программ известные вам системы программирования?

  15.  Какие проблемы решаются при создании распределенных систем?

  16.  Дайте понятие жизненного цикла программной системы. Какие модели жизненного цикла вы знаете?

  17.  Определите, что такое CASE-инструментарий? BI-инструментарий? Языковой инструментарий? Какова связь с метамоделированием?

Тематика практических занятий:

Примерный перечень заданий, выполняемых на практических занятиях приведен в приложении.

3.  Методические рекомендации (материалы) преподавателю:

На лекциях используется «проблемный» подход к изложению материала: материал каждой лекции иллюстрируется примерами, рассматриваются нестандартные ситуации, требующие решения с использованием рассматриваемого материала. При этом студенты должны активно участвовать в обсуждении вопросов, выработке решений. Для самостоятельного изучения предлагается использовать электронные ресурсы, в частности, курсы по информационным технологиям INTUIT.

На лабораторных занятиях используются следующие методы обучения и контроля усвоения материала:

1)  выполнение лабораторных работ по теме занятия сопровождается контрольным опросом;

2)  обсуждение различных вариантов решения, предложенных студентами, сравнение решений, анализ возможных ситуаций.

4.  Методические указания студентам:

Студенту рекомендуется следующая схема подготовки к лабораторному занятию:

1)  проработать конспект лекций;

2)  проанализировать основную и дополнительную литературу, рекомендованную по изучаемому разделу;

3)  проанализировать варианты решений, предложенные преподавателем;

4)  при затруднениях сформулировать вопросы к преподавателю.

5.  Рекомендации по использованию информационных технологий

Практические занятия проводятся в форме семинаров. Для самостоятельной работы время выделяется в компьютерном классе. Программное обеспечение сети должно поддерживать

1)  возможность доступа к материалам для подготовки, размещаемым на сервере;

2)  возможность использовать визуальные средства создания моделей;

3)  возможность оформления отчетов по выполненным заданиям с помощью текстовых редакторов и электронных таблиц.

Автор программы: __________________________________________ / /

Тематический расчет часов

№	Наименование разделов и тем (с разбивкой по модулям)	Аудиторные часы	Самостоятельная работа	Всего часов
Лекции	Семинарские или практические занятия	Всего
	Модуль 4	20	20	40	60	100
1	Информационные системы и информационные технологии	2	0	2	10	12
2	Понятие модели и моделирование информационных систем	10	12	22	32	54
3	Математическая теория систем	8	8	16	18	34
	Всего за модуль:	20	20	40	60	100
	Модуль 5	24	24	48	68	116
4	Математические основы информационных технологий	8	12	20	30	50
5	Проблемы создания сложных программных систем и математические методы решения	8	12	20	30	50
6	Методы и средства создания информационных систем	8	0	8	8	16
	Всего за модуль:	24	24	48	68	116
	Всего за год:	44	44	88	128	216

Автор программы: __________________________________________ / /

Приложение 1.

План практических занятий

Тема 1. Понятие модели и моделирование информационных систем (12 часов)

Аналитические модели. Численное моделирование. Имитационные модели. Сравнение методов на примере построения и исследования простейшей модели системы массового обслуживания с одним прибором и очередью.

Рекомендуемая литература:

Лядова Л. Н. Имитационное моделирование: Методические указания. Пермь: Пермский университет, 2003. [Электронный ресурс]

Шаврин С. М. Моделирование и проектирование информационных систем: учеб.-метод. пособие / , , ; Перм. гос. ун‑т.– Пермь, 2007.

Тема 2. Математическая теория систем (8 часов)

Разработка и исследование простейших моделей систем. Сравнение.

Рекомендуемая литература:

Е. Теория информационных систем: Курс лекций [Электронный ресурс]. Екатеринбург: УГТУ, 1999.

Тема 3. Математические основы информационных технологий (12 часов)

Модели данных: иерархическая, сетевая, реляционная модель. Примеры. Сравнение.

Операции над моделями. Особенности выполнения.

Неклассические логики, нечеткие множества: примеры использования.

Рекомендуемая литература:

Лядова Л. Н. Основы информатики и информационных технологий: Учебное пособие / , , . Пермь: Пермский университет, 2004.

Тема 4. Проблемы создания сложных программных систем и математические методы решения (12 часов)

Системы с параллельными процессами и проблема взаимного исключения. Программные методы. Алгоритм Деккера. Анализ недостатков. Семафорная техника решения проблемы взаимного исключения.

Примеры моделей с различными типами ресурсов. Исследование моделей. Распознавание и предотвращение тупиков, вывод системы из тупика.

Рекомендуемая литература:

Лядова Л. Н. Теоретические основы информационных систем: Методические указания [Электронный ресурс].

Приложение 2.

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

1. Проблема взаимного исключения: анализ состояний системы для выявления тупиков

1.  Пусть в системе есть два процесса P1 и P2 и два единичных повторно используемых ресурса R1 и R2. Процессы имеют следующее описание:

Процесс 1	Процесс 2
process P1 ; begin ... While true do begin … request ( R1, 1) ; ... request ( R2, 1) ; ... release ( R2, 1) ; ... release ( R1, 1) ; ... end ... end.	process P2 ; begin ... While true do begin … request ( R2, 1) ; ... request ( R1, 1) ; ... release ( R2, 1) ; ... release ( R1, 1) ; ... end ... end.

Построить граф состояний системы. Возможны ли в системе тупиковые состояния?

1.  Пусть в системе есть два процесса P1 и P2 и два потребляемых ресурса R1 и R2, используемых этими процессами. Ресурс R1 производится процессом P1, а R2 – P2. Процессы имеют следующее описание:

Процесс 1	Процесс 2
process P1 ; begin ... While true do begin … request ( R2, 1) ; ... release ( R1, 1) ; ... end ... end.	process P2 ; begin ... While true do begin … request ( R1, 1) ; ... release ( R2, 1) ; ... end ... end.

Построить граф состояний системы. Возможны ли в системе тупиковые состояния?

2. Проблема взаимного исключения: программные методы решения

1.  Задача: решить программным способом задачу взаимного исключения. Являются ли приведенные ниже процедуры решением поставленной задачи? Если нет, объясните, когда могут возникнуть ошибки?

Решение:

process INIT; common boolean C1. C2;

begin С1:=false; С2:=false; start(P1); start(P2); end;

process P1;

Begin

while true do

begin BEFORE1; C1:=true; while C2 do ; CS1; C1:=false; AFTER1; end

end;

process P2;

Begin

while true do

begin BEFORE2; while C1 do ; C2:=true; CS1; C2:=false; AFTER2; end

end;

2.  Решить задачу взаимного исключения, используя логические переменные и процедуру перевода процесса в состояние задержки (приостановки) Delay(T), где параметр T задает время задержки процесса (время, на которое он выводится из конкуренции за время процессора).

3.  Алгоритм Деккера можно сформулировать следующим образом:

Процедура инициализации	Первый процесс	Второй процесс
procedure INIT; common boolean C1,C2 ; common integer N ; begin C1 := false ; C2 := false ; N := 1 ; start(P1) ; start(P2) end INIT .	process P1; common boolean C1,C2 ; begin while true do begin BEFORE1 ; C1 := true ; while C2 do begin if N<>1 then begin C1 := false ; while N<>1 do ; C1 := true ; end end ; CS1 ; C1 := false; N := 2; AFTER1 ; end end P1 .	process P2; common boolean C1,C2 ; begin while true do begin BEFORE2 ; C2 := true ; while C1 do begin if N<>2 then begin C2 := false ; while N<>2 do ; C2 := true ; end end ; CS2 ; C2 := false; N:=1; AFTER2 ; end end P2 .

Написать алгоритм Деккера для N процессов.

4.  Решается ли в приведенных ниже программах проблема взаимного исключения (random – процедура, генерирующая случайное число, delay(T) – процедура задержки процесса на время T, в течение которого процесс не будет конкурировать за время процессора)?

process INIT; common boolean C1. C2; common integer N; common real T1, T2;

begin С1:=false; С2:=false; T1:= random; T1:= random; N:=1; start(P1); start(P2); end;

process P1;

Begin

while true do

begin BEFORE1;

C1:=true;

while C2 and (N<>1) do delay(T1);

CS1;

C1:=false; N:=2;

AFTER1;

end

end;

process P2;

Begin

while true do

begin BEFORE2;

C2:=true;

while C1 and (N<>2) do delay(T2);

CS2;

C2:=false; N:=1;

AFTER2;

end

end;

3. Проблема взаимного исключения: использование семафоров

1.  Задача: написать процедуры, моделирующие семафорные примитивы для общего семафора (допускаются только неотрицательные значения целочисленной переменной, моделирующей считающий семафор). При написании процедур можно использовать бинарные семафоры. Ниже приведен код процедур PP и VP, которые моделируют работу семафорных примитивов для общего семафора в соответствии с поставленной задачей. Решена ли задача? Найти в приведенном ниже псевдокоде ошибки, объяснить и исправить их, если они есть.

a.  Решение:

Init: proc (var S: integer; value: integer);

common binary semaphore B1, B2;

begin B1:=1; B2:=1; S:=value end;

PP: procedure (var S: integer); common binary semaphore B1, B2;

Begin P(B2); P(B1); S:=S–1; if S>0 then V(B2); V(B1) end;

VP: procedure (var S: integer); common binary semaphore B1, B2;

Begin P(B1); S:=S+1; V(B1); V(V2 ) end;

b.  Решение:

Init: proc (var S: integer; value: integer);

common binary semaphore B1, B2;

begin B1:=1; B2:=1; S:=value end;

PP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B2); P(B1); S:=S–1; V(B1) end;

VP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B1); S:=S+1; V(B1); V(V2 ) end;

c.  Решение:

Init: proc (var S: integer; value: integer);

common binary semaphore B1, B2;

begin B1:=1; B2:=1; S:=value end;

PP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B2); while S<=0 do; P(B1); S:=S–1; V(B1); V(B2) end;

VP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B1); S:=S+1; V(B1); V(V2 ) end;

d.  Решение:

Init: proc (var S: integer; value: integer);

common binary semaphore B;

begin B:=1; S:=value end;

PP: procedure (var S: integer);

common binary semaphore B;

Begin P(B); if S>0 then S:=S–1; V(B) end;

VP: procedure (var S: integer);

common binary semaphore B;

Begin P(B); S:=S+1; V(B) end;

2.  Задача: написать процедуры, моделирующие семафорные примитивы для общего семафора (допускаются любые значения целочисленной переменной, моделирующей считающий семафор). При написании процедур можно использовать бинарные семафоры. Ниже приведен код процедур PP и VP, которые моделируют работу семафорных примитивов для общего семафора в соответствии с поставленной задачей. Решена ли задача? Найти в приведенном ниже псевдокоде ошибки, объяснить и исправить их, если они есть.

a.  Решение:

Init: proc (var S: integer; value: integer); begin S:=value end;

PP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B1); S:=S–1; if S<0 then begin V(B1); P(B2) end

Else V(B1) end;

VP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B1); S:=S+1; if S<=0 then V(B2); V(V1 ) end;

b.  Решение:

Init: proc (var S: integer; value: integer);

common binary semaphore B1, B2;

begin B1:=1; B2:=0; S:=value end;

PP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B1); S:=S–1; P(B2) end;

VP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B2); S:=S+1; V(V1 ) end;

c.  Решение:

Init: proc (var S: integer; value: integer); common binary semaphore B;

begin B:=1; S:=value end;

PP: procedure (var S: integer);

common binary semaphore B;

Begin if S>0 then begin P(B); S:=S–1; V(B) end end;

VP: procedure (var S: integer);

common binary semaphore B;

Begin P(B); S:=S+1; V(B) end;

d.  Решение:

Init: proc (var S: integer; value: integer); begin S:=value end;

PP: procedure (var S: …); common binary semaphore B1, B2;

Begin P(B1); S:=S–1; if S<0 then P(B2) Else V(B1) end;

VP: procedure (var S: …); common binary semaphore B1, B2;

Begin P(B1); S:=S+1; if S<=0 then V(B2); V(V1 ) end;

e.  Решение:

Init: proc (var S: integer; value: integer);

common binary semaphore B1, B2;

begin B1:=1; B2:=1; S:=value end;

PP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B1); S:=S–1; if S<0 then P(B2) Else V(B1) end;

VP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B1); S:=S+1; if S>0 then V(B2); V(V1 ) end;

3.  Задача “обедающие философы” формулируется следующим образом: “Пять философов садятся обедать за круглый стол, в центре которого стоит одно блюдо со спагетти. На столе имеется пять тарелок и пять вилок между ними. Философ может начать есть, если у него есть тарелка и две вилки, которые он может взять с двух сторон от своей тарелки. Философ может отдать вилки соседям только после того, как он закончит обед”. О соображениях гигиены мы здесь умалчиваем. Может ли описанный ниже на псевдокоде процесс представить алгоритм поведения философа за столом?

a.  Решение:

Инициализация:

{ “Вилки”, которые используются философами – это разделяемые ресурсы,
защищенные бинарными семафорами: }

common B: array[0..4] of binary semaphore; { глобальный массив семафоров}

for I:=0 to 4 do B[I]:=1; { все “вилки” свободны }

process Философ(I: Integer);

{ Это процесс, описывающий поведение I-го философа. }

{ “Вилки”, которыми он ест, защищаются двумя бинарными семафорами. }

common B: array[0..4] of binary semaphore

begin { Пытается получить вилки: }

while (P(B[I])=0) or (P(B[(I+1) mod 5])=0) do ;

{ Ест спагетти, используя вилки, находящиеся слева и справа } …

{ Освобождает вилки: } V(B[(I+1) mod 5]); V(B[I]);

end;

b.  Решение:

Инициализация:

{ “Вилки”, которые используются философами – это разделяемые ресурсы,
защищенные бинарными семафорами: }

common B: array[0..4] of binary semaphore; { глобальный массив семафоров}

for I:=0 to 4 do B[I]:=1; { все “вилки” свободны }

process Философ(I: Integer);

{ Это процесс, описывающий поведение I-го философа. }

{ “Вилки”, которыми он ест, защищаются двумя бинарными семафорами. }

common B: array[0..4] of binary semaphore

begin

{ Пытается получить вилки: }

P(B[I]); P(B[(I+1) mod 5]);

{ Ест спагетти, используя вилки, находящиеся слева и справа } …

{ Освобождает вилки: }

V(B[(I+1) mod 5]); V(B[I]);

end;

3. Модели данных

Выполните анализ и постройте

1) инфологическую модель предметной области (ER-диаграммы, диаграммы потоков работ и пр.);

2) модель с использованием инвертированных списков, иерархическую модель, сетевую модель, реляционную модель (выполните «интуитивную» нормализацию).

Предметную область выберите самостоятельно и согласуйте с преподавателем (рассмотреть простейшую предметную область со сложностью порядка 4‑5 объектов).

Сравните преимущества и недостатки построенных моделей с точки зрения трудоемкости построения и возможностей контроля целостности данных при выполнении операций.