Пример задания:

Р-04. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

	A	B	C	D	E	F	G
A		5		12			25
B	5			8
C				2	4	5	10
D	12	8	2
E			4				5
F			5				5
G	25		10		5	5

Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).

Решение:

1. начнём строить возможные маршруты из пункта A; за 1 шаг можно приехать в B, C или сразу в G (в скобках показаны длины маршрутов):

AB(5), AD(12), AG(25)

заметим, что G – это целевая точка (конечный пункт), поэтому мы уже имеем один полный маршрут длиной 25

2. строим двух шаговые маршруты: из B дальше можно ехать в D (возврат в А неинтересен!)

ABD (5 + 8 = 13)

этот маршрут нет смысла продолжать, поскольку в D можно приехать быстрее: длина уже найденного маршрута AD равна 12

3. из D можно ехать в B и C:

ADB (12 + 8 = 20)

ADC (12 + 2 = 14)

4. третий шаг: маршрут ADB продолжать бессмысленно: из B можно вернуться только в A и D

5. продолжаем маршрут ADC (14):

ADCE (14 + 4 = 18)

ADCF (14 + 5 = 19)

ADCG (14 + 10 = 24)

в последнем варианте мы приехали в конечный пункт, причем новый маршрут имеет длину 24 < 25, то есть, он короче найденного ранее

6. четвёртый шаг: продолжаем маршрут ADCE:

ADCEG (18 + 5 = 23)

и маршрут ADCF:

ADCFG (19 + 5 = 24)

7. других продолжений (без возврата в уже посещённые пункты) нет, поэтому кратчайший маршрут – ADCEG, он имеет длину 23.

8. Ответ: 23.

9. Заметим, что эти рассуждения можно зарисовать в виде дерева возможных маршрутов. После первого шага:

После второго шага:

После третьего шага:

После четвёртого шага:

Задачи

1. В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.

	A	B	C	D	E
A		1	4		1
B	1		2
C	4	2		3
D			3
E	1

1)	2)	3)	4)
		D	D

2. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.

3. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.

Задание 4-1

Тема: Поиск и сортировка информации в базах данных.

Что нужно знать:

• при составлении условия отбора можно использовать знаки отношений <, <= (меньше или равно), >, >= (больше или равно), = (равно), <> (не равно)

• последовательность выполнения логических операций в сложных запросах: сначала выполняются отношения, затем – «И», потом – «ИЛИ»

• для изменения порядка выполнения операции используют скобки

• реляционные базы данных обычно хранятся в памяти компьютера в виде нескольких связанных таблиц

• столбцы таблицы называются полями, а строки – записями

• каждая таблица содержит описание одного типа объектов (человека, бригады, самолета) или одного типа связей между объектами (например, связь между автомобилем и его владельцем)

• в каждой таблице есть ключ – некоторое значение (это может быть одно поле или комбинация полей), которое отличает одну запись от другой; в таблице не может быть двух записей с одинаковыми значениями ключа

• на практике часто используют суррогатные ключи – искусственно введенное числовое поле (обычно оно называется идентификатор, ID)

Р-06. В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите, сколько прямых потомков (т.е. детей и внуков) Павленко А.К. упомянуты в таблице 1.

Решение:

1. сначала находим в таблице 1 Павленко А.К. (ID = 2155)

2. теперь по таблице 2 ищем его детей – их идентификаторы 2302 и 3002; можно строить генеалогическое дерево:

3. далее так же определяем внуков 2155, то есть, детей 2302 и 3002:

4. как следует из таблицы, данных о правнуках 2155 в таблице нет

5. всего прямых потомков 7 – двое детей и 5 внуков.

6. Ответ: 7.

Задачи

1. Из правил соревнования по тяжелой атлетике: Тяжелая атлетика – это прямое соревнование, когда каждый атлет имеет три попытки в рывке и три попытки в толчке. Самый тяжелый вес поднятой штанги в каждом упражнении суммируется в общем зачете. Если спортсмен потерпел неудачу во всех трех попытках в рывке, он может продолжить соревнование в толчке, но уже не сможет занять какое-либо место по сумме 2-х упражнений. Если два спортсмена заканчивают состязание с одинаковым итоговым результатом, высшее место присуждается спортсмену с меньшим весом. Если же вес спортсменов одинаков, преимущество отдается тому, кто первым поднял победный вес. Таблица результатов соревнований по тяжелой атлетике:

Фамилия И.О.	Вес спортсмена	Взято в рывке	Рывок с попытки	Взято в толчке	Толчок с попытки
Айвазян Г.С.	77,1	147,5	3	200,0	2
Викторов М.П.	79,1	147,5	1	202,5	1
Гордезиани Б.Ш.	78,2	147,5	2	200,0	1
Михальчук М.С.	78,2	147,5	3	202,5	3
Пай С.В.	79,5	150,0	1	200,0	1
Шапсугов М.Х.	77,1	147,5	1	200,0	1

Кто победил в общем зачете (по сумме двух упражнений)?

1) Айвазян Г.С. 2) Викторов М.П. 3) Михальчук М.С. 4) Пай С.В.

2. Ниже приведены фрагменты таблиц базы данных сообщества писателей:

Литератор	Издательство
Волкова П.Е.	Словеса
Зайцев К.Ю.	Чтиво
Иванов В.В.	Библон
Ивочкин Р.Д.	Словеса
Крот В.Ф.	Библон
Крот В.Ф.	Словеса
Крот В.Ф.	Чтиво
Рылон Ш.О.	Библон
Швец У.П.	Словеса

Литератор	Жанр	Число публикаций
Волкова П.Е.	Проза	20
Зайцев К.Ю.	Проза	5
Иванов В.В.	Поэзия	21
Ивочкин Р.Д.	Проза	6
Крот В.Ф.	Драматургия	77
Ивочкин Р.Д.	Поэзия	3
Иванов В.В.	Драматургия	13
Рылон Ш.О.	Поэзия	43
Швец У.П.	Поэзия	20

Сколько авторов, сотрудничающих с издательством «Словеса», работают в жанре поэзии и имеют в этом жанре более 20 публикаций?

1) 3 2) 2 3) 1 4) 0

3. В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите, сколько всего внуков и внучек есть у Ковач Л.П

1) 1 2) 2 3) 3 4) 4

Задание 5

Тема: Кодирование и декодирование информации.

Что нужно знать:

• кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)

• обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход

• один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)

• кодирование может быть равномерное и неравномерное; при равномерном кодировании все символы кодируются кодами равной длины; при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование

• закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;

• закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;

• условие Фано – это достаточное, но не необходимое условие однозначного декодирования.