Структуры данных. Линейные списки. Стек и очередь. Двоичные деревья



Скачать 118.46 Kb.
страница2/6
Дата06.11.2018
Размер118.46 Kb.
Название файла-
1   2   3   4   5   6
Основные понятия и определения

Структура G на множестве M - это пара (R,M) где R это отношение порядка на множестве M.

Определение.

Отношение порядка на множестве M это подмножество множества M*M обладающее следующими свойствами:

1.a<=a - рефлективность;

2.если a<=b и b<=c, то a<=c - транзитивность;

3.если a<=b и b<=a, то a=b - антисимметричность.

Если отношение не обладает свойством антисимметричности, то оно называется предпорядком.

Определение.

Отношение порядка назывется линейным, если оно определено для любых a и b из M.

Определение.

Множество называется частично упорядоченным если на нем зафиксирован некоторый порядок.

Примеры.

1. Множество натуральных чисел с отношением <=.

2. Множество слов в алфавите с отношением лексико-графического упорядочения.

3. Множество людей с отношением родства.

4. Множество людей с отношением начальник-подчиненный.

Для выбора и обозачения элементов на M используют индексацию I: I - это отображение M -> [ 1.. |M| ].





Поделитесь с Вашими друзьями:
1   2   3   4   5   6


База данных защищена авторским правом ©rppna.ru 2017
обратиться к администрации

    Главная страница