Викиконспекты - Вклад участника [ru]

Старые вопросы на экзамен по C++

2011-06-24T05:00:20Z

VasilevArtem: /* Ввод-вывод */

__TOC__

== Классы, контейнеры ==
# Что определяет класс? Чем обличается класс от объекта?
#: Класс определяет тип объекта, а объект - это конкретный экземпляр класса.
# Можно ли объявлять массив объектов? А массив классов?
#: Смотря что считать массивом - в обычном смысле можно объявить массив объектов, с помощью метапрограммирования можно делать списки типов(классов)
# Разрешается ли объявлять указатель на объект? А указатель на класс?
#: Да. Нет.
# Допускается ли передавать объекты в качестве параметров, и какими способами? А возвращать как результат?
#: Допускается по значению и по ссылке. Возвращать также можно значение или ссылку.
# Как называется использование объекта одного класса в качестве поля другого класса?
#: Композиция
# Является ли структура классом? Чем класс отличается от структуры?
#: Является, у структуры все поля/методы по умолчанию public, у класса - private.
# Объясните принцип инкапсуляции.
#: Инкапсуляция - сокрытие методов и полей класса от пользователя, в целях сохранения внутренних инвариантов. При этом то, что помечено как public, называется интерфейсом класса.
# Что такое композиция?
#: Это создание нового класса путем объединения уже существующих в единую структуру.
# Для чего используются ключевые слова public и private?
#: см. инкапсуляция, также при public - наследовании все члены базового класса наследуются с теми же модификаторами, при private - все члены базового класса становятся private.
# Можно ли использовать ключевые слова public и private в структуре?
#: да
# Существуют ли ограничения на использование public и private в классе? А в структуре?
#: нет
# Обязательно ли делать поля класса приватными?
#: нет
# Что такое метод? Как вызывается метод?
#: Это функция, являющаяся членом класса. Если она не статическая, при ее вызове в нее неявно передается указатель на экземпляр, от которого она вызывается.
# Может ли метод быть приватный?
#: да
# Как определить метод непосредственно внутри класса? А вне класса? Чем эти определения отличаются?
#: Просто берем и определяем :) Вне класса - в описании класса пишем только объявление метода, вне класса реализацию.
# Можно в методах присваивать параметрам значения по умолчанию?
#: да
# Что обозначается ключевым словом this?
#: указатель на экземпляр класса, для которого вызван текущий метод. В статическом методе this недоступен.
# Зачем нужны константные методы? Чем отличается определение константного метода от обычного?
#: константный метод гарантирует, что мы не изменим состояние класса в процессе его работы. После сигнатуры надо написать const.
# Может ли константный метод вызываться для объектов-переменных? А обычный метод — для объектов-констант?
#: Да. Нет.
# Объясните принцип полиморфизма.
#: Полиморфизм - возможность работать с разными типами одинаковым образом. Статический - перегрузка функций, шаблоны. Динамический - виртуальные функции.
# Сколько места в памяти занимает объект класса? Как это узнать?
#: sizeof(a)
# Каков размер «пустого» объекта?
#: Здесь вроде понятно, что он должен быть ненулевой(у меня 1 байт, например), там добавляется фейковый член чтобы вообще можно было как-то хранить его в памяти.
# Влияют ли методы на размер объекта?
#: Если есть виртуальные методы, то размер увеличивается засчет указателся на таблицу виртуальных функций.
# Одинаков ли размер класса и аналогичной структуры?
#: да
# Какие операции нельзя перегружать? Как вы думаете, почему?
#: a ? b : c - в Страуструпе говорится что нет особых причин запрещать его перегрузку, так что непонятно.
#: a::b - это вообще говоря не какая-то функция, а просто удобный способ избежать конфликта имен.
#: a.b - непонятно, как тогда вызывать методы, и могут возникать конфликты ([http://pastebin.com/fJm050jm])
#: sizeof(a), typeid(a) - видимо, что-то низкоуровневое, тоже надо поподробнее узнать
#: a.*b - вообще без понятия что он делает
# Можно ли перегружать операции для встроенных типов данных?
#: Нет
# Можно ли при перегрузке изменить приоритет операции?
#: Нет
# Можно ли определить новую операцию?
#: Нет
# Перечислите особенности перегрузки операций как методов класса. Чем отличается перегрузка внешним образом от перегрузки как метода класса?
#: Первый параметр оператора как метода класса - всегда неявно *this. Внешним образом нельзя обратиться к private полям класса. По этой причине, видимо, оператор>>/<< делается friend'ом - так как там он фактически перегружается внешним образом.
# Какой результат должны возвращать операции с присваиванием?
#: Ссылку на *this
# Как различаются перегруженная префиксная и постфиксная операции инкремента и декремента?
#: Префиксная(++a): T & operator++(); Постфиксная(a++): T operator++(int); - с фейковым параметром чтобы как-то отличать
# Что означает выражение *this? В каких случаях оно используется?
#: Разыменование указателя на текущий экземпляр. Например, чтобы вернуть объект :)
# Какие операции не рекомендуется перегружать как методы класса? Почему?
#: Нужно перегружать только те, которые меняют private члены(типа +=, -= и т.д.). А вот уже +, - и т.д. - могут воспользоваться уже перегруженными +=, -=. Не рекомендуется перегружать ||, &&, так как по умолчанию они оптимальны - т.е. если установлена истинность одного аргумента, второй даже не обрабатывается.
# Какие операции разрешается перегружать только как методы класса?
#: =, [], (), ->. Вопрос - почему?
# Дайте определение дружественной функции. Как объявляется дружественная функция? А как определяется?
#: Дружественная для данного класса функция - которой предоставлен доступ к private и protected членам. Функция объявляется внутри класса, к которому надо предоставить доступ, определяется там, где нужно(уже без модификатора friend).
# Дайте определение конструктора. Каково назначение конструктора? Перечислите отличия конструктора от метода.
#: Конструктор - функция, которая вызывается при просто объявлении(конструктор по умолчанию) или инициализации объекта. Назначение - получать объект класса с какими-то начальными параметрами. Конструктор для данного можно вызвать только один раз.
# Сколько конструкторов может быть в классе? Допускается ли перегрузка конструкторов? Какие виды конструкторов создаются по умолчанию?
#: Сколько угодно. Допускается. По умолчанию создается пустой конструктор и конструктор копирования.
# Может ли конструктор быть приватным? Какие последствия влечет за собой объявление конструктора приватным?
#: Может. Последствия - объект не может быть сконструирован этим конструктором извне.
# Приведите несколько случаев, когда конструктор вызывается неявно.
#: bigint a;(вызван пустой конструктор)
#: bigint a = "123214";(вызван конструктор от string)
#: bigint a = 10;(вызван конструтор от long long)
# Как проинициализировать динамическую переменную?
#: T* t = new T();
# Как объявить константу в классе? Можно ли объявить дробную константу?
#: Просто взять и объявить. Да.
# Каким образом разрешается инициализировать константные поля в классе?
#: Инициализировать ее можно только через список инициализации. Можно еще static const, ее нужно инициализировать сразу при объявлении
# В каком порядке инициализируются поля в классе? Совпадает ли этот порядок с порядком перечисления инициализаторов в списке инициализации конструктора?
#: В порядке объявления. Нет.
# Какие конструкции С++ разрешается использовать в списке инициализации качестве инициализирующих выражений?
#: Где бы это найти?
# Какой вид конструктора фактически является конструктором преобразования типов?
#: Видимо, любой неявный констркутор от одного аргумента.
# Для чего нужны функции преобразования? Как объявить такую функцию в классе?
#: Что это??
# Как запретить неявное преобразование типа, выполняемое конструктором инициализации?
#: Для этого есть ключевое слово explicit
# Какие проблемы могут возникнуть при определении функций преобразования?
#: ????
# Для чего служит ключевое слово explicit?
#: Чтобы не позволить вызвать конструктор от одного аргумента неявно.
# Влияет ли наличие целочисленных констант-полей на размер класса?
#: Они ничем не отличаются от обычных не-const полей.
# Разрешается ли объявлять массив в качестве поля класса. Как присвоить элементам массива начальные значения?
#: Разрешается, надо написать что-нибудь вроде int a[] = {1, 2, 3};
# Сколько операндов имеет операция индексирования []? Какой вид результата должна возвращать эта операция?
#: Операции индексирования нужен один аргумент - индекс. Возвращать T или T& в зависимости от того, можно ли менять объект.
# Для чего нужны статические поля в классе? Как они определяются?
#: Это какие-то параметры класса. Определяются с помощью ключевого слова static
# Как объявить в классе и проинициализировать статический константный массив?
#: struct S{static const int a[];}; const int S::a[] = {1, 2, 3};
# Что такое выравнивание и от чего оно зависит? Влияет ли выравнивание на размер класса?
#: Это способ расположения данных для ускорения доступа к ним. Да, размер может увеличиться.
# Дайте определение контейнера.
#: Это объект, который хранит "коллекцию" других объектов. Контейнер сам заботится о выделении памяти и других низкуровневых штуках, а нам предоставляет доступ к объектам, которые в нем находятся.
# Какие виды встроенных контейнеров в С++ вы знаете?
#: vector, deque, set, map, list
# Какие виды доступа к элементам контейнера вам известны?
#: Для чтения и(или) записи в одном/двух направлениях. Также есть произвольный доступ.
# Чем отличается прямой доступ от ассоциативного?
#: Прямой(direct access) - это вроеде через оператор[], а что такое ассоциативный??
# Перечислите операции, которые обычно реализуются для последовательного доступа к элементам контейнера.
#: Видимо, инкремент итератора.
# Дайте определение итератора.
#: Это объект - обертка над указателем на какой-либо элемент контейнера. В нем должны быть реализованы хотя бы операции инкремента и разыменования.
# Можно ли реализовать последовательный доступ без итератора? В чем преимущества реализации последовательного доступа с помощью итератора?
# Что играет роль итератора для массивов С++?
#: Хм, указатели, видимо.
# Что такое деструктор? Может ли деструктор иметь параметры?
#: Деструктор - то что будет вызвано после того, как объект выходит из своей области видимости для того, чтобы корректно освободить то, что выделяли в динамической памяти.
# Почему для классов-контейнеров деструктор надо писать явным образом?
#: Потому что там используется динамическая память.
# Допускается ли перегрузка деструкторов?
#: Нет
# Что такое «глубокое копирование» и когда в нем возникает необходимость?
#: Если мы копируем объект, в котором есть поле-указатель, надо скопировать объект, на который указывает тот указатель, а не просто указатель.
# Какое копирование осуществляет стандартный конструктор копирования?
#: Тупо копируются все поля.
# Чем отличается копирование от присваивания?
#: Копирование - инициализация объектом того же типа. Присваивание - замена уже существующего объекта.
# Объясните, почему в операции присваивания требуется проверка присваивания самому себе?
#: Потому что если мы работаем с ссылками, можно попортить объект при очистке памяти:
#: struct A{int* a; A(){a = new int(10);} A & operator=(const A &b){delete a; a = new int(*b.a); return *this}
#: В этом коде если присваиваем самому себе, неявно мы изменяем b после вызова delete a, и теряем значение *a.
# Можно ли в качестве операции индексирования использовать операцию вызова функции ()? В чем ее преимущества перед операцией []?
#: Можно впринципе. Плюс, видимо, в том что можно передавать сколько хочешь аргументов.
# Почему необходимо писать два определения операции индексирования? Чем они отличаются?
#: Первое определение возвращает ссылку на элемент, которых храним в контейнере, для того чтобы можно было его изменять.
#: T & operator[](size_t index);
#: Второе определение возвращает новый объект, для случая, когда мы работаем с контейнером, который нельзя менять.
#: T operator[](size_t index);
# Дайте определение вложенного класса.
#: Класс внутри класса(and we need to go deeper :) )
# Можно ли класс-итератор реализовать как внешний класс? А как вложенный? В чем отличия этих методов реализации?
# Может ли объемлющий класс иметь неограниченный доступ к элементам вложенного класса? А вложенный класс — к элементам объемлющего?
#: Я пока не очень понимаю, как иметь допуск не к static элементам. Надо получше про это узнать.
# Ограничена ли глубина вложенности классов?
#: ?? Где про это можно узнать?
# Можно ли определить вложенный класс внешним образом? Зачем это может понадобиться?
#: Да. Зачем - непонятно.
# Каким образом вложенный класс может использовать методы объемлющего класса? А объемлющий — методы вложенного?
#: Я пока не очень понимаю, как иметь допуск не к static элементам. Надо получше про это узнать.
# Что такое «запредельный» элемент, какую роль он играет в контейнерах?
#: В стандартных контейнерах это end(), используется для обозначения конца контейнера, возвращения в случае неудачного поиска, и т.д.
# Объясните, по каким причинам трудно написать универсальный контейнер, элементы которого могут иметь произвольный тип.

== Исключения ==
# Назовите ключевые слова С++, которые используются для обработки исключений.
#: try, catch, throw
# Исключение — это:
## событие;
## ситуация;
## объект;
## ошибка в программе;
## прерывание;
# Каким образом исключение генерируется?
# Каковы функции контролируемого блока?
# Что обозначается ключевым словом catch?
## контролируемый блок;
## блок обработки исключения;
## секция-ловушка;
## генератор исключения;
## обработчик прерывания;
# Какого типа может быть исключение?
# Сколько параметров разрешается писать в заголовке секции-ловушки?
# Какими способами разрешается передавать исключение в блок обработки?
# Объясните, каким образом преодолеть ограничение на передачу единственного параметра в блок обработки.
# Почему нельзя выполнять преобразования типов исключений при передаче в секцию-ловушку?
# Напишите конструкцию, которая позволяет перехватить любое исключение.
# Могут ли контролируемые блоки быть вложенными?
# Зачем нужен «контролируемый блок-функция» и чем он отличается от обычного контролируемого блока?
# Перечислите возможные способы выхода из блока обработки.
# Каким образом исключение «передать дальше»?
# Сколько секций-ловушек должно быть задано в контролируемом блоке?
# Что такое «спецификация исключений»?
# Что происходит, если функция нарушает спецификацию исключений?
# Учитывается ли спецификация исключений при перегрузке функций?
# Что такое «иерархия исключений»?
# Существуют ли стандартные исключения? Назовите два-три типа стандартных исключений.
# Поясните «взаимоотношение» исключений и деструкторов.
# Объясните, зачем может понадобиться подмена стандартных функций завершения.
# Какие виды нестандартных исключений вы знаете?
# В чем отличие механизма структурной обработки исключений Windows от стандартного механизма?

== Динамический полиморфизм ==
# Какие две роли выполняет наследование?
# Какие виды наследования возможны в С++?
#: Простое и множественное?
# Чем отличается модификатор доступа protected от модификаторов private и public?
# Чем открытое наследование отличается от закрытого и защищенного?
# Какие функции не наследуются?
# Сформулируйте правила написания конструкторов в производном классе.
# Каков порядок вызова конструкторов? А деструкторов?
#: Конструкторы - сначала базовый, потом производный. Деструкторы наоборот.
# Можно ли в производном классе объявлять новые поля? А методы?
# Если имя нового поля совпадает с именем унаследованного, то каким образом разрешить конфликт имен?
# Что происходит, если имя метода-наследника совпадает с именем базового метода?
# Сформулируйте принцип подстановки.
# Когда выполняется понижающее приведение типов?
# Объясните, что такое «срезка» или «расщепление».
#: Что это???
# Объясните, зачем нужны виртуальные функции.
#: Чтобы перегрузить их поведение при наследовании.
# Что такое связывание?
#: Связывание - сопоставление вызова функции с телом функции, которую вызовут.
# Чем «раннее» связывание отличается от «позднего»?
#: Раннее связывание - компилятор/компоновщик решают какая функция будет вызвана на этапе компиляции. Позднее - нужная функция выбирается на в рантайме.
# Какие два вида полиморфизма реализованы в С++?
#: Статический и динамический
# Дайте определение полиморфного класса.
#: Класс, в котором есть виртуальные методы.
# Может ли виртуальная функция быть дружественной функцией класса?
#: да
# Наследуются ли виртуальные функции?
#: наследуются по определению :)
# Каковы особенности вызова виртуальных функций в конструкторах и деструкторах?
# Можно ли сделать виртуальной перегруженную операцию, например, сложение?
#: Можно
# Может ли конструктор быть виртуальным? А деструктор?
#: Нет. Да.
# Как виртуальные функции влияют на размер класса?
#: К размеру класса добавляется размер виртуальной таблицы функций.
# Как объявляется «чистая» виртуальная функция?
#: В конце сигнатуры пишут =0;
# Дайте определение абстрактного класса.
#: Абстрактный класс - класс, содержащий чисто абстрактные функции. У чисто абстрактного класса не может быть экзмепляра, но можно хранить на него указатель.
# Наследуются ли чистые виртуальные функции?
#: Да
# Можно ли объявить деструктор чисто виртуальным?
#: да
# Чем отличается чистый виртуальный деструктор от чистой виртуальной функции? //чистый деструктор o_O
# Зачем требуется определение чистого виртуального деструктора?
#: чтобы можно было удалять объекты по указателю на базовый класс.
# Наследуется ли определение чистой виртуальной функции?
#: Да
# Приведите классификацию целей наследования.
#: Что это??
# Объясните разницу наследования интерфейса от наследования реализации.
#: ????

== Компиляция ==
# Назовите причины, требующие разделения программ на части.
#: во-первых, просто декомпозиция, для меньшей путаницы
#: во-вторых, для того чтобы уменьшить время компиляции
# Дайте определение термина «единица трансляции»?
#: Данные, которые поступают компилятору для создания объектного файла, уже после того как прошли препроцессинг.
# Чем отличается файл с исходным текстом от единицы трансляции?
#: файл с исходным кодом не всегда является единицей трансляции.
# Существуют ли в С++ конструкции, позволяющие идентифицировать отдельный модуль?
#: Что такое модуль??
# Какие способы сборки программы вы можете назвать?
# Что такое «объектный модуль»? Программа, которая «собирает» объектные модули в программу, называется _____________ ?
#: ???. Программа - линкер или компоновщик.
# В чем заключается отличие аргумента «файл» от <файл> в директиве #include?
#: <file> - ищет в папках, которые указаны в свойствах какой-то переменной Include(в вижаке задается свойствами проекта), "file" - в текущей директории.
# Что такое ODR?
#: One Definition Rule - принцип, по которому, переменная/класс/метод может быть опеределена только один раз в одной из единиц трансляции. При этом объявлять можно сколько угодно.
# Объясните, что такое «страж» включения и зачем он нужен.
#: Это или #pragma once или #ifndef H_NAME #define H_NAME //код хедера #endif. Нужен чтобы соблюдать ODR.
# Является ли интерфейс класса его определением?
# Сколько определений класса может быть в единице трансляции?
#: одно
# Сколько определений класса может быть в многофайловой программе?
#: несколько
# Чем отличаются стандартные заголовки <string>, <string.h> и <cstring>?
#: <string> - строки C++, библиотеки STL. <string.h> - Строки C. <cstring> - то же, что <string.h>, но все обернуто в пространство имен std.
# Объясните суть идиомы Pimpl.
# Что такое делегирование и как его можно использовать для повышения степени инкапсуляции?
# Каким образом глобальную переменную, определенную в одной единице трансляции, сделать доступной в другой единице трансляции? А константу?
# Можно ли использовать слово extern при объявлении функций?
# Как локализовать объявление функции в файле?
# Чем отличается «внешнее» связывание от «внутреннего» связывания?
# Что такое «спецификации компоновки»?
# Какие объекты обладают внутренним связыванием по умолчанию?

== Области видимости ==
# Какие области видимости имен вы знаете?
# Для чего используются пространства имен?
#: Для какой-то логической группировки имен, и чтобы в область видимости не лезло то, что не нужно.
# Чем отличаются именованные и неименованные пространства имен?
#: К неименованному пространству имен нельзя будет обратиться откуда-то, кроме текущей единицы трансляции.
# Могут ли пространства имен быть вложенными?
#: Да
# Для чего применяются алиасы пространства имен?
#: Для удобства, чтобы каждый раз не писать длинный путь к функции или еще чему-нибудь.
# Как сделать члены пространства имен доступными в нескольких (в пределе — во всех) файлах программного проекта?
#: Вынести объявления всего что в них лежит в хедер.
# Объясните разницу между статической и динамической инициализацией.
#: Видимо, статическая - на этапе компиляции, динамичестая - в рантайме.
# В чем состоит проблема инициализации глобальных статических переменных?
#: Скорее всего в том, что непонятно, в каком порядке они инициализируются.
# Какие элементы класса можно объявлять статическими?
#: Поля и методы.
# Можно ли объявить в классе статическую константу? А константный статический массив?
#: Да. хм, надо попробовать.
# А какие статические поля можно инициализировать непосредственно в классе?
# Как определяются статические поля? В какой момент работы программы выполняется инициализация статических полей?
# Сколько места в классе занимают статические поля ?
#: нисколько
# Чем отличается статический метод от обычного?
#: Статический метод - метод класса, у него нет доступа к this.
# Какие методы класса не могут быть статическими?
#: Видимо, конструктор и деструктор?
# Какие применения статических полей вы можете привести? А каким образом применяются статические методы?
#: Тут можно привести нашу длинку, например, и то, как мы храним базу. Например, можно сделать класс со статическими методами Math(как в джаве), и реализовать там всякие математические операции, очень даже удобно.
# Приведите структуру и принцип действия паттерна Singleton.

