РусҚаз

Айналамыздағы графтар

Информатика · 10-сынып · Графтар және жол іздеу · Сабақ 4 / 4

Интерактивті сабақты ашу ›Өз қолыңмен тәжірибе, дауыспен дәріс, ЖИ-тәлімгер және тест. Тегін.

Бұл не?

Сабақтың тақырыбы — «Айналамыздағы графтар». Талдап көрейік. Телефоныңдағы навигаторды аш — оның ішінде бүкіл қала граф ретінде сақталған: қиылыстар — төбелер, көшелер — қабырғалар, ал салмақ — кептелістерді ескергендегі жолдағы уақыт. Графтар айналамызда барлық жерде: интернетте, әлеуметтік желілерде, іздеу жүйелерінде, тіпті жасанды интеллект көмекшілерінде де.

Айналамыздағы графтар — Бұл не?

Бұл не үшін керек?

Интернет маршрутизаторлары деректер пакеттері үшін ең қысқа жолдарды есептейді, әлеуметтік желілер достардың достарын ұсынады, ал тілдік модельдерді жасанды интеллект фактілер арасындағы тексерілген байланыстарға сүйенуі үшін білім графтарына қосады. Ұшқышсыз аппараттар, жеткізу роботтары мен энергия желілері де графтармен ойлайды. Жасанды интеллект неғұрлым көп жұмысты өз мойнына алса, алгоритм қандай тапсырманы шешетінін түсінетін, сай келетінін таңдайтын және нәтиженің алдамайтынын тексеретін адам соғұрлым маңызды. Өмірден графты көре біліп, оған дұрыс құрал таңдау — орындаушының емес, жобалаушының дағдысы.

Айналамыздағы графтар — Бұл не үшін керек?

Бұл қалай жұмыс істейді?

Әлі сенің досың емес достардың достары — сенен екі қашықтықтағы төбелер, оларды кәдімгі ені бойынша аралау табады. Іздеу жүйелері беттердің маңыздылығын қарапайым идея бойынша бағалаған: егер бетке маңызды беттер сілтесе, ол маңызды. Білім графы фактілерді байланыстырады, мысалы «Мария Кюри — алды — Нобель сыйлығын». Ал алгоритмді тапсырмаға қарай таңдайды: ауысып отырулар саны маңызды болса — ені бойынша аралау, уақыт немесе баға маңызды болса — Дейкстра алгоритмі.

Айналамыздағы графтар — Бұл қалай жұмыс істейді?

Аздап тарих

Беттерді сілтемелер бойынша бағалау идеясын ПейджРанк деп атады. Оны Стэнфорд университетінің аспиранттары Ларри Пейдж бен Сергей Брин қарқынды өсіп келе жатқан интернетте тәртіп орнатудың жолын іздеп жүргенде ойлап тапты. Осы студенттік жобадан Гугл іздеу жүйесі өсіп шықты, және оның алғашқы бүкіл күші сілтемелер графы туралы бір ғана ойға сүйенді.

Айналамыздағы графтар — Аздап тарих

Практикада не істейміз?

Ал енді практикалық тапсырманы орындап көрейік. Қазір экранда сенің графыңның басы тұр: A-дан D-ға дейінгі төрт төбе және салмақтары бар үш қабырға, бастау A-да, мәре D-да, «құру» режимі қосулы. Графты кемінде алты төбе мен жеті қабырғаға дейін толықтыр да, салмақтарды бастаудан мәреге дейінгі Дейкстра маршрутында ені бойынша аралау жолынан көбірек қабырға болатындай етіп таңда. Қабырғалар саны бойынша қысқа жолды өте қымбат, ал ұзын айналма жолды арзан қалай етуге болатынын ойлан. Содан кейін екі алгоритмді де іске қосып, маршруттарды салыстыр. Бірдеңе түсініксіз болып қалса — ештеңе етпейді, менен кез келген нәрсені сұра, жауап беремін. Уайымдама.

Тәжірибедегі тапсырма

Өз графыңызды құрыңыз: кемінде 6 төбе және 7 қабырға. Дейкстраның старттан мәреге дейінгі маршрутында BFS жолына қарағанда қабырғалар көп болатындай салмақтарды таңдап, екі алгоритмді де іске қосыңыз.
Интерактивті сабақты ашу ›Өз қолыңмен тәжірибе, дауыспен дәріс, ЖИ-тәлімгер және тест. Тегін.

Тақырып сабақтары: Графтар және жол іздеу

  1. Граф деген не
  2. Ені бойынша аралау
  3. Дейкстра алгоритмі
  4. Айналамыздағы графтар