Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра «Информатика и методика обучения информатике и математике»

Курсовая работа

по дисциплине Методика обучения и воспитания(информатика)

на тему: «Методика решения задач моделирования и теории графов в формате ЕГЭ по информатике»

Выполнил студент:

Матьякубов Ш.

Руководител:

Губанова О.М

Пенза 2018



Содержание

Введение

Глава 1. Теоретическая часть

1.1 Моделирование как метод решения прикладных задач по информатике

1.2 Основные термины теории графов

1.3 Методика решения задач моделирования с использованием графов в формате ЕГЭ по информатике

Глава 2. Реализация методики решения задач моделирования и теории графов в формате ЕГЭ по информатике

2.1 Поиск кратчайшего пути

2.2 Сравнение строковых данных

2.3 Кодирование и расшифровка информации

2.4 Поиск количества путей

2.5 Динамическое программирование

Заключение

Список использованной литературы



Введение

На сегодняшний день общество развивается в условиях информационной среды. Наиболее значимой ценностью, которая может быть у человека, представляется его способность находить, обрабатывать и представлять информацию в разнообразных видах и формах. Информационно-коммуникативные технологии неразрывнос современнойжизнедеятельности человечества, информатизация затрагивает все сферы жизни общества. С появлением компьютеров значительно облегчились некоторые виды труда.

Информатика в качестве отдельной учебной дисциплиныявляется благодатнойосновой для развитияглавных компетенций: информационной, коммуникационной, исследовательской. Информатика предоставляет возможность формирования основных универсальных учебных действий в процессе решения практических и прикладных задач.При изучении материала в курсе информатики школьникиприспосабливаются к восприятию актуальной ситуации в мире науки и технологии, учатся использовать главную материальную и духовную ценностью в настоящее время - информацию.

В настоящее время подготовка к сдаче выпускниками ЕГЭ по информатике осуществляется на основании модельного подхода, по конкретным блокам, одним из которых является «Моделирование». Задачам по данной теме отводится важное место в основном курсе, поскольку онинацелены на развитие умений и навыков владения информационно-коммуникационными технологиями. Такие задачи в большинстве случаев называют практическими заданиями, в связи с их объёмом и продолжительностью решения. Некоторые задачи на моделирование в среде текстового и графического редактора достаточно просты для выполнения, тогда какзадачи на моделирование в сфере электронных таблиц, графов и баз данных могут быть довольнотрудными и громоздкими, то обуславливает необходимость изучения алгоритма и методики их решений.

Цель исследования - проанализировать методику решения задач моделирования и теории графов в формате ЕГЭ по информатике.

Объект исследования -подготовка школьников к сдаче ЕГЭ по информатике.

Предмет исследования - методика решения задач моделирования и теории графов в формате ЕГЭ по информатике.

Исходя из цели, в работе были поставлены следующие задачи:

1. Рассмотреть моделирование как метод решения прикладных задач по информатике

2. Изучить основные термины теории графов

3. Определить методику решения задач моделирования с использованием графов в формате ЕГЭ по информатике

4. Представить реализацию методики решения задач моделирования и теории графов в формате ЕГЭ по информатике по темам: поиск кратчайшего пути; сравнение строковых данных; кодирование и расшифровка сообщений; поиск количества путей и динамическое программирование.

Теоретическая и практическая значимость исследования заключается в возможности использования полученного материала в педагогической практике работников образовательных учреждений нашей страны.

При проведении исследования были использованы следующие методы: библиографический метод, приемы абстрактно-аналитического осмысления, метод научного анализа, метод научного синтеза и обобщения.

Структура курсовой работы обусловлена целями и задачами исследования, логикой изложения материала и состоит из введения, двух глав, заключения, списка использованной литературы.



Глава 1. Теоретическая часть

1.1 Моделирование как метод решения прикладных задач по информатике

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

Модель является достаточно широким понятием, включающим в себя большое количество способов представления исследуемой реальности. Принято классифицировать модели материальные (натурные) и идеальные (абстрактные). Материальные модели базируются на чем-то объективном, существующем вне зависимости от человеческого сознания (каких-либо телах или процессах). Материальные модели классифицируют на физические (к примеру, авто- и авиамодели) и аналоговые, которые основаны на процессах, аналогичных в том ил ином отношении исследуемому (например, процессы в электрических цепях оказываются аналогичными большинству механических, химических, биологических и даже социальных процессов и могут быть применены для их моделирования). Границу между физическими и аналоговыми моделями провести можно достаточно приблизительно, и такая классификация моделей отличается условным характером[7].