== Шаблоны ==
# Для чего предназначены шаблоны?
# Какие виды шаблонов в С++ вы знаете?
# Объясните термин «инстанцирование шаблона».
# В чем разница между определением и объявлением шаблона?
# Объясните назначение ключевого слова typename.
# Какие виды параметров разрешается задавать в шаблоне класса? А в шаблоне функции?
# Можно ли параметрам шаблона присваивать значения по умолчанию?
# Может ли параметром шаблона быть другой шаблон? Каковы особенности объявления параметра-шаблона?
# Что такое специализация шаблона? Объясните разницу между полной и частичной специализацией.
# Разрешается ли специализировать шаблон функции?
# Может ли класс-шаблон быть вложенным в другой класс-шаблон? А в обычный класс?
# Можно ли объявить в классе шаблонный метод? А шаблонный конструктор?
# Можно ли перегружать функцию-шаблон?
# Какие параметры функции-шаблона выводятся автоматически?
# Может ли шаблон класса быть наследником обычного класса? А обычный класс от шаблона?
# Объясните, что такое класс свойств (класс трактовок).
# Каким образом можно использовать возможность наследования обычного класса от шаблона?
# Может ли шаблонный конструктор быть конструктором по умолчанию?
# Для чего применяются директивы явного инстанцирования?
# Объясните, в чем состоят проблемы, возникающие при разделении шаблонного класса на интерфейс и реализацию?
# Что такое «модель явного инстанцирования» и как она работает?
# Может ли шаблонный класс иметь «друзей»?
# Какие проблемы возникают при объявлении дружественной функции для класса-шаблона?
# Разрешается ли определять в классе-шаблоне статические поля? А статические методы?
# Что такое «инициализация нулем»?

== Память ==
# Что является единицей памяти в С++? Какие требования к размеру единицы памяти прописаны в стандарте С++?
#: Байт. Чтобы в нее вмещался любой символ, причем не требуется чтобы в байте было 8 бит.
# В каких единицах выдает результат операция sizeof? Какие типы данных имеют размер 1?
#: В байтах. char(signed/unsigned), bool
# Какие три вида памяти входят в модель памяти С++?
# Сколько видов динамической памяти обеспечивает С++?
# Какие функции для работы с динамической памятью достались С++ по наследству от С? В какую библиотеку они включены?
#: malloc, calloc, realloc, free. <cstdlib>
# Какие функции выделяют память, и с помощью каких функций память освобождается?
#: malloc, calloc, realloc, new([]) выделяют, free, delete([]) освобождают(realloc, видимо, тоже может)
# Какое важное отличие имеет функция calloc() от функции malloc()?
#: calloc не только
# Какие действия выполняют функции выделения памяти, если память не может быть выделена?
# Зависит ли объем выделенной памяти от типа указателя? Влияет ли выравнивание на объем выделяемой динамической памяти?
# Можно ли с помощью функции realloc() уменьшить объем выделенной памяти?
# Что произойдет, если функции free() передать в качестве аргумента нулевой указатель?
# В чем главное отличие объектно-ориентированного механизма new/delete от механизма malloc()/free()?
# Сколько существует форм new/delete? В чем их отличие?
#: new, delete, new[], delete[]. Первые два - для объектов, вторые - для массивов объектов.
# Какие типы являются POD-типами? Чем отличается работа механизма new/delete с POD-объектами и nonPOD-объектами?
# Какие функции выполняет обработчик new?
# Можно ли реализовать собственный обработчик new и «прицепить» его к механизму new/delete?
# В чем главное отличие объединения от других видов классов С++?
#: Размер объединения всегда равен размеру максимального его члена. Соответственно, в любой момент он корректно хранит только одно из своих полей.
# Может ли объединение участвовать в иерархии наследования?
# Разрешается ли определять для объединения конструкторы и деструктор? А виртуальные функции?
# В чем похожи и чем отличаются объединение и размещающий new?
# Объясните, почему при использовании размещающего new нужно явным образом вызывать деструктор?
# Зачем нужны интеллектуальные указатели?
#: Чтобы не запутаться в new/delete. Умные указатели сами следят за объектами, которыми владеют.
# Что такое «стратегия владения»? Сколько стратегий владения вы знаете?
# Какой интеллектуальный указатель реализован в стандартной библиотеке STL, и какую стратегию владения он реализует?
# Объясните, в чем преимущества и недостатки интеллектуальных указателей со счетчиком ссылок.
# Разрешается ли перегружать new и delete и какими способами?
# Опишите схему функции, перегружающей глобальную функцию new.
# Отличается ли реализация перегруженной функции new[]() для массивов от реализации «обычной» функции new()?
# Как вы думаете, почему функции new/delete, перегружаемые для класса, являются статическими?
# Зачем при перегрузке new/delete для класса нужно проверять размер запрашиваемой памяти?
# Объясните, чем определяется «динамичность» контейнеров?
# Что такое «стратегия распределения памяти», и какие стратегии выделения памяти вы знаете?
# Рассмотрите следующую стратегию распределения памяти: память выделяется для нескольких элементов блоками фиксированной длины, но блоки связываются в список. Для какого вида контейнера можно использовать такую стратегию?
# Какие операции можно перегрузить для доступа к элементам двумерного массива?
# В чем заключаются сложности использования операции индексирования [] для доступа к элементам двумерного массива?
# Каковы способы реализации операций с контейнерами?
# Какую конструкцию можно назвать «обобщенный алгоритм»?
# Каким образом объявить указатель на метод?
# Объясните разницу между указателем на функцию и указателем на метод.
# Каким образом получить адрес метода?
# Можно ли указателю на функцию присваивать адрес метода?
# Какие операции определены в С++ для косвенного вызова метода через указатель?
# Что такое «функтор»? Приведите пример функционального класса.
#: Это класс с перегруженным оператором(). Например, можно сделать абстрактный интерфейс унарной функции, у которой будет виртуальный оператор().
# Какими способами функтор вызывается?
# Можно ли использовать наследование при разработке функторов?
# Разрешается ли операцию вызова функции () определять как виртуальный метод? А как статический?
# В чем преимущества функторов перед указателями на функции?
# Объясните, зачем нужны адаптеры функторов? Какие виды адаптеров вы знаете?
# Как используются классы свойств при разработке функторов?
# Объясните, что такое «композиция» и приведите примеры?
# Объясните, чем отличается множественное наследование от простого?
# Приведите структуру и принцип действия паттерна Adapter.
# Сформулируйте основную проблему множественного наследования.
# Выполняется ли принцип подстановки при открытом множественном наследовании?
# Что такое виртуальное наследование? Каковы его преимущества и недостатки по сравнению с обычным наследованием?
# Может ли виртуальное наследование быть одиночным?
# Влияет ли виртуальное наследование на размер класса?
# Объясните, каким образом с помощью виртуального наследования можно вообще запретить наследование.
# Какие средства С++ составляют RTTI?
#: dynamic cast и typeid
# Объясните разницу между повышающим, понижающим и перекрестным приведением.
# Какими свойствами должен обладать класс, чтобы с ним работал механизм RTTI?
# В чем приведение указателей отличается от приведения ссылок?
# Какие исключения связаны с механизмом RTTI?

== Ввод-вывод ==
# Что такое «поток» — дайте определение.
#: Поток - абстрактный объект, который представляет собой определенное устройство для выполнения операций ввода/вывода. Обычно представляет собой источник/получатель символов неопределенной длины. Чаще всего ассоциируются с физическими источниками/получателями символов, такие как файлы, клавиатура, консоль, etc
# Как классифицируются потоки, реализованые в библиотеках ввода/вывода С++?
#: (???) Вопрос под вопросом.
# Что такое буферизация и зачем она нужна?
#: Буферизация нужна для более эффективной передачи данных: поток с буферизацией собирает символы в streambuf, который хранит символы в массиве, пока не будет вынужден из-за переполнения записать их по назначению. Небуферизованный ввод-вывод сразу осуществляет передачу символов, не заботясь о том, чтобы сделать передачу эффективной.
# Какие библиотеки ввода/вывода реализованы в С++ и чем они отличаются?
#: Основная библиотека для ввода/вывода в С++ - iostream. Ее организация:
#* <ios>, <istream>, <ostream>, <streambuf> and <iosfwd> aren't usually included directly in most C++ programs. They describe the base classes of the hierarchy and are automatically included by other header files of the library that contain derived classes.
#*<iostream> declares the objects used to communicate through the standard input and output (including cin and cout).
#*<fstream> defines the file stream classes (like the template basic_ifstream or the class ofstream) as well as the internal buffer objects used with these (basic_filebuf). These classes are used to manipulate files using streams.
#*<sstream>: The classes defined in this file are used to manipulate string objects as if they were streams.
#*<iomanip> declares some standard manipulators with parameters to be used with extraction and insertion operators to modify internal flags and formatting options.
# Перечислите стандартные потоки и объясните их назначение.
#: Стандартный поток ввода: std::cin, вывода - std::cout, error output stream - std::cerr
# Зачем нужен процесс форматирования и когда он выполняется?
#: (???) Зачем - понятно, но когда?
# Что такое «форматная строка», и в каких функциях она используется?

# Объясните назначение элементов спецификатора формата.
# Сколько спецификаторов формата может быть в форматной строке?
# Какой из элементов спецификатора формата не является умалчиваемым?
# Перечислите несколько известных вам обозначений типов в спецификаторе формата, и укажите их назначение.
# Сколько модификаторов типа вы знаете, и какую роль модификатор типа играет в спецификаторе формата?
# С помощью какого флага можно выровнять выводимое значение влево? А каким образом вывести ведущие нули?
# Какое действие оказывают на выводимую строку ширина, точнойть и флаги в спецификаторе формата?
# Для чего в спецификаторе формата может использоваться символ звездочка («*»)? Чем отличается действие этого символа при воде и при выводе?
# Каковы особенности ввода строк?
# Каким образом ограничить набор вводимых символов при вводе?
# Что является главной проблемой при использовании форматного ввода/вывода из библиотеки <cstdio>?
# Объясните, для чего нужны строковые потоки. Почему строковые потоки —всегда форматируемые?
# С помощью каких функций выполняется работа со строковыми потоками?
# Можно ли использовать тип string (и каким образом) со строковыми потоками?
# Объясните, в чем заключается различие между текстовым и двоичным файлом.
# Объясните, что означает «открыть» файл и «закрыть» файл?
# Каким образом внешний файл связывается с потоком?
# Можно ли один и тот же поток связать с разными файлами? А один и тот же файл с разными потоками?
# Перечислите режимы открытия файла. Чем отличается режим “r” от режима “a”?
# Какую роль в режиме открытия играет знак плюс («+»)?
# В каких случаях необходимо следить за ситуацией «конец файла»? Каким способом это делается?
# Можно ли текстовый файл открыть как двоичный? А двоичный — как текстовый?
# Какие функции ввода/вывода используются для обмена с текстовыми файлами?
# Перечислите функции ввода/вывода для работы с двоичными файлами.
# Какие функции реализованы в библиотеке <cstdio> для обеспечения прямого доступа к записям двоичного файла? Можно ли их использовать для работы с текстовыми файлами?
# Объясните назначение функции fseek().
# Чем отличается функция ftell() от функции fgetpos()?
# Объясните, что означает «перенаправление» потока? Какие потоки можно перенаправлять и куда?
# Каким образом перенаправление ввода можно использовать для ввода строк с пробелами?
# В чем преимущества объектно-ориентированной библитеки по сравнению с процедурной?
# В каких состояних может находиться поток? Каким образом отслживается состояние «конец потока»?
# Какие объектно-ориентированные потоки связаны со стандартными потоками?
# Чем отличаются объектно-ориентированные строковые потоки от процедурных строковых потоков?
# Каким образом строковые потоки можно использовать для ограничения ширины поля ввода? А можно ли с той же целью использовать строковые потоки <cstdio>?
# Сравните средства форматирования объектно-ориентированной и процедурной библиотеки.
# Каким образом ввести строку типа string с пробелами?
# Каково назначение флагов форматированя? Какие средства реализованы в библиотеке для работы с флагами форматирования?
# Что такое «манипулятор»? В чем преимущества манипуляторов перед флагами форматирования?
# Как связываются файлы с потоками в объектно-ориентированной библиотеке?
# Можно ли файлы, записанные функциями библиотеки <cstdio>, прочитать объектно-ориентированными средствами? А наоборот?
# Перечислите режимы открытия объектно-ориентированных файловых потоков. каким образом комбинируются режимы открытия файлоавых потоков?
# Обязательно ли закрывать файл, связанный с объектно-ориентированным файловым потоком? А открывать?
# Каким образом открыть файловый поток для чтения и записи одновременно?
# Как открыть файловый поток для дозаписи?
# Можно ли вывести значение переменной в двоичном виде и как это сделать?
# Разрешается ли наследовать от классов библиотеки ввода/вывода?
# Каким образом можно еренаправить объектно-ориентированный поток?
# Как используется буфер потока для копирования потока?
# Какими операциями выполняется форматированный ввод/вывод в файловые потоки? А неформатированный?
# Реализованы ли в объектно-ориентированной библиотеке средства прямого доступа к файловым потокам? Сравните их с аналогичными средствами библиотеки <cstdio>.
# С какими объектно-ориентированными потоками разрешается, и с какими не разрешается использовать средства прямого доступа?
# Покажите, каким образом можно выполнить перегрузку операций ввода/вывода для нового типа данных.
# Как выполняется обработка ошибок ввода/вывода в объектно-ориентированной библиотеке?
# Какое стандартное исключение генерируется при ошибках ввода/вывода? Обязательно ли оно генерируется?
# Чем стандартные широкие потоки отличаются от узких?
# Что такое — «локаль», и каково ее назначение?
# Как установить русский шрифт при выводе в консольное окно?
# Чем отличается ли ввод/вывод широких файловых потоков от узких?

== STL ==
# Перечислите все последовательные контейнеры стандартной библиотеки. Чем они отличаются друг от друга?
# Перечислите адаптеры последовательных контейнеров и дайте их подробную характеристику.
# Почему для адаптеров-очередей нельзя использовать вектор в качестве базового?
# Чем простая очередь queue отличается от приоритетной очереди priority_queue?
# Каким требованиям должны удовлетворять элементы контейнера?
# Могут ли быть указатели элементами контейнера? А итераторы?
# Почему нельзя использовать в качестве элементов контейнера стандартный интеллектуальный указатель auto_ptr?
# Зачем в контейнере list реализованы собственные методы сортировки поиска и слияния? Можно ли пользоваться соответствующими стандартными алгоритмами при обработке списка?
# Перечислите типовые виды конструкторов, с помощью которых можно создавать последовательный контейнер.
# Можно ли инициализировать контейнер элементами встроенного массива? А элементами другого контейнера? Какими способами это можно сделать?
# Почему конструктор инициализации, параметрами которого являются итераторы, сделан шаблонным во всех контейнерах?
# Какие методы реализованы в контейнере-векторе для доступа к элементам?
# Отличается ли функция at() доступа по индексу от перегруженной операции индексирования и чем?
# Перечислите методы контейнера deque, относящиеся к определению размеров контейнера.
# Чем метод size() отличается от метода capacity()? А в чем отличие этих методов от метода max_size()?
# Перечислите методы контейнера list, предназначенные для вставки удаления и замены элементов. Отличаются ли эти методы от соответствующих методов вектора и дека?
# Каким образом выполняются операции сравнения контейнеров?
# Разрешается ли изменять элемент ассоциативного контейнера, доступный в данный момент по итератору?
# Какие контейнеры называются ассоциативными и почему?
# Чем контейнер map отличается от контейнера multimap?
# Объясните, почему в ассоциативных контейнерах нельзя изменять элемент, доступный в данный момент по итератору.
# По каким причинам в контейнере-множестве не реализованы типовые операции объединения, пересечения, разности и другие?
# Как используется структура-пара в ассоциативных контейнерах?
# Объясните, что такое «критерий сортировки», и каким требованиям он должен удовлетворять? Какой критерий сортировки принят по умолчанию?
# Какими преимуществами обладает функция make_pair() по сравнению с конструктором pair()?
# Почему в контейнерах-отображениях операция индексирования перегружена, а в контейнерах-множествах — нет?
# Какие гарантии безопасности обеспечивают контейнеры стандартной библиотеки?
# Что такое «транзакционная гарантия безопасности» и чем она отличается от базовой?
# На какие 4 класса по надежности можно разделить все операции с контейнерами?
# Что такое «распределитель памяти» и зачем он нужен?
# Чем отличается битовый вектор bitset от битового вектора vector<bool>?
# Дайте определение итератора.
# Что такое «начальный» итератор и «конечный» итератор? Какие методы, связанные с итераторами, обязательно включает каждый контейнер?
# Чем константный итератор отличается от неконстантного?
# Объясните, что такое «недействительный» итератор. В каких случаях итераторы становятся недействительными?
# Какие категории итераторов вы знаете? Какие операции обязательно реализуются для всех категорий итераторов?
# К какому виду итераторов можно отнести встроенный указатель и почему?
# Какие вспомогательные функции для итераторов вы знаете? В каких случаях оправдано их применение?
# Какие адаптеры итераторов реализованы в библиотеке?
# Объясните, почему итераторы реализованы как вложенные классы в контейнерах.
# Чем отличаются итераторы вставки от обычных итераторов?
# Каким образом используются потоковые итераторы?
# Какие стандартные функторы реализованы в библиотеке STL? Каково их основное назначение?
# Для чего нужны адаптеры функторов bind1st() и bind2nd()?
# Как применяются адаптеры-отрицатели?
# Почему алгоритмы remove() не удаляют элементы из контейнеров? Как реально удалить элементы из контейнера?
# Чем отличается стабильная сортировка от обычной?
# Какую функцию выполняет алгоритмы unique()?
# Могут ли стандартные алгоритмы работать со строками?
# Нужно ли сортировать ассоциативные контейнеры?
# Можно ли алгоритмы для работы с множествами применять для последовательных контейнеров? При каких условиях?
# Какие алгоритмы предназначены для заполнения контейнера значениями? С какими контейнерами они могут работать?
# Каким образом заполнить с помощью алгоритма generate() последовательный контейнер, не имеющий ни одного элемента?
# Перечислите алгоритмы, предназначенные для операций с каждым элементом контейнера.
# Можно ли с помощью алгоритма for_each() изменить элементы контейнера?

''PS Обращаю Ваше внимание на то, что это - базовый список. В него не включены вопросы, которые обсуждаются на лекциях, поэтому не стоит считать, что они не будут заданы Вам на экзамене.''

''С уважением, Ковалев Антон''

Фибоначчиева куча

2011-06-15T21:23:35Z

VasilevArtem:

'''Фибоначчиевы кучи''' - модификация [[Биномиальная_куча|биномиальных куч]], в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость <tex> O(1) </tex>. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций <tex> Extract\_min </tex> и <tex> Delete </tex> значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные <tex> k </tex> - ичные кучи на практике эффективнее.

= Фибоначчиевы деревья =
{{Определение
|definition=
'''Фибоначчиево дерево''' - биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
}}

{{Лемма
|statement=
Фибоначчиево дерево с вершиной степени <tex> k </tex> содержит не менее <tex> F_k </tex> вершин, где <tex> F_k </tex> {{---}} <tex> k </tex> число Фибоначчи, определяемое формулой: <tex> F_0 = F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} </tex>
|proof=
Для вершин со степенью 0 и 1 соответствующие деревья содержат не менее одной вершины, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.

Рассмотрим дерево степени <tex> k </tex>

Оно в худшем случае (удален ребенок со степенью <tex> k - 1 </tex>) содержит <tex> 1 + F_1 + F_2 + \dots + F_{k-2} </tex> вершин.

Эта сумма, в свою очередь, равна <tex> F_k </tex>
}}

Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то максимальная степень вершины в фибоначчиевой куче с <tex> N </tex> вершинами есть <tex> O(\log N) </tex>. Обозначим эту величину за <tex> D[H] </tex>.

Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).

Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за <tex> O(1) </tex>

Также в любой вершине хранятся поля <tex> degree[x], \, mark[x] </tex>: степень вершины(число ее детей) и пометка о том, потеряла ли вершина <tex> x </tex> ребенка после того, как она в последний раз сделалась чьим-либо потомком.

= Фибоначчиевы кучи =

{{Определение
|definition=
'''Фибоначчиева куча''' - набор фибоначчиевых деревьев.
}}

[[File:Fibonacci-heap.png|thumb|400px|Пример фибоначчиевой кучи]]

Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список (корневой список, root list). В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня.

Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче.

Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью методов амортизационного анализа.

= Операции =

== Потенциал ==

Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H]) </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> mark[x] == true </tex>). Подходящую константу <tex> C </tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.

== Создание кучи ==

Создается новый пустой корневой список, в <tex> min[H] </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.

== Слияние ==

Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.

== Вставка элемента ==

Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4.

