Количество путей в графе — ОГЭ по информатике

Каталог заданий ОГЭ

Выберите раздел или тему для подготовки.

Типы задач

Учебные подборки по навыкам из каталога «Решу ОГЭ», включая дополнительные задания.

Объём текста и кодировки · 1 79 Кодирование и декодирование · 2 77 Логические выражения · 3 85 Кратчайший путь по таблице дорог · 4 91 Команды числового исполнителя · 5, Д13 103 Анализ программы с ветвлением · 6 77 Адреса файлов в Интернете · 7 79 Поисковые запросы и множества · 8 80 Количество путей в графе · 9 85 Системы счисления · 10, Д12, Д19 150 Поиск в текстах и документах · 11 66 Поиск и подсчёт файлов · 12 160 Презентации и текстовые документы · 13 120 Обработка данных в таблицах · 14 86 Алгоритмы для Робота · 15 77 Написание программы · 16 170

Темы информатики

1. Цифровая грамотность385

Все задания раздела 385 1.1 Файлы и папки (каталоги). Принципы построения файловых систем. Полное имя файла (папки). Путь к файлу (папке). Работа с файлами и каталогами средствами операционной системы: создание, копирование, перемещение, переименование и удаление файлов и папок (каталогов). Типы файлов. Свойства файлов. Файловый менеджер. Поиск файлов средствами операционной системы 226 1.2 Объединение компьютеров в сеть. Сеть Интернет. Веб-страница, веб-сайт. Структура адресов веб-ресурсов. Браузер. Поисковые системы. Поиск информации по ключевым словам и по изображению. Достоверность информации, полученной из Интернета. IP-адреса узлов. Сетевое хранение данных 159

2. Теоретические основы информатики567

Все задания раздела 567 2.1 Дискретность данных. Возможность описания непрерывных объектов и процессов с помощью дискретных данных. Символ. Алфавит. Мощность алфавита. Двоичный алфавит. Количество всевозможных слов (кодовых комбинаций) фиксированной длины в двоичном алфавите. Преобразование любого алфавита к двоичному. Количество различных слов фиксированной длины в алфавите определённой мощности. Кодирование символов одного алфавита с помощью кодовых слов в другом алфавите, кодовая таблица, декодирование. Кодирование текстов. Равномерный код. Неравномерный код. Кодировка ASCII. Восьмибитные кодировки. Понятие о кодировках UNICODE. Декодирование сообщений с использованием равномерного и неравномерного кода. Информационный объём текста 156 2.2 Информационный объём данных. Бит – минимальная единица количества информации – двоичный разряд. Единицы измерения информационного объёма данных. Бит, байт, килобайт, мегабайт, гигабайт. Скорость передачи данных. Единицы скорости передачи данных 792.3 Кодирование цвета. Цветовые модели. Модель RGB. Глубина кодирования. Палитра. Растровое и векторное представление изображений. Пиксель. Оценка информационного объёма графических данных для растрового изображения 02.4 Кодирование звука. Разрядность и частота записи. Количество каналов записи. Оценка количественных параметров, связанных с представлением и хранением звуковых файлов 02.5 Непозиционные и позиционные системы счисления. Алфавит. Основание. Развёрнутая форма записи числа. Перевод в десятичную систему чисел, записанных в других системах счисления. Римская система счисления 02.6 Двоичная система счисления. Перевод целых чисел в пределах от 0 до 1024 в двоичную систему счисления. Восьмеричная система счисления. Перевод чисел из восьмеричной системы в двоичную и десятичную системы и обратно. Шестнадцатеричная система счисления. Перевод чисел из шестнадцатеричной системы в двоичную, восьмеричную и десятичную системы и обратно. Арифметические операции в двоичной системе счисления 150 2.7 Логические высказывания. Логические значения высказываний. Элементарные и составные высказывания. Логические операции: «и» (конъюнкция, логическое умножение), «или» (дизъюнкция, логическое сложение), «не» (логическое отрицание). Приоритет логических операций. Определение истинности составного высказывания, если известны значения истинности входящих в него элементарных высказываний. Логические выражения. Правила записи логических выражений. Построение таблиц истинности логических выражений 852.8 Логические элементы. Знакомство с логическими основами компьютера 02.9 Непрерывные и дискретные модели. Имитационные модели. Игровые модели. Оценка адекватности модели моделируемому объекту и целям моделирования 02.10 Табличные модели. Таблица как представление отношения. Базы данных. Отбор в таблице строк, удовлетворяющих заданному условию 02.11 Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра. Весовая матрица графа. Длина пути между вершинами графа. Поиск оптимального пути в графе. Начальная вершина (источник) и конечная вершина (сток) в ориентированном графе. Вычисление количества путей в направленном ациклическом графе 1762.12 Дерево. Корень, вершина (узел), лист, ребро (дуга) дерева. Высота дерева. Поддерево. Примеры использования деревьев. Перебор вариантов с помощью дерева 0

3. Алгоритмы и программирование427

Все задания раздела 427 3.1 Свойства алгоритма. Способы записи алгоритма (словесный, в виде блок-схемы, программа). Составление алгоритмов и программ с использованием ветвлений, циклов и вспомогательных алгоритмов для управления исполнителем Робот или другими исполнителями, такими как Черепашка, Чертёжник и другими. Выполнение алгоритмов вручную и на компьютере 77 3.2 Язык программирования (Python, C++, Паскаль, Java, C#, Школьный Алгоритмический Язык). Система программирования: редактор текста программ, транслятор, отладчик. Переменная: тип, имя, значение. Целые, вещественные и символьные переменные. Оператор присваивания. Арифметические выражения и порядок их вычисления. Операции с целыми числами: целочисленное деление, остаток от деления. Ветвления. Составные условия (запись логических выражений на изучаемом языке программирования). Нахождение минимума и максимума из двух, трёх и четырёх чисел. Решение квадратного уравнения, имеющего вещественные корни. Цикл с условием. Алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел. Разбиение записи натурального числа в позиционной системе с основанием, меньшим или равным 10, на отдельные цифры. Цикл с переменной. Алгоритмы проверки делимости одного целого числа на другое, проверки натурального числа на простоту 783.3 Обработка символьных данных. Символьные (строковые) переменные. Посимвольная обработка строк. Подсчёт частоты появления символа в строке. Встроенные функции для обработки строк 03.4 Определение возможных результатов работы алгоритма при данном множестве входных данных, определение возможных входных данных, приводящих к данному результату 103 3.5 Табличные величины (массивы). Одномерные массивы. Составление и отладка программ, реализующих типовые алгоритмы обработки одномерных числовых массивов, на одном из языков программирования (Python, C++, Паскаль, Java, C#, Школьный Алгоритмический Язык): заполнение числового массива случайными числами, в соответствии с формулой или путём ввода чисел, нахождение суммы элементов массива, линейный поиск заданного значения в массиве, подсчёт элементов массива, удовлетворяющих заданному условию, нахождение минимального (максимального) элемента массива. Сортировка массива. Обработка потока данных: вычисление количества, суммы, среднего арифметического, минимального и максимального значения элементов последовательности, удовлетворяющих заданному условию 1693.6 Управление. Сигнал. Обратная связь. Получение сигналов от цифровых датчиков (касания, расстояния, света, звука и другого). Примеры использования принципа обратной связи в системах управления техническими устройствами с помощью датчиков, в том числе в робототехнике 0

4. Информационные технологии206

Все задания раздела 206 4.1 Текстовые документы и их структурные элементы (страница, абзац, строка, слово, символ). Текстовый процессор – инструмент создания, редактирования и форматирования текстов. Правила набора текста. Редактирование текста. Свойства символов. Шрифт. Типы шрифтов (рубленые, с засечками, моноширинные). Полужирное и курсивное начертание. Свойства абзацев: границы, абзацный отступ, интервал, выравнивание. Параметры страницы. Стилевое форматирование. Структурирование информации с помощью списков и таблиц. Многоуровневые списки. Добавление таблиц в текстовые документы. Вставка изображений в текстовые документы. Обтекание изображений текстом. Включение в текстовый документ диаграмм, формул, нумерации страниц, колонтитулов, ссылок и других элементов 614.2 Растровые рисунки. Использование графических примитивов. Операции редактирования графических объектов, в том числе цифровых фотографий: изменение размера, обрезка, поворот, отражение, работа с областями (выделение, копирование, заливка цветом), коррекция цвета, яркости и контрастности. Векторная графика. Создание векторных рисунков встроенными средствами текстового процессора или других программ (приложений). Добавление векторных рисунков в документы 04.3 Подготовка мультимедийных презентаций. Слайд. Добавление на слайд текста и изображений. Работа с несколькими слайдами. Добавление на слайд аудиовизуальных данных. Анимация. Гиперссылки 594.4 Типы данных в ячейках электронной таблицы. Редактирование и форматирование таблиц. Встроенные функции для поиска максимума, минимума, суммы и среднего арифметического. Сортировка данных в выделенном диапазоне. Построение диаграмм (гистограмма, круговая диаграмма, точечная диаграмма). Выбор типа диаграммы. Преобразование формул при копировании. Относительная, абсолютная и смешанная адресация 04.5 Условные вычисления в электронных таблицах. Суммирование и подсчёт значений, отвечающих заданному условию. Обработка больших наборов данных. Численное моделирование в электронных таблицах 86

Количество путей в графе — ОГЭ по информатике — страница 8

Каталог заданий ОГЭ

Типы задач

Темы информатики

Есть вопрос по подготовке?

Обращение принято