Характеристика базовых алгоритмов, применяемых при сдаче ЕГЭ по информатике и ИКТ

Введение 2
1. Краткое описание алгоритмов, применяемых при решении задач ЕГЭ по информатике 4
2. Практические аспекты программирования задач, предлагаемых для решения с применением языка Pascal ABC. Net 14
3. Рекомендации по подготовке абитуриентов для успешного решения задач ЕГЭ по информатике 19
Заключение 38
Список использованных источников 39

Весь текст будет доступен после покупки

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

Весь текст будет доступен после покупки

По сравнению с 2022 годом, в 2023 году появилась новая формулировка задачи под номером 22, приведенная ниже.
Постановка задачи: Имеется информация о совокупности N вычислительных процессов, которые могут выполняться последовательно или параллельно. Считается, что процесс B зависит от процесса A, в случае если для выполнения процесса B необходимы результаты выполнения процесса A. В данном случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В 1 столбце введен идентификатор процесса (ID), во 2 столбце– t его выполнения в миллисекундах, в 3 столбце приводятся с разделителем «;» ID процессов, от которых зависит текущий процесс.
Если процесс является независимый, то в таблице вводится 0.

Требуется определить min время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. Эта таблица является перечнем смежности графа – структурой данных, где каждой вершине графа подходит строка со списком смежных вершин.
Задача решается с помощью теории графов, при этом вершинами которого будут ID процессов из первого столбца «ID процесса B», а рёбрами – связи процессов, заданные столбцами «ID процесса A» и «ID процесса B». Поскольку для выполнения процесса B иногда необходимы результаты выполнения процесса А, рёбра графа будут дугами (в теории графов ребро, имеющее направление, называется ориентированным ребром или дугой), а сам граф – ориентированным графом или орграфом. В столбце «ID процесса(ов) A» содержатся номера вершин графа, являющихся началом дуги, в столбце «ID процесса B» задан конец для каждой дуги (рис. 1).

Процессы с ID 1, 2, 9, 10 – независимые, не имеют предшествующих процессов и поэтому отображаются на графе как корневые вершины. Процесс № 3 может начаться только по окончании выполнения процессов № 1 и 2, поэтому на графе отображены дуги P1 > P3, P2 > P3. Процессы № 4 и 5 зависят от результатов работы процесса № 3, чему соответствуют дуги P3 > P4 и P3 > P5. Для решения задачи следует изменить форму представления информации с табличной на графическую, данные о дугах для вершин P1, P2, P3, P4, P5 получены из следующих строк таблицы: Обозначим рядом с каждой вершиной графа время выполнения процесса из второго столбца таблицы «Время выполнения процесса B (мс)» – вес вершины. Получим граф со взвешенными вершинами (рис. 2).

Весь текст будет доступен после покупки

1.Ахо А. В., Хопкрофт Д., Ульман Д. Д. Структуры данных и алгоритмы: пер. с англ. М.: Вильямс, 2000. 384 с.
2. Беллман Р. Динамическое программирование: пер. с англ. М.: Издательство иностранной литературы, 1960 - 400 с.
3. Варианты ЕГЭ досрочного периода 2020 года. Информатика и ИКТ. http://doc.fipi.ru/o-nas/novosti/varianty-yege-dosrochnogo-perioda-2020-goda/informatika-i-ikt.zip
4. Демоверсии, спецификации, кодификаторы ЕГЭ. https://fipi.ru/ege/demoversii-specifikacii-kodifikatory

Весь текст будет доступен после покупки