ОЧЕНЬ СРОЧНО. Подскажите пожалуйста
ОЧЕНЬ СРОЧНО. Выбери верный ответ.
_______________ расписания является моделью движения электричек.
Ответ:
1. таблица
2. карта
3. схема
4. графы
Лучший ответ
Расписание движения поездов может рассматриваться как пример модели следующего вида:
а) натурной;
б) табличной;
в) графической;
г) компьютерной;
д) математической.
https://иванов-ам.рф/informatika_11_34_sim/informatika_materialy_zanytii_11_34_63.html
Остальные ответы
Похожие вопросы
Ваш браузер устарел
Мы постоянно добавляем новый функционал в основной интерфейс проекта. К сожалению, старые браузеры не в состоянии качественно работать с современными программными продуктами. Для корректной работы используйте последние версии браузеров Chrome, Mozilla Firefox, Opera, Microsoft Edge или установите браузер Atom.
Приближенный алгоритм составления расписаний движения автобусов Текст научной статьи по специальности «Математика»
Предлагается приближенный метод решения класса задач, связанных с оптимизацией транспортного процесса, который позволяет эффективно строить расписания с учетом ограничений, характеризующих реальные условия.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по математике , автор научной работы — Скрипина Ирина Валентиновна
Метод поиска оптимальных решений для одного обобщения задачи о назначениях
Нейросетевая адаптивная фильтрация полигармонических стохастических сигналов
Модели и методы решения задач маршрутизации в зоне техногенной аварии
Постановка многокритериальной задачи маршрутизации и планирования графиков полета пилотируемой и беспилотной авиации в динамической обстановке и подход к ее решению с помощью генетических алгоритмов
Эффективное построение множества расписаний с минимальным суммарным временем завершения работ
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Aproximate algorithm of sheduling the timetable of moving the buses
The algorithm of building a timetable of bus motion with provision for real restrictions, under which are executed passenger transportation is offered All optimum decisions are found in a polynomial time
Текст научной работы на тему «Приближенный алгоритм составления расписаний движения автобусов»
В том случае, когда контур настройки множителя Лагранжа устойчиво поддерживает ограничение ст (к) E = 1, первое соотношение (41) автоматически приобретает форму широко распространенного в теории искусственных нейронных сетей алгоритма обучения Уидроу-Хоффа [8]:
являющегося в свою очередь одной из разновидностей дельта-правила настройки нейронов.
Предлагаемый подход позволяет выделить из анализируемого сигнала произвольное количество гармонических компонент, обладая при этом высоким быстродействием, обеспечиваемым как параллельной организацией вычислений, так и оптимальными свойствами алгоритмов обучения.
Литература: 1 .Рабинер П, Гоулд Б. Теория и применение цифровой обработки сигналов. М.:Мир, 1978. 848 с. 2. Мизин И.А., Матвеев А.А. Цифровые фильтры. М.: Связь, 1979. 240с. 3. КаппелиниВ., Константинидис А.Дж., Эмилиани П. Цифровые фильтры и их применение. М.: Энергоатомиздат, 1983. 360с. 4. Signal Processing Handbook / Ed.by C.H.Chen.-N.Y. and Basel:Marcel Dekker, Inc., 1988. 818p. 5. Адаптивные фильтры/Под ред.К.Ф.Н. Коуэна, П.М. Гранта. М.:Мир, 1988. 392с. 6. Уидроу Б., Стирнс С. Адаптивная обработка сигналов. М.:Радио и связь, 1989. 440с. 7. Balmer L. Signals and Systems. An Introduction.-Prentice Hall Europe, 1997. 550p. 8. Cichocki A., Unbehauen R. Neural Networks for Optimization and Signal Processing.Stuttgart:Teubner,1993. 526p. 9. Kwan T, Martin K. Adaptive detection and enhancement of multiple sinusoids using a cascade IIR filter / / IEEE Trans. Circuits and Systems-1989. 36. N7. P.937-947. 10. Doraiswami R., Jiang J. A linear time-varying filter for estimating a signal from unknown noise and its applications to identification / / Int.J.Contr. 1985. 42. N1. P.97-117. 11. Galvan J.B. An unsupervised recurrent neural network for noise identification // J. Syst.Eng. 1996. 6. P.177-185. 12. Бодянс-
кий Е.В. Адаптивные алгоритмы идентификации нелинейных объектов управления//АСУ и приборы автоматики. 1987. Вып.81. C.43-46. 13. БодянскийЕ.В., Воробьев С.А. Алгоритмы обучения искусственных нейронных сетей в задаче идентификации нелинейного стохастического нестационарного объекта// Праці П’ятої Української Конференції з автоматичного управління “Автоматика-98”: К., 13-16 травня 1998р. 4.III. Київ: НТУУ “КПІ”, 1998. С.350-354. 14. Goodwin G.C,Ramadge P.J., Caines P.E. A globally convergent adaptive predictor/ / Automatica.-1981. 17. N1. P.135-140. 15. Бодянский Е.В., Руднева ИА. Об одном адаптивном алгоритме обнаружения разладок в случайных последовательностях// Автоматика и телемеханика 1995. N10. C.101-106.
Поступила в редколлегию 20.10.2000
Рецензент: д-р техн. наук, проф. Любчик Л.М.
Бодянский Евгений Владимирович, д-р техн. наук, профессор кафедры искусственного интеллекта, научный руководитель проблемной НИЛ АСУ ХТУРЭ, член IEEE, WSES. Научные интересы: нейро-фаззи-системы. Адрес: Украина, 61166, Харьков, пр. Ленина, 14, тел. 40-98-90.
E-mail: Bodyanskiy@ieee.org, bodya@kture.kharkov.ua
Котляревский Сергей Владимирович, канд. техн. наук, старший научный сотрудник проблемной НИЛ АСУ ХТУРЭ. Научные интересы: нейро-фаззи-системы. Адрес: Украина, 61166, Харьков, пр. Ленина, 14, тел. 40-98-90.
Чапланов Алексей Павлович, инженер кафедры искусственного интеллекта ХТУРЭ. Научные интересы: искусственные нейронные сети. Адрес: Украина, 61166, Харьков, пр. Ленина, 14, тел. 40-98-90.
Шило Александр Владимирович, канд. биол. наук, старший научный сотрудник отдела криофизиологии Института проблем криобиологии и криомедицины НАН Украины. Научные интересы: нейрофизиология головного мозга, хаос в физиологии, фракталы. Адрес: Украина, 61015, Харьков, ул. Переяславская, 23, тел. (0572)-702-935. E-mail: sasha@ashilo.kharkov.ua
ПРИБЛИЖЕННЫЙ АЛГОРИТМ СОСТАВЛЕНИЯ РАСПИСАНИЙ ДВИЖЕНИЯ АВТОБУСОВ
Предлагается приближенный метод решения класса задач, связанных с оптимизацией транспортного процесса, который позволяет эффективно строить расписания с учетом ограничений, характеризующих реальные условия.
Предметом изучения является модель эффективной организации пассажирских перевозок, построение которой основано на решении известной задачи о назначении. Эта задача располагает широким спектром практических приложений на транспорте.
Доказано, что задача о назначении эффективно разрешима. При этом предполагается, что для достижения оптимума ее целевой функции достаточно найти единственное ее решение. Однако в практических ситуациях возникает потребность в
нахождении множества оптимальных решений с заданными свойствами, при различных условиях.
Результаты изучения этих свойств составляют содержание данной статьи. Условия, при которых необхо -димо минимизировать суммарное время выполнения автобусами маятниковых маршрутов между двумя пунктами 1 и 2, содержат дополнительное требование. Оно заключается в том, что перевозки между этими пунктами должны обеспечивать m автобусов, из них m1 автобусов автопредприятия, расположенного в пункте 1, и m- mi автобусов автопредприятия, расположенного в пункте 2. Из расписания движения по автостанциям известно время отправления для каждого рейса из пункта 1 в пункт 2 и обратно — из пункта 2 в пункт 1. Любой автобус автопредприятия, расположенного в пункте к, к = 1,2 , начинает и завершает маршрут согласно расписанию в этом пункте.
Рейс i из пункта 1 в пункт 2 начинается в момент времени ti j, i = 1, m и его продолжительность равна тц . Рейс j из пункта 2 в пункт 1, начинающийся в момент времени 12j j = 1, m , выполняется за время
^2j. Для автобуса, отправляющегося рейсом i из пункта 1 в пункт 2 и возвращающегося рейсом j из пункта 2 в пункт 1, время в наряде определяется как Yij = t2j “ tii +T2j , t2j — tii
Аналогично, продолжительность маятникового маршрута автобуса, выполняющего вначале рейс i, а затем j, равна Рji = tii -t2j +Т1Ь tii — t2j ^T2j.
Пусть Y = [yij]m и Z = [zjj]m обозначают (0, 1)-квадратные матрицы порядка m, удовлетворяющие следующим условиям:
Уі = Z yij = i V о , yj = £ Yij = i v 0 ,
Z Z у ij = mi , 0 < m. < m ; i=ij=i i
zi = Z zij = i v 0 , z. = £ zij = i v 0 , j=i J i—i
ZZzij = m — mi; y+z=x, i=ij=i
X = [Xij] — матрица перестановки.
Рассмотрим квадратные матрицы [ Т ij ] m и [ Pij ] m порядка m , связанные с матрицами Y, Z и X функционалом
т(ль л 2) = ZZyij у ij +ZZzijP ij, (і)
где у ij, Pij — неотрицательные целые числа; л. — подмножество из mi индексов строк матрицы Y, а л 2 — соответственно непустое множество из m-mi индексов строк матрицы Z. Матрице перестановки X соответствует последовательность л = (л. , Л2) , представленная разбиением на подмножества л. и %2: л=л. ил2, л. П1Л2, л., Л2 ^0, | л. |= m., | Л21= m-щ.
Поставим задачу нахождения такой перестановки л*, что её разбиение
доставляет функционалу (1) значение
Т(л* ,л2) = min Т(лі,л2).
Анализ задачи начинается с составления матриц [Yij]m и [Pij]m. Каждый элемент у^ первой таблицы равен времени выполнения маятникового маршрута, включающего рейс i из пункта 1 в пункт 2, а затем рейс j из пункта 2 в пункт 1.
Матрица [Pij]m содержит длительности всех маршрутов, которые начинаются выполнением рейса j, j = 1, m, из пункта 2 в пункт 1, и заканчиваются рейсом і, і = і, m, из пункта 1 в пункт 2. Иначе говоря, матрица [у ij]m составлена в предположении m. = m, а матрица [Pij]m содержит информацию о продолжительности маршрутов при условии, что m. = 0.
Наложением матриц [ У ij ] m и [ Pij ] m образуем таблицу [(уij,Рij)]m из m2 упорядоченных пар (Y ij, Pij), i,j = 1,m . Любая матрица перестановки X элементов л = (л[1],л[2]. л[к]. л[l]. л[m]) индексов строк полученной конфигурации, а также разбиение л на подмножества л. и л2, | л. |= m.,
Т(ль л2) = Т(лі) + Т(л2), (2)
Т(лі) = Zy*[k] Т(л 2) = zp^i]
Таким образом, допустимое решение задачи отыскания минимума (1) включает в себя перестановку л индексов из m строк таблицы [(yij,Pij)]m и разбиение (л., л2) перестановки л на подмножества л. и %2 с наперёд заданным числом элементов m., 0 < m. < m в подмножестве л.. Обозначим л = (л., л2) допустимое решение (1).
Рассматриваемая задача содержит все признаки задачи о назначениях. В отсутствие ограничений на количество элементов в подмножестве л. её оптимальное решение л* является решением задачи о назначениях с исходными данными в виде матрицы [a ij]m, где а ij = mrn .
Задача минимизации (1) имеет наглядное представление в терминах теории графов.
Таблице [(yij,Pij)]m поставим в соответствие полный двудольный ориентированный граф G=(VuW,E), IV = |W| = m, |E = 2m2 , где каждая пара вершин , Vi є V, Wj є W образует две дуги (vi,w jMwj,vi)є E c весами Y(vi,Wj) = y ij и P(Wj,Vi) = Pij . Тогда последовательность л = (л[1]л[2]. л[m]) элементов таблицы [(Yij,Pij)]m можно представить как совершенное паросочетание полного двудольного неориентированного графа G0 = (V u W,E0), где E0 — множество рёбер |vi,Wj|, Vi є V, Wj є W |E0| = m2 . Разбиение л = (л., л2) устанавливает ориентацию ребра из Vi є V в Wj є W и его вес, равный у ij, если |vi,Wj>ЄЛ1, |л.| = m. . Если |vi,Wj>єл2 ,
|л 2 = m — m., то ребро ориентировано из w j є W в Vi є V и принимает вес, равный Pij. Определим вес полученного ориентированного подграфа графа G=(VuW,E) как сумму весов входящих в него дуг. Требуется построить на множестве всех таких подграфов подграф л* = (л*,л2) с наименьшим весом.
Оценим мощность области допустимых решений л = (л.,л2). Таблица [(Yij,PijXIm порождает m! последовательностей л, а число всех возможных разбиений элементов л на два таких подмножества л. и л2 , что | л. |= m., | л2 |= m — m., 0 < m. < m, равно
m! /(mj (m — mj)). Следовательно, область поиска разбиения п* = (я* ,%2) содержит (m!)2/(mj(m — mj)) допустимых решений П = (nj, Я 2) .
Приведём промежуточный результат, позволяющий выполнять построение П* = (Л* ,я2) на множестве из m! перестановок я = ^, я 2).
С этой целью рассмотрим задачу разбиения m упорядоченных пар (уj,Pj) , j= j,m на два подмножества ст0 и ст0 с заданным числом mi пар в ст0 , О < mj < m и с наименьшей величиной
Т(ст0, ст 2) = min ( ^ Y j + ЕР j)
0-(0!’ °2) jeaj je(J2 (3)
среди всех разбиений (стьСт2 ) множества ° = .
Утверждение. Величина Т(ст О, ст О) достигается упорядочением множества ст = <(у j, р j) / і < j < m>по неубыванию значений 8 j =у j -р j и включением в подмножество ст0 mj первых слева элементов полученной последовательности.
Доказательство. Для разбиения множества ст = <(У j, Pj)/! ^ j ^ m>на подмножества ctj и Ст2, |ctj| = mb|ст2| = m-mі,mі >О имеем
Т (сь ст 2) =Еу j + ЕР j = Еу j + EPj -ЕР j =
jeaj jen 2 je°j j=j je°j
= EP j + E (y j-P j) = const+ E8 j.
Отсюда следует, что для нахождения минимума Т(ст j, ст 2) достаточно получить последовательность ст° компонент (уj,Рj) , j> j
и подпоследовательность ст0, состоящую из mj первых слева компонент ст° . Утверждение доказано.
Таким образом, установленный результат позволяет легко находить по заданной последовательности л = (я[Ц,я[2] . я[щ]), соответствующей матрице перестановки X элементов таблицы [(у ij, Pij)]m , единственное разбиение % = (^0, я®), у которого величина (2) достигает наименьшего значениия среди всех m!/(mj!(m — mj)!) разбиений, порождаемых множеством <(уЛ[ j], P[j])/j - j - m>.
Опишем алгоритм, который не гарантирует построения точного решения, но для типичных индивидуальных примеров задач определяет близкое к оптимальному расписание.
S1. Матрица [Уу]ш составлена в предположении mj = m, а матрица [Pij]m содержит информацию о продолжительности маршрутов при условии, что
Матрица [(у ij, Pij)]m, определяемая наложением [Yij]m на [Pij]m ; mj и m — mj — заданное число автобусов в пунктах 1 и 2.
52. Определить матрицу , где а- = у- +Р- .
53. Найти множество всех решений, минимизирующих целевую функцию задачи о назначениях для
54. Каждому оптимальному решению задачи о назначениях поставить в соответствие m компонент из матрицы [(уij,Pij)]m и упорядочить их с помощью шагов S11-S14 алгоритма [1] при n=m.
55. Определить соответственно mj первых слева компонент матрицы [yy]m и m — mj компонент матрицы [Pij]m .
Точность допустимого решения зависит от длины входа, задаваемой разностью матриц [Уі- ]m и [Pij ]m , и от того, в каких пределах изменяются значения их элементов. Так как содержательная формулировка задачи исключает на входе присутствие чрезвычайно больших чисел, то есть все основания ожидать на выходе алгоритма решений с приемлемыми на практике погрешностями. Определив
перестановку я0 = (я0^), я0(2). я^щ)) , доставляющую минимум целевой функции задачи о назначениях для исходных данных в виде матрицы [a 0-]m , а 0 = min( у ij Pi-), получим неравенства
Еал0(-) ^ Т (ль л2) ^ Т , лг),
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
устанавливающие диапазон поиска значения ** п2).
Оценим трудоемкость построения допустимого решения ^j+, я 2+ ]. При выполнении шагов S1 и S2 для определения матриц [(уij,Рij)]m и [aij]m нужно o(m2) элементарных действий. Применяемая на шаге S3 процедура построения всех оптимальных решений задачи о назначениях выполняется за время O(Nmaxm4 log2 m) операций.
Рассмотрим пример. Пассажирские перевозки между пунктами 1 и 2 осуществляются двумя автобусами автопредприятия, расположенного в пункте 1, и тремя автобусами автопредприятия, расположенного в пункте 2.
Из расписания движения автобусов по автостанциям определим:
время отправления автобусов из первого пункта t1jj=при соответствующих TU =,
время отправления автобусов из второго пункта t2j=при соответствующих T2,j =, m1=2, m2=5-2=3.
В соответствии с исходными данными определим таблицы [Уij ]m и [Pij ]m :
[^ ij ]5 — 25 27 30 28 12
[Р ij ]5 = 23 25 26 30 11
Наложением матриц [ 7 ij ]m и [ Р ij ] m
таблицу [(у ij, Р ij)]
‘(29,28) (27,30) (24,23 (14,15) (18,16)»
(29.26) (31,28) (27,30) (12,13) (16,15)
(25,23) (27,25) (30,26) (28,30) (12,11)
(21,20) (23,22) (26,26) (28,31) (32,32)
(19,16) (21,18) (24,22) (27,26) (30,28)
[a ij]m где «ij = = 7ij + Pij
Найдем все решения, доставляющие минимум целевой функции задачи о назначениях для исходных данных, представленных матрицей [a ij]m :
Т( %1 )=47+25+23+41+39=175,
%2 = (а13,« 24, «35, «42, «51) ’
Т(л 2) =47+25+23+45+35=175.
Для каждого элемента перестановки ^ найдем соответствующую пару из [(у ij, Р ij )b, в результате чего получим множество из пяти пар:
(У13, Р13) =(24,23), (У 24, Р 24) =(12,13),
(7 35, Р35) =(12,11), (У 41, Р 41) =(21,20),
Теперь определим стj для ^1 : Ст1 = 24-23=1, Ст2 = 12-13=-1, ст3 =12-11=1, ст4 =21-20=1, ст5 =21-18=3. Упорядочив значения стj по неубыванию, получим последовательность Ст2 < 01
ЕУі) = У24 +У13 = 24 +12 = 36 , i,jen1
Е Pij = Р35 + Р41+ Р52 = 11 + 20+18 = 49,Т(л1) = 85.
Аналогично найдем для каждого элемента перестановки ^2 соответствующую пару из [(у ij, Pij)]5 , в результате чего получим множество из пяти пар:
(У13, Р13) =(24,23), (У 24, Р 24) =(12,13),
(7 35, Р35) =(12,11Х (7 42, Р 42) =(23,22Х (7 51Р51) =(19,16).
Теперь определим стj для Ст1 = 24-23=1, Ст2 = 12-13=-1, ст3 = 12-11=1, ст4 = 23-22=1, ст5 = 19-16=3. Получим последовательность а2 < 01
Е 7ij =У24 +713 = 24 +12 = 36 , i,je7tl1
Е Pii — Р35 +Р42 + Р51 _ 11 + 22 + 16 _ 49,Т(л2) _ 85. ■ ■ + i,j£»22
Все полученные разбиения доставляют целевой функции задачи значение, равное 85.
Совершенное паросоочетание, соответствующее разбиению ^1 = (л 11, л21), представлено на рисунке.
Оценим точность построенных решений. Для этого вычислим нижнюю границу Т(л*, л^), равную 0 n
Т(л 0) = 2 min( у ij, Pij) j=1
Из [( У ij , Р ij )] 5 определим
Решение задачи о назначениях дает последовательность л0 = («13,«24,«35,«41,«52) , для которой Т(л 0) = 23 +12 +11 + 20 +18 = 84 . Таким образом, величина Т^ , л 2) ограничена снизу значением Т(л0) = 84, а сверху — значением Т^ ,л2) =85.
Литература: 1.Панишев А.В., Подоляка О.А., Скакалина Е.В. Эффективный алгоритм распараллеливания работ на неидентичных машинах //Авиационно-космическая техника и технология: Сб.науч.тр. Вып. 13. Харьков: Гос.аэрокосм.у-т. “ХАИ “, 1999. С. 136-146.
Поступила в редколлегию 24.03.2001 Рецензент: д-р техн. наук, проф. Евдокимов А.Г.
Скрипина Ирина Валентиновна, старший преподаватель кафедры информатики Харьковского государственного автомобильно-дорожного технического университета. Научные интересы: математическое моделирование, теория расписаний и ее применение. Адрес: Украина, 61078, Харьков, ул. Петровского, 25, тел. 10-77-53.
Компьютерное информационное моделирование
Внимание! Все тесты в этом разделе разработаны пользователями сайта для собственного использования. Администрация сайта не проверяет возможные ошибки, которые могут встретиться в тестах.
ООО КОМПЭДУ, http://compedu.ru При поддержке проекта http://videouroki.net
Система оценки: 5* балльная
Список вопросов теста
Вопрос 1
Выберите свойства объекта «ученик», необходимые для создания информационной модели ученика, представленной в школьном журнале.
Выберите несколько из 5 вариантов ответа:
Варианты ответов
Вопрос 2
Выберете из представленных моделей информационные.
Выберите несколько из 10 вариантов ответа:
Варианты ответов
- Бронзовый бюст композитора
- Расписание движения автобусов
- Макет застройки агрогородка
- Карта метрополитена
- Рисунок родословного дерева
- Распечатка программы
- Список школьников гимназии
- Солнцезащитные очки
- Инструмент для резки овощей
- Прогноз погоды на сайте в сети Интернет
Вопрос 3
К какому виду моделей можно отнести математическое выражение .
Выберите один из 3 вариантов ответа:
Варианты ответов
- Знаковая
- Образная
- Материальная
Вопрос 4
Учащиеся ежедневно измеряли утреннюю и вечернюю температуру воздуха и строили графики её изменения. Какой тип модели (с точки зрения временного фактора) представляет подобный график?
Выберите один из 4 вариантов ответа:
Варианты ответов
- Статическая
- Образно-знаковая
- Динамическая
- Знаковая
Вопрос 5
Для описания отношений между элементами системы удобнее всего использовать информационную модель следующего вида:
Выберите один из 5 вариантов ответа:
Варианты ответов
- текстовую
- математическую
- графическую
- структурную
- табличную
Вопрос 6
Вид информационной модели зависит от:
Выберите один из 5 вариантов ответа:
Варианты ответов
- числа признаков
- цели моделирования
- размера объекта
- внешнего вида объекта
- стоимости объекта
Вопрос 7
Сколько моделей можно создать при описании Солнечной системы?
Выберите один из 4 вариантов ответа:
Варианты ответов
Вопрос 8
Примером какой модели является расписание движения автобусов?
Выберите один из 4 вариантов ответа:
Варианты ответов
- Компьютерной
- Табличной
- Графической
- Математической
Вопрос 9
Компьютерная модель ядерного взрыва не позволяет:
Выберите один из 5 вариантов ответа:
Варианты ответов
- Сохранить экологию окружающей среды
- Уменьшить стоимость исследования
- Обеспечить безопасность исследователей
- Провести натуральное исследование процессов
- Получить данные о влиянии взрыва на здоровье человека
Вопрос 10
Учитель на уроке рассказывает о гибели динозавров. К какому виду моделей (по способу представления) можно отнести его рассказ?
Выберите один из 3 вариантов ответа:
Варианты ответов
- Материальная
- Образная
- Вербальная
§1.4 Табличные информационные модели
В табличных информационных моделях информация об объектах представляется в виде прямоугольной таблицы, состоящей из столбцов и строк.
Вам хорошо известно табличное представление расписания уроков, в табличной форме представляются расписания движения автобусов, самолётов, поездов и многое другое.
Представленная в таблице информация наглядна, компактна и легко обозрима.
1.4.1. Представление данных в табличной форме
В качестве информационных моделей объектов, обладающих одинаковыми наборами свойств, как правило, используются таблицы типа «объект—свойство».
Например, информацию о регионах нашей страны можно представить с помощью таблицы, фрагмент которой приведён в табл. 1.1.
В этой таблице каждая строка содержит информацию об одном объекте — регионе; столбцы — отдельные характеристики (свойства) рассматриваемых объектов: название, дата образования, площадь и т. д. Такие таблицы могут содержать числовую, текстовую и графическую информацию.
Таблица 1.1. Регионы Российской Федерации
В таблицах типа «объект—объект» отражается взаимосвязь между объектами одного или нескольких классов. Например, в школьных журналах есть таблица «Сведения о количестве уроков, пропущенных обучающимися»; её фрагмент представлен в табл. 1.2.
Таблица 1.2. Сведения о пропусках уроков
В этой таблице отражена связь «количество пропущенных уроков» между объектами класса «Учащиеся» и объектами класса «Число».
В таблице «Расстояния между городами» (табл. 1.3) представлены расстояния между парами объектов, принадлежащих одному классу «Город». Создайте эту таблицу в текстовом редакторе и добавьте в свободные строку и столбец информацию о своём населённом пункте.
Таблица 1.3. Расстояния между городами (км)
В форме таблицы «объект-объект* можно представить информацию о наличии границ (сухопутной, морской, озёрной, речной) России с другими странами; её фрагмент представлен в табл. 1.4.
Таблица 1.4. Граница Российской Федерации
Если граница соответствующего вида есть, то в нужную ячейку ставится 1, а если нет — 0.
Важная особенность этой таблицы состоит в том, что в ней фиксируются не количественные («Сколько?»), а качественные свойства (наличие/отсутствие связи между объектами).
1.4.2. Использование таблиц при решении задач
Рассмотрим несколько примеров задач, которые удобно решать с помощью табличных информационных моделей.
Пример 1. Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой из которых 3 камня, а во второй — 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в ка-кую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16. Кто выигрывает при безошибочной игре — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Ранее мы рассмотрели способ записи решения подобных задач с помощью дерева. Сейчас оформим решение в виде таблицы (табл. 1.5).
Таблица 1.5. Таблица игры
Три числа в каждой ячейке таблицы обозначают соответственно количество камней в кучах и их сумму. В первом столбце зафиксировано распределение камней перед игрой (исходное положение).
Во втором столбце рассмотрены все возможные варианты ходов первого игрока; победить с первого хода он не может.
В третьем столбце рассмотрены имеющиеся выигрышные варианты ходов второго игрока (отмечены «галочкой»). При безошибочной игре первого игрока такие ситуации возникнуть не должны. Поэтому рассматриваем все возможные ходы второго игрока в случаях, когда у него нет выигрышного хода. Если получены одинаковые варианты, то все из них, кроме одного, исключаем из дальнейшего рассмотрения.
В четвёртом столбце отмечены имеющиеся выигрышные варианты второго хода первого игрока. При безошибочной игре второго игрока такие ситуации возникнуть не должны. Поэтому рассматриваем все возможные ходы первого игрока в случае, когда у него нет выигрышного хода.
В пятом столбце отмечены выигрышные ходы второго игрока, имеющиеся при всех вариантах хода первого игрока.
Таким образом, при безошибочной игре соперников побеждает второй игрок. Его первый ход должен быть таким, чтобы в кучах стало 4 и 3 камня.
Пример 2. С помощью взвешенного графа на рис. 1.6 представлена схема дорог, соединяющих населённые пункты А, В, С, Z), Е. Построим таблицу, соответствующую этому графу (рис. 1.10).