Еще более сложную картину представляют идеальные модели, неразрывным образом связанные с человеческим мышлением, воображением, восприятием. Среди идеальных моделей необходимо выделить интуитивные модели, к которым принято относить, к примеру, произведения искусства - живопись, скульптура, литература, театр и т.д., однако единого подхода к классификации других видов идеальных моделей нет. В некоторых случаяхтакие модели все одновременно относят к информационным. В основе данного подхода заложена расширительнаяинтерпретация понятия «информация»: «информацией принято считатьпрактически все на свете, а может быть, даже вообще все». Данный подход представляетсянедостаточно оправданным, так как он переносит информационную природу познания на суть применяемых в процессе моделей - при этом любая модель выступает информационной. Более результативным представляется такой подход к классификации идеальных моделей, при котором классифицируют следующие[7].

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

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

3. Информационные модели - класс знаковых моделей, которые описывают информационные процессы (появление, передачу, преобразование и использование информации) в системах разнообразной природы.

Граница между вербальными, математическими и информационными моделями может быть проведена достаточно условно; вероятно, информационные модели целесообразно считать подклассом математических моделей. Однако, в рамках информатики в качестве самостоятельной науки, отдельной от математики, физики, лингвистики и иныхдисциплин, выделение класса информационных моделей является необходимым. Информатика имеет самое непосредственное отношение и к математическим моделям, поскольку они представляют собой основуиспользования компьютера при решении задач различной природы: математическая модель исследуемого процесса или явления на определенной стадии исследования преобразуется в компьютерную (вычислительную) модель, которая в дальнейшем превращается в алгоритм и компьютерную программу.

1.2 Основные термины теории графов

Декартовым произведением двух множеств A и B считается множество пар элементов, таких, что первый элемент пары выбирается из множества A, второй из B: A x B = {(a, b): a A, b B}[11].

К примеру, декартовым произведением множеств A ={0,1} и B = {a, b, c} выступает множество A x B = {(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)}.

Граф является парой G = (V, E), где V - множество вершин, E - множество ребер (дуг).

Граф представляется совокупностью конечного числа точек, которые называются вершинами графа, и попарно соединяющих часть из этих вершин линий, которые называютсяребрами или дугами графа[11].

Вершины графа принято обозначать латинскими буквами A, B, C, D или цифрами. В некоторых случаях граф в целом можно обозначать одной заглавной буквой.

Неупорядоченная пара вершин называется ребром, упорядоченная - дугой. Иными словами, отрезок между вершинами, имеющий направление, называют дугой. Направление обозначается стрелочкой на конце.

Отрезок между вершинами, не имеющий направления, называют ребром.

Благодаря применению графов можно упростить решение задач, которые сформулированы в разных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач[11].

Граф, которые содержат только дуги, называется ориентированным.

Ориентированным считается граф, в котором множество упорядоченных пар вершин вида (x, y), где x - называется началом, y - концом дуги. Дугу (x, y) часто записывают как и изображают в виде[11]:

Рис. 1. Изображение дуги (x, y) в ориентированном графе

Принято считать, что дуга ведет от вершины x к вершине y, а вершина y смежная с вершиной x. Ориентированный граф также получил название«орграф».

В некоторых случаях дугам графа приписывают определенное число (к примеру, расстояние между городами, время передачи данных между узлами), называемое весом. Тогда граф называют взвешенным орграфом. Этот вес может иметь разные единицы измерения, исходя из условия, по которому строится граф[11].

Граф, который содержит только ребра, называется неориентированным.

На практике граф применяется для задания симметрических отношений для объектов. Если над ребрами графа указать числовое значение, то получится взвешенный граф.

Вершины, которые соединены общим ребром, получили название«смежные вершины». Ребра, имеющие общую вершину, называются смежными ребрами.

Ребро и любая из двух вершин, с которыми связано данное ребро, называются инцидентными.

В неориентированном графе степенью вершины принято считатьчисло инцидентных с данной вершиной рёбер.