== Извлечение минимума ==

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate ("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в куче) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.

=== "Уплотнение" (Consolidate) ===

Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(D[H]) </tex> вершин.

Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.

Затем происходит [[Биномиальная_куча#Union | процесс, аналогичный слиянию биномиальных куч ]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.

Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:

Пусть изначально в корневом списке было <tex> r </tex> вершин. Тогда в ходе операции <tex> Consolidate </tex> мы сделали <tex> O(r) </tex> слияний деревьев. Но эти <tex> O(r) </tex> слияний скомпенсируются уменьшением потенциала <tex> t_i + \Phi_i - \Phi_{i - 1} = r + C(O(D[H]) - r) = O(D[H]) </tex>. Остальных действий будет также <tex> O(D[H]) </tex>. Таким образом, учетная стоимость <tex> Consolidate: \, O(D[H]) </tex>.

На языке метода предоплаты: Положим у каждой вершины-ребенка удаленной монету. Это <tex> O(D[H]) </tex> действий. Теперь: у каждой вершины в корневом списке лежит монета, потратим ее на то, чтобы провести процедуру <tex> Consolidate </tex>. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого <tex> O(D[H]) + O(D[H]) = O(D[H]) </tex> действий.

== Уменьшение ключа ==

Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня; тогда дерево не придется сильно перестраивать. Для этого, при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:

# Проверяем, если новое значение ключа все же меньше значения ключа родителя, то все хорошо, и мы выходим.
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.

=== Вырезание вершины ===

При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> degree[p[x]] </tex>) и снимаем пометку с текущей вершины (<tex> mark[x] = false </tex>).

=== Каскадное вырезание ===

[[File:Cascading-cut.png|thumb|600px|Каскадное вырезание]]

Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> mark[x] == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.

Докажем, что амортизированное время работы операции "уменьшение ключа" есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> mark[x] == true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(k) + \Phi_i - \Phi_{i - 1} = O(k) + C(k - 2k + O(1)) </tex>. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало <tex> O(1) </tex>. Теперь также стало ясно, для чего в определении нашего потенциала количество вершин с пометкой <tex> mark[x] </tex> учитывается вдвое больше, чем количество вершин в корневом списке.

На языке метода предоплаты: Покажем, что взяв в начале 4 монеты, нам хватит этого для выполнения данной операции. Возьмем 4 монеты перед началом уменьшения ключа. Теперь 1 монету потратим на перенос в корневой список и релаксацию минимума, еще 1 - на то, чтобы положить монету у новой вершины в корневом списке. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда <tex> mark[p[x]] == false </tex>, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.

Иначе, <tex> mark[p[x]] == true </tex> и там лежит 2 монеты. 2 + 2 = 4, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.

На рисунке проиллюстрирован процесс понижения ключа вершины c 10 до 7. Серым помечены вершины с <tex> mark[x] == true </tex>.

== Удаление вершины ==

Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D[H]) = O(D[H]) </tex>.

Поскольку, ранее мы показали, что <tex> D[H] = O(log|H|) = O(logN) </tex>, то соответствующие оценки доказаны.

= Ссылки =

* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн - Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4
* http://ru.wikipedia.org/wiki/Фибоначчиева_куча
* http://www.intuit.ru/department/algorithms/dscm/7/2.html - INTUIT.ru
* Визуализаторы на rain.ifmo.ru: http://rain.ifmo.ru/cat/view.php/vis/heaps
* http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf

Фибоначчиева куча

2011-06-15T07:22:18Z

VasilevArtem: /* Каскадное вырезание */

'''Фибоначчиевы кучи''' - модификация [[Биномиальная_куча|биномиальных куч]], в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость <tex> O(1) </tex>. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций <tex> Extract\_min </tex> и <tex> Delete </tex> значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные <tex> k </tex> - ичные кучи на практике эффективнее.

= Фибоначчиевы деревья =
{{Определение
|definition=
'''Фибоначчиево дерево''' - биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
}}

{{Лемма
|statement=
Фибоначчиево дерево с вершиной степени <tex> k </tex> содержит не менее <tex> F_k </tex> (<tex> k </tex> число Фибоначчи) вершин
|proof=
Для вершин со степенью 0 и 1 соответствующие деревья содержат не менее одной вершины, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.

Рассмотрим дерево степени <tex> k </tex>

Оно в худшем случае (удален ребенок ранка <tex> k - 1 </tex>) содержит <tex> 1 + F_1 + F_2 + ... + F_{k-2} </tex> вершин.

Эта сумма, в свою очередь, равна <tex> F_k </tex>
}}

Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то максимальная степень вершины в фибоначчиевой куче с <tex> N </tex> вершинами есть <tex> O(logN) </tex>. Обозначим эту величину за <tex> D[H] </tex>.

Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).

Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за <tex> O(1) </tex>

Также в любой вершине хранятся поля <tex> degree[x], \, mark[x] </tex>: степень вершины(число ее детей) и пометка о том, потеряла ли вершина <tex> x </tex> ребенка после того, как она в последний раз сделалась чьим-либо потомком.

= Фибоначчиевы кучи =

{{Определение
|definition=
'''Фибоначчиева куча''' - набор фибоначчиевых деревьев.
}}

[[File:Fibonacci-heap.png|thumb|273px|Пример фибоначчиевой кучи]]

Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list). В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня.

Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче.

Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью методов амортизационного анализа.

= Операции =

== Потенциал ==

Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H]) </tex>, как количество элементов в корневом списке (<tex> t[H] </tex>) прибавить удвоенное количество вершин с <tex> mark[x] == true \, (m[H]) </tex>. Подходящую константу <tex> C </tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.

== Создание кучи ==

Создается новый пустой корневой список, в <tex> min[H] </tex> устанавливается значение <tex> null </tex>. Реальное время работы - <tex> O(1) </tex>.

== Слияние ==

Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы - <tex> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.

== Вставка элемента ==

Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4.

== Извлечение минимума ==

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в куче) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.

=== "Уплотнение" (Consolidate) ===

Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(D[H]) </tex> вершин.

Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.

Затем происходит [[Биномиальная_куча#Union | процесс, аналогичный слиянию биномиальных куч ]] добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.

Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:

Пусть изначально в корневом списке было <tex> r </tex> вершин. Тогда в ходе операции <tex> Consolidate </tex> мы сделали <tex> O(r) </tex> слияний деревьев. Но эти <tex> O(r) </tex> слияний скомпенсируются уменьшением потенциала <tex> t_i + \Phi_i - \Phi_{i - 1} = r + C(O(D[H]) - r) = O(D[H]) </tex>. Остальных действий будет также <tex> O(D[H]) </tex>. Таким образом, учетная стоимость <tex> Consolidate: \, O(D[H]) </tex>.

На языке метода предоплаты: Положим у каждой вершины-ребенка удаленной монету. Это <tex> O(D[H]) </tex> действий. Теперь: у каждой вершины в корневом списке лежит монета, потратим ее на то, чтобы провести процедуру <tex> Consolidate </tex>. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого <tex> O(D[H]) + O(D[H]) </tex> действий.

== Уменьшение ключа ==

Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Хотим, чтобы вершина не всплывала до корня. Для этого, при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:

# Проверяем, если новое значение ключа все же меньше значения ключа родителя, то все хорошо, и мы выходим.
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.

=== Вырезание вершины ===

При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем <tex> degree[p[x]] </tex> и снимаем пометку с текущей вершины (<tex> mark[x] = false </tex>).

=== Каскадное вырезание ===

[[File:Cascading-cut.png|thumb|273px|Каскадное вырезание]]

Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> mark[x] == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.

Докажем, что амортизированное время работы операции "уменьшение ключа" есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> mark[x] == true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(k) + \Phi_i - \Phi_{i - 1} = O(k) + C(k - 2 * k + O(1)) </tex>. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало <tex> O(1) </tex>. Теперь также стало ясно, для чего в определении нашего потенциала количество вершин с пометкой <tex> mark[x] </tex> учитывается вдвое больше, чем количество вершин в корневом списке.

На языке метода предоплаты: Покажем, что взяв в начале 4 монеты, нам хватит этого для выполнения данной операции. Возьмем 4 монеты перед началом уменьшения ключа. Теперь 1 монету потратим на перенос в корневой список и релаксацию минимума, еще 1 - на то, чтобы положить монету у новой вершины в корневом списке. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда <tex> mark[p[x]] == false </tex>, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.

Иначе, <tex> mark[p[x]] == true </tex> и там лежит 2 монеты. 2 + 2 = 4, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.

На рисунке проиллюстрирован процесс понижения ключа вершины c 10 до 7. Серым помечены вершины с <tex> mark[x] == true </tex>.

== Удаление вершины ==

Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D[H]) = O(D[H]) </tex>.

Поскольку, ранее мы показали, что <tex> D[H] = O(log|H|) = O(logN) </tex>, то соответствующие оценки доказаны.

= Ссылки =

* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн - Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4
* http://ru.wikipedia.org/wiki/Фибоначчиева_куча
* http://www.intuit.ru/department/algorithms/dscm/7/2.html - INTUIT.ru
* Визуализаторы на rain.ifmo.ru: http://rain.ifmo.ru/cat/view.php/vis/heaps
* http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf

Фибоначчиева куча

2011-06-15T07:19:21Z

VasilevArtem:

'''Фибоначчиевы кучи''' - модификация [[Биномиальная_куча|биномиальных куч]], в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость <tex> O(1) </tex>. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций <tex> Extract\_min </tex> и <tex> Delete </tex> значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные <tex> k </tex> - ичные кучи на практике эффективнее.

= Фибоначчиевы деревья =
{{Определение
|definition=
'''Фибоначчиево дерево''' - биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
}}

{{Лемма
|statement=
Фибоначчиево дерево с вершиной степени <tex> k </tex> содержит не менее <tex> F_k </tex> (<tex> k </tex> число Фибоначчи) вершин
|proof=
Для вершин со степенью 0 и 1 соответствующие деревья содержат не менее одной вершины, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.

Рассмотрим дерево степени <tex> k </tex>

Оно в худшем случае (удален ребенок ранка <tex> k - 1 </tex>) содержит <tex> 1 + F_1 + F_2 + ... + F_{k-2} </tex> вершин.

Эта сумма, в свою очередь, равна <tex> F_k </tex>
}}

Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то максимальная степень вершины в фибоначчиевой куче с <tex> N </tex> вершинами есть <tex> O(logN) </tex>. Обозначим эту величину за <tex> D[H] </tex>.

Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).

Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за <tex> O(1) </tex>

Также в любой вершине хранятся поля <tex> degree[x], \, mark[x] </tex>: степень вершины(число ее детей) и пометка о том, потеряла ли вершина <tex> x </tex> ребенка после того, как она в последний раз сделалась чьим-либо потомком.

= Фибоначчиевы кучи =

{{Определение
|definition=
'''Фибоначчиева куча''' - набор фибоначчиевых деревьев.
}}

[[File:Fibonacci-heap.png|thumb|273px|Пример фибоначчиевой кучи]]

Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list). В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня.

Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче.

Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью методов амортизационного анализа.

= Операции =

== Потенциал ==

Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H]) </tex>, как количество элементов в корневом списке (<tex> t[H] </tex>) прибавить удвоенное количество вершин с <tex> mark[x] == true \, (m[H]) </tex>. Подходящую константу <tex> C </tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.

== Создание кучи ==

Создается новый пустой корневой список, в <tex> min[H] </tex> устанавливается значение <tex> null </tex>. Реальное время работы - <tex> O(1) </tex>.

== Слияние ==

Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы - <tex> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.

== Вставка элемента ==

Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4.

== Извлечение минимума ==

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в куче) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.

=== "Уплотнение" (Consolidate) ===

Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(D[H]) </tex> вершин.

Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.

Затем происходит [[Биномиальная_куча#Union | процесс, аналогичный слиянию биномиальных куч ]] добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.

Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:

Пусть изначально в корневом списке было <tex> r </tex> вершин. Тогда в ходе операции <tex> Consolidate </tex> мы сделали <tex> O(r) </tex> слияний деревьев. Но эти <tex> O(r) </tex> слияний скомпенсируются уменьшением потенциала <tex> t_i + \Phi_i - \Phi_{i - 1} = r + C(O(D[H]) - r) = O(D[H]) </tex>. Остальных действий будет также <tex> O(D[H]) </tex>. Таким образом, учетная стоимость <tex> Consolidate: \, O(D[H]) </tex>.

На языке метода предоплаты: Положим у каждой вершины-ребенка удаленной монету. Это <tex> O(D[H]) </tex> действий. Теперь: у каждой вершины в корневом списке лежит монета, потратим ее на то, чтобы провести процедуру <tex> Consolidate </tex>. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого <tex> O(D[H]) + O(D[H]) </tex> действий.

== Уменьшение ключа ==

Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Хотим, чтобы вершина не всплывала до корня. Для этого, при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:

# Проверяем, если новое значение ключа все же меньше значения ключа родителя, то все хорошо, и мы выходим.
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.

=== Вырезание вершины ===

При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем <tex> degree[p[x]] </tex> и снимаем пометку с текущей вершины (<tex> mark[x] = false </tex>).

=== Каскадное вырезание ===

[[File:Cascading-cut.png|thumb|273px|Каскадное вырезание]]

Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> mark[x] == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.

Докажем, что амортизированное время работы операции "уменьшение ключа" есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> mark[x] == true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(k) + \Phi_i - \Phi_{i - 1} = O(k) + C(k - 2 * k + O(1)) </tex>. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало <tex> O(1) </tex>

На языке метода предоплаты: Покажем, что взяв в начале 4 монеты, нам хватит этого для выполнения данной операции. Возьмем 4 монеты перед началом уменьшения ключа. Теперь 1 монету потратим на перенос в корневой список и релаксацию минимума, еще 1 - на то, чтобы положить монету у новой вершины в корневом списке. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда <tex> mark[p[x]] == false </tex>, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.

Иначе, <tex> mark[p[x]] == true </tex> и там лежит 2 монеты. 2 + 2 = 4, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.

На рисунке проиллюстрирован процесс понижения ключа вершины c 10 до 7. Серым помечены вершины с <tex> mark[x] == true </tex>.

== Удаление вершины ==

Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D[H]) = O(D[H]) </tex>.

Поскольку, ранее мы показали, что <tex> D[H] = O(log|H|) = O(logN) </tex>, то соответствующие оценки доказаны.

= Ссылки =

* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн - Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4
* http://ru.wikipedia.org/wiki/Фибоначчиева_куча
* http://www.intuit.ru/department/algorithms/dscm/7/2.html - INTUIT.ru
* Визуализаторы на rain.ifmo.ru: http://rain.ifmo.ru/cat/view.php/vis/heaps
* http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf

Фибоначчиева куча

2011-06-15T07:12:28Z

VasilevArtem: /* Фибоначчиевы деревья */

'''Фибоначчиевы кучи''' - модификация [[Биномиальная_куча|биномиальных куч]], в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость <tex> O(1) </tex>. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций <tex> Extract\_min </tex> и <tex> Delete </tex> значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные <tex> k </tex> - ичные кучи на практике эффективнее.

= Фибоначчиевы деревья =
{{Определение
|definition=
'''Фибоначчиево дерево''' - биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
}}

{{Лемма
|statement=
Фибоначчиево дерево с вершиной степени <tex> k </tex> содержит не менее <tex> F_k </tex> (<tex> k </tex> число Фибоначчи) вершин
|proof=
Для вершин со степенью 0 и 1 соответствующие деревья содержат не менее одной вершины, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.

Рассмотрим дерево степени <tex> k </tex>

Оно в худшем случае (удален ребенок ранка <tex> k - 1 </tex>) содержит <tex> 1 + F_1 + F_2 + ... + F_{k-2} </tex> вершин.

Эта сумма, в свою очередь, равна <tex> F_k </tex>
}}

Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то максимальная степень вершины в фибоначчиевой куче с <tex> N </tex> вершинами есть <tex> O(logN) </tex>.

Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).

Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за <tex> O(1) </tex>

Также в любой вершине хранятся поля <tex> degree[x], \, mark[x] </tex>: степень вершины(число ее детей) и пометка о том, потеряла ли вершина <tex> x </tex> ребенка после того, как она в последний раз сделалась чьим-либо потомком.

= Фибоначчиевы кучи =

{{Определение
|definition=
'''Фибоначчиева куча''' - набор фибоначчиевых деревьев.
}}

[[File:Fibonacci-heap.png|thumb|273px|Пример фибоначчиевой кучи]]

Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list). В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня.

Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче.

Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью методов амортизационного анализа.

= Операции =

== Потенциал ==

Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H]) </tex>, как количество элементов в корневом списке (<tex> t[H] </tex>) прибавить удвоенное количество вершин с <tex> mark[x] == true \, (m[H]) </tex>. Подходящую константу <tex> C </tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.

== Создание кучи ==

Создается новый пустой корневой список, в <tex> min[H] </tex> устанавливается значение <tex> null </tex>. Реальное время работы - <tex> O(1) </tex>.

== Слияние ==

Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы - <tex> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.

== Вставка элемента ==

Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4.

== Извлечение минимума ==

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.

=== "Уплотнение" (Consolidate) ===

Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(D[H]) </tex> вершин.

Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.

Затем происходит [http://neerc.ifmo.ru/mediawiki/index.php/Биномиальная_куча#Union процесс, аналогичный слиянию биномиальных куч ] добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.

Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:

Пусть изначально в корневом списке было <tex> r </tex> вершин. Тогда в ходе операции <tex> Consolidate </tex> мы сделали <tex> O(r) </tex> слияний деревьев. Но эти <tex> O(r) </tex> слияний скомпенсируются уменьшением потенциала <tex> t_i + \Phi_i - \Phi_{i - 1} = r + C(O(D[H]) - r) = O(D[H]) </tex>. Остальных действий будет также <tex> O(D[H]) </tex>. Таким образом, учетная стоимость <tex> Consolidate: \, O(D[H]) </tex>.

На языке метода предоплаты: Положим у каждой вершины-ребенка удаленной монету. Это <tex> O(D[H]) </tex> действий. Теперь: у каждой вершины в корневом списке лежит монета, потратим ее на то, чтобы провести процедуру <tex> Consolidate </tex>. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого <tex> O(D[H]) + O(D[H]) </tex> действий.

== Уменьшение ключа ==

Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Хотим, чтобы вершина не всплывала до корня. Для этого, при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:

# Проверяем, если новое значение ключа все же меньше значения ключа родителя, то все хорошо, и мы выходим.
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.

=== Вырезание вершины ===

При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем <tex> degree[p[x]] </tex> и снимаем пометку с текущей вершины (<tex> mark[x] = false </tex>).

=== Каскадное вырезание ===

[[File:Cascading-cut.png|thumb|273px|Каскадное вырезание]]

Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> mark[x] == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.

Докажем, что амортизированное время работы операции "уменьшение ключа" есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> mark[x] == true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(k) + \Phi_i - \Phi_{i - 1} = O(k) + C(k - 2 * k + O(1)) </tex>. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало <tex> O(1) </tex>

На языке метода предоплаты: Покажем, что взяв в начале 4 монеты, нам хватит этого для выполнения данной операции. Возьмем 4 монеты перед началом уменьшения ключа. Теперь 1 монету потратим на перенос в корневой список и релаксацию минимума, еще 1 - на то, чтобы положить монету у новой вершины в корневом списке. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда <tex> mark[p[x]] == false </tex>, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.

Иначе, <tex> mark[p[x]] == true </tex> и там лежит 2 монеты. 2 + 2 = 4, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.

На рисунке проиллюстрирован процесс понижения ключа вершины c 10 до 7. Серым помечены вершины с <tex> mark[x] == true </tex>.

== Удаление вершины ==

Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D[H]) = O(D[H]) </tex>.

Поскольку, ранее мы показали, что <tex> D[H] = O(log|H|) = O(logN) </tex>, то соответствующие оценки доказаны.

= Ссылки =

* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн - Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4
* http://ru.wikipedia.org/wiki/Фибоначчиева_куча
* http://www.intuit.ru/department/algorithms/dscm/7/2.html - INTUIT.ru
* Визуализаторы на rain.ifmo.ru: http://rain.ifmo.ru/cat/view.php/vis/heaps
* http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf

Фибоначчиева куча

2011-06-15T07:10:31Z

VasilevArtem:

'''Фибоначчиевы кучи''' - модификация [[Биномиальная_куча|биномиальных куч]], в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость <tex> O(1) </tex>. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций <tex> Extract\_min </tex> и <tex> Delete </tex> значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные <tex> k </tex> - ичные кучи на практике эффективнее.

= Фибоначчиевы деревья =
{{Определение
|definition=
'''Фибоначчиево дерево''' - биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
}}

{{Лемма
|statement=
Фибоначчиево дерево с вершиной степени <tex> k </tex> содержит не менее <tex> F_k </tex> (<tex> k </tex> число Фибоначчи) вершин
|proof=
Для рангов 0 и 1 соответствующие деревья содержат не менее одной вершины, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.

Рассмотрим дерево степени <tex> k </tex>

Оно в худшем случае (удален ребенок ранка <tex> k - 1 </tex>) содержит <tex> 1 + F_1 + F_2 + ... + F_{k-2} </tex> вершин.

Эта сумма, в свою очередь, равна <tex> F_k </tex>
}}

Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то максимальная степень вершины в фибоначчиевой куче с <tex> N </tex> вершинами есть <tex> O(logN) </tex>.

Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).

Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за <tex> O(1) </tex>

Также в любой вершине хранятся поля <tex> degree[x], \, mark[x] </tex>: степень вершины(число ее детей) и пометка о том, потеряла ли вершина <tex> x </tex> ребенка после того, как она в последний раз сделалась чьим-либо потомком.

= Фибоначчиевы кучи =

{{Определение
|definition=
'''Фибоначчиева куча''' - набор фибоначчиевых деревьев.
}}

[[File:Fibonacci-heap.png|thumb|273px|Пример фибоначчиевой кучи]]

Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list). В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня.

Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче.

Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью методов амортизационного анализа.

= Операции =

== Потенциал ==

Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H]) </tex>, как количество элементов в корневом списке (<tex> t[H] </tex>) прибавить удвоенное количество вершин с <tex> mark[x] == true \, (m[H]) </tex>. Подходящую константу <tex> C </tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.

== Создание кучи ==

Создается новый пустой корневой список, в <tex> min[H] </tex> устанавливается значение <tex> null </tex>. Реальное время работы - <tex> O(1) </tex>.

== Слияние ==

Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы - <tex> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.

== Вставка элемента ==

Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4.

== Извлечение минимума ==

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.

=== "Уплотнение" (Consolidate) ===

Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(D[H]) </tex> вершин.

Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.

Затем происходит [http://neerc.ifmo.ru/mediawiki/index.php/Биномиальная_куча#Union процесс, аналогичный слиянию биномиальных куч ] добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.

Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:

Пусть изначально в корневом списке было <tex> r </tex> вершин. Тогда в ходе операции <tex> Consolidate </tex> мы сделали <tex> O(r) </tex> слияний деревьев. Но эти <tex> O(r) </tex> слияний скомпенсируются уменьшением потенциала <tex> t_i + \Phi_i - \Phi_{i - 1} = r + C(O(D[H]) - r) = O(D[H]) </tex>. Остальных действий будет также <tex> O(D[H]) </tex>. Таким образом, учетная стоимость <tex> Consolidate: \, O(D[H]) </tex>.

На языке метода предоплаты: Положим у каждой вершины-ребенка удаленной монету. Это <tex> O(D[H]) </tex> действий. Теперь: у каждой вершины в корневом списке лежит монета, потратим ее на то, чтобы провести процедуру <tex> Consolidate </tex>. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого <tex> O(D[H]) + O(D[H]) </tex> действий.

== Уменьшение ключа ==

Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Хотим, чтобы вершина не всплывала до корня. Для этого, при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:

# Проверяем, если новое значение ключа все же меньше значения ключа родителя, то все хорошо, и мы выходим.
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.

=== Вырезание вершины ===

При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем <tex> degree[p[x]] </tex> и снимаем пометку с текущей вершины (<tex> mark[x] = false </tex>).

=== Каскадное вырезание ===

[[File:Cascading-cut.png|thumb|273px|Каскадное вырезание]]

Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> mark[x] == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.

Докажем, что амортизированное время работы операции "уменьшение ключа" есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> mark[x] == true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(k) + \Phi_i - \Phi_{i - 1} = O(k) + C(k - 2 * k + O(1)) </tex>. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало <tex> O(1) </tex>

На языке метода предоплаты: Покажем, что взяв в начале 4 монеты, нам хватит этого для выполнения данной операции. Возьмем 4 монеты перед началом уменьшения ключа. Теперь 1 монету потратим на перенос в корневой список и релаксацию минимума, еще 1 - на то, чтобы положить монету у новой вершины в корневом списке. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда <tex> mark[p[x]] == false </tex>, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.

Иначе, <tex> mark[p[x]] == true </tex> и там лежит 2 монеты. 2 + 2 = 4, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.

На рисунке проиллюстрирован процесс понижения ключа вершины c 10 до 7. Серым помечены вершины с <tex> mark[x] == true </tex>.

== Удаление вершины ==

Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D[H]) = O(D[H]) </tex>.

