Изучение математических дисциплин в компьютерной среде, страница 14

Ключевые слова выбираются из меню. Ответ считается верным, если введена верная последовательность ключевых слов и символов. Использование этого под-хода, в частности позволило сформулировать вопросы с ответами типа«да», «нет», конструировать числовые ответы. В зависимости от результата выполнения заданий обучаемый получает рекомендации поизучению теоретического материала и повторно обращается к разделам справочника. Обучаемый может получить необходимую помощь вдостижении требуемого уровня понимания путем обращения к теоретико-справочному модулю, осмыслению Не1р'ов и комментариев.

Поокончании выполнения заданий обучаемый получает рекомендации поповторному изучению разделов теоретического материала. Пример 1.Дайте определение отношений эквивалентности и частичного порядка.Отношение эквивалентности — это ............................ бинарное отношение.Отношение частичного порядка тг- это................бинарное отношение.Ключевые слова: симметричное, антисимметричное, транзитивное, рефлексивное.Пример 2.Укажите тип отношения1. Отношение равенства на множестве целых чисел является отношением ...................................2. Отношение « < » на множестве целых чисел является .

. . .3. Отношение «меньше или равно» на множеств целых чисел является отношением ....................................4. Отношение принадлежности к одной школе на множествешкольников есть отношение . .............5. Отношение «состоять в родстве» на множестве людей являетсяотношением ....................................6. Отношение «старшинства или равенства по званию» на множестве военных обладает свойствами .

..................................7. Отношение { <х,у>, <x,z>, <x,x>, <y,y>,'<z,z> } намножестве {х, у, z } является отношением....................................Ключевые слова: эквивалентности, частичного порядка, линейного порядка, рефлексивным, симметричным, антисимметричным, транзитивным. (Допускаются различные варианты ответов на один и тотже вопрос. В частности, так как отношение линейного порядка является отношением частичного порядка, то в третьем пункте вернымиявляются два ответа).84857.2.

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

Если обучаемый допускаетошибку, ему предоставляется возможность повторно изучить соответствующий раздел теоретического материала, затем повторить выполнение задания.Приведем примеры упражнений, предлагаемых к решению на этапе «Выработка умений».Пример 1. Перечислите элементы отношения, заданного диаграммой Хассе.Найдите минимальные элементы. Найдите максимальные элементы.Пример 2. Напишите МТ, которая, начав работу с пустой лентой,выводит на ленту надпись «Машина Тьюринга».Пример 3. Найдите пути минимальной длины из вершины х j вовсе достижимые в нагруженном графе, заданном матрицей С длин дуг.ооооПри выполнении, например, упражнения 1 студент должен ввестис клавиатуры элементы соответствующего бинарного отношения, например R-{<a , a > , < b , b > , < c , c > , <d,d>, < e , e > , </,/>,<a,d>, <a,f>, < b , d > , < b , e > , <b,f>, < c , e > , <c,/>}, его ми86нимальные элементы а , b, си максимальный элемент/.

Если обучаемый сделал ошибку, то на экране появляется сообщение «Ответ неверен», и ему предоставляются следующие возможности: просмотретьтеорию по этой теме, повторно выполнить упражнение, выполнитьаналогичное упражнение.В процессе выполнения более сложных заданий (например, 2 и 3)при ошибочных промежуточных результатах на экране будут появляться сообщения, комментирующие эти ошибки.Осуществление контроля владения информацией и уровня понимания заложено в системной оболочке «Ракель».Модель контроля уровня умения аналогична модели выработкиумения и лишь не включает возможности обращения к теории и повторного выполнения заданий.Контроль уровня умения в КК поддерживается зачетным модулем.Зачетный модуль предназначен для окончательного контроля знанийстудентов по практической части курса. Система предлагает обучаемому решать задачи, аналогичные тем,которые решались в процессеобучения.

Все варианты заданий формируются случайным образом, поэтому каждый экзаменуемый имеет индивидуальное задание. В ходевыполнения задания обучаемый имеет одну попытку ответа на вопроси лишен возможности пользоваться теоретическим материалом. Ответы на вопросы заносятся в протокол с комментариями.7.3. Задания для самостоятельного решения иприкладные задачиДля самостоятельного решения предлагаются задачи по теме «Машина Тьюринга» и прикладные задачи из раздела «Теория графов».1. Напишите МТ, которая, начав работу с пустой лентой, выводитна ленту надпись «машинное слово».2.

Напишите МТ, которая переводит все «маленькие» буквы слова,записанного на ленте, в «большие» (т.е. переписывает слово «большими» буквами).Приняты следующие правила кодирования чисел в алфавите{0,| } : число 0 кодируется одним символом «|»; число N кодируетсяN+1 символом «|».3. Напишите МТ, переводящую ленту из конфигурации ... 0^0....в конфигурацию ... 0X0f(X) 0. . . (X и f(X) -^коды в алфавите{0, | }, т.е. вычисляющуюf(X), ще/(Х)=Х+2.4.

Напишите МТ, переводящую ленту из конфигурации. . . Y 0 X 0 . . . в конфигурацию ... Y0X0f(X, У)0...(X, Y иf(X,Y)— коды в алфавите { 0 , | } , т.е. вычисляющую f(X,Y),где/(Х, Y) =.Х div Y— целочисленное деление XnaY.875. Пусть граф G = <X,T> представляет структуру руководства,или «влияний» в некоторой организации. Требуется выделить множетство людей, которые имеют равную власть или равное влияние другна друга (например, составляют комитет).Указание. Пусть множество X вершин графа — это множествосотрудников данной организации, и две вершины х и >> соединены дугой <jc,;y> тогда и только тогда, когда х имеет влияние на у, то множество сотрудников, имеющих равное влияние — это элементы однойкомпоненты сильной связности.6.

Различные организации х i,.. . , х п обмениваются некоторой информацией (при этом каналы связи могут быть направленными). Еслимежду организациями х,- и Xj возможен непосредственный обмен информацией, то затраты на него составят г,у рублей. Возможен ли обмен информацией между двумя организациями? Если возможен, то какосуществить этот обмен с минимальными затратами?У к а з а н и е . Рассмотрим граф, вершинам которого соответствуют организации JCJ , . . . ,х п , а дугам — пары организаций<X},X'j>, между которыми возможен непосредственный обмен информацией, вес дуги <Xi,Xj> равен г,у . Для решения поставленнойзадачи применяется алгоритм нахождения пути минимального веса вориентированном графе.7. Требуется сформировать наибольшую возможную комиссию изгруппы лиц, некоторые из которых попарно несовместимы.Указание.

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

Пусть сеть связи описывается графом, вершины которого — узлы сети, ребра — каналы связи. Если выйдут из строя некоторые каналы, то между узлами связь может быть нарушена. Какие каналыможно удалять без нарушения связи? Оставшийся «осле удаления всехтаких ребер граф является остовным деревом. Если при этом каждомуканалу (ребру) приписан некоторый вес, то какие ребра удалить, чтобы остовное дерево имело минимальный суммарный вес?К задаче нахождения минимального остовного дерева сводитсярешение следующих вопросов: при прокладке дорог (газопроводов,линий электропередач и т.д.) необходимо связать п точек некоторойсетью, чтобы общая длина «линий связи» была минимальной. Точкиможно считать вершинами полного графа (т.е.

такого /г-вершинногографа, между любой парой вершин которого есть ребро), весом ребра —расстояние между точками. Так как разветвление дорог допускается взаданных точках — вершинах, то минимальное остовное дерево и будет сетью дорог, имеющей минимальную общую длину.10. Рассмотрим задачу, связанную с морским грузооборотом.Пусть некоторые порты a j,..., а % располагают продуктом, имеющимспрос в портах Ь \,..., Ъ т , и пусть наличный запас продукта в портуа,- равен 5,->0, а потребность в этом продукте в порту bj равнаdj>0.

Обозначим через с ij полное количество продукта, которое способны перевезти суда, плывущие из а,- в bj . Возможно ли удовлетворить все потребности? Как организовать перевозки?У к а з а н и е . Для решения этих задач целесообразно построитьтранспортную сеть. Каждый из портов а,- соединим с портом bj дугойс пропускной способностью с ij (они соответствуют промежуточнымвершинам сети). Затем рассмотрим две дополнительные вершины —источник х i и сток х п . Соединим х j с каждой вершиной a ; дугой спропускной способностью 5 j , а каждую вершину bj — с хп дугой спропускной способностью dj.