В орграфе полустепенью исхода вершины называется количество дуг, исходящих из неё; полустепенью захода -- количество дуг, заходящих в нее; степенью вершины -- сумма полустепеней исхода и захода.

Основоположником теории графов принято считать Леонарда Эйлера. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей в дальнейшем одной из классических задач теории графов[15].

В ходе рассуждений над данной задачей Эйлер сформулировал следующие свойства графов[15]:

· Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Не представляется возможным начертить граф, который имел бы нечётное число нечётных вершин.

· Если все вершины графа чётные, то можно, без отрыва карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.

· Граф с более чем двумя нечётными вершинами нельзя начертить одним росчерком.

1.3 Методика решения задач моделирования с использованием графов в формате ЕГЭ по информатике

Одним из разделов в ЕГЭ по информатике представляется «Моделирование и компьютерный эксперимент». Главное понятие в данном разделе - это модель. Модель является объект, который создается искусственно и позволяет создать упрощенное представление о действительном объекте, процессе или явлении, отражающий отличительные стороны изучаемого объекта с позиции цели моделирования. Следовательно, моделирование является процессом создания моделей, которые предназначены для изучения и исследования объектов, процессов или явлений.

В рамках данного раздела решаются следующие задания ЕГЭ по информатике[2]:

1. Задание 3 - Поиск кратчайшего пути.

2. Задание 4 - Сравнение строковых данных.

3. Задание 5 - Кодирование и расшифровка сообщений.

4. Задание 15 - Графы. Поиск количества путей.

5. Задание 22 - Динамическое программирование.

В процессе решения задач по информатике в сфере моделировании школьникам приходится сталкиваться с разнообразными видами информационных моделей, в том числе тех, которые целесообразно решать с помощью графов. Графы используются в различных областях, для каждой области используются определенные, которые имеют свою направленность, ограничения, а также дополнительные данные о вершинах и ребрах.

Графы можно представить с помощью различных способов[2]:

1) графический способ - изображение графа;

2) список ребер - перечисление всех ребер графа как пар обозначений, связываемых этими ребрами вершин;

3) матрица смежности - квадратная симметричная таблица, в которой столбцы и строки соответствуют вершинам графа, а на пересечении ячеек записываются числа, которые обозначают наличие или отсутствие связей между соответствующими парами вершин;

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

Таблица является систематизированным перечнем цифровых данных или каких-либо иных сведений, которые расположены в определенном порядке по графам.

Диаграмма представляется графически представлением данных. Они применяются для анализа и сравнения данных, представления их в наглядном виде.

Принято классифицировать различные виды диаграмм[2]:

1) гистограмма - графическое представление в форме прямоугольников одинаковой ширины, которые расположены вертикально, одиночные прямоугольники,или сгруппированные по конкретному признаку. Используются для распределения числовых значений определенного показателя во времени или по составным частям;

2) линейчатые диаграммы - графическое представление в форме прямоугольников, которые расположены горизонтально. Высота прямоугольников соответствует числовым значениям сравниваемых величин;

3) круговая диаграмма - графическое представление в формеокружности, круга. Используется для изображения удельного веса составных частей какого-либо целого (в долях или процентах).

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

Значимость данной задачи определяется её различными практическими применениями. Например, в GPS-навигаторах, где осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Сумма расстояний всех дорог между перекрестками должна быть минимальной, тогда найден самый короткий путь.

Если, в рамках задачи, в ориентированном графе нет циклов, то можно провести топологическую сортировку вершин, после чего выполнить релаксацию исходящих дуг в порядке возрастания номеров вершин.

Проанализируем особенности решения типовой задачи по моделированию, представленной в ЕГЭ[3].

Условие:

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

Рис. 2.Таблица смежности для решения задачи по моделированию

Методика решения:

1. Поскольку в условии задачи представлена таблица смежности, определяется, что это задача на построение графа. Далее определяется, что вершинами графа выступают названия городов, от A до F, а ребра определяются наличием в таблице чисел, которые указывают вес этих ребер. Расставляются вершины и соединяются линиями только те, на пересечении столбца и строки которых имеются непустые ячейки. Число, в соответствующих ячейках, записывается над ребрами.

2. Определяется, что раз в условии задачи не сказано, что движение в одном направлении, следовательно, граф не является ориентированным. Матрица смежности зеркально симметрична (т.е. ячейки над главной диагональю и под симметричны).