Поскольку, ранее мы показали, что <tex> D[H] = O(log|H|) = O(logN) </tex>, то соответствующие оценки доказаны.

= Ссылки =

* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн - Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4
* http://ru.wikipedia.org/wiki/Фибоначчиева_куча
* http://www.intuit.ru/department/algorithms/dscm/7/2.html - INTUIT.ru
* Визуализаторы на rain.ifmo.ru: http://rain.ifmo.ru/cat/view.php/vis/heaps
* http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf

Файл:Cascading-cut.png

2011-06-15T07:02:59Z

VasilevArtem: Каскадное вырезание

Каскадное вырезание

Файл:Fibonacci-heap.png

2011-06-15T07:01:55Z

VasilevArtem: Пример фибоначчиевой кучи.

Пример фибоначчиевой кучи.

Умножение перестановок, обратная перестановка, группа перестановок

2010-12-17T10:36:43Z

VasilevArtem:

=Умножение перестановок=

{{Определение
|definition=
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу:

<tex> (a \circ b)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a \circ (b \circ c))_i = ((a \circ b) \circ c)_i </tex>

|proof=

Доказывается простым раскрытием скобок.

# <tex> (a \circ (b \circ c))_i = a_{(b \circ c)_i} = a_{b_{c_i}} </tex>
# <tex> ((a \circ b) \circ c)_i = (a \circ b)_{c_i} = a_{b_{c_i}} </tex>

}}

==Пример==

<tex dpi="130"> a = {{1, 2, 3, 4, 5, 6} \choose {2, 5, 6, 3, 1, 4}},
b = {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} </tex>

<tex dpi="130"> {{1, 2, 3, 4, 5, 6} \choose {2, 5, 6, 3, 1, 4}} \circ {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} =
{{4, 1, 3, 6, 5, 2} \choose {3, 2, 6, 4, 1, 5}} \circ {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} =
{{1, 2, 3, 4, 5, 6} \choose {3, 2, 6, 4, 1, 5}}
</tex>

=Обратная перестановка=

{{Определение
|definition=

Обратной перестановкой <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1} \circ a)_i = (a \circ a^{-1})_i = i </tex>

}}

При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

{{Определение
|definition=
Перестановка, равная своей обратной, называется инволюцией:

<tex> a_i = a^{-1}_i \Rightarrow (a \circ a ^{-1})_i = (a \circ a)_i = a_{a_i} = i </tex>

}}

=Группа перестановок=

{{Определение
|definition=
Группа - алгебраическая структура, удовлетворяющая следующим свойствам:

Пусть <tex> M </tex> - множество, <tex> M = \{ x, y, z, ... \} </tex>, и на этом множестве задана бинарная операция <tex> \circ </tex>, такая, что <tex> \forall x, y \in M: x \circ y = z \in M </tex>.

Тогда для группы выполняются:

# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> - ассоциативность соответствующей бинарной операции.
# Существование нейтрального элемента <tex> e </tex> относительно <tex> \circ </tex>: <tex> \forall g \in M: g \circ e = e \circ g = g </tex>
# Существование обратного элемента <tex> g^{-1} </tex> : <tex> \forall g \in M: \exists g^{-1} \in M: g \circ g^{-1} = g^{-1} \circ g = e </tex>

}}

{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>).
|proof=
Свойства 1 и 3 выполняются уже по пунктам 1 и 2 выше, а в качестве нейтрального элемента можно брать тождественную перестановку (<tex> \pi_i = i </tex>).
}}

[[Теорема Кэли]] утверждает, что любая конечная группа изоморфна подгруппе соответствующей группе перестановок.

Участник:Rybak

2010-12-17T08:12:21Z

VasilevArtem: /* Матан */

Андрей Рыбак, группа 1538

== Матан ==

*[[Математический анализ 1 курс]]

*[[Отображения]]

*[[Грани числовых множеств]]

*[[Мощность множества]]

# [[Предел последовательности]]
#[[Три основных теоремы о пределах]]
#[[Метрическое пространство]]
#[[Предел отображения в метрическом пространстве]]

Умножение перестановок, обратная перестановка, группа перестановок

2010-12-16T23:26:15Z

VasilevArtem: Новая страница: «=Умножение перестановок= {{Определение |definition= Умножением (композицией) перестановок назы…»

=Умножение перестановок=

{{Определение
|definition=
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу:

<tex> (a \circ b)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a \circ (b \circ c))_i = ((a \circ b) \circ c)_i </tex>

|proof=

Доказывается простым раскрытием скобок.

# <tex> (a \circ (b \circ c))_i = a_{(b \circ c)_i} = a_{b_{c_i}} </tex>
# <tex> ((a \circ b) \circ c)_i = (a \circ b)_{c_i} = a_{b_{c_i}} </tex>

}}

==Пример==

<tex dpi="130"> a = {{1, 2, 3, 4, 5, 6} \choose {2, 5, 6, 3, 1, 4}},
b = {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} </tex>

<tex dpi="130"> {{1, 2, 3, 4, 5, 6} \choose {2, 5, 6, 3, 1, 4}} \circ {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} =
{{4, 1, 3, 6, 5, 2} \choose {3, 2, 6, 4, 1, 5}} \circ {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} =
{{1, 2, 3, 4, 5, 6} \choose {3, 2, 6, 4, 1, 5}}
</tex>

=Обратная перестановка=

{{Определение
|definition=

Обратной перестановкой <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1} \circ a)_i = (a \circ a^{-1})_i = i </tex>

}}

При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

=Группа перестановок=

{{Определение
|definition=
Группа - алгебраическая структура, удовлетворяющая следующим свойствам:

Пусть <tex> M </tex> - множество, <tex> M = \{ x, y, z, ... \} </tex>, и на этом множестве задана бинарная операция <tex> \circ </tex>, такая, что <tex> \forall x, y \in M: x \circ y = z \in M </tex>.

Тогда для группы выполняются:

# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> - ассоциативность соответствующей бинарной операции.
# Существование нейтрального элемента <tex> e </tex> относительно <tex> \circ </tex>: <tex> \forall g \in M: g \circ e = e \circ g = g </tex>
# Существование обратного элемента <tex> g^{-1} </tex> : <tex> \forall g \in M: \exists g^{-1} \in M: g \circ g^{-1} = g^{-1} \circ g = e </tex>

}}

{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>).
|proof=
Свойства 1 и 3 выполняются уже по пунктам 1 и 2 выше, а в качестве нейтрального элемента можно брать тождественную перестановку (<tex> \pi_i = i </tex>).
}}

[[Теорема Кэли]] утверждает, что любая конечная группа изоморфна подгруппе соответствующей группе перестановок.

Дискретная математика и алгоритмы

2010-12-16T13:12:27Z

VasilevArtem:

== Отношения ==
*Определение отношения
*Степень отношений
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
*[[Транзитивное отношение]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]

== Булевы функции ==
*[[Определение булевой функции]]
*[[Примеры булевых функций|Примеры булевых функций: все функции от нуля, одной и двух переменных]]
*[[Подстановка одной функции в другую, отождествление переменных]]
*[[Представление функции формулой, полные системы функций]]
*[[СДНФ]]
*[[СКНФ]]
*[[Полином Жегалкина]]
*[[Теорема Поста о полной системе функций]]
*[[Сокращенная и минимальная ДНФ]]
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]

== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Изменение размера оптимальной схемы при переходе к другому базису]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]

== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]
*[[Алгоритм Хаффмана]]

== Алгоритмы сжатия ==
*[[Алгоритм LZW]]
*[[Алгоритмы LZ77 и LZ78]]
*[[Преобразование Барроуза-Уиллера]]
*[[Преобразование MTF]]
*[[Расстояние Хэмминга]]
*[[Избыточное кодирование, код Хэмминга]]

== Комбинаторика ==
*[[Комбинаторные объекты]]
*[[Лексикографический порядок]]
*[[Формула включения-исключения]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Получение номера об объекту и объекта по номеру]]
*[[Получение следующего объекта]]
*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Цепные коды]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
*[[Таблица инверсий]]
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
*[[Теорема Кэли]]
*[[Матричное представление перестановок]]
*[[Задача о минимуме/максимуме скалярного произведения]]
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
*[[Поиск наибольшей возрастающей подпоследовательности и т. д.]]

== Динамическое программирование ==
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о перемножении матриц]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
*[[Метод четырех русских для умножения матриц]]
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о редакционном расстоянии, алгоритм Левенштейна]]
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]

== Теория вероятности ==
*[[Формула Байеса]]
*[[Дискретная случайная величина]]
*[[Условная вероятность]]
*[[Формула полной вероятности]]

Три основных теоремы о пределах

2010-12-10T19:00:46Z

VasilevArtem:

{{В разработке}}

Лекция от 27 сентября 2010.
=Теорема Вейерштрасса=
{{Определение
|definition=
Последовательность <tex> a \uparrow </tex> (<tex> a </tex> ''возрастает''), если <tex> \forall n: a_n \le a_{n+1} </tex>

Последовательность <tex> a \downarrow </tex> (<tex> a </tex> ''убывает''), если <tex> \forall n: a_n \ge a_{n+1} </tex>
}}

{{Определение
|definition=
Последовательность <tex> a_n </tex> ''ограничена'', если <tex> \exists a \in \mathbb R: |a_n| \le a </tex>

<tex> a_n </tex> - ''ограничена сверху'', если <tex> \exists a \in \mathbb R: a_n \le a </tex>

<tex> a_n </tex> - ''ограничена снизу'', если <tex> \exists a \in \mathbb R: a_n \le a </tex>
}}

{{Теорема
|author=Вейерштрасс
|statement=
Пусть <tex> a_n \uparrow </tex> и <tex> a_n </tex> ограничена сверху. Тогда она сходится. (Аналогично, если <tex> a_n \downarrow </tex>, <tex> a_n </tex> - ограничена снизу).
|proof=
<tex> \exists d \in \mathbb R: d = \sup\limits_{n \in \mathbb N} a_n </tex>, поскольку <tex> a_n </tex> - ограничена сверху, и <tex> d </tex> - конечен, так как <tex> a_n </tex> - ограничена сверху.

По определению <tex> \sup a_n </tex>:

<tex> \forall \varepsilon > 0, \exists N: d - \varepsilon < a_n </tex>

Так как <tex> a_n \uparrow </tex>, то <tex> \forall n > N: a_n \ge a_N </tex>

<tex> d - \varepsilon < a_n \Rightarrow d - \varepsilon \le a_n \le d + \varepsilon </tex>

Итак: <tex> \forall \varepsilon > 0: \exists N: \forall n > N: |d - a_n| \le \varepsilon \Rightarrow d = \lim a_n </tex>
}}

==Пример==

<tex> a_n = (1 + \frac 1n)^n = \sum\limits_{k=0}^n C_n^k \frac {1}{n^k} </tex>

<tex> C_n^k = \frac {n!}{k!(n-k)!} = \frac {1}{k!} (n(n-1)(n-2)...(n-k+1)) </tex>

Разделив данное равенство на <tex> n ^ k </tex>, получаем:

<tex> a_n = \sum\limits_{k=0}^n (1 - \frac 0n)(1 - \frac 1n)...(1-\frac {k-1}{n}) \qquad {(*)} </tex>

<tex> a_{n+1} = \sum\limits_{k=0}^{n+1} (1 - \frac {0}{n+1})(1 - \frac {1}{n+1})...(1-\frac {k-1}{n+1}) </tex>

Сравнивая эти две суммы, можно заметить, что все слагаемые положительны, и каждое текущее слагаемое второй суммы больше соответствующего слагаемого 2 суммы, из чего следует, что <tex> a_{n+1} > a_n \Rightarrow a_n \uparrow </tex>

Теперь покажем, что <tex> a_n </tex> ограничена.

<tex> 2 = a_1, a_n \uparrow \Rightarrow \forall n \ge 1: a_n \ge 2 </tex>

Если вернуться к <tex> (*) </tex>, то видно, что все скобки не превосходят 1:

<tex> a_n < \sum\limits_{k=0}^n \frac{1}{k!} = \frac 1{0!} + \frac 1{1!} + \sum\limits_{k=2}^n \frac 1{k!} </tex>

Пользуясь неравенством <tex> k! > 2 ^ {k - 1} </tex>, получаем:

<tex> a_n < \frac 1{0!} + \frac 1{1!} + \sum\limits_{k=2}^n (\frac 12)^{k-1} < 1 + 1 + 1 = 3</tex> (по формуле геометрической прогрессии: <tex> \sum\limits_{i=1}^n (\frac 12)^k < 1 </tex>).

<tex> 2 < a_n < 3 \Rightarrow </tex> По теореме Вейерштрасса, <tex> \exists \lim\limits_{n \rightarrow \infty} (1 + \frac 1n)^n </tex>. Его обозначают числом <tex> e </tex>. Также только что мы показали, что <tex> 2 < e < 3 </tex>.

=Теорема Больцано=

{{Определение
|definition= Если дана последовательность <tex> \{ a_n \} </tex> и <tex> \phi: \mathbb N \rightarrow \mathbb N, \phi \uparrow </tex>, тогда
тогда последовательность <tex> b_n = a_{\phi_(n)} </tex> называется ''подпоследовательностью'' исходной последовательности.
}}

===Пример===

<tex> b_n = a_{2n} : b_1 = a_2, b_2 = a_4, \dots </tex>

В силу строго возрастания <tex> \phi \uparrow </tex>, очевидно, что если <tex> a_n \rightarrow k </tex>, то <tex> a_{\phi(n)} \rightarrow k </tex>. Любая подпоследовательность сходится к тому же пределу.

{{Теорема
|author=Больцано
|statement=Из любой ограниченной подпоследовательности можно выделить сходящуюся подпоследовательность
|proof= Применим способ половинного деления, основанный на принципе вложенных отрезков: если строить систему отрезков путем деления предыдущего отрезка пополам, то получится система вложенных отрезков, и так до бесконечности..

Пересечение всех отрезков - 1 точка (по свойству системы вложенных отрезков).

Раз <tex> a_n </tex> ограничена, то <tex> \forall n: a_n \in \Delta_0 = [c, d] </tex>

Делим его пополам, тогда в одной из двух половин этого отрезка будет содержаться бесконечно много <tex> a_n </tex>. Назовем его <tex> \Delta_1, |\Delta_1| = \frac 12 |\Delta_0| </tex>

Далее делим <tex> \Delta_1 </tex> на 2 части и называем <tex> \Delta_2 </tex> ту половину, в которой содержится бесконечно много <tex> a_n </tex>. Продолжаем этот процесс до бесконечности.

<tex> \Delta_{n+1} \subset \Delta_n </tex>

<tex> |\Delta_n| \rightarrow 0 </tex>

По принципу вложенных отрезков: <tex> \exists !d^*: d^* \in \bigcap\limits_{n=0}^{\infty} \Delta_n </tex>

<tex> \Delta_n = [c_n, d_n], c_n, d_n \rightarrow d^* </tex>

Построим следующую таблицу:

<tex> (a_{00}, a_{01}, a_{02}, \dots) \in \Delta_0 </tex>

<tex> (a_{10}, a_{11}, a_{12}, \dots) \in \Delta_1 </tex>

<tex> (a_{20}, a_{21}, a_{22}, \dots) \in \Delta_2 </tex>

<tex> \dots </tex>

Каждая последующая строчка составляется из предыдущей. Выбирая подпоследовательность так, чтобы номер следующего элемента был строго больше номера предыдущего выбранного элемента в предыдущей строчка.

Получили подпоследовательность <tex> b_n </tex>:

<tex> c_n \le b_n \le \Rightarrow b_n \rightarrow d^* </tex>

<tex> b_n </tex> - подпоследовательность <tex> a_n </tex> и <tex> b_n </tex> сходится.

}}

=Теорема Коши=

Пункт третий связан с одним из фундаментальных свойств числовой оси - ''полнотой''.

{{Определение
|definition=
Последовательность <tex> a_n </tex> ''сходится в себе'':

<tex> \lim\limits_{m,n \rightarrow \infty} |a_n - a_m| = 0 </tex>

<tex> \forall \varepsilon > 0, \exists N \in \mathbb N: \forall n, m > N \Rightarrow |a_n - a_m| < \varepsilon </tex>

}}

{{Утверждение
|statement=Если <tex> a_n </tex> сходится, то <tex> a_n </tex> сходится в себе.
|proof=
Пусть <tex> a_n \rightarrow a, |a_n - a_n| < |a_n - a| + |a_m - a| < \varepsilon </tex>, если в определении предела для <tex> a_n \rightarrow a </tex> положить <tex> \varepsilon ' = \frac {\varepsilon}2 </tex>, тогда каждое слагаемое не больше <tex> \frac {\varepsilon}2 </tex>.
}}

{{Теорема
|author=Коши
|statement=Если числовая последовательность сходится в себе, то она сходится.
|proof=
Положим <tex> \varepsilon = 1 \Rightarrow \exists N: \forall n \ge N: |a_n - a_N| < 1 </tex>.

Вне <tex> (a_N - 1, a_N + 1) </tex> может оказаться самое большее <tex> a_1, a_2, ..., a_{N - 1} \Rightarrow </tex> последовательность <tex> \{ a_n \} </tex> - ограничена. Раз она ограничена, по теореме Больцано, в ней можно выделить сходящуюся подпоследовательность.

<tex> \exists a_{n_k} \rightarrow a </tex> при <tex> k \rightarrow \infty (a_{phi(n)} = a_{n_k}) </tex>.

<tex> |a_n - a| \le |a_n - a_{m_k}| + |a_{m_k} - a| </tex>

По сходимости в себе: <tex> \forall \varepsilon > 0, \exists N: \forall m, n > N: |a_n - a_m| < \frac {\varepsilon}2 </tex>

По сходимости <tex> a_{n_k}: \exists M: \forall k > M \Rightarrow |a_{n_k} - a| < \frac {\varepsilon}2 </tex>

Так как <tex> m_k </tex> - неограниченно возрастающая последовательность натуральных чисел <tex> \exists k_0 > M, m_{k_0} > N </tex>, так как <tex> M, N </tex> заданы.

Тогда для такого <tex> k_0 </tex> и всех <tex> N, M : |a_n - a| \le |a_n - a_{m_{k_0}}| + |a_{m_{k_0}} - a| < \varepsilon \Rightarrow \lim\limits_{n \rightarrow \infty} a_n = a </tex>

}}

<tex> \{ a_n \} </tex> сходится <tex> \Leftrightarrow \{ a_n \} </tex> сходится в себе.

Такое свойство принято называть полнотой вещественной оси, также - критерий Коши существования предела числовой последовательности.

[[Категория:Математический анализ 1 курс]]

Три основных теоремы о пределах

2010-12-09T03:41:02Z

VasilevArtem: Т. Вейерштрасса + пример

Лекция от 27 сентября 2010.
=Теорема Вейерштрасса=
{{Определение
|definition=
Последовательность <tex> a \uparrow </tex> (<tex> a </tex> ''возрастает''), если <tex> \forall n: a_n \le a_{n+1} </tex>

Последовательность <tex> a \downarrow </tex> (<tex> a </tex> ''убывает''), если <tex> \forall n: a_n \ge a_{n+1} </tex>
}}

{{Определение
|definition=
Последовательность <tex> a_n </tex> ''ограничена'', если <tex> \exists a \in \mathbb R: |a_n| \le a </tex>

<tex> a_n </tex> - ''ограничена сверху'', если <tex> \exists a \in \mathbb R: a_n \le a </tex>

<tex> a_n </tex> - ''ограничена снизу'', если <tex> \exists a \in \mathbb R: a_n \le a </tex>
}}

{{Теорема
|author=Вейерштрасс
|statement=
Пусть <tex> a_n \uparrow </tex> и <tex> a_n </tex> ограничена сверху. Тогда она сходится. (Аналогично, если <tex> a_n \downarrow </tex>, <tex> a_n </tex> - ограничена снизу).
|proof=
<tex> \exists d \in \mathbb R: d = \sup\limits_{n \in \mathbb N} a_n </tex>, поскольку <tex> a_n </tex> - ограничена сверху, и <tex> d </tex> - конечен, так как <tex> a_n </tex> - ограничена сверху.

По определению <tex> \sup a_n </tex>:

<tex> \forall \varepsilon > 0, \exists N: d - \varepsilon < a_n </tex>

Так как <tex> a_n \uparrow </tex>, то <tex> \forall n > N: a_n \ge a_N </tex>

<tex> d - \varepsilon < a_n \Rightarrow d - \varepsilon \le a_n \le d + \varepsilon </tex>

Итак: <tex> \forall \varepsilon > 0: \exists N: \forall n > N: |d - a_n| \le \varepsilon \Rightarrow d = \lim a_n </tex>
}}

==Пример==

<tex> a_n = (1 + \frac 1n)^n = \sum\limits_{k=0}^n C_n^k \frac {1}{n^k} </tex>

<tex> C_n^k = \frac {n!}{k!(n-k)!} = \frac {1}{k!} (n(n-1)(n-2)...(n-k+1)) </tex>

Разделив данное равенство на <tex> n ^ k </tex>, получаем:

<tex> a_n = \sum\limits_{k=0}^n (1 - \frac 0n)(1 - \frac 1n)...(1-\frac {k-1}{n}) \qquad {(*)} </tex>

<tex> a_{n+1} = \sum\limits_{k=0}^{n+1} (1 - \frac {0}{n+1})(1 - \frac {1}{n+1})...(1-\frac {k-1}{n+1}) </tex>

Сравнивая эти две суммы, можно заметить, что все слагаемые положительны, и каждое текущее слагаемое второй суммы больше соответствующего слагаемого 2 суммы, из чего следует, что <tex> a_{n+1} > a_n \Rightarrow a_n \uparrow </tex>

Теперь покажем, что <tex> a_n </tex> ограничена.

<tex> 2 = a_1, a_n \uparrow \Rightarrow \forall n \ge 1: a_n \ge 2 </tex>

Если вернуться к <tex> (*) </tex>, то видно, что все скобки не превосходят 1:

<tex> a_n < \sum\limits_{k=0}^n \frac{1}{k!} = \frac 1{0!} + \frac 1{1!} + \sum\limits_{k=2}^n \frac 1{k!} </tex>

Пользуясь неравенством <tex> k! > 2 ^ {k - 1} </tex>, получаем:

<tex> a_n < \frac 1{0!} + \frac 1{1!} + \sum\limits_{k=2}^n (\frac 12)^{k-1} < 1 + 1 + 1 = 3</tex> (по формуле геометрической прогрессии: <tex> \sum\limits_{i=1}^n (\frac 12)^k < 1 </tex>).

<tex> 2 < a_n < 3 \Rightarrow </tex> По теореме Вейерштрасса, <tex> \exists \lim\limits_{n \rightarrow \infty} (1 + \frac 1n)^n </tex>. Его обозначают числом <tex> e </tex>. Также только что мы показали, что <tex> 2 < e < 3 </tex>.

Метрическое пространство

2010-12-07T07:35:52Z

VasilevArtem:

{{В разработке}}
==Метрика и метрическое пространство==

Пусть <tex>X</tex> {{---}} абстрактное [[Множества|множество]].

<tex> X \times X = \{ (x_1, x_2): x_i \in X \} </tex> {{---}} прямое произведение множества <tex>X</tex> на себя

{{Определение
|definition=
Отображение <tex> \rho : X \times X \rightarrow \mathbb{R^+} </tex> {{---}} называется '''метрикой''' на <tex>X</tex>, если выполняются аксиомы
# <tex> \rho (x, y) \ge 0 ;\ \rho (x, y) = 0 \iff x = y </tex>
# <tex> \rho (x, y) = \rho (y, x) </tex>
# <tex> \rho (x, y) \le \rho (x, z) + \rho (z, y) </tex> {{---}} неравенство треугольника
}}

Если на <tex>X</tex> определена метрика, то пара <tex>(X, \rho)</tex> называется ''метрическим пространством'', аббревиатура {{---}} ''МП''.

=== Примеры ===

Числовая ось: <tex> X = \mathbb{R}; x, y \in X \Rightarrow \rho (x, y) = |x - y| </tex>

<tex> X = \mathbb{R}^n = \underbrace{\mathbb{R} \times \mathbb{R} \times \dots \times \mathbb{R}}_{n} ; \overrightarrow{x} = (x_1, \dots, x_n) </tex>
#<tex> \rho_1 (x, y) = \sum\limits_{k = 1}^n |x_k - y_k| </tex>
#<tex> \rho_2 (x, y) = \max\limits_{k = 1 \dots n} |x_k - y_k| </tex>

То есть, одно и то же множество можно по-разному превращать в метрическое пространство.

== Открытые шары ==

Для метрических пространств основное значение имеют открытые шары.

{{Определение
|definition=
Пусть <tex> (X, \rho) </tex> {{---}} метрическое пространство, пусть <tex>\ \ r \in \mathbb{R},\ r > 0,\ a \in X </tex>, тогда открытый шар радиуса
<tex>\ r\ </tex> в точке <tex>\ a\ </tex> {{---}} это множество <tex> V_r(a) = \{x \in X| \rho(x, a) < r \} </tex>
}}

=== Пример ===

<tex> X = \mathbb{R}: V_r(a) = (a - r; a + r) </tex>

=== Свойства шаров ===
{{Теорема
|about=
Основное свойство шаров
|statement=
Пусть <tex> b \in V_{r_1}(a_1) \cap V_{r_2}(a_2)</tex>. Тогда <tex> \exists r > 0:\ V_r(b) \subset \ V_{r_1}(a_1) \cap V_{r_2}(a_2)</tex> 

Простым языком: Если два открытых шара пересекаются, то существует открытый шар, лежащий в их пересечении.
|proof=

Замечание: для <tex>X = \mathbb{R}</tex> это очевидно (переcечение двух интервалов есть интервал).

: Пусть <tex> y \in V_{r}(b)</tex>
: <tex> \rho (b, a_j) < r_j, j = 1,2 </tex>
: <tex> \exists r > 0: \rho (y, b) < r \Rightarrow \rho (y, a_j) < r_j, j = \overline{1,2}.</tex>
# <tex> \rho (y, a_1) \le \rho (y, b) + \rho (b, a_1) < r_1 \Rightarrow \rho (y, b) < r_1 - \rho(b, a_1) = d_1,\ d_1 > 0 </tex>
# <tex> \rho (y, a_2) \le \rho (y, b) + \rho (b, a_2) < r_2 \Rightarrow \rho (y, b) < r_2 - \rho(b, a_2) = d_2,\ d_2 > 0 </tex>
: <tex> r = \min(d_1, d_2) \Rightarrow \rho(y, b) < r \Rightarrow y</tex> войдет в оба шара
}}

== Открытые множества ==

{{Определение
|definition=
Множество <tex> G \subset X </tex> называется открытым в метрическом пространстве, если его можно записать как некоторое объединение открытых шаров (в общем случае объединение может состоять из несчетного числа шаров).
: <tex> \tau </tex> — класс открытых множеств.
: <tex> \tau = \{ G </tex> {{---}} открытые в МП <tex>(X, \rho) \}</tex>
}}

===Свойства открытых множеств ===
# <tex> X, \varnothing \in \tau </tex> {{---}} все пространство и пустое множество открыты
# <tex> G_{\alpha} \in \tau, \alpha \in A \Rightarrow \bigcup\limits_{\alpha \in A} \in \tau </tex> — очевидно
# <tex> G_1 \dots G_n \in \tau \Rightarrow \bigcap\limits_{j = 1}^n G_j \in \tau </tex>

Доказательство свойства 3:

: <tex> G_1 = \bigcup\limits_{\alpha}V_{\alpha}; G_2 = \bigcup\limits_{\beta}V_{\beta} </tex>
: <tex> G_1 \cap G_2 = \bigcup\limits_{\alpha, \beta}(V_{\alpha} \cap V_{\beta}) </tex>
: По основному свойству шаров: <tex> b \in V_\alpha \cap V_\beta \Rightarrow \exists V(b) \subset V_\alpha \cap V_\beta </tex>
: Следовательно <tex> V_{\alpha} \cap V_{\beta} </tex> {{---}} объединение открытых шаров <tex> \Rightarrow G_1 \cap G_2 </tex> {{---}} тоже объединение открытых шаров <tex> \Rightarrow G_1 \cap G_2 \in \tau</tex> по 2 свойству.

Класс <tex> \tau </tex> называется (метрической) топологией на множестве <tex>X</tex>.

Если в <tex>X</tex> выделен класс множеств <tex> \tau </tex>, удовлетворяющий всем трем свойствам, то пара <tex>(X, \tau)</tex> называется ''топологическим пространством''(ТП). В этом смысле МП {{---}} частный случай ТП.

== Замкнутые множества ==

Множество F называется замкнутым в МП<tex>(X, \rho)</tex>, если <tex> \overline F = X \backslash F </tex> - открыто.

Применяя закон де Моргана, видим что класс открытых множеств <tex> \tau </tex> двойственен классу замкнутых множеств.

=== Свойства замкнутых множеств ===
# <tex> X, \varnothing </tex> {{---}} замкнуты
# Если <tex>\ F_{\alpha} </tex> {{---}} замкнуто <tex>\forall \alpha \in A </tex>, то <tex>\bigcup\limits_{\alpha \in A} F_{\alpha} </tex> {{---}} замкнуто
# Если <tex>\ F_1 \dots F_n </tex> {{---}} замкнуты, то <tex> \Rightarrow \bigcap\limits_{j = 1}^n F_j </tex> {{---}} замкнуто

== Предел в метрическом пространстве ==
{{Определение
|definition=
<tex> x_n \rightarrow x </tex> в МП <tex>(X, \rho)</tex>, если:
# <tex>\ \lim\limits_{n \rightarrow \infty} \rho(x_n, x) = 0\ </tex> , или
#<tex>\forall \varepsilon > 0, \exists N \in \mathbb{N}, \forall n > N \Rightarrow \rho(x_n, x) < \varepsilon </tex>
}}
<tex> V_\varepsilon(x) = \{ y: \rho(y, x) < \varepsilon \} </tex>

<tex>\lim\limits_{n \rightarrow \infty} x_n = x: \forall \varepsilon > 0, \exists N \in \mathbb{N}, \forall n > N: x_n \in V_\varepsilon(x)</tex>

{{Теорема
|about=
Единственность предела
|statement=
<tex> x_n \rightarrow x', x_n \rightarrow x'' </tex> в МП<tex>(X, \rho) \Rightarrow x' = x'' </tex>
|proof=
<tex> \rho(x', x'') \leq \rho(x', x) + \rho(x'', x) \Rightarrow \rho(x', x'') = 0; x' = x'' </tex>

На самом деле, этот факт {{---}} свойство МП, состоящее в выполении в нем аксиомы отделимости Хаусдорфа:

Пусть <tex> (X, \tau) </tex> - ТП, тогда если <tex> \forall a \ne b: \exists G_1, G_2 \in \tau :</tex>
# <tex> G_1 \cap G_2 = \varnothing </tex>
# <tex> a \in G_1; b \in G_2 </tex>
Тогда в таком ТП выполнима аксиома отделимости Хаусдорфа.

Частный случай на МП:
: <tex> (X, \rho), a \ne b, \rho(b, a) > 0: r = \frac 1 3 \rho(a, b); V_r(a) \cap V_r(b) = \varnothing </tex> , ч.т.д.
}}

==Основное характеристическое свойство замкнутых множеств==
{{Утверждение
|about=
В прямую сторону
|statement=
F - замкнуто, если оно содержит в себе пределы всех своих сходящихся последовательностей. 
F - замкнуто <tex> \iff \forall \{ x_1 \dots x_n \} \in F, x_n \rightarrow x, x \in F </tex>
|proof= 
: Пусть <tex> x \notin F, F = \overline G \Rightarrow x \in G = \bigcup\limits_\alpha V \Rightarrow x \in V </tex>
: <tex> F \cap G = \varnothing \Rightarrow F \cap V = \varnothing </tex>
: <tex> x_n \rightarrow x : \forall \varepsilon > 0 \, \exists N \, \forall n > N : x_n \in V </tex> , что противоречит <tex> x_n \in F (F \cap V = \varnothing) \Rightarrow x \in F </tex>
}}
{{TODO| t = Написал вроде бы понятное доказательство в обратную сторону. Если есть какие-либо косяки - пишите в обсуждение.}}
{{Утверждение
|about=
В обратную сторону
|statement=
: Если множество F содержит в себе пределы всех своих сходящихся последовательностей, то оно замкнуто.
|proof=
Рассмотрим <tex> x \notin F </tex>. Пусть <tex> G = \overline F </tex>. Если <tex> G </tex> - открытое, то <tex> F </tex> - замкнутое множество (по определению).
: Тогда каждый <tex> y \notin F </tex> входит в <tex> G </tex> вместе с каким-то открытым шаром (по определению - <tex> G = \bigcup\limits_i V_i </tex> - открытое множество), причём, всегда можно выделить такой шар, что <tex> y </tex> является его центром (достаточно положить <tex> r' = r - \rho (x, y) </tex>, где <tex> x </tex> - центр шара, в который входит <tex> y </tex>, а <tex> r </tex> - его радиус). При этом, <tex> F \cap G = \varnothing \Rightarrow \forall i: V_i \cap F = \varnothing </tex>.
: Предположим, что это не так, и для какого-то <tex> x \notin F </tex> не найдется такого открытого шара <tex> V(x): x \in V_r(x) , \, V_r(x) \cap F = \varnothing </tex>
: Запишем это формально: <tex> \forall r: F \cap V_r(x) \neq \varnothing</tex>.
: Определим следующие последовательности:
: <tex> r_n = \frac 1n </tex>, <tex> \{ x_n \} : x_n \in (F \cap V_{r_n}(x)) </tex>.
: <tex> r_n \rightarrow 0 \Rightarrow x_n \rightarrow x </tex>.
: Каждый <tex> x_n \in F, x_n \rightarrow x \Rightarrow \{ x_n \} </tex> - сходящаяся последовательность в <tex> F </tex>
: Но, по предположению, <tex> F </tex> содержит в себе пределы всех своих сходящихся последовательностей, а значит <tex> x \in F </tex>.
: Получили противоречие, значит <tex> G = \overline F </tex> - открытое множество, а значит <tex> F </tex> - замкнуто.
}}

[[Категория:Математический анализ 1 курс]]

Метрическое пространство

2010-12-06T22:59:04Z

VasilevArtem: Доказательство свойства замкнутого множества в обратную сторону.

{{В разработке}}
==Метрика и метрическое пространство==

Пусть <tex>X</tex> {{---}} абстрактное [[Множества|множество]].

<tex> X \times X = \{ (x_1, x_2): x_i \in X \} </tex> {{---}} прямое произведение множества <tex>X</tex> на себя

{{Определение
|definition=
Отображение <tex> \rho : X \times X \rightarrow \mathbb{R^+} </tex> {{---}} называется '''метрикой''' на <tex>X</tex>, если выполняются аксиомы
# <tex> \rho (x, y) \ge 0 ;\ \rho (x, y) = 0 \iff x = y </tex>
# <tex> \rho (x, y) = \rho (y, x) </tex>
# <tex> \rho (x, y) \le \rho (x, z) + \rho (z, y) </tex> {{---}} неравенство треугольника
}}

Если на <tex>X</tex> определена метрика, то пара <tex>(X, \rho)</tex> называется ''метрическим пространством'', аббревиатура {{---}} ''МП''.

=== Примеры ===

Числовая ось: <tex> X = \mathbb{R}; x, y \in X \Rightarrow \rho (x, y) = |x - y| </tex>

<tex> X = \mathbb{R}^n = \underbrace{\mathbb{R} \times \mathbb{R} \times \dots \times \mathbb{R}}_{n} ; \overrightarrow{x} = (x_1, \dots, x_n) </tex>
#<tex> \rho_1 (x, y) = \sum\limits_{k = 1}^n |x_k - y_k| </tex>
#<tex> \rho_2 (x, y) = \max\limits_{k = 1 \dots n} |x_k - y_k| </tex>

То есть, одно и то же множество можно по-разному превращать в метрическое пространство.

== Открытые шары ==

Для метрических пространств основное значение имеют открытые шары.

{{Определение
|definition=
Пусть <tex> (X, \rho) </tex> {{---}} метрическое пространство, пусть <tex>\ \ r \in \mathbb{R},\ r > 0,\ a \in X </tex>, тогда открытый шар радиуса
<tex>\ r\ </tex> в точке <tex>\ a\ </tex> {{---}} это множество <tex> V_r(a) = \{x \in X| \rho(x, a) < r \} </tex>
}}

=== Пример ===

<tex> X = \mathbb{R}: V_r(a) = (a - r; a + r) </tex>

=== Свойства шаров ===
{{Теорема
|about=
Основное свойство шаров
|statement=
Пусть <tex> b \in V_{r_1}(a_1) \cap V_{r_2}(a_2)</tex>. Тогда <tex> \exists r > 0:\ V_r(b) \subset \ V_{r_1}(a_1) \cap V_{r_2}(a_2)</tex> 

Простым языком: Если два открытых шара пересекаются, то существует открытый шар, лежащий в их пересечении.
|proof=

Замечание: для <tex>X = \mathbb{R}</tex> это очевидно (переcечение двух интервалов есть интервал).

: Пусть <tex> y \in V_{r}(b)</tex>
: <tex> \rho (b, a_j) < r_j, j = 1,2 </tex>
: <tex> \exists r > 0: \rho (y, b) < r \Rightarrow \rho (y, a_j) < r_j, j = \overline{1,2}.</tex>
# <tex> \rho (y, a_1) \le \rho (y, b) + \rho (b, a_1) < r_1 \Rightarrow \rho (y, b) < r_1 - \rho(b, a_1) = d_1,\ d_1 > 0 </tex>
# <tex> \rho (y, a_2) \le \rho (y, b) + \rho (b, a_2) < r_2 \Rightarrow \rho (y, b) < r_2 - \rho(b, a_2) = d_2,\ d_2 > 0 </tex>
: <tex> r = \min(d_1, d_2) \Rightarrow \rho(y, b) < r \Rightarrow y</tex> войдет в оба шара
}}

== Открытые множества ==

{{Определение
|definition=
Множество <tex> G \subset X </tex> называется открытым в метрическом пространстве, если его можно записать как некоторое объединение открытых шаров (в общем случае объединение может состоять из несчетного числа шаров).
: <tex> \tau </tex> — класс открытых множеств.
: <tex> \tau = \{ G </tex> {{---}} открытые в МП <tex>(X, \rho) \}</tex>
}}

===Свойства открытых множеств ===
# <tex> X, \varnothing \in \tau </tex> {{---}} все пространство и пустое множество открыты
# <tex> G_{\alpha} \in \tau, \alpha \in A \Rightarrow \bigcup\limits_{\alpha \in A} \in \tau </tex> — очевидно
# <tex> G_1 \dots G_n \in \tau \Rightarrow \bigcap\limits_{j = 1}^n G_j \in \tau </tex>

Доказательство свойства 3:

: <tex> G_1 = \bigcup\limits_{\alpha}V_{\alpha}; G_2 = \bigcup\limits_{\beta}V_{\beta} </tex>
: <tex> G_1 \cap G_2 = \bigcup\limits_{\alpha, \beta}(V_{\alpha} \cap V_{\beta}) </tex>
: По основному свойству шаров: <tex> b \in V_\alpha \cap V_\beta \Rightarrow \exists V(b) \subset V_\alpha \cap V_\beta </tex>
: Следовательно <tex> V_{\alpha} \cap V_{\beta} </tex> {{---}} объединение открытых шаров <tex> \Rightarrow G_1 \cap G_2 </tex> {{---}} тоже объединение открытых шаров <tex> \Rightarrow G_1 \cap G_2 \in \tau</tex> по 2 свойству.

Класс <tex> \tau </tex> называется (метрической) топологией на множестве <tex>X</tex>.

Если в <tex>X</tex> выделен класс множеств <tex> \tau </tex>, удовлетворяющий всем трем свойствам, то пара <tex>(X, \tau)</tex> называется ''топологическим пространством''(ТП). В этом смысле МП {{---}} частный случай ТП.

== Замкнутые множества ==

Множество F называется замкнутым в МП<tex>(X, \rho)</tex>, если <tex> \overline F = X \backslash F </tex> - открыто.

Применяя закон де Моргана, видим что класс открытых множеств <tex> \tau </tex> двойственен классу замкнутых множеств.

=== Свойства замкнутых множеств ===
# <tex> X, \varnothing </tex> {{---}} замкнуты
# Если <tex>\ F_{\alpha} </tex> {{---}} замкнуто <tex>\forall \alpha \in A </tex>, то <tex>\bigcup\limits_{\alpha \in A} F_{\alpha} </tex> {{---}} замкнуто
# Если <tex>\ F_1 \dots F_n </tex> {{---}} замкнуты, то <tex> \Rightarrow \bigcap\limits_{j = 1}^n F_j </tex> {{---}} замкнуто

== Предел в метрическом пространстве ==
{{Определение
|definition=
<tex> x_n \rightarrow x </tex> в МП <tex>(X, \rho)</tex>, если:
# <tex>\ \lim\limits_{n \rightarrow \infty} \rho(x_n, x) = 0\ </tex> , или
#<tex>\forall \varepsilon > 0, \exists N \in \mathbb{N}, \forall n > N \Rightarrow \rho(x_n, x) < \varepsilon </tex>
}}
<tex> V_\varepsilon(x) = \{ y: \rho(y, x) < \varepsilon \} </tex>

<tex>\lim\limits_{n \rightarrow \infty} x_n = x: \forall \varepsilon > 0, \exists N \in \mathbb{N}, \forall n > N: x_n \in V_\varepsilon(x)</tex>

{{Теорема
|about=
Единственность предела
|statement=
<tex> x_n \rightarrow x', x_n \rightarrow x'' </tex> в МП<tex>(X, \rho) \Rightarrow x' = x'' </tex>
|proof=
<tex> \rho(x', x'') \leq \rho(x', x) + \rho(x'', x) \Rightarrow \rho(x', x'') = 0; x' = x'' </tex>

На самом деле, этот факт {{---}} свойство МП, состоящее в выполении в нем аксиомы отделимости Хаусдорфа:

Пусть <tex> (X, \tau) </tex> - ТП, тогда если <tex> \forall a \ne b: \exists G_1, G_2 \in \tau :</tex>
# <tex> G_1 \cap G_2 = \varnothing </tex>
# <tex> a \in G_1; b \in G_2 </tex>
Тогда в таком ТП выполнима аксиома отделимости Хаусдорфа.

Частный случай на МП:
: <tex> (X, \rho), a \ne b, \rho(b, a) > 0: r = \frac 1 3 \rho(a, b); V_r(a) \cap V_r(b) = \varnothing </tex> , ч.т.д.
}}

==Основное характеристическое свойство замкнутых множеств==
{{Утверждение
|about=
В прямую сторону
|statement=
F - замкнуто, если оно содержит в себе пределы всех своих сходящихся последовательностей. 
F - замкнуто <tex> \iff \forall \{ x_1 \dots x_n \} \in F, x_n \rightarrow x, x \in F </tex>
|proof= 
: Пусть <tex> x \notin F, F = \overline G \Rightarrow x \in G = \bigcup\limits_\alpha V \Rightarrow x \in V </tex>
: <tex> F \cap G = \varnothing \Rightarrow F \cap V = \varnothing </tex>
: <tex> x_n \rightarrow x : \forall \varepsilon > 0 \, \exists N \, \forall n > N : x_n \in V </tex> , что противоречит <tex> x_n \in F (F \cap V = \varnothing) \Rightarrow x \in F </tex>
}}
{{TODO| t = Написал вроде бы понятное доказательство в обратную сторону. Если есть какие-либо косяки - пишите в обсуждение.}}
{{Утверждение
|about=
В обратную сторону
|statement=
: Если множество F содержит в себе пределы всех своих сходящихся последовательностей, то оно замкнуто.
|proof=
Рассмотрим <tex> x \notin F </tex>. Пусть <tex> G = \overline F </tex>. Если <tex> G </tex> - открытое, то <tex> F </tex> - замкнутое множество (по определению).
: Тогда каждый <tex> y \in F </tex> входит в <tex> G </tex> вместе с каким-то открытым шаром (по определению - <tex> G = \bigcup\limits_i V_i </tex> - открытое множество). При этом, <tex> F \cap G = \varnothing \Rightarrow \forall i: V_i \cap F = \varnothing </tex>.
: Предположим, что это не так, и для любого <tex> x \notin F </tex> не найдется такого открытого шара <tex> V(x): x \in V(x)_r , \, V(x)_r \cap F = \varnothing </tex>
: Запишем это формально: <tex> \forall r: \exists x': x' \in (F \cap V(x)_r) </tex>.
: Определим следующие последовательности:
: <tex> r_n = \frac 1n </tex>, <tex> \{ x_n \} : x_n \in (F \cap V(x)_{r_n}) </tex>.
: <tex> r_n \rightarrow 0 \Rightarrow x_n \rightarrow x </tex>.
: Каждый <tex> x_n \in F, x_n \rightarrow x \Rightarrow \{ x_n \} </tex> - сходящаяся последовательность в <tex> F </tex>
: Но, по предположению, <tex> F </tex> содержит в себе пределы всех своих сходящихся последовательностей, а значит <tex> x \in F </tex>.
: Получили противоречие, значит <tex> G = \overline F </tex> - открытое множество, а значит <tex> F </tex> - замкнуто.
}}

[[Категория:Математический анализ 1 курс]]

Предел последовательности

2010-11-21T03:16:01Z

VasilevArtem: Новая страница: «Лекция от 20 сентября. =Последовательность= {{Определение |definition= '''Последовательность''' - …»

Лекция от 20 сентября.

=Последовательность=

{{Определение
|definition=
'''Последовательность''' - функция натурального аргумента:

<tex> f: \mathbb N \rightarrow \mathbb R </tex>

<tex> f(n) </tex> - значения <tex> f </tex>, <tex> f(n) = a_n </tex>

<tex> f(N) </tex> - множество значений <tex> f </tex>

}}

<tex> c_n = a_n + b_n </tex> - сумма последовательностей.

<tex> c_n = a_n * b_n </tex> - произведение последовательностей.

В общем, арифметические действия с последовательностями совершаются над элементами с одинаковыми номерами.

{{Определение
|definition=
Последовательность <tex> a_n = f(n) </tex> '''ограничена сверху(снизу)''', если <tex> f(N) </tex> ограничено сверху(снизу).
}}

Иначе это можно записать так:

<tex> \exists d : \forall n : d \le a_n \Rightarrow a_n </tex> ограниченa снизу.

<tex> \exists d : \forall n : d \ge a_n \Rightarrow a_n </tex> ограниченa сверху.

{{Определение
|definition=

Последовательность <tex> a_n </tex> '''возрастает''' (пишут: <tex> a_n \uparrow </tex>), если: <tex> \forall n : a_n \le a_{n+1} </tex>.

Аналогично, если <tex> \forall n : a_n \ge a_{n+1} </tex>, то говорят, что последовательность <tex> a_n </tex> '''убывает''' (<tex> a_n \downarrow </tex>).
}}

=Предел последовательности=

{{Определение
|definition=
Число <tex> a \in \mathbb R </tex> называется '''пределом последовательности''' <tex> a_n </tex>, если:

<tex> \forall \varepsilon > 0, \exists n_0 \in \mathbb N: \forall n > n_0: |a_n - a| < \varepsilon </tex>

Записывают: <tex> a = \lim\limits_{n \rightarrow \infty} a_n </tex>
}}

Если последовательность имеет предел, то она ''сходится'': <tex> a_n \rightarrow a </tex>.

В определении предела последовательности <tex> \forall n > n_0: |a_n - a| < \varepsilon </tex>, строгие знаки неравенства можно заменять на нестрогие.

Также в определении предела, при выборе <tex> \varepsilon </tex> разрешено ставить ограничение на <tex> \varepsilon </tex> сверху:

<tex> 0 < \varepsilon < \varepsilon_0 </tex>.

Однако, ограничение <tex> 0 < \varepsilon </tex> обязательно.

<tex> \lim\limits_{n \rightarrow \infty} a_n = -\infty \Leftrightarrow
\forall \varepsilon > 0: \exists n_0 \in \mathbb N: \forall n > n_0 : a_n < -\varepsilon </tex>

<tex> \lim\limits_{n \rightarrow \infty} a_n = +\infty \Leftrightarrow
\forall \varepsilon > 0: \exists n_0 \in \mathbb N: \forall n > n_0 : a_n > \varepsilon </tex>

<tex> \lim\limits_{n \rightarrow \infty} a_n = \infty \Leftrightarrow
\forall \varepsilon > 0: \exists n_0 \in \mathbb N: \forall n > n_0 : |a_n| > \varepsilon </tex>

=Ряд простейших свойств предела=

{{Утверждение
|statement=
Если <tex> \{ a_n \} </tex> сходится, то <tex> \{ a_n \} </tex> - ограничена.
|proof=
Если взять <tex> \varepsilon = 1 </tex>, то:

<tex> \exists N \in \mathbb N : \forall n > N \Rightarrow a_n \in (a - 1, a + 1) </tex>

Вне интервала <tex> (a - 1, a + 1) </tex> лежат не более, чем точки <tex> a_1, a_2, ..., a_N </tex>, а таких - конечное число.
}}

{{Утверждение
|statement=
<tex> a_n \rightarrow a, a_n \rightarrow b \Rightarrow a = b </tex> - единственность предела последовательности.
|proof=
<tex> |b - a| \le |a_n - a| + |a_n - b| \Rightarrow
\forall \varepsilon > 0 : |b - a| < \varepsilon \Rightarrow
|b - a| = 0 \Rightarrow a = b </tex>
}}

{{Утверждение
|statement=
<tex> a_n \le b_n \Rightarrow \lim a_n \le \lim b_n </tex> - предельный переход в неравенстве.
|proof=
Предположим обратное:
<tex> \lim a_n = a, \lim b_n = b, a > b </tex>

Положим <tex> \varepsilon = \frac{a - b}{3} </tex>:

<tex> \exists N_1: \forall n > N_1: a_n \in (a - \varepsilon, a + \varepsilon) </tex>

<tex> \exists N_2: \forall n > N_2: b_n \in (b - \varepsilon, b + \varepsilon) </tex>

Отрезки <tex> (a - \varepsilon, a + \varepsilon) </tex> и <tex> (b - \varepsilon, b + \varepsilon) </tex> не пересекаются, и первый лежит, по предположению,
правее второго на числовой оси.

Но <tex> \forall n > (N_1 + N_2) : a_n > b_n </tex>, получили противоречие <tex> \Rightarrow \lim a_n \le \lim b_n </tex>
}}

{{Утверждение
|statement=
Если для последовательностей <tex> a_n, b_n, c_n </tex> выполняется:

<tex> a_n \le b_n \le c_n </tex> и <tex> a_n \rightarrow d, c_n \rightarrow d </tex>, то:

<tex> b_n \rightarrow d </tex> (принцип сжатой переменной)

|proof=

Рассмотрим отрезок <tex> [a_n, c_n] </tex>

Зафиксировав в определении предела для <tex> a_n </tex> и <tex> c_n </tex> определенный <tex> \varepsilon > 0 </tex>, '
получаем, что для какого-то <tex> N: \forall n > N: a_n \in (d - \varepsilon, d + \varepsilon), c_n \in (d - \varepsilon, d + \varepsilon)
\Rightarrow [a_n, c_n] \subset (d - \varepsilon, d + \varepsilon) </tex>

Но <tex> a_n \le b_n \le c_n \Rightarrow b_n \in [a_n, c_n] \Rightarrow b_n \in (d - \varepsilon, d + \varepsilon) </tex>.

В силу того, что ранее мы могли зафиксировать любой <tex> \varepsilon > 0 </tex>, получаем, что:

<tex> \forall \varepsilon : \exists N : \forall n > N : b_n \in (d - \varepsilon, d + \varepsilon)
\Rightarrow \lim b_n = d </tex>
}}

==Примеры==

{{Определение
|definition=
Если <tex> \lim a_n = 0 </tex>, то <tex> a_n </tex> называют '''бесконечно малой''' (б.м.) величиной,
и обозначают прописной греческой буквой (<tex> \alpha_n, \beta_n, \gamma_n, ... </tex>).
}}

<tex> \alpha_n = \frac 1n </tex> (из аксиомы Архимеда).

<tex> 0 < \varepsilon < 1, \exists N \in \mathbb N: 1 < N*\varepsilon \Leftrightarrow \frac 1N < \varepsilon </tex>

<tex> n > N \Rightarrow \frac 1n < \frac 1N < \varepsilon </tex> - выполняется для произведения <tex> \varepsilon </tex> и <tex> n > N \Rightarrow
\lim\frac 1n = 0 </tex>

===Пример 1===
<tex> a_n = 2^{\frac 1n} \rightarrow 1 \, (?)</tex>

<tex> 2^{\frac 1n} > 1 </tex>. Обозначим <tex> \alpha_n = 2^{\frac 1n} - 1 > 0 </tex>

<tex> 2^{\frac 1n} = 1 + \alpha_n \Rightarrow 2 = (1 + \alpha_n)^n \ge 1 + n*\alpha_n </tex> (используем неравенство Бернулли).

<tex> 0 < \alpha_n \le \frac 1n \Rightarrow \alpha_n </tex> - бесконечно малая.

<tex> 2^{\frac 1n} = 1 + </tex> (б.м.) <tex> \Rightarrow \lim 2^{\frac 1n} = 1 </tex>

Именно по этой причине говорят, что <tex> 2^0 = 1 </tex>.

===Пример 2===

<tex> a_n = n^{\frac 1n} \rightarrow 1 </tex>

<tex> n^{\frac 1n} > 1 </tex>

<tex> 0 < \alpha_n = n^{\frac 1n} - 1 </tex>

<tex> n^{\frac 1n} = \alpha_n + 1 \Rightarrow n = (1 + \alpha_n)^n =
\sum\limits_{j=0}^n {n \choose i} * \alpha_n^j \ge {n \choose 2} * \alpha_n^2 </tex>

<tex> {n \choose 2} = \frac {n(n-1)}{2} </tex>

<tex> 0 < \alpha_n^2 < \frac 2{n-1} \rightarrow 0 \Rightarrow \alpha_n^2 \rightarrow 0 </tex>

<tex> \alpha_n^2 \rightarrow 0 </tex>:

<tex> \forall \varepsilon_0 = \varepsilon^2 > 0, \exists N: \forall n > N: \alpha_n^2 < \varepsilon_0 = \varepsilon^2 </tex>

<tex> \alpha_n^2 < \varepsilon^2 \Rightarrow \alpha_n < \varepsilon </tex> - определение предела верно и для <tex> \alpha_n </tex>

<tex> \alpha_n </tex> - бесконечно малая <tex> \Rightarrow n^{\frac 1n} = 1 + \alpha_n \rightarrow 1 </tex>

{{Утверждение
|statement=
Пусть <tex> \alpha_n, \beta_n </tex> - бесконечно малые.

Тогда <tex> (\alpha_n + \beta_n), (\alpha_n * \beta_n) </tex> - также бесконечно малые.

|proof=

1) <tex> \forall \varepsilon > 0, \exists N: \forall n > N: \alpha_n < \frac {\varepsilon}2 , \beta_n < \frac {\varepsilon}2 </tex>

<tex> |\alpha_n + \beta_n| \le |\alpha_n| + |\beta_n| < \frac {\varepsilon}2 + \frac {\varepsilon}2 = \varepsilon </tex> - для всех n, начиная с N.

2) <tex> \forall \varepsilon > 0, \exists N: \forall n > N: \alpha_n < \varepsilon , \beta_n < 1 </tex>

<tex> |\alpha_n + \beta_n| = |\alpha_n||\beta_n| < \varepsilon * 1 = \varepsilon </tex> - для всех n, начиная с N.
}}

Таким же приемом, для произведения, доказывается, что, если <tex> \alpha_n </tex> - бесконечно малая, и <tex> a_n </tex> - ограниченная, то <tex> \alpha_n * a_n </tex> - также бесконечно малая <tex> \Rightarrow </tex> ''произведение бесконечно малой на ограниченную - также бесконечно малая''.

{{Утверждение
|statement=
Из пунктов 4 и 5 вытекает так называемая '''арифметика пределa''':

<tex> a_n \rightarrow n, b_n \rightarrow b \Rightarrow </tex>:

# <tex> (a_n \pm b_n) \rightarrow a \pm b </tex>
# <tex> (a_n * b_n) \rightarrow a * b </tex>
# Если <tex> b_n \nrightarrow 0 </tex>, то <tex> ( \frac {a_n}{b_n} ) \rightarrow \frac ab </tex>

|proof=

Докажем, например, свойство для произведения:

Представим <tex> a_n, b_n </tex> в виде: <tex> a_n = a + \alpha_n, b_n = b + \beta_n </tex>.

Тогда <tex> a_n * b_n = (a + \alpha_n) * (b + \beta_n) = a * b + \alpha_n * b + \beta_n * a + \alpha_n * \beta_n </tex>

По доказанному ранее свойству бесконечно малых, их произведение и произведение бесконечно малой на ограниченную - также бесконечно малые величины:

<tex> \alpha_n * b + \beta_n * a + \alpha_n * \beta_n \rightarrow 0 \Rightarrow a * b + \alpha_n * b + \beta_n * a + \alpha_n * \beta_n \rightarrow a * b </tex>
}}

[[Категория:Математический анализ 1 курс]]

Грани числовых множеств

2010-11-20T05:08:25Z

VasilevArtem: Добавлена категория

Лекция от 20 сентября 2010.
=Определения=
{{Определение
|definition=
Если <tex> A \subset \mathbb R, \, \exists b \in \mathbb R : A \le b </tex>, то A называется '''ограниченным сверху''' множеством.

<tex> b </tex> называется '''верхней границей''' множества А.

Если <tex> A \subset \mathbb R, \, \exists c \in \mathbb R : A \ge c </tex>, то A называется '''ограниченным снизу''' множеством.

<tex> c </tex> называется '''нижней границей''' множества А.

Если <tex> A \subset \mathbb R, \, \exists b, c \in \mathbb R : c \le A \le b </tex>, то A называется '''ограниченным''' множеством.
}}

{{Определение
|definition=
Если <tex> A </tex> - ограничено сверху, то наимешьшая из его верхних границ называется '''верхней гранью'''.

<tex> b = \sup A</tex> ("супремум")
}}

{{Определение
|definition=
Если <tex> A </tex> - ограничено снизу, то наибольшая из его нижних границ называется '''нижней гранью'''.

<tex> b = \inf A</tex> ("инфиум")
}}

=Существование грани множества=

{{Теорема
|statement=
Если А ограничено сверху, то у него существует верхняя грань (Аналогично для А, ограниченного снизу).
|proof=
Пусть M - множество верхних границ А. Так как А ограничено сверху, то <tex> M \ne \varnothing </tex>.
По определению верхней границы: <tex> A \le M </tex>.

По аксиоме непрерывности:

<tex> \exists d \in \mathbb R: \, A \le d \le M </tex>:

#<tex> A \le d \Rightarrow d \in M </tex>.
#<tex> d \le M \Rightarrow d </tex> - наименьшая из верхних границ А.
Получили, что d - верхняя граница А, и d не больше всех верхних границ А <tex>\Rightarrow d = sup \, A </tex>.
Аналогично для нижней грани ограниченного снизу множества А.
}}

=Принцип вложенных отрезков=

{{Определение
|definition=
Множество <tex> (a, b) = \{ x: a < x называется '''интервалом''' или '''открытым промежутком'''.

Множество <tex> [a, b] = \{ x: a \le x \le b \} </tex> называется '''отрезком''' или '''замкнутым промежутком'''.

Обозначение <tex> <a, b> = \{ x: a\, ?\, x\, ?\, b \} </tex> ('''промежуток''') используется, когда неизвестно включение границ.

По аналогии определяются и промежутки типа <tex> (a, b] </tex>.
}}

{{Определение
|definition=
Пусть дана система отрезков: <tex> a_n \le b_n, \Delta_n = [a_n, b_n] </tex>

<tex> \forall n \in \mathbb N: \Delta_{n+1} \subset \Delta_n </tex>

Тогда эта система отрезков называется '''вложенной'''.
}}

{{Утверждение
|statement=
<tex> \bigcap \limits_{n=1}^{\infty} \Delta_n \ne \varnothing </tex>
|proof=
Определим следующие числовые множества:

<tex> A = \{ a_n | n \in \mathbb N \} </tex>

<tex> B = \{ b_n | n \in \mathbb N \} </tex>

Пусть <tex> c = sup \, A, d = inf \, B </tex>.

<tex> c </tex> и <tex> d </tex> существуют.

В силу вложенности отрезков:

<tex> A \le c \le d \le B \Rightarrow \forall n: [c, d] \subset \Delta_n </tex>
}}

Исходя из определения граней, если:

<tex> d = sup \, A \in \mathbb R : </tex>

<tex> \forall \varepsilon > 0, \exists a \in A: d - \varepsilon < a </tex>

<tex> c = sup \, A \in \mathbb R : </tex>

<tex> \forall \varepsilon > 0, \exists a \in A: c + \varepsilon > a </tex>

[[Категория:Математический анализ 1 курс]]

Мощность множества

2010-11-20T03:50:42Z

VasilevArtem: Новая страница: «Лекция от 20 сентября 2010. =Определения= {{Определение |definition= Если А и В - произвольные множес…»

Лекция от 20 сентября 2010.

=Определения=
{{Определение
|definition=
Если А и В - произвольные множества, и между ними можно установить биекцию, что они '''равномощны''':

<tex> |A| = |B| </tex>
}}

Множество называется ''конечным'', если его элементы можно пересчитать, иначе его оно называется ''бесконечным''.

{{Определение
|definition=
Если <tex> |A| = |\mathbb N| </tex>, то A называется '''счетным''' множеством.
}}

<tex> A = \{a_1, a_2, ... , a_n \} </tex> - счетное множество.

Мощность счетных множеств минимальна по сравнению с другими бесконечными множествами.

{{Утверждение
|statement=
Если А - бесконечное множество, то в нем содержится по меньшей мере одно счетное подмножество.
|proof=
<tex> B \subset A </tex>

<tex> a_1 \in A \Rightarrow A \backslash \{ a_1 \} = A_1 </tex> - бесконечное множество.

<tex> a_2 \in A_1 \Rightarrow A_1 \backslash \{ a_2 \} = A_2 </tex> - также бесконечное множество.

Продолжаем этот процесс далее, пока не останется <tex> B \subset A </tex> - счетное множество. (ЩИТО? У кого есть что-нибудь адекватное насчет этого, исправьте, пожалуйста.)
}}

Если <tex> \{ a_1, a_2, ... , a_n, ... \} </tex> - совокупность попарно различных элементов, то это - счетное множество.

Для счетных множеств часто применяется следующий факт:
{{Утверждение
|statement=
Не более чем счетное объединение не более, чем счетных множеств, не более, чем счетно:

Пусть <tex> A_n </tex> - счетное/конечное множество.

Тогда: <tex> | \bigcup\limits_n A_n | = |\mathbb N| </tex>

|proof=

<tex> A_n = \{ a_{n1}, a_{n2}, ... \} </tex>.

TODO: А вот тут должна какая-то биекция, доказывающая это утверждение.

<tex> \begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots \\ a_{21} & a_{22} & \cdots \\ a_{31} & \cdots \\ \cdots \end{pmatrix} </tex>
}}

{{Определение
|definition=
<tex> Множество I = [0, 1] </tex> называется ''континииумом''.
}}

{{Утверждение
|statement=
<tex> I </tex> - несчетное множество.
|proof=
Будем доказывать от противного. Применим принцип вложенных отрезков:

Пусть <tex> I = \{ x_1, x_2, ... , x_n \} </tex>

Разделим I на 3 части и назовем <tex> \Delta_1 : x_1 \notin \Delta_1 </tex>. Такой отрезок всегда существует.

Далее разобьем <tex> \Delta_1 </tex> на 3 части. Назовем <tex> \Delta_2 </tex> тот отрезок, который не содержит <tex> x_2 </tex>, и так далее..

В результате выстраивается система вложенных отрезков:

<tex> \{ \Delta_n : \Delta_{n+1} \subset \Delta_n, x_n \notin \Delta_n \} </tex>

По свойству системы вложенных отрезков:

<tex> \exists d = \bigcap\limits_{n=1}^{\infty} \Delta_n </tex>

<tex> d \in I </tex>. Пусть теперь <tex> d \in \{ x_i \} \Rightarrow d = x_{n_0} </tex>.

По построению: <tex> d = x_{n_0} \notin \Delta_{n_0} </tex>, но <tex> d \in \bigcap\limits_{n=1}^{\infty} \Delta_n \Rightarrow d \in \Delta_{n_0} </tex>, противоречие.

}}

Если <tex> |A| = |I| </tex>, то обычно говорят, что А ''обладает мощностью континиума'':

{{Утверждение
|statement=
<tex> |\mathbb R| = |I| </tex>
|proof=
Рассмотрим функцию <tex> y = tg \, x, x \in ( -\frac{\pi}{2}, \frac{\pi}{2} ) </tex>

С ее помощью можно установить биекцию между множествами <tex> \mathbb R </tex> и <tex> ( -\frac{\pi}{2}, \frac{\pi}{2} ) </tex>.

Биекцию между множествами <tex> (0, 1) </tex> и <tex> ( -\frac{\pi}{2}, \frac{\pi}{2} ) </tex> можно установить параллельным переносом и сжатием:

<tex> x \leftrightarrow (x * \pi) - \frac {\pi}{2} </tex>

Получили, что <tex> |\mathbb R| = | ( -\frac{\pi}{2}, \frac{\pi}{2} ) | = | (0, 1) | </tex>.

Осталось доказать, что <tex> |(0, 1)| = |[0, 1]| </tex>.

Применим следующий прием:

Пусть <tex> a_1, a_2, ... , a_n, ... \in (0, 1) </tex> - попарно различны.

Множество <tex> A = \{ a_1, a_2, ... , a_n, ... \} </tex> - счетное.

Определим множество <tex> B = A \cup \{ 0, 1 \} </tex>. Множество <tex> B </tex> также счетное.

Между счетными множествами можно установить биекцию: <tex> B \leftrightarrow A \Rightarrow (0, 1) \backslash A = [0, 1] \backslash B
\Rightarrow (0, 1) = [0, 1] \Rightarrow |(0, 1)| = |[0, 1]| </tex>

В итоге получили, что <tex> |\mathbb R| = |[0, 1]| </tex>

}}

<tex> \mathbb Q </tex> - счетно.

<tex> |\mathbb R \backslash \mathbb Q| = |I| \Rightarrow </tex> иррациональных чисел по мощности континииум.

[[Категория:Математический анализ 1 курс]]

Грани числовых множеств

2010-11-20T01:31:11Z

VasilevArtem:

Лекция от 20 сентября 2010.
=Определения=
{{Определение
|definition=
Если <tex> A \subset \mathbb R, \, \exists b \in \mathbb R : A \le b </tex>, то A называется '''ограниченным сверху''' множеством.

<tex> b </tex> называется '''верхней границей''' множества А.

Если <tex> A \subset \mathbb R, \, \exists c \in \mathbb R : A \ge c </tex>, то A называется '''ограниченным снизу''' множеством.

<tex> c </tex> называется '''нижней границей''' множества А.

Если <tex> A \subset \mathbb R, \, \exists b, c \in \mathbb R : c \le A \le b </tex>, то A называется '''ограниченным''' множеством.
}}

{{Определение
|definition=
Если <tex> A </tex> - ограничено сверху, то наимешьшая из его верхних границ называется '''верхней гранью'''.

<tex> b = sup \, A</tex> ("супремум")
}}

{{Определение
|definition=
Если <tex> A </tex> - ограничено снизу, то наибольшая из его нижних границ называется '''нижней гранью'''.

<tex> b = inf \, A</tex> ("инфиум")
}}

=Существование грани множества=

{{Теорема
|statement=
Если А ограничено сверху, то у него существует верхняя грань (Аналогично для А, ограниченного снизу).
|proof=
Пусть M - множество верхних границ А. Так как А ограничено сверху, то <tex> M \ne \varnothing </tex>.
По определению верхней границы: <tex> A \le M </tex>.

По аксиоме непрерывности:

<tex> \exists d \in \mathbb R: \, A \le d \le M </tex>:

#<tex> A \le d \Rightarrow d \in M </tex>.
#<tex> d \le M \Rightarrow d </tex> - наименьшая из верхних границ А.
Получили, что d - верхняя граница А, и d не больше всех верхних границ А <tex>\Rightarrow d = sup \, A </tex>.
Аналогично для нижней грани ограниченного снизу множества А.
}}

=Принцип вложенных отрезков=

{{Определение
|definition=
Множество <tex> (a, b) = \{ x: a < x называется '''интервалом''' или '''открытым промежутком'''.

Множество <tex> [a, b] = \{ x: a \le x \le b \} </tex> называется '''отрезком''' или '''замкнутым промежутком'''.

Обозначение <tex> <a, b> = \{ x: a\, ?\, x\, ?\, b \} </tex> ('''промежуток''') используется, когда неизвестно включение границ.

По аналогии определяются и промежутки типа <tex> (a, b] </tex>.
}}

{{Определение
|definition=
Пусть дана система отрезков: <tex> a_n \le b_n, \Delta_n = [a_n, b_n] </tex>

<tex> \forall n \in \mathbb N: \Delta_{n+1} \subset \Delta_n </tex>

Тогда эта система отрезков называется '''вложенной'''.
}}

{{Утверждение
|statement=
<tex> \bigcap \limits_{n=1}^{\infty} \Delta_n \ne \varnothing </tex>
|proof=
Определим следующие числовые множества:

<tex> A = \{ a_n | n \in \mathbb N \} </tex>

<tex> B = \{ b_n | n \in \mathbb N \} </tex>

Пусть <tex> c = sup \, A, d = inf \, B </tex>.

<tex> c </tex> и <tex> d </tex> существуют.

В силу вложенности отрезков:

<tex> A \le c \le d \le B \Rightarrow \forall n: [c, d] \subset \Delta_n </tex>
}}

Исходя из определения граней, если:

<tex> d = sup \, A \in \mathbb R : </tex>

<tex> \forall \varepsilon > 0, \exists a \in A: d - \varepsilon < a </tex>

<tex> c = sup \, A \in \mathbb R : </tex>

<tex> \forall \varepsilon > 0, \exists a \in A: c + \varepsilon > a </tex>

Грани числовых множеств

2010-11-20T01:24:38Z

VasilevArtem: Новая страница: «Лекция от 20 сентября 2010. =Определения= {{Определение |definition= Если <tex> A \subset \mathbb R, \, \exists b \in \math…»

Лекция от 20 сентября 2010.
=Определения=
{{Определение
|definition=
Если <tex> A \subset \mathbb R, \, \exists b \in \mathbb R : A \le b </tex>, то A называется '''ограниченным сверху''' множеством.

<tex> b </tex> называется '''верхней границей''' множества А.

Если <tex> A \subset \mathbb R, \, \exists c \in \mathbb R : A \ge c </tex>, то A называется '''ограниченным снизу''' множеством.

<tex> c </tex> называется '''нижней границей''' множества А.

Если <tex> A \subset \mathbb R, \, \exists b, c \in \mathbb R : c \le A \le b </tex>, то A называется '''ограниченным''' множеством.
}}

{{Определение
|definition=
Если <tex> A </tex> - ограничено сверху, то наимешьшая из его верхних границ называется '''верхней гранью'''.

<tex> b = sup \, A</tex> ("супремум")
}}

{{Определение
|definition=
Если <tex> A </tex> - ограничено снизу, то наибольшая из его нижних границ называется '''нижней гранью'''.

<tex> b = inf \, A</tex> ("инфиум")
}}

=Существование грани множества=

{{Теорема
|statement=
Если А ограничено сверху, то у него существует верхняя грань (Аналогично для А, ограниченного снизу).
|proof=
Пусть M - множество верхних границ А. Так как А ограничено сверху, то <tex> M \ne \varnothing </tex>.
По определению верхней границы: <tex> A \le M </tex>.

По аксиоме непрерывности:

<tex> \exists d \in \mathbb R: \, A \le d \le M </tex>:

#<tex> A \le d \Rightarrow d \in M </tex>.
#<tex> d \le M \Rightarrow d </tex> - наименьшая из верхних границ А.
Получили, что d - верхняя граница А, и d не больше всех верхних границ А, <tex> d = sup \, A </tex>.
Аналогично для нижней грани ограниченного снизу множества А.
}}

=Принцип вложенных отрезков=

{{Определение
|definition=
Множество <tex> (a, b) = \{ x: a < x называется '''интервалом''' или '''открытым промежутком'''.

Множество <tex> [a, b] = \{ x: a \le x \le b \} </tex> называется '''отрезком''' или '''замкнутым промежутком'''.

Обозначение <tex> <a, b> = \{ x: a\, ?\, x\, ?\, b \} </tex> ('''промежуток''') используется, когда неизвестно включение границ.

По аналогии определяются и промежутки типа <tex> (a, b] </tex>.
}}

{{Определение
|definition=
Пусть дана система отрезков: <tex> a_n \le b_n, \Delta_n = [a_n, b_n] </tex>

<tex> \forall n \in \mathbb N: \Delta_{n+1} \subset \Delta_n </tex>

Тогда эта система отрезков называется '''вложенной'''.
}}

{{Утверждение
|statement=
<tex> \bigcap \limits_{n=1}^{\infty} \Delta_n \ne \varnothing </tex>
|proof=
Определим следующие числовые множества:

<tex> A = \{ a_n, n \in \mathbb N \} </tex>

<tex> B = \{ b_n, n \in \mathbb N \} </tex>

Пусть <tex> c = sup \, A, d = inf \, B </tex>.

<tex> c </tex> и <tex> d </tex> существуют.

В силу вложенности отрезков:

<tex> A \le c \le d \le B \Rightarrow \forall n: [c, d] \subset \Delta_n </tex>
}}

Исходя из определения граней, если:

<tex> d = sup \, A \in \mathbb R : </tex>

<tex> \forall \varepsilon > 0, \exists a \in A: d - \varepsilon < a </tex>

<tex> c = sup \, A \in \mathbb R : </tex>

<tex> \forall \varepsilon > 0, \exists a \in A: c + \varepsilon > a </tex>

Вещественные числа

2010-11-16T07:15:56Z

VasilevArtem: Новая страница: «Лекция от 13 сентября 2010. <tex> \mathbb N </tex> - натуральные числа = {1, 2, 3, ...} Определяются следующим …»

Лекция от 13 сентября 2010.

<tex> \mathbb N </tex> - натуральные числа = {1, 2, 3, ...}
Определяются следующим образом:

За числом n в натуральном ряде непосредственно следует n + 1, между n и n + 1 других
<tex> k \in \mathbb N </tex> ''нет''.

Гильберт: натуральные числа - первичные элементы, природа которых не обсуждается, все остальное базируется на этом.

<tex> \mathbb Z = \{ 0 \} \cup \{ n, -n | n \in \mathbb N \} </tex> - множество целых чисел.

<tex> \mathbb N \subset \mathbb Z </tex>

<tex> \mathbb Q </tex> - рациональные числа:
<tex> \mathbb Q = \{\frac mn ; m \in \mathbb Z, n \in \mathbb N \}; </tex>

Множество <tex> \mathbb Q </tex> ''упорядочено''.

Всегда выполняется только один из трех случаев: <tex> r < q, r = q, r > q </tex>

{{Определение
|definition= <tex> |x| = \begin{cases} \ \ x, & x > 0 \\ 0, & x = 0 \\ -x, & x < 0 \end{cases} </tex>
- модуль или абсолютная величина числа x
}}
//Почему же так неровно?

Свойства:

<tex>
1) |ab| = |a||b|; \\
2) |x + y| \le |x| + |y|; \\
3) |x - a| \le r \Leftrightarrow a - r \le x \le a + r;
</tex>

В <tex> \mathbb Q </tex> выполняется '''аксиома Архимеда''':

<tex> 0 < r < q; \\ r, q \in \mathbb Q \Rightarrow \\
\exists n \in \mathbb N : q < n*r
</tex>

Пусть A, B - два числовых множества.

{{Определение
|definition= Запись A \forall a \in A, b \in B \Rightarrow a 
}}

Аналогично определяются записи типа <tex> A \le B </tex>, ...

Если <tex> B = \{b\}: A 

{{Утверждение
|statement= Пусть А, B состоят из рациональных положительных чисел r, таких, что

A = {рациональные положительные r: r^2 < 2};

B = {рациональные положительные r: r^2 > 2};

Тогда <tex> \exists d \in \mathbb Q : A \le d \le B </tex>
|proof=
Допустим, что существует <tex> d \in \mathbb Q </tex>

<tex> d^2 < 2, d^2 = 2, d^2 > 2</tex>

<tex> d^2=2</tex> - невозможно, доказывается через несократимость дроби <tex> d = \frac mn: </tex>

<tex> m^2 = 2n^2, </tex>2 - простое, значит m делится без остатка на 2n

<tex> m = 2p, 4p^2 = 2n^2, n^2=2p^2; n\, \vdots \, 2</tex>, противоречие.

2 случая: либо <tex> d^2 < 2 </tex>, либо <tex> d^2 > 2 </tex>.

1) Для всех рациональных <tex> \delta \in (0; 1): </tex>

<tex> (d + \delta)^2 = d^2 + 2d\delta + \delta^2 </tex>

<tex> \delta^2 < \delta \Rightarrow (d + \delta)^2 < d^2 + 2d\delta + \delta = d^2 + (2d+1)\delta </tex>

<tex> d^2 + (2d+1)\delta < 2 \Leftrightarrow \delta < \frac{2 - d^2}{2d+1}, d^2 < 2, 2 - d^2 > 0 </tex>

<tex> \delta_0 \in \mathbb Q = min\{ \frac{1}{3}, \frac{2-d^2}{2d+1} \} \in (0; 1) </tex>;

Для такого <tex> \delta_0: (d + \delta_0)^2 < 2 \Leftarrow (d + \delta_0) \in A </tex>

<tex> A \le d. d + \delta_0 \le d, \delta_0 \le 0 </tex>, противоречие.

Для случая <tex> d^2 > 2 </tex> доказывается аналогично.
}}

Этим утверждением обнаруживается серьезный пробел в <tex> \mathbb Q </tex>.
Для его ликвидации вводятся некоторые объекты. При таком пополнении должны выполняться:
# 4 арифметических действия с сохранением законов арифметики.
# Сохранение упорядоченности.
# Выполнение аксиомы непрерывности:

Пусть А и В - 2 произвольных подмножества из пополненного множества рациональных чисел, и <tex> A \le B </tex>, то в пополненном множестве
<tex> \exists d: A \le d \le B </tex>

Получается множество, называемое множеством ''вещественных'' чисел - <tex> \mathbb R, \, \mathbb Q \subset \mathbb R </tex>

Из разбора ясно, что мы стоим на аксиоматических позициях.

Для анализа важно то, что для <tex> \mathbb R </tex> выполняется аксиома непрерывности.

Несколько моделей <tex> \mathbb R </tex> :
# Модель Дедекинда
# Модель Вейерштрасса
# Модель Кантора

Базируясь на аксиоме Архимеда и непрерывности, можно установить, что <tex> \mathbb Q </tex> ''всюду плотно'' на <tex> \mathbb R </tex>:

В любом вещественном интервале <tex> (a, b) : (x: a < x < b) </tex> найдется рациональное число.

Для нас этот важен тем, что он гарантирует единственность пополнения <tex> \mathbb Q </tex> для выполнения аксиомы непрерывности.

Любое такое пополнение приводит к множествам, изоморфным друг другу.

Отображения

2010-11-16T03:22:33Z

VasilevArtem:

{{В разработке}}

Лекция от 13 сентября 2010 года.

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

{{Определение | definition =
Закон f, посредством которого каждому <tex>a \in A</tex> , сопоставляется единственный <tex>b \in B</tex>, называют отображением.
}}

Формы записи:

<tex> f: A \rightarrow B \\
b = f(a) </tex>

{{Определение | definition =
Если A и B состоят из чисел, f называется функцией.
}}

Отображение - три объекта: множество A(откуда), множество B(куда), функция f(как).

=Связанные понятия=

Пусть:
: <tex> f : A \rightarrow B </tex>
: <tex> C \subset A </tex>
: <tex> g : C \rightarrow B </tex>
: <tex> \forall c \in C : g(c) = f(c) </tex>
Тогда, g - '''сужение''' f на C, <tex> g = f \big|_C </tex>

<tex> A = D(f) </tex> - ''область определения'' f

<tex> R(f) = \{ b | b = f(a), a \in A \} </tex> - ''область значений'' f

<tex> C \subset A ; f(C) = \{f(a)| a \in A \} </tex> - ''образ'' множества C при отображении f

<tex> D \subset B ; f^{-1}(D) = \{ a| a \in A, f(a) \in D \} </tex> - ''прообраз'' множества D при отображении f

{{Определение | definition =
Отображение <tex>f^{-1}: B \rightarrow A</tex> называется обратным отображением для f.
}}

<tex> f(f^{-1}(a)) = a; \\
f^{-1}(f(b)) = b;
</tex>

Термины "прямое" и "обратное" отображения взаимны.

=Свойства отображений=

'''Инъективное''' отображение - переводит разные элементы A в разные элементы B:
: <tex> \forall a_1, a_2 \in A : f(a_1) \ne f(a_2) </tex>

'''Сюръективное''' отображение(на множестве B) - каждый элемент множества B является образом хотя бы одного элемента множества A:
: <tex> \forall b \in B: \exists a : b = f(a) </tex>

'''Биективное''' отображение - инъекция + сюръекция - взаимно однозначное соответствие, обладает двумя предыдущими свойствами.

=См. также=
*[[Множества]]

[[Категория:Математический анализ 1 курс]]

Множества

2010-11-14T21:18:56Z

VasilevArtem:

{{В разработке}}
[[Категория:Математический анализ 1 курс]]

Лекция от 06.09.10.

=Начальные определения=
Множество - первичное математическое понятие, которому не может быть дано строгое математическое определение. Часто множество определяют как "совокупность объектов, объединенных общим свойством".

В математическом анализе используется "наивная" теория множеств, которая является удобным языком описания фактов. Создана немецким математиком Г. Кантором(1870).

<tex>a \in A</tex> (объект а принадлежит множеству А)

<tex>a \notin A</tex> (объект а не принадлежит множеству А)

=Задание множеств=

1) Перечислением элементов: <tex> A = \{a_1, a_2 ..., a_n, ...\} </tex>

2) Заданием определенного свойства обьектов: <tex> A = \{a: P\} </tex> , где P - определенное свойство обьекта а

=Операции=

1) <tex> A \subset B </tex> (A является подмножеством B, каждый элемент из А также принадлежит В (<tex> \forall x: x \in A \Rightarrow x \in B </tex>);

2) <tex> A \cap B </tex> (Пересечение множеств А и В: <tex> (x \in A) \wedge (x \in B) </tex>);

3) <tex> A \cup B </tex> (Объединение множеств А и В: <tex> (x \in A) \vee (x \in B) </tex>);

4) <tex> B \backslash A </tex> (Разность множеств: <tex> (x \in B) \wedge (x \notin A) </tex>;

5) <tex> \varnothing </tex> - пустое множество:

<tex> A \cup \varnothing = A </tex>

<tex> A \cap \varnothing = \varnothing </tex>

<tex> \forall A: \varnothing \subseteq A </tex>

<tex> \bigcup\limits_{\alpha\in W} A_\alpha</tex> - обьединение нескольких множеств. В общем случае может состоять из бесконечного количества множеств:

<tex> \bigcup\limits_{j \in N} A_j = A_1 \cup A_2 \cup </tex> ...

<tex> \bigcup\limits_{0 < x < 1} A_x </tex>

<tex> \bigcup\limits_{\alpha \in W} A_{\alpha} </tex>, и так далее..

<tex> A \cup B \cup C ... \subseteq U </tex> - "множество всего".

<tex>\overline{A} = U </tex> \ <tex> A </tex> - дополнение множества А, дополнительное множество к А до U;

{{Теорема
|statement=
<tex>\overline{\bigcup\limits_\alpha A_\alpha} = \bigcap\limits_\alpha \overline{A_\alpha} \\
\overline{\bigcap\limits_\alpha A_\alpha} = \bigcup\limits_\alpha \overline{A_\alpha} </tex>
||proof=
????????
}}

Композиция отношений

2010-10-15T16:39:59Z

VasilevArtem:

{{Определение
|definition=
'''Композицией''' (произведением, суперпозицией) бинарных отношений <tex>R\subseteq A\times B</tex> и <tex>S\subseteq B\times C</tex> называется такое отношение <tex> (R \circ S) \subseteq A\times C</tex>, что:

<tex>\forall a \in A, c \in C : a (R \circ S) c \Leftrightarrow \exists b \in B : (a R b) \wedge (b S c) </tex>.
}}

Примером такого отношения может служить отношение на некотором множестве <tex>A</tex> населенных пунктов <tex>R\subseteq A\times A</tex> - отношение "можно доехать на поезде", а <tex>S\subseteq A\times A</tex> - отношение "можно доехать на автобусе". Тогда отношение <tex>R\circ S\subseteq A\times A</tex> - отношение "можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)".

=Степень отношений=

{{Определение
|definition=
'''Степень отношения''' <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:

* <tex> R^{n} = R^{n-1} \circ R; </tex>

* <tex> R^{1} = R; </tex>

* <tex> R^{0} = \{ (x, x) \mid x \in A \}</tex>;
}}

В связи с этим понятием, также вводятся обозначения:

<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </tex>

<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> - [[Транзитивное замыкание]] отношения R

=Обратное отношение=

{{Определение
|definition=
Отношение <tex>R^{-1} \subseteq B\times A</tex> называют '''обратным''' для отношения <tex> R \subseteq A\times B</tex>, если:

<tex> aR^{-1}b \Leftrightarrow bRa </tex>
}}

{{Определение
|definition=
'''Ядром отношения''' R называется отношение <tex> R\circ R^{-1} </tex>
}}

=Свойства=

* Ядро отношения R [[Симметричное отношение|симметрично]]: <tex> a (R \circ R^{-1}) b \Leftrightarrow \exists c: (a R c) \wedge (c R^{-1} b) \Leftrightarrow \exists c: (b R c) \wedge (c R^{-1} a) \Leftrightarrow b (R \circ R^{-1} ) a</tex>

* <tex> (R^{-1})^{-1} = R </tex>

* <tex> (R \circ S) \circ T = R \circ (S \circ T) </tex>

* <tex> (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) </tex>

* <tex> (R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1}) </tex>

* <tex> (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) </tex>

Композиция отношений

2010-10-13T17:34:15Z

VasilevArtem:

{{Определение
|definition=
'''Композицией''' (произведением, суперпозицией) бинарных отношений <tex>R\subseteq A\times B</tex> и <tex>S\subseteq B\times C</tex> называется такое отношение <tex> (R \circ S) \subseteq A\times C</tex>, что:

<tex>\forall a \in A, c \in C : a (R \circ S) c \Leftrightarrow \exists b \in B : (a R b) \wedge (b S c) </tex>.
}}

Примером такого отношения может служить отношение на некотором множестве <tex>A</tex> населенных пунктов <tex>R\subseteq A\times A</tex> - отношение "можно доехать на поезде", а <tex>S\subseteq A\times A</tex> - отношение "можно доехать на автобусе". Тогда отношение <tex>R\circ S\subseteq A\times A</tex> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

=Степень отношений=

{{Определение
|definition=
'''Степень отношения''' <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:

* <tex> R^{n} = R^{n-1} \circ R; </tex>

* <tex> R^{1} = R; </tex>

* <tex> R^{0} = \{ (x, x) \mid x \in A \}</tex>;
}}

В связи с этим понятием, также вводятся обозначения:

<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </tex>

<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> - [[Транзитивное замыкание]] отношения R

=Обратное отношение=

{{Определение
|definition=
Отношение <tex>R^{-1} \subseteq B\times A</tex> называют '''обратным''' для отношения <tex> R \subseteq A\times B</tex>, если:

<tex> aR^{-1}b \Leftrightarrow bRa </tex>
}}

{{Определение
|definition=
'''Ядром отношения''' R называется отношение <tex> R\circ R^{-1} </tex>
}}

=Свойства=

* Ядро отношения R [[Симметричное отношение|симметрично]]: <tex> a (R \circ R^{-1}) b \Leftrightarrow \exists c: (a R c) \wedge (c R^{-1} b) \Leftrightarrow \exists c: (b R c) \wedge (c R^{-1} a) \Leftrightarrow b (R \circ R^{-1} ) a</tex>

* <tex> (R^{-1})^{-1} = R </tex>

* <tex> (R \circ S) \circ T = R \circ (S \circ T) </tex>

* <tex> (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) </tex>

* <tex> (R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1}) </tex>

* <tex> (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) </tex>

Антисимметричное отношение

2010-10-13T17:30:25Z

VasilevArtem:

{{Определение
|definition =
'''Антисимметричное''' отношение - бинарное отношение <tex>R \subseteq A\times A</tex>, для которого выполняется:
<tex> \forall a, b\in A: (aRb) \wedge (bRa) \Rightarrow a = b</tex>.
}}
Определение антисимметричного отношения как <tex> (aRb) \Rightarrow \neg(bRa) </tex> является неверным, поскольку из такого определения также следует [[Рефлексивное_отношение| антирефлексивность]] R.

Примерами антисимметричных отношений являются, по определению, все отношения полного и частичного порядка(<tex> <, >, \le, \ge </tex> и другие).

{{Определение
|definition =
'''Асимметричное''' отношение - бинарное отношение R, для которого выполняется:

<tex> (a R b) \Rightarrow \neg (b R a) </tex>
}}

Асимметричность отношения R эквивалентна [[Рефлексивное_отношение|антирефлексивности]] и антисимметричности отношения R.

==См. также==
* [[Симметричное отношение]]

Обратное отношение

2010-10-12T16:52:30Z

VasilevArtem: Перенаправление на Композиция отношений

#REDIRECT [[Композиция отношений]]

Степень отношений

2010-10-12T16:51:09Z

VasilevArtem: Перенаправление на Композиция отношений

#REDIRECT [[Композиция отношений]]

Композиция отношений

2010-10-11T20:20:13Z

VasilevArtem:

{{Определение
|definition=
Композицией бинарных отношений <tex>R\subseteq A\times B</tex> и <tex>S\subseteq B\times C</tex> называется такое отношение <tex> (R \circ S) \subseteq A\times C</tex>, что:

<tex>\forall a \in A, c \in C : a (R \circ S) c \Leftrightarrow \exists b \in B : (a R b) \wedge (b S c) </tex>.
}}

Примером такого отношения может служить отношение на некотором множестве <tex>A</tex> населенных пунктов <tex>R\subseteq A\times A</tex> - отношение "можно доехать на поезде", а <tex>S\subseteq A\times A</tex> - отношение "можно доехать на автобусе". Тогда отношение <tex>R\circ S\subseteq A\times A</tex> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

=Степень отношений=

{{Определение
|definition=
Степень отношения <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:

* <tex> R^{n} = R^{n-1} \circ R; </tex>

* <tex> R^{1} = R; </tex>

* <tex> R^{0} = \{ (x, x) \mid x \in A \}</tex>;
}}

В связи с этим понятием, также вводятся обозначения:

<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </tex>

<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> - [[Транзитивное замыкание]] отношения R

=Обратное отношение=

{{Определение
|definition=
Отношение <tex>R^{-1} \subseteq B\times A</tex> называют ''обратным'' для отношения <tex> R \subseteq A\times B</tex>, если:

<tex> aR^{-1}b \Leftrightarrow bRa </tex>
}}

{{Определение
|definition=
''Ядром отношения'' R называется отношение <tex> R\circ R^{-1} </tex>
}}

=Свойства=

* Ядро отношения R [[Симметричное отношение|симметрично]]: <tex> a (R \circ R^{-1}) b \Leftrightarrow \exists c: (a R c) \wedge (c R^{-1} b) \Leftrightarrow \exists c: (b R c) \wedge (c R^{-1} a) \Leftrightarrow b (R \circ R^{-1} ) a</tex>

* <tex> (R^{-1})^{-1} = R </tex>

* <tex> (R \circ S) \circ T = R \circ (S \circ T) </tex>

* <tex> (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) </tex>

* <tex> (R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1}) </tex>

* <tex> (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) </tex>

Композиция отношений

2010-10-11T20:18:51Z

VasilevArtem:

{{Определение
|definition=
Композицией бинарных отношений <tex>R\subseteq A\times B</tex> и <tex>S\subseteq B\times C</tex> называется такое отношение <tex> (R \circ S) \subseteq A\times C</tex>, что:

<tex>\forall a \in A, c \in C : a (R \circ S) c \Leftrightarrow \exists b \in B : (a R b) \wedge (b S c) </tex>.
}}

Примером такого отношения может служить отношение на некотором множестве <tex>A</tex> населенных пунктов <tex>R\subseteq A\times A</tex> - отношение "можно доехать на поезде", а <tex>S\subseteq A\times A</tex> - отношение "можно доехать на автобусе". Тогда отношение <tex>R\circ S\subseteq A\times A</tex> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

=Степень отношений=

Степень отношения <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:

* <tex> R^{n} = R^{n-1} \circ R; </tex>

* <tex> R^{1} = R; </tex>

* <tex> R^{0} = \{ (x, x) \mid x \in A \}</tex>;

В связи с этим понятием, также вводятся обозначения:

<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </tex>

<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> - [[Транзитивное замыкание]] отношения R

=Обратное отношение=

{{Определение
|definition=
Отношение <tex>R^{-1} \subseteq B\times A</tex> называют ''обратным'' для отношения <tex> R \subseteq A\times B</tex>, если:

<tex> aR^{-1}b \Leftrightarrow bRa </tex>
}}

{{Определение
|definition=
''Ядром отношения'' R называется отношение <tex> R\circ R^{-1} </tex>
}}

=Свойства=

* Ядро отношения R [[Симметричное отношение|симметрично]]: <tex> a (R \circ R^{-1}) b \Leftrightarrow \exists c: (a R c) \wedge (c R^{-1} b) \Leftrightarrow \exists c: (b R c) \wedge (c R^{-1} a) \Leftrightarrow b (R \circ R^{-1} ) a</tex>

* <tex> (R^{-1})^{-1} = R </tex>

* <tex> (R \circ S) \circ T = R \circ (S \circ T) </tex>

* <tex> (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) </tex>

* <tex> (R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1}) </tex>

* <tex> (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) </tex>

Антисимметричное отношение

2010-10-10T06:27:31Z

VasilevArtem:

{{Определение
|definition =
''Антисимметричное'' отношение - бинарное отношение <tex>R \subseteq A\times A</tex>, для которого выполняется:
<tex> \forall a, b\in A: (aRb) \wedge (bRa) \Rightarrow a = b</tex>.
}}
Определение антисимметричного отношения как <tex> (aRb) \Rightarrow \neg(bRa) </tex> является неверным, поскольку из такого определения также следует [[Рефлексивное_отношение| антирефлексивность]] R. Такое отношение называют ''асимметричным''.

Примерами антисимметричных отношений являются, по определению, все отношения полного и частичного порядка(<tex> <, >, \le, \ge </tex> и другие).

==См. также==
* [[Симметричное отношение]]

Антисимметричное отношение

2010-10-07T05:13:48Z

VasilevArtem:

''Антисимметричное'' отношение - бинарное отношение <tex>R \subseteq A\times A</tex>, для которого выполняется:
<tex> \forall a, b\in A: (aRb) \wedge (bRa) \Rightarrow a = b</tex>. Определение антисимметричного отношения как <tex> (aRb) \Rightarrow \neg(bRa) </tex> является неверным, поскольку из такого определения также следует [[Рефлексивное_отношение| антирефлексивность]] R. Такое отношение называют ''асимметричным''.

Примерами антисимметричных отношений являются, по определению, все отношения полного и частичного порядка(<tex> <, >, \le, \ge </tex> и другие).

==См. также==
* [[Симметричное отношение]]

Антисимметричное отношение

2010-10-07T04:46:48Z

VasilevArtem: Новая страница: «''Антисимметричное'' отношение - бинарное отношение <tex>R \subseteq A\times A</tex>, для которого выполн…»

''Антисимметричное'' отношение - бинарное отношение <tex>R \subseteq A\times A</tex>, для которого выполняется:
<tex> \forall a, b\in A: aRb \wedge bRa \Rightarrow a = b</tex>. Определение антисимметричного отношения как <tex> aRb \Rightarrow b \overline{R} a </tex> является неверным, поскольку из такого определения также следует [[Рефлексивное_отношение| антирефлексивность]] R.

Примерами антисимметричных отношений являются, по определению, все отношения полного и частичного порядка(<tex> <, >, \le, \ge </tex> и другие).

==См. также==
* [[Симметричное отношение]]

Композиция отношений

2010-10-03T21:50:21Z

VasilevArtem:

Композицией бинарных отношений <tex>R\subseteq A\times B</tex> и <tex>S\subseteq B\times C</tex> называется такое отношение <tex> (R \circ S) \subseteq A\times C</tex>, что:

<tex>\forall a \in A, c \in C : a (R \circ S) c \Leftrightarrow \exists b \in B : (a R b) \wedge (b S c) </tex>.

Примером такого отношения может служить отношение на некотором множестве <tex>A</tex> населенных пунктов <tex>R\subseteq A\times A</tex> - отношение "можно доехать на поезде", а <tex>S\subseteq A\times A</tex> - отношение "можно доехать на автобусе". Тогда отношение <tex>R\circ S\subseteq A\times A</tex> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

=Степень отношений=

Степень отношения <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:

<tex> R^{n} = R^{n-1} \circ R; </tex>

<tex> R^{1} = R; </tex>

<tex> R^{0} = \{ (x, x) \mid x \in A \}</tex>;

В связи с этим понятием, также вводятся обозначения:

<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </tex>

<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> - [[Транзитивное замыкание]] отношения R

=Обратное отношение=

Отношение <tex>R^{-1} \subseteq B\times A</tex> называют ''обратным'' для отношения <tex> R \subseteq A\times B</tex>, если:

<tex> aR^{-1}b \Leftrightarrow bRa </tex>

''Ядром отношения'' R называется отношение <tex> R\circ R^{-1} </tex>

Оно [[Симметричное отношение|симметрично]]: <tex> a (R \circ R^{-1}) b \Leftrightarrow \exists c: (a R c) \wedge (c R^{-1} b) \Leftrightarrow \exists c: (b R c) \wedge (c R^{-1} a) \Leftrightarrow b (R \circ R^{-1} ) a</tex>

Композиция отношений

2010-10-03T04:53:44Z

VasilevArtem: <math> -> <tex>

= Определение =
Композицией бинарных отношений <tex>R\subseteq A\times B</tex> и <tex>S\subseteq B\times C</tex> называется такое отношение <tex> (R \circ S) \subseteq A\times C</tex>, что:

<tex>\forall a \in A, c \in C : a (R \circ S) c \Leftrightarrow \exists b \in B \mid (a R b) \wedge (b S c) </tex>.

Примером такого отношения может служить отношение на некотором множестве <tex>A</tex> населенных пунктов <tex>R\subseteq A\times A</tex> - отношение "можно доехать на поезде", а <tex>S\subseteq A\times A</tex> - отношение "можно доехать на автобусе". Тогда отношение <tex>R\circ S\subseteq A\times A</tex> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

=Степень отношений=

Степень отношения <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:

<tex> R^{n} = R^{n-1} \circ R; </tex>

<tex> R^{1} = R; </tex>

<tex> R^{0} = \{ (x, x) \mid x \in A \}</tex>;

В связи с этим понятием, также вводятся обозначения:

<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </tex>

<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> - [[Транзитивное замыкание]] отношения R

=Обратное отношение=

Отношение <tex>R^{-1} \subseteq B\times A</tex> называют ''обратным'' для отношения <tex> R \subseteq A\times B</tex>, если:

<tex> aR^{-1}b \Leftrightarrow bRa </tex>

''Ядром отношения'' R называется отношение <tex> R\circ R^{-1} </tex>

Оно симметрично: <tex> a (R \circ R^{-1}) b \Leftrightarrow \exists c: (a R c) \wedge (c R^{-1} b) \Leftrightarrow \exists c: (b R c) \wedge (c R^{-1} a) \Leftrightarrow b (R \circ R^{-1} ) a</tex>

Композиция отношений

2010-09-28T17:57:17Z

VasilevArtem:

= Определение =
Композицией бинарных отношений <math>R\subseteq A\times B</math> и <math>S\subseteq B\times C</math> называется такое отношение <math> (R \circ S) \subseteq A\times C</math>, что:

<math>\forall a, c: a(R\circ S)c \Leftrightarrow \exists b\in B\mid (aRb)\and (bSc)</math>.

Примером такого отношения может служить отношение на некотором множестве <math>A</math> населенных пунктов <math>R\subseteq A\times A</math> - отношение "можно доехать на поезде", а <math>S\subseteq A\times A</math> - отношение "можно доехать на автобусе". Тогда отношение <math>R\circ S\subseteq A\times A</math> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

=Степень отношений=

Степень отношения <math>R^{n} \subseteq A\times A</math>, определяется следующим образом:

<math> R^{n} = R^{n-1} \circ R; </math>

<math> R^1 = R;

R^0 = \{ (x, x) \mid x\in A\}</math>

В связи с этим понятием, также вводятся обозначения:

<math> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </math>

<math> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </math> - [[Транзитивное замыкание]] множества R

=Обратное отношение=

Отношение <math>R^{-1} \subseteq B\times A</math> называют ''обратным'' для отношения <math> R \subseteq A\times B</math>, если:

<math> aR^{-1}b \Leftrightarrow bRa </math>

''Ядром отношения'' R называется отношение <math> R\circ R^{-1} </math>

Оно симметрично: <math> a(R\circ R^{-1})b \Rightarrow \exists c: (aRc)\and(cR^{-1}b) \Rightarrow \exists c:(bRc)\and (cR^{-1}a) \Rightarrow b(R\circ R^{-1}) a</math>

Композиция отношений

2010-09-28T17:17:14Z

VasilevArtem:

= Определение =
Композицией бинарных отношений <math>R\subseteq A\times B</math> и <math>S\subseteq B\times C</math> называется такое отношение <math> R \circ S </math>, что:

<math>\forall a, c: a(R\circ S)c \Leftrightarrow \exists b\in B\mid (aRb)\and (bSc)</math>.

Примером такого отношения может служить отношение на некотором множестве <math>A</math> населенных пунктов <math>R\subseteq A\times A</math> - отношение "можно доехать на поезде", а <math>S\subseteq A\times A</math> - отношение "можно доехать на автобусе". Тогда отношение <math>R\circ S\subseteq A\times A</math> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

=Степень отношений=

Степень отношения <math>R^{n} \subseteq A\times A</math>, определяется следующим образом:

<math> R^{n} = R^{n-1} \circ R; </math>

<math> R^1 = R;

R^0 = \{ (x, x) \mid x\in A\}</math>

В связи с этим понятием, также вводятся обозначения:

<math> R^{+} = \cup^{\infty}_{i=1} R^{i}; </math>

<math> R^{*} = \cup^{\infty}_{i=0} R^{i} </math> - [[Транзитивное замыкание]] множества R

=Обратное отношение=

Отношение <math>R^{-1} \subseteq B\times A</math> называют ''обратным'' для отношения <math> R \subseteq A\times B</math>, если:

<math> aR^{-1}b \Leftrightarrow bRa </math>

Ядром отношения R называется отношение <math> R\circ R^{-1} </math>

Оно симметрично: <math> a(R\circ R^{-1})b \Rightarrow \exists c: (aRc)\and(cR^{-1}b) \Rightarrow \exists c:(bRc)\and (cR^{-1}a) \Rightarrow b(R\circ R^{-1}) a</math>

Композиция отношений

2010-09-28T15:07:52Z

VasilevArtem:

Композиция отношений

2010-09-28T06:19:07Z

VasilevArtem:

= Определение =
Композицией бинарных отношений <math>R\subseteq A\times B</math> и <math>S\subseteq B\times C</math> называется такое отношение <math> R \circ S </math>, что:

<math>\forall a, c: a(R\circ S)c \Leftrightarrow \exists b\in B\mid (aRb)\and (bSc)</math>.

Примером такого отношения может служить отношение на некотором множестве <math>A</math> населенных пунктов <math>R\subseteq A\times A</math> - отношение "можно доехать на поезде", а <math>S\subseteq A\times A</math> - отношение "можно доехать на автобусе". Тогда отношение <math>R\circ S\subseteq A\times A</math> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

=Степень отношений=

Степень отношения <math>R^{n} \subseteq A\times A</math>, определяется следующим образом:
<math> R^{n} = R^{n-1} \circ R; </math>

<math> R^1 = R;

R^0 = \{ (x, x) \mid x\in A\}</math>

В связи с этим понятием, также вводятся обозначения:
<math> R^{+} = \cup^{\infty}_{i=1} R^{i}; </math>
<math> R^{*} = \cup^{\infty}_{i=0} R^{i} </math> - [[Транзитивное замыкание]] множества R

=Обратное отношение=

Отношение <math>R^{-1} \subseteq B\times A</math> называют ''обратным'' для отношения <math> R \subseteq A\times B</math>, если:

<math> aR^{-1}b \Leftrightarrow bRa </math>

Композиция отношений

2010-09-28T06:18:15Z

VasilevArtem:

= Определение =
Композицией бинарных отношений <math>R\subseteq A\times B</math> и <math>S\subseteq B\times C</math> называется такое отношение <math> R \circ S </math>, что:

<math>\forall a, c: a(R\circ S)c \Leftrightarrow \exists b\in B\mid (aRb)\and (bSc)</math>.

Примером такого отношения может служить отношение на некотором множестве <math>A</math> населенных пунктов <math>R\subseteq A\times A</math> - отношение "можно доехать на поезде", а <math>B\subseteq A\times A</math> - отношение "можно доехать на автобусе". Тогда отношение <math>R\circ S\subseteq A\times A</math> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

=Степень отношений=

Степень отношения <math>R^{n} \subseteq A\times A</math>, определяется следующим образом:
<math> R^{n} = R^{n-1} \circ R; </math>

<math> R^1 = R;

R^0 = \{ (x, x) \mid x\in A\}</math>

В связи с этим понятием, также вводятся обозначения:
<math> R^{+} = \cup^{\infty}_{i=1} R^{i}; </math>
<math> R^{*} = \cup^{\infty}_{i=0} R^{i} </math> - [[Транзитивное замыкание]] множества R

=Обратное отношение=

Отношение <math>R^{-1} \subseteq B\times A</math> называют ''обратным'' для отношения <math> R \subseteq A\times B</math>, если:

<math> aR^{-1}b \Leftrightarrow bRa </math>

Композиция отношений

2010-09-28T06:14:55Z

VasilevArtem: Новая страница

= Определение =
Композицией бинарных отношений <math>R\subseteq A\times B</math> и <math>S\subseteq B\times C</math> называется такое отношение <math> R \circ S </math>, что:

<math>\forall a, c: a(R\circ S)c \Leftrightarrow \exists b\in B\mid (aRb)\and (bSc)</math>.

Примером такого отношения может служить отношение на некотором множестве населенных пунктов A <math>R\subseteq A\times A</math> - отношение "можно доехать на поезде", а <math>B\subseteq A\times A</math> - отношение "можно доехать на автобусе". Тогда отношение <math>R\circ S\subseteq A\times A</math> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

=Степень отношений=

Степень отношения <math>R^{n} \subseteq A\times A</math>, определяется следующим образом:
<math> R^{n} = R^{n-1} \circ R; </math>

<math> R^1 = R;

R^0 = \{ (x, x) \mid x\in A\}</math>

В связи с этим понятием, также вводятся обозначения:
<math> R^{+} = \cup^{\infty}_{i=1} R^{i}; </math>
<math> R^{*} = \cup^{\infty}_{i=0} R^{i} </math> - [[Транзитивное замыкание]] множества R

=Обратное отношение=

Отношение <math>R^{-1} \subseteq B\times A</math> называют ''обратным'' для отношения <math> R \subseteq A\times B</math>, если:

<math> aR^{-1}b \Leftrightarrow bRa </math>