Тема 9 · Информатика
Графы, деревья и файловая система
Кратчайшие пути и подсчёт маршрутов, таблицы дорог, дерево каталогов, полное имя файла, маски. 100 заданий на отработку.
Простыми словами
Карта дорог между городами, схема метро, друзья в соцсети — всё это графы: точки и линии между ними. А папки на диске устроены как особый граф — дерево.
Вершины соединены рёбрами; во взвешенном графе у ребра есть число (длина дороги). В ориентированном графе рёбра — стрелки (дороги с односторонним движением). Степень вершины — число рёбер, выходящих из неё. Граф связный, если между любыми двумя вершинами есть путь. Связный граф без циклов — дерево: при вершинах в нём ровно ребро.
Кратчайший путь
Метод: идём от начала и пишем у каждой вершины наименьшую найденную сумму длин; если нашёлся путь короче — исправляем число.
- B: . C: напрямую , через B — берём .
- D: через B . E: через C . D через E: — оставляем .
- F: через D , через E . Ответ: .
Прямая дорога не всегда короче: A–C длиной 5 проигрывает пути A–B–C длиной 4. Проверяйте все обходы.
Таблица дорог (весовая матрица) задаёт тот же граф: число на пересечении строки и столбца — длина прямой дороги, пустая клетка — дороги нет. Таблица симметрична. По ней сначала рисуют схему, потом ищут путь. Степень вершины по таблице — число заполненных клеток (или «+») в её строке.
Количество путей
В графе со стрелками идём от начала: у A ставим 1, у каждой следующей вершины — сумму чисел всех вершин, из которых в неё входят стрелки.
Считайте вершины в таком порядке, чтобы к моменту подсчёта все «входящие» уже были посчитаны.
Дерево каталогов и маски
Полное имя файла = путь от корневого каталога через все вложенные папки + имя файла с расширением: C:\Школа\Рефераты\referat3.bmp. Файл «непосредственно находится» в той папке, которая стоит в пути последней.
C:\История\Физика\shema8.odt — файл лежит непосредственно в папке «Физика»| Символ маски | Что заменяет |
|---|---|
* | любую последовательность символов, в том числе пустую |
? | ровно один произвольный символ |
Маска p?an.*: имя из 4 букв, первая p, вторая любая, затем «an»; расширение любое. Подходит plan.pptx, не подходит pan.doc (нет символа под ?) и plans.txt (лишняя буква).
Звёздочка стоит только в расширении — значит, имя должно совпасть с шаблоном точно по длине.
Дерево: термины
Дерево — связный граф без циклов. В дереве с вершинами рёбер. Вершина без потомков называется листом; верхняя вершина дерева каталогов — корень (диск, например C:\).
Где это пригодится: ОГЭ — 4 заданияЗадания экзамена 9 класса, которые опираются на этот материал — нажмите, чтобы раскрыть список
Готовые работы по теме
Собраны заранее — одним нажатием: распечатать с ключом, раздать ученикам ссылкой или QR-кодом, поменять настройки. Номер набора постоянный: по этой ссылке всегда та же работа.
теория этой темы, 8 заданий по подтемам и ключ — файлом DOCX, который можно править под себя.
Прохождение онлайн
Имя ученика никуда не отправляется: он вводит только номер по списку, а таблицу «номер → фамилия» видите только вы.
Классы, выданные работы и результаты учеников по кодам — в журнале учителя: без регистрации, хранится только на этом компьютере.