3. Далее строится граф для данной таблицы смежности:

Рис. 3. Построение графа для задачи по моделированию

4. Методом перебора перечислятся все допустимые пути от A к F и определяется самый короткий путь.

AF - длина пути: 24;

ABCDF - длина пути: 4+3+3+8=18;

ABCF - длина пути: 4+3+14=21;

ABCEF - длина пути: 4+3+7+6=20;

ACDF - длина пути: 10+3+8=21;

ACF -длина пути: 10+14=24;

ACEF -длина пути: 10+7+6+23.

Самый короткий путь ­ ABCDF длиной 18 единиц.

На основании представленного алгоритма, решаются все аналогичные задачи по моделированию.



Глава 2. Реализация методики решения задач моделирования и теории графов в формате ЕГЭ по информатике

2.1 Поиск кратчайшего пути

Тема - Построение простого графа по таблице или построение таблицы по графу.

Задание 3 в ЕГЭ. Базовый уровень, время выполнения - 3 минуты.

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

1. В заданиях ЕГЭ по теме «Поиск кратчайшего пути»в большинстве случаевприменяются две информационные модели - таблицы и схемы.

2. Информация в таблице выстраиваетсяпри соблюдении следующих правил: на пересечении строки и столбца размещается информация, которая характеризует комбинацию данной строки и столбца.

3. На схеме информация выстраиваетсяпри соблюдении следующего правила: если между объектами схемы существует связь, то она должна быть отображена линией, которая соединяетнаименованияданных объектов на схеме. моделирование граф кодирование программирование

Пример задания[10]:

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

Таблица 1. Условие задания - таблица

	П1	П2	П3	П4	П5	П6	П7
П1			30		25		18
П2			17	12
П3	30	17		23		34	15
П4		12	23			46
П5	25						37
П6			34	46			18
П7	18		15		37	18

Рис. 4 Условие задания - граф

Методика решения.

1. Определим степени вершин по весовой матрице и по изображению графа: П1 - 3;П2 - 2;П3 - 5;П4 - 3;П5 - 2;П6 - 3;П7 - 4 (таблица 1).

2. По изображению графа на рис. 4определяем, что обе интересующих нас вершины, А и Д, имеют степени 3; кроме того, степень 3 имеет еще и вершина Г.

3. В таблице 1также есть три вершины со степенью 3 (это П1, П4 и П6), но вершина П1 (это вершина Г на рисунке 3) не имеет общих ребёр с вершинами П4 и П6 (а это А и Д).

4. Таким образом, ответ представлен длиной ребра между вершинами П4 и П6 (эти ячейки выделены в весовой матрице в таблице 1синим фоном).

5. Следовательно, ответ - 46.

2.2 Сравнение строковых данных

Тема - Построение графа при работе с базой данных.

Задание 4 в ЕГЭ. Базовый уровень, время выполнения - 3 минуты.

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

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

Пример задания[5]:

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

Таблица 2 Условие задания

ID	Фамилии ИО	Пол	ID родителя	ID ребенка
2146	Кривич Л.П.	Ж	2146	2302
2155	Павленко А.К.	М	2146	3002
2431	Хитрук П.А.	М	2155	2302
2480	Кривич А.А.	М	2155	3002
2302	Павленко Е.А.	Ж	2302	2431
2500	Сокол Н.А.	Ж	2302	2511
3002	Павленко И.А.	М	2302	3193
2523	Павленко Т.Х.	Ж	3002	2586
2529	Хитрук А.П	М	3002	2570
2570	Павленко П.И.	М	2523	2586
2586	Павленко Т.И.	Ж	2523	2570
2933	Симонян А.А.	Ж	2529	2431
2511	Сокол В.А.	Ж	2529	2511
3193	Биба С.А.	Ж

Решение:

1. Изначально находим в таблице 2 Павленко А.К. (Id = 2155)

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

Рис. 5 Генеалогическое древо 1 (дети Павленко А.К.)

3. После этого так же определяем внуков 2155, то есть, детей 2302 и 3002 (рис. 6).

Рис. 6 Генеалогическое древо 1 (внуки Павленко А.К.)

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

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

6. Окончательный ответ: 7.



2.3 Кодирование и расшифровка информации

Тема - Граф и коды.

Задание 5 в ЕГЭ. Базовый уровень, время выполнения - 3 минуты.

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

1. Декодирование (расшифровка) является процессом восстановления сообщения из некоторой последовательности кодов.

2. С целью решения задач с декодированием,важно знать условие Фано: ни одно кодовое слово не должно выступать началом другого кодового слова (что способствует обеспечению однозначного декодирования сообщений с начала).Префиксный код является кодом, в котором ни одно кодовое слово не совпадает с началом второго кодового слова. Сообщения при примененииданного кода декодируются однозначно.

Пример задания[6]:

По каналу связи передаются сообщения, содержащие только 4 буквы П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.

Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение:

1. Условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков;

2. Построим дерево для заданных кодовых слов О - 0, Т - 111 и П - 100: (рис. 7).



Рис. 7 Дерево для заданных кодовых слов

3. Из рис. 7 видно, что штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» лист для кодового слова буквы С: 101 или 110; из них минимальное значение имеет код 101

4. Таким образом, выбрав кодовые слова А - 0, Б - 110, В - 10, Г - 111, получаем суммарную длину кодовых слов 9 символов. Ответ: 101

2.4 Поиск количества путей

Тема - Поиск кратчайшего пути в ориентированном графе

Задание 15 в ЕГЭ. Базовый уровень, время выполнения - 5минут.

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

1. Если в город R из города A можно добраться исключительно из населенных пунктов X, Y и Z, то число разных путей из пункта A в пункт R равно сумме количества различных путей проезда из A в X, из A в Y и из A в Z, иными словами:

NR = NX + NY + NZ

где NR является числом путей из вершины A в вершину R.

2. Количество путей не бесконечно, исключением выступает только граф, в котором присутствуют циклы - замкнутые пути.

3. Нередко задачи с графами эффективнее решать с конца.

Пример задания[9]:

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

Рис. 8 Граф по условию задания

Решение.

1. На основании рис. 8 можно сделать вывод, что ответ - 4.

Пример задания[9]:

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

Рис. 9 Граф по условию задания



Решение.

1. На основании рис. 9 можно сделать вывод, что ответ - 96.

2.5 Динамическое программирование

Тема - Граф или таблица

Задание 22 в ЕГЭ. Продвинутый уровень, время выполнения - 7минут.

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

1. Динамическое программирование является способом или техникой решения сложных задач посредством приведения их к более простым подзадачам аналогичного типа.

2. Динамическое программирование облегчает решение задач, которые требуют полного перебора вариантов. Задание может иметь следующую формулировку:

«подсчитайте число способов…»;

«как оптимально распределить…»;

«выберите оптимальный маршрут…».

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

Пример задания[14]:

Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 - это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10? Траектория вычислений программы - это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение.

1. Построим граф с учетом вышеприведенных условий (рис. 10).

Рис. 10 Граф по заданным условиям

При заданных условиях нецелесообразно решать задачу графом, так как количество решений может быть большое и граф будет очень большим.

2. Отметим, что при выполнении любой из команд число увеличивается (не может уменьшаться). Для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через KNобозначить количество разных программ для получения числа N из начального числа 1, то K1 = 1.

3. Далее рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательностиK1, K2, ……. Kn-1, то есть с решениями таких же задач для меньших N, KN

4. Число N могло быть получено одной из двух операций:

- увеличением на 1 числа N-1;

- умножением на 2 числа N/2 (только для N, которые делятся на 2);

- для нечётных чисел

- для чётных чисел

5. Поскольку траектория должна проходить через число 10, сначала выясняем, сколькими способами можно получить 10 из 1, а затем будем считать, сколько есть способов получить 21 из 10.

6. Заполняем таблицу от 1 до 10 по полученным формулам:

KN= Kn-1

KN= Kn-1 +Kn/2

Второй этап - определяем таким же образом (и по таким же формулам), сколько есть способов получить конечное число 21 из 10, только верхние строки таблицы (от 1 до 10) мы уже не рассматриваем.

Таблица 3 Решение задачи на динамическое программирование

N	1	2	3	4	5	6	7	8	9	10
KN	1	2	2	4	4	6	6	10	10	14
N	10	11	12	13	14	15	16	17	18	19	20	21
KN	14	14	14	14	14	14	14	14	14	14	28	28

7. Ответ: 28.

1. При решении задач в рамках ЕГЭ по информатике целесообразно использовать как графы, так и таблицы. И таблицы, и графы являются важнейшими способами решения как задач по моделированию, так и различныхситуаций обычной повседневной жизни.

2. С помощью таблиц решаются задачи на истинность и ложность высказываний - таблицы истинности. Логические уравнения и системы можно решить с помощью графа. При этом, графы и таблицы являютсявзаимосвязанными моделями, что необходимо учитывать при подготовке школьников к сдаче ЕГЭ по информатике.



Заключение

Подготовка к сдаче единого государственного экзамена по информатике представляется трудоемким процессом, который требует от педагога владения серьезной теоретической базой и практическими навыками выбора заданий, созданиянаиболее эффективной схемы решения заданий и пр.

Структура ЕГЭ в настоящее времястроится таком образом, что оцениваются умения выпускникарешать задания на все виды деятельности, а также проверяется уровень владения знаниями всех тематических разделов школьного курса. Следовательно, проблемы в изучении той или иной темы значительно снизят итоговый балл, что может стать причиной неконкурентоспособности будущего абитуриента.

Структура ЕГЭ также выстроена таким образом, что осуществлять подготовку к сдаче экзамена наиболее целесообразно отдельно по каждому блоку тем, иными словами,используя модульный подход. При изучении каждого блока важнодетально разработать системы уроков, с целью эффективного усвоения материала по каждой теме. Также рекомендуется ранжировать задания по уровням трудности и по исследуемым видам деятельности, чтобы школьники могли привыкнуть к действительной структуре ЕГЭ.

В ходе подготовки по каждому разделу, должны определяться существующие трудности в знании, понимании, умении использовать знания для решения определенной задачи у всех школьников, осуществляющих подготовку к сдаче экзамена ЕГЭ.



Список использованной литературы

1. Горячев А.В. Практикум по информационным технологиям. - М.: Бином, 2016. - 272 c.

2. Демина О.А. Экзамен по информатике. - М.: Приор, 2015. - 176 c.

3. Зорина Е.М. ЕГЭ 2019. Информатика. Сборник заданий: 350 заданий с ответами. -- М.: Эксмо, 2018.-420 с.

4. Информатика. Федеральный банк экзаменационных материалов/ Под редакцией П.А. Якушкина, С.С. Крылова. - М.: Эксмо, 2013. - 513 с.

5. Крылов С.С., Чуркина Т.Е. ЕГЭ-2018. Информатика и ИКТ. Типовые экзаменационные варианты. 20 вариантов - М.: Национальное образование, 2017. - 125 с.

6. Лещинер В.Р. ЕГЭ 2018. Информатика. Типовые тестовые задания. -- М.: Экзамен, 2017. - 154 с.

7. Ляхович В.Ф. Информатика 10-11 класс. - М.: Просвещение, 2015. - 352 c.

8. Молодцов В.А. Информатика: тесты, задания, лучшие методики. - Ростов-на-Дону: Феникс, 2013. - 200 с.

9. Ройтберг М.А., Зайдельман Я.Н. Информатика и ИКТ. Подготовка к ЕГЭ в 2018 году. Диагностические работы. - М.: МЦНМО, 2017. - 294 с.

10. Самылкина Н.Н., Синицкая И.В., Соболева В.В. ЕГЭ 2019. Информатика. Задания, ответы, комментарии. - М.: Эксмо, 2018. - 96 с.

11. Семакин И.Г., Шеина Т.Ю. Преподавание базового курса информатики в средней и старшей школе. Методическое пособие. - М.: Бином, 2011. - 365 с.

12. Софронова Н.В. Теория и методика обучения информатике. - М.: Высшая школа, 2014. - 453 с.

13. Угринович Н. Информатика и информационные технологии. - М.: Бином. Лаборатория знаний, 2017. - 512 c.

14. Ушаков Д.М. ЕГЭ-2019. Информатика. 10 тренировочных вариантов экзаменационных работ для подготовки к ЕГЭ. - М.: АСТ, 2018. - 88 с.

15. Шестакова Л.В. Информатика и информационно-коммуникационные технологии. Базовый курс. 10-11 класс. - М.: Бином, 2017. - 176 c.

Размещено на Allbest.ru

...