Алгоритмы поиска данных (10 класс)

1.

АЛГОРИТМЫ ПОИСКА ДАННЫХ
Теоретические основы информатики
Информатика
10 класс
Углубленный
уровень

2.

ПОИСК
ИНФОРМАЦИИ:
Поиск
- процесс,
в ходе которого в тойОСНОВНЫЕ
или иной
последовательности производится соотнесение
ПОНЯТИЯ,
ВИДЫ
И ФОРМЫ
ОРГАНИЗАЦИИ
отыскиваемого
с каждым
объектом, хранящимся
в массиве.
Цель любого поиска заключается в потребности,
необходимости или желании находить различные виды
информации, способствующие получению лицом,
осуществляющим поиск, нужных ему сведений, знаний и т.д.
для повышения собственного профессионального,
культ урного и любого иного уровня; создания новой
информации и формирования новых знаний; принятия
управленческих решений и т.п.

3.

ПОИСК ДАННЫХ

4.

АТРИБУ ТЫ ПОИСКА
Набор данных – совокупность данных, среди
которых осуществляется поиск.
Состоит из записей, состоящих из полей.

5.

АТРИБУ ТЫ ПОИСКА
Ключ поиска– поле записи, по значению
которого осуществляется поиск.

6.

АТРИБУ ТЫ ПОИСКА
Критерий поиска– условие, которому должно
удовлетворять значение ключа поиска в
искомой записи.

7.

ОРГАНИЗАЦИЯ НАБОРА ДАННЫХ
Набор данных
Неупорядоченные
данные
Структура данных

8.

" Релевантность" -
устанавливаемое
при информационном
поиске соответствие
содержания
документа информаци
онному запросу или
поискового образа
документа поисковому
предписанию.

9.

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

10.

Методы поиска, т.е. выделение подмножества
документов, потенциально содержащих
описание решения задачи отбора документов
(ОД), являются отражением процесса
нахождения решения и зависят от характера
задачи и предметной области.
Стратегии поиска и могут быть разделены на
следующие классы - методы поиска в:
1) одном пространстве (обычно, тематическом);
2) иерархически упорядоченном пространстве;
3) альтернативных пространствах;
4) динамическом (изменяющемся в процессе
поиска) пространстве.

11.

ОДНОМ ПРОСТРАНСТВЕ
(ОБЫЧНО, ТЕМАТИЧЕСКОМ)

12.

ИЕРАРХИЧЕСКИ УПОРЯДОЧЕННОМ
ПРОСТРАНСТВЕ

13.

14.

ДИНАМИЧЕСКИЕ (ИЗМЕНЯЮЩЕЕСЯ
В ПРОЦЕССЕ ПОИСКА)

15.

Механизмы поиска - совокупность реализованных в
системе моделей и алгоритмов процесса формирования
выдачи документов в ответ на поисковый запрос.
Средства поиска, с одной стороны, - взаимозависимый
комплекс информационно-поисковых языков (ИПЯ) и
языков определения/управления данными,
обеспечивающий структурные и семантические
преобразования объектов обработки (документов,
словарей, совокупностей результатов поиска), а с другой,
- объекты пользовательского интерфейса,
обеспечивающие управление последовательностью
выбора операционных объектов конкретной АИПС.

16.

ПОСЛЕДОВАТЕЛЬНЫЙ ПЕРЕБОР
Среднее время
поиска:
N/2

17.

МЕТОД БИНАРНОГО ПОИСКА
1 2 3 4 5 6 7 8 X
Универсальный метод поиска для любых
упорядоченных данных.

18.

БЛОЧНЫЙ ПОИСК
Блочно-последовательный
с помощью индекса
выбирается нужный блок;
внутри блока поиск
производится
последовательный поиск.
Метод спуска
используется для
иерархических структур
данных.

19.

ЗАДАНИЕ
В
журнале
успеваемости
учащихся со сведениями о
годовых оценках требуется
осуществить
поиск
всех
отличников по информатике.
Что в этой ситуации является
набором данных, что – ключом
поиска,
что
критерием
поиска?

20.

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

21.

22.

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

23.

Функционирование современных ИПС
основано на двух предположениях:
1) документы, необходимые пользователю,
объединены наличием некоторого признака
или комбинации признаков;
2) пользователь способен указать этот
признак.

24.

Автоматизированные
ИПСТРАДИЦИОННЫЕ
(АИПС), используют компьютерные
ИПС ДЕЛЯТСЯ НА:
(РУЧНЫЕ,
программно-технические средства и технологии и
МЕХАНИЧЕСКИЕ,
ЭЛЕКТРОМЕХАНИЧЕСКИЕ)
предназначаются
для нахождения
и выдачи пользователям И
информации
по заданным критериям.
Определяющими для
АВТОМАТИЗИРОВАННЫЕ
(ЭЛЕКТРОННЫЕ).
понимания методов автоматизации поиска являются два
следующих фактора:
1) сравниваются не сами объекты, а описания - так
называемые "поисковые образы";
2) сам процесс является сложным (составным и не
одноактным) и обычно реализуется последовательностью
операций.

25.

ПРИМЕР 1

26.

ПРИМЕР 1
Решение
По считаем сколько ребер у каждой вершины:
Три ребра имеет только одна вершина — А,
поэтому только А может соответствовать П3.
Уникальное значение количества ребер имеет также вершина Д,
— два ребра. В таблице вершине Д будет соответствовать П4.
Вершины Г и В имеют по 4 ребра. Рассмотрим матрицу, в ней 4
числа соответствуют пунктам П2 и П5.
С пунктом Д пересекается только вершина Г ( Г -> 4 (А В Д К) ).
В ве совой матрице с вершиной Д пре секается П5. Значит
вершина Г соответствует П5.
В П5 на пересечении с П3 находится число 6.
Результат: 6

27.

ПРИМЕР 2

28.

ПРИМЕР 2
Решение

29.

ПРИМЕР 2

30.

Р е з у л ьт а т : 5 6

31.

САМОСТОЯТЕЛЬНО
С ПОДРОБНЫМ ОПИСАНИЕМ
ЗАДАНИЕ 1
Описываем Как в примерах

32.

САМОСТОЯТЕЛЬНО
С ПОДРОБНЫМ ОПИСАНИЕМ
ЗАДАНИЕ 2
О п и с ы в а е м Ка к в
примерах

33.

РАБОТА С ФАЙЛАМИ В PASCAL
Описание:
var
f: text;
Связь файла в коде и
файла на диске:
Открытие
существующего файла
для чтения:
Чтение из файла:
assign(f,’input.txt’);
reset(f);
read(f, x)

34.

var
f: text;
team: array[1..16] of string;
p: array[1..16] of byte;
i,er: integer;
s: string;
begin
assign(f,'input.txt');
reset(f);
for i:=1 to 16 do
begin
readln(f, s);
team[i]:= copy(s,1,pos(';',s)-1);
val(copy(s,pos(';',s)+1,length(s)),p[i],er);
end;
for i:=1 to 16 do
write(team[i], ' ', p[i], chr(13));
end.