1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Что вы можете сказать о формах представления информации в презентации и в учебнике? Какими слайдами вы могли бы дополнить презентацию?
2. Какие информационные модели относят к графическим?
Графическими считаются такие информационные модели, которые изображают сведения с помощью рисунков, схем, чертежей, карт, диаграмм или любых других наглядных изображений. Они позволяют представить объекты, их свойства и связи в визуальном виде.
3. Приведите примеры графических информационных моделей, с которыми вы имеете дело:
а) при изучении других предметов;
б) в повседневной жизни.
Примеры графических моделей при изучении предметов можно увидеть в географии в виде карт, в биологии в виде рисунков организмов или схем строения клетки, в математике в виде графиков функций или геометрических чертежей. В повседневной жизни графические модели встречаются в виде дорожных схем, карт местности, инструкций с картинками, схем бытовой техники или планов зданий.
4. Что такое граф? Что является вершинами и рёбрами графа на рис. 1.6? Приведите примеры цепей и циклов, имеющихся в этом графе. Определите, какие два пункта наиболее удалены друг от друга (два пункта считаются самыми удалёнными, если длина кратчайшего пути между ними больше, чем длина кратчайшего пути между любыми другими двумя пунктами). Укажите длину кратчайшего пути между этими пунктами.
Граф представляет собой набор точек и линий, которые обозначают объекты и связи между ними. Вершинами на рисунке считаются обозначенные пункты, а рёбрами — линии, соединяющие эти пункты. Цепью называется любая последовательность вершин, соединённых рёбрами без разрывов, например переход от одного пункта к другому через промежуточные. Циклом является цепь, в которой путь возвращается в исходную вершину. На рисунке можно выделить несколько таких замкнутых обходов.
5. Приведите пример системы, модель которой можно представить в форме графа. Изобразите соответствующий граф.
Пример системы, модель которой можно представить в форме графа, — городская автобусная сеть, где узлы обозначают остановки, а ребра — регулярные маршруты между ними. Наглядное изображение такого графа приведено ниже (цифры — остановки, линии — прямые маршруты):
1 / 2---3 \ 4---5
В этом графе вершины 1, 2, 3, 4, 5 — остановки, а рёбра 1–2, 1–3, 2–3, 2–4, 3–5, 4–5 — маршруты между ними.
6. Грунтовая дорога проходит последовательно через населённые пункты А, В, С и D. При этом длина грунтовой дороги между А и В равна 40 км, между В и С — 25 км, и между С и D — 10 км. Между А и D дороги нет. Между A и С построили новое асфальтовое шоссе длиной 30 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге — 20 км/ч, по шоссе — 30 км/ч.
Имеются дороги A–B 40 км (грунт), B–C 25 км (грунт), C–D 10 км (грунт), и шоссе A–C 30 км (асфальт). Скорость по грунтовой дороге 20 км/ч, по шоссе 30 км/ч. Вариант 1 прямой путь A–B по грунтовой дороге занимает время 40 / 20 = 2,0 часа. Вариант 2 путь A–C по шоссе занимает 30 / 30 = 1,0 часа, затем C–B по грунту 25 / 20 = 1,25 часа, суммарно 2,25 часа. Других путей короче нет, следовательно минимально возможное время равно 2,0 часа.
7. Составьте семантическую сеть по русской народной сказке «Колобок».
Основные элементы и связи можно записать так (стрелки показывают направление связи, слова после стрелок — тип связи): Дед и Баба — испекли -> Колобок; Колобок — убежал -> Лес; Колобок — пел -> Песня о себе; Колобок — встретил -> Заяц; Заяц — пытался съесть -> Колобок; Колобок — встретил -> Волк; Волк — пытался съесть -> Колобок; Колобок — встретил -> Медведь; Медведь — пытался съесть -> Колобок; Колобок — встретил -> Лиса; Лиса — обманула -> Колобок; Лиса — съела -> Колобок. Дополнительные узлы: Дом (где жили Дед и Баба), Лес (место встречи), Песня (повторяющийся мотив). Такая сеть наглядно показывает, кто кого встречал, кто кем управлял действием и чем закончилась каждая встреча.
8. Что такое дерево? Моделями каких систем могут служить деревья? Приведите пример такой системы.
Дерево в теории графов — это связный граф, не содержащий циклов (то есть между любыми двумя вершинами существует ровно один простой путь). Деревья служат моделями иерархических и разветвлённых структур: родословных деревьев, файловой структуры компьютера, организационных схем, схем принятия решений, филогенетических деревьев в биологии. Пример системы, моделируемой деревом: файловая система компьютера, где вершины — каталоги и файлы, ребро соединяет каталог с вложенным файлом или подкаталогом; корень — корневой каталог, от которого расходятся ветви вглубь структуры.
9. Сколько трёхзначных чисел можно записать с помощью цифр 2, 4, 6 и 8 при условии, что в записи числа не должно быть одинаковых цифр?
Трёхзначные числа, записываемые цифрами 2, 4, 6, 8 без повторений. На сотнях может стоять любая из 4 цифр, на десятках — любая из оставшихся 3, на единицах — любая из оставшихся 2. Всего 4 * 3 * 2 = 24 числа.
10. Сколько существует трёхзначных чисел, все цифры которых различны?
Трёхзначные числа с различными цифрами. Первая (сотни) цифра может быть любой от 1 до 9, то есть 9 вариантов; вторая цифра может быть любой из оставшихся 9 (включая 0, если он не выбран первым); третья — любая из оставшихся 8. Получаем 9 * 9 * 8 = 648 чисел.
11. Для составления цепочек используются бусины, помеченные буквами А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором — любая гласная, если первая буква гласная, и любая согласная, если первая согласная. На третьем месте — одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?
Условие: бусины A, B, C, D, E. На первом месте одна из A, C, E. Если первая буква гласная, на втором — любая гласная; если первая согласная, на втором — любая согласная. На третьем месте — одна из C, D, E, причём она не должна совпадать с той, что стоит на первом месте. В алфавите из этих бусин гласные — A и E, согласные — B, C, D. Разбив по случаям: если первая A, то вторых вариантов 2 (A или E), третьих 3 (C,D,E), итого 6; если первая E, вторых 2, третьих (из C,D,E, но не E) 2, итого 4; если первая C, вторых 3 (B,C,D), третьих (из C,D,E, но не C) 2, итого 6. Всего 6 + 4 + 6 = 16 допустимых цепочек.
12. Два игрока играют в следующую игру. Перед ними лежит куча из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Игра с кучей из 6 камней, за ход берут 1, 2 или 3 камня; проигрывает тот, кто забирает последний камень (условие «берущий последний проигрывает» — мисерный вариант). Анализ по шагам: при 1 камне ходящий обязан взять его и потому проигрывает, значит позиция с 1 камнем проигрышная для игрока на ходу. Позиции с 2, 3 и 4 камнями выигрышные (есть ход, переводящий соперника в состояние с 1 камнем). Позиция с 5 камнями проигрышная (любой допустимый ход переводит в 2, 3 или 4 — выигрышные для соперника). Следовательно позиция с 6 камнями выигрышная: существует ход, переводящий соперника в 5 камней. Этот ход — взять 1 камень. Значит при безошибочной игре выигрывает игрок, делающий первый ход, и первый его ход должен быть взятие одного камня.