«Аттестация учащихся 9-х классов по информатики и ИКТ» Барабонин Сергей Юрьевич, МОУ СОШ 59

Что такое Государственная итоговая аттестация (ГИА)? В практику современной школы, в связи с введением в средней школе профильного обучения, позволяющего более полно учитывать интересы, склонности и способности учащихся, введена новая модель экзамена для выпускников основной школы. На основании результатов ГИА будет проходить зачисление в 10 класс по выбранному профилю обучения. Задания для государственной (итоговой) аттестации (ГИА) выпускников 9-х классов создаются специалистами Федерального института педагогических измерений (

Как подготовить учащихся к ГИА? Чтобы успешно сдать итоговые экзамены за основную школу и выдержать конкурс в профильную школу, учащимся необходимо сделать несколько важных шагов: Объективно оценить свой актуальный уровень знаний и возможностей Опираясь на свои интересы, профориентацию и знания выбрать направление дальнейшего обучения в профильной школе

При подготовки к ГИА учащимся необходимо: разъяснить особенности формулировок заданий; познакомить с критериями, которыми руководствуются эксперты при проверке тестовых заданий; рассмотреть самые распространенные ошибки; отработать навыки тестирования; научить распределять время на выполнение тестовых заданий; ознакомить, по каким темам больше всего вопросов в тестах

Рассмотрим задания 3

Проверяемые элементы содержания Умение анализировать формальные описания реальных объектов и процессов. Проверяемые элементы содержания по кодификатору Формализация описания и моделирование реальных объектов и процессов Требования к уровню подготовки по кодификатору создавать и использовать различные формы представления информации: формулы, графики, диаграммы, таблицы (в том числе динамические, электронные, в частности в практических задачах); переходить от одного представления данных к другому Уровень сложности задания - базовый Максимальный балл за выполнение задания - 1 Примерное время выполнения задания (мин.) – 3

ГИА 2011

Что нужно знать: Информационная модель может быть построена с помощью графов

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

рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во- вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет

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

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 9 2) 10 3) 11 4) 12

Решение (вариант 1, использование схемы): построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4): A B C 2 4

для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7): A B C E

новые маршруты из С – в D и E (длины путей соответственно 3 и 4): D A B C E

новый маршрут из D – в E (длина пути 3): D A B C E

новый маршрут из E – в F (длина пути 2): D FA B C E

нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E попробуем перечислить возможные маршруты из А в Е: А – В – Едлина 9 А – В – С – Е длина 7 А – В – C – D – Е длина 9 А –C – Е длина 8 А –C – B – Е длина 12 А –C – D – Е длина 10

из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C- E-F равна = 9 таким образом, правильный ответ – 1.

Решение (вариант 2, с начала маршрута): 1.составим граф, который показывает, куда (и как) можно ехать из пункта А, рядом с дугами будем записывать увеличение пути, а рядом с названиями пунктов – общую длину пути от пункта A: A BC

2.видно, что напрямую в пункт F из A не доехать 3.строим граф возможных путей дальше: определяем, куда можно ехать из B и C (конечно, не возвращаясь обратно); из B можно ехать только в A (обратно), в C и в E; 4.узел C уже есть на схеме, и оказывается, что короче ехать в него по маршруту A-B-C, чем напрямую A-C, длина «окольного» пути составляет 3 вместо 4 для «прямого»; при движении по дороге B-E длина увеличивается на 7: A BC E +7 9

5.строим маршруты из пункта C; кроме A и B, из пункта C можно ехать в D (длина 3) и E (длина 4), причем кратчайший маршрут из A в E оказывается A-B-C-E (длина 7); «невыгодные» маршруты на схеме показывать не будем: A BC E D

6.из пункта D, кроме как в С и E, ехать некуда; путь D-C – это возврат назад (нас не интересует), путь D-E тоже не интересует, поскольку он дает длину = 9, а мы уже нашли, что в E из A можно доехать по маршруту длины 7 7.из пункта E можно ехать в F, длина полного маршрута = 9 A BC E D F +2 9

Решение (вариант 3, с конца маршрута): 1.можно точно так же начинать с пункта F и искать кратчайший маршрут до A; судя по таблице, из F можно ехать только в E: E 2 F +2+2

2.из E ведут дороги в B, C и D BC 9 6 E D 5 F из B можно сразу попасть в A, длина пути будет равна 11: BC 9 6 E D 5 F A

4.из пункта C есть прямая дорога в A длиной 4, таким образом, существует маршрут длиной = 10 BC 9 6 E D 5 F A

5.кроме того, есть дорога C-B, которая дает маршрут F-E-C-B-A длиной 9 BC 7 6 E D 5 F A рассмотрение пути C-D не позволяет улучшить результат: оптимальный маршрут имеет длину 9

Возможные проблемы: можно не заметить, что маршруты, проходящие через большее число пунктов, оказываются короче (A-B-C короче, чем A-C и A-B-C-E короче, чем A-B-E)

Рассмотрим задания 11

Проверяемые элементы содержания Умение анализировать информацию, представленную в виде схем Проверяемые элементы содержания по кодификатору Диаграммы, планы, карты Формализация описания и моделирование реальных объектов и процессов Требования к уровню подготовки по кодификатору создавать и использовать различные формы представления информации: формулы, графики, диаграммы, таблицы (в том числе динамические, электронные, в частности в практических задачах); переходить от одного представления данных к другому Уровень сложности задания - базовый Максимальный балл за выполнение задания - 1 Примерное время выполнения задания (мин.) – 4

Что нужно знать: если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть, где обозначает число путей из вершины A в некоторую вершину i число путей конечно, если в графе нет циклов – замкнутых путей

Пример задания: На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? Г ВА К Е БД Ж И

Решение (1 вариант, подстановки): 1.начнем считать количество путей с конца маршрута – с города К 2.будем обозначать через N X количество различных путей из города А в город X 3.общее число путей обозначим через N 4.по схеме видно, что N Б = N Г = 1 5.очевидно, что если в город X можно приехать только из Y, Z, то N X = N Y + N Z, то есть нужно сложить число путей, ведущих из A во все города, откуда можно приехать в город X

6.поскольку в K можно приехать из Е, Д, Ж или И, поэтому N = N К = N Д + N Е + N Ж + N И 7.в город И можно приехать только из Д, поэтому N И = N Д 8.в город Ж можно приехать только из Е и В, поэтому N Ж = N Е + N В Г ВА К Е БД Ж И

9.подставляем результаты пп. 6 и 7 в формулу п. 5: N = N В + 2N Е + 2N Д 10.в город Д можно приехать только из Б и В, поэтому N Д = N Б + N В так что N = 2N Б + 3N В + 2N Е Г ВА К Е БД Ж И

11.в город Е можно приехать только из Г, поэтому N­ Е = N Г так что N = 2N Б + 3N В + 2N Г 12.по схеме видно, что N Б = N Г = 1, кроме того, N В = 1 + N­ Б + N Г = 3 Г ВА К Е БД Ж И

13.окончательно N = 2N Б + 3N В + 2N Г = 2·1 + 3·3 + 2·1 = Ответ: 13. Г ВА К Е БД Ж И

Решение (2 вариант, удобная форма записи): начнем считать количество путей с конца маршрута – с города К

1.записываем для каждой вершины, из каких вершин можно в нее попасть К ИДЖЕ И Д Ж ВЕ Е Г Д БВ Г А В АБГ Б А Вершина откуда? КИДЖЕ ИД ЖВЕ ЕГ ДБВ ГА ВАБГ БА Г ВА К Е БД Ж И

2.теперь для удобства «обратного хода» вершины можно отсортировать так, чтобы сначала шли все вершины, в которые можно доехать только из начальной точки А: Б А Г А затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки): В АБГ Е Г далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е: Д БВ Ж ВЕ на следующем шаге добавляем вершину И И Д и, наконец, конечную. вершину К ИДЖЕ именно в таком порядке мы и будем вычислять количество путей для каждой вершины Такая процедура называется топологической сортировкой графа. вершинаоткуда?N БА1 ГА1 ВАБГ3 ЕГ1 ДБВ4 ЖВЕ4 ИД4 КИДЖЕ13 Г ВА К Е БД Ж И

Возможные ловушки и проблемы: очень важна аккуратность и последовательность; сначала идем от конечной точки к начальной, выписывая все вершины, из которых можно приехать в данную; затем идем обратно, определяя числовые значения построение полного дерева маршрутов – занятие трудоемкое и достаточно бесперспективное

Решение (3 вариант, перебор вершин по алфавиту): 1.Запишем вершины в алфавитном порядке и для каждой из них определим, из каких вершин можно в нее попасть вершинаоткуда? БА ВАБГ ГА ДБВ ЕГ ЖВЕ ИД КИДЖЕ

2.теперь определяем количество путей; сначала ставим 1 для тех вершин, в которые можно проехать только из начальной (А): вершинаоткуда?N БА1 ВАБГ ГА1 ДБВ ЕГ ЖВЕ ИД КИДЖЕ

3.затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки): вершинаоткуда?N БА1 ВАБГ3 ГА1 ДБВ ЕГ1 ЖВЕ ИД КИДЖЕ

4.следующий шаг вершинаоткуда?N БА1 ВАБГ3 ГА1 ДБВ4 ЕГ1 ЖВЕ4 ИД КИДЖЕ

5.и последние 2 шага вершинаоткуда?N БА1 ВАБГ3 ГА1 ДБВ4 ЕГ1 ЖВЕ4 ИД4 КИДЖЕ13

Где брать задания для учащихся?

Пособия для подготовки к ГИА по информатике ГИА-2011.Экзамен в новой форме. Информатика:9 класс. Тренировочные варианты экзаменационных работ для проведения государственной итоговой аттестации в новой форме. Информатика и ИКТ. 9кл. Подготовка к ГИА-2011_Лысенко, Евич_2011 Информатика. ГИА. Учебно-справочные материалы для 9 класса. Авдошин С.М., Ахметсафина Р.З., Максименкова О.В. и др.

Дополнительные материалы для учащихся? Презентация «Введение в теорию графов»