WWW.KONFERENCIYA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Конференции, лекции

 

Лекция 8: Алгоритмы для задач о

паросочетаниях

Б.М.Верников, А.М.Шур

Уральский федеральный университет,

Институт математики и компьютерных наук,

кафедра алгебры и дискретной математики

Б.М.Верников, А.М.Шур Лекция 8: Алгоритмы для задач о паросочетаниях

Задача о назначениях

В этой лекции мы опишем алгоритм решения задачи о назначениях, а

также более сложного ее варианта задачи об оптимальных назначениях.

Напомним формулировку задачи.

Задача о назначениях В данном двудольном графе найти максимальное паросочетание.

Нам потребуются два понятия для работы с паросочетаниями. Пусть дан двудольный граф G и паросочетание P в нем.

Простая цепь в G называется чередующейся относительно P, если из любых двух соседних ребер этой цепи ровно одно лежит в P.

Чередующаяся относительно P (u, v )-цепь называется увеличивающей относительно P, если вершины u и v свободны относительно P.

Если из контекста понятно, о каком паросочетании идет речь, мы опускаем слова относительно P, ребра из паросочетания называем темными, остальные ребра графа светлыми, а изменение статуса ребра (добавление в паросочетание или удаление из паросочетания) перекраской ребра.

Б.М.Верников, А.М.Шур Лекция 8: Алгоритмы для задач о паросочетаниях Увеличивающие цепи Лемма об увеличивающей цепи Если в двудольном графе G есть увеличивающая относительно паросочетания P цепь, то при перекраске всех ребер этой цепи получится паросочетание, содержащее на одно ребро больше, чем P.

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

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

Данная лемма объясняет термин увеличивающая цепь.

Б.М.Верников, А.М.Шур Лекция 8: Алгоритмы для задач о паросочетаниях Увеличивающие цепи: пример На рис. 1 слева изображен граф G, в котором жирными линиями отмечено паросочетание P. Цепь x1 y2 x3 y4 x5 y3 является увеличивающей относительно P; в результате перекраски всех ее ребер получим паросочетание P, изображенное на рис. 1 справа.

y1 y2 y3 y4 y1 y2 y3 y x1 x2 x3 x4 x5 x1 x2 x3 x4 x Рис. Построение увеличивающих цепей основной ингредиент венгерского алгоритма, решающего задачу о назначениях. Перед изложением алгоритма мы докажем теорему, из которой следует его корректность.

Нам потребуется следующее несложное Замечание Если в связном графе степень любой вершины равна 1 или 2, то этот граф является либо простой цепью, либо простым циклом.

Б.М.Верников, А.М.Шур Лекция 8: Алгоритмы для задач о паросочетаниях Теорема Бержа Теорема Бержа Паросочетание P в двудольном графе G является максимальным тогда и только тогда, когда не существует увеличивающей относительно P цепи.

Доказательство. Необходимость следует из леммы об увеличивающей цепи: если такая цепь относительно P существует, то P не максимально.

Достаточность. Пусть увеличивающей относительно P цепи не существует и пусть в G есть максимальное паросочетание P, отличное от P (если такого паросочетания нет, то P максимальное паросочетание, к тому же единственное в G, и доказывать нечего). Рассмотрим подграф G в G, состоящий из всех ребер, принадлежащих ровно одному из паросочетаний P, P, и всех вершин, инцидентных этим ребрам. На рис. 2 слева приведен пример паросочетаний P (жирные линии) и P (красные линии), а справа соответствующий подграф G.

Теорема Бержа: окончание доказательства Любая вершина в подграфе G имеет степень не ниже 1 и не выше (вершина может быть инцидентна максимум одному ребру из P и максимум одному ребру из P ). Согласно сделанному выше замечанию, каждая компонента связности графа G является простой цепью либо простым циклом.

Любая цепь в G является чередующейся (как относительно P, так и относительно P ), поскольку ребра из одного паросочетания не имеют общих вершин. В то же время, в G (а значит, и в его подграфе G ) нет увеличивающих цепей ни относительно P по условию, ни относительно по доказательству необходимости в данной теореме. Следовательно, крайние ребра любой цепи в G принадлежат разным паросочетаниям, а значит, длина такой цепи четна. Циклы имеют четную длину по критерию двудольности (лекция 7). Но тогда в любой компоненте связности графа G ребер из P столько же, сколько и ребер из P, т. е. получаем |P \ P | = |P \ P|, откуда |P| = |P |. Таким образом, паросочетание P максимально.

Б.М.Верников, А.М.Шур Лекция 8: Алгоритмы для задач о паросочетаниях Венгерский алгоритм Венгерский алгоритм Вход: двудольный граф G с долями X и Y, |Y | |X |.

Выход: список ребер максимального паросочетания P в графе G.



1. Выбрать произвольное ребро (x, y ), положить P = {(x, y )}.

2. Положить F = Y \ {y }.

3. Если F пусто, закончить работу, иначе пометить все вершины из F как непросмотренные.

4. Выбрать непросмотренную вершину v из F ; если существует увеличивающая цепь с началом в v, перекрасить все ребра этой цепи, удалить v из F и вернуться на шаг 3.

5. Пометить вершину v как просмотренную; если в F остались непросмотренные вершины, вернуться на шаг 4.

Легко проверить, что венгерский алгоритм корректен: он всегда останавливается, строит паросочетание (по лемме об увеличивающей цепи), и это паросочетание максимально (если остановка произошла на шаге 3, то текущее паросочетание насыщает все вершины из Y, а если алгоритм вышел из цикла после шага 5, то в графе нет увеличивающих относительно P цепей и применима теорема Бержа).

Б.М.Верников, А.М.Шур Лекция 8: Алгоритмы для задач о паросочетаниях Венгерский алгоритм: пример Единственная техническая сложность венгерского алгоритма поиск увеличивающих цепей. Для этого используются деревья поиска, уже упоминавшиеся в лекции 6. Мы продемонстрируем их построение на примере, найдя максимальное паросочетание в графе, изображенном на рис. 1 (он воспроизведен на рис. 3 слева).

Пусть на шаге 1 алгоритма выбрано ребро (x1, y1 ), шаги 2 и произведены. Далее, пусть на шаге 4 строится увеличивающая цепь из вершины y2. Для этого строится дерево с корнем y2 ; сыновьями корня становятся все смежные с y2 вершины. Если среди этих вершин есть свободная (на рис. 3 справа свободные вершины помещены в квадратики), то увеличивающая цепь найдена. Перекраска цепи в данном случае это занесение ребра (x3, y2 ) в P. После этого вершина y2 удаляется из F.

Следующая итерация выглядит аналогично: в P добавится ребро (x5, y3 ), вершина y3 будет удалена из F.

Венгерский алгоритм: пример (окончание) После двух итераций паросочетание P выглядит как на рис. 4 слева. На третьей итерации поиск увеличивающей цепи будет производиться из вершины y4 единственной оставшейся свободной верхней вершины. При этом на первом шаге построения дерева свободная нижняя вершина найдена не будет; продолжим поиск, сначала дописав в сыновья к каждой из нижних вершин смежную с ней в P верхнюю вершину (цепь должна быть чередующейся), а затем дописав в сыновья эти верхним вершинам все смежные с ними нижние вершины, еще не попавшие в дерево (см. рис.

4 посередине). В этот момент мы найдем свободную вершину x4 и увеличивающую цепь единственную (y4, x4 )-цепь в построенном дереве.

Перекраска цепи состоит в удалении из P ребра (x3, y2 ) и добавлении в P ребер (x3, y4 ) и (x4, y2 ). Итоговое паросочетание приведено на рис. справа. На следующей итерации алгоритм завершит работу, поскольку свободных верхних вершин не осталось.

Задача об оптимальном назначении (1) Рассмотрим усложненный вариант задачи о назначениях, в котором присутствует функция выгодности назначения.

Задача об оптимальном назначении (неформальная постановка) Имеется n вакантных должностей и n претендентов на них. Каждый из претендентов может быть назначен на любую должность; выгода от назначения i-го претендента на j-ю должность выражается числом wij.

Требуется произвести назначения так, чтобы добиться максимально возможной суммарной выгоды.

Чтобы перевести эту задачу на язык теории графов, нам понадобится Определение Двудольный граф, в котором любые две вершины из разных долей соединены ровно одним ребром, называется полным двудольным. Через Kn,m обозначается полный двудольный граф, доли которого содержат n и m вершин.

Б.М.Верников, А.М.Шур Лекция 8: Алгоритмы для задач о паросочетаниях Задача об оптимальном назначении: графовая постановка Построим двудольный граф, в котором, как и при формализации задачи о назначении, нижние вершины {x1,..., xn } будут соответствовать претендентам, а верхние {y1,..., yn } должностям. Поскольку теперь каждый претендент может быть назначен на любую должность и число претендентов равно числу должностей, мы получим полный двудольный граф Kn,n. Для каждых i, j = 1,..., n ребру (xi, yj ) припишем вес wij, т. е.

выгоду от соответствующего назначения. Получим взвешенный граф (Kn,n, w ) (где n число претендентов, w весовая функция, задаваемая равенствами w (xi, yj ) = wij ).

Определение Совершенное паросочетание в графе (Kn,n, w ), имеющее максимальный вес среди всех совершенных паросочетаний этого графа, называется оптимальным.

Задача об оптимальном назначении (графовая постановка) Найти оптимальное паросочетание в заданном взвешенном графе Алгоритм решения этой задачи активно использует венгерский алгоритм.

Матрица весов Определение Пусть (Kn,n, w ) взвешенный граф, w (xi, yj ) = wij для всех i, j = 1, 2,..., n. Квадратная матрица W = (wij ) порядка n называется матрицей весов этого графа. Вместо (Kn,n, w ) мы будем писать Kn,n [W ].

Так, матрица на рис. 5 справа задает взвешенный граф (K3,3, w ) на рис. слева.

Рис. 5. Взвешенный двудольный граф и его матрица весов Вершинная разметка Определение Допустимой разметкой взвешенного графа Kn,n [W ] называется функция, сопоставляющая каждой вершине v графа действительное число f (v ) так, что f (xi ) + f (yj ) wij для всех i, j = 1, 2,..., n. Число f (v ) называется меткой вершины v. Граф Kn,n [W ] с допустимой вершинной разметкой f обозначается через Kn,n [W ; f ].





Замечание Допустимая вершинная разметка существует в каждом взвешенном графе Kn,n [W ]. Ее можно получить, например, положив Подграф равенств Определение Пусть Kn,n [W ; f ] взвешенный граф с допустимой разметкой. Подграфом равенств графа Kn,n [W ; f ] называется его суграф, определяемый следующим образом: ребро (xi, yj ) графа Kn,n [W ; f ] является ребром подграфа равенств тогда и только тогда, когда f (xi ) + f (yj ) = wij.

Подграф равенств графа Kn,n [W ; f ] мы будем обозначать через GW,f.

На рис. 6 слева представлен граф, изображеный на рис. 5, с допустимой разметкой, задаваемой формулами (1) (метки вершин указаны в скобках), а справа подграф равенств этого графа.

Рис. 6. Граф с допустимой вершинной разметкой и его подграф равенств Подграф равенств и оптимальное паросочетание Лемма о подграфе равенств допустимая разметка взвешенного графа Kn,n [W ]. Если подграф равенств графа Kn,n [W ; f ] содержит совершенное паросочетание P, то P является оптимальным паросочетанием в графе Kn,n [W ].

Доказательство. Пусть P совершенное паросочетание в графе GW,f (а значит, и в графе Kn,n [W ]), Q другое совершенное паросочетание в Kn,n [W ]. Напомним, что вес графа это сумма весов входящих в него ребер. Используя определение допустимой разметки и тот факт, что в совершенном паросочетании каждая вершина графа инцидентна ровно одному ребру, получаем откуда по определению следует максимальность P.

Алгоритм Куна–Манкреса Алгоритм Куна–Манкреса Вход: взвешенный граф Kn,n [W ] с долями X и Y.

Выход: множество ребер оптимального паросочетания P в данном графе.

1. Задать в Kn,n [W ] произвольную допустимую разметку f и найти подграф равенств GW,f.

2. Венгерским алгоритмом найти максимальное паросочетание P в графе GW,f и множество F свободных относительно P вершин доли X.

3. Если F =, закончить работу.

4. Найти все чередующиеся цепи в графе GW,f, начинающиеся в F, положить S и T равными множеству всех вершин доли X (соответственно, доли Y ), встретившихся в этих цепях.

5. Если в T нет свободных вершин, положить новый граф GW,f и вернуться на шаг 4.

6. Увеличить P, перекрасив найденную увеличивающую цепь, и вернуться на шаг 3.

Алгоритм Куна–Манкреса: корректность В соответствии с леммой о подграфе равенств, алгоритм Куна–Манкреса перестраивает исходную разметку так, чтобы найти совершенное паросочетание в подграфе равенств. Следующие замечания обеспечивают корректность алгоритма:

величина всегда строго положительна (по построению S и T, вершины из S смежны в GW,f только вершинам из T ; значит, в (2) для любого ребра (xi, yj ) имеем f (xi ) + f (yj ) wij > 0);

измененная на шаге 5 функция f остается допустимой разметкой (сумма меток вершин, инцидентных ребру, уменьшилась только для ребер, соединяющих вершины из S и Y \ T, причем величина определена так, чтобы эта сумма осталась не меньше веса ребра);

ребра, вошедшие в максимальное паросочетание в текущем графе равенств, остаются в графе равенств после изменения разметки (метки увеличились только для вершин из T, но по построению они связаны темными ребрами только с вершинами из S, у которых метки соответственно уменьшились);

после изменения графа GW,f на шаге 5 множество S не меняется, а во множество T добавляется хотя бы одна вершина (та, на которой достигается минимум в (2); это обеспечивает конечность числа итераций шагов 4–5 между увеличениями паросочетания, а значит, тот факт, что алгоритм остановится).

Б.М.Верников, А.М.Шур Лекция 8: Алгоритмы для задач о паросочетаниях Алгоритм Куна–Манкреса: пример Найдем оптимальное паросочетание в графе K5,5 с долями Зададим допустимую разметку в соответствии с формулами (1):

Найдем в графе Kn,n [W ; f ] подграф равенств GW,f (см. рис. 7; возле каждой вершины в скобках указана ее метка).

Пусть P максимальное паросочетание в графе GW,f, выделенное на рис.

7 жирными линиями.

Алгоритм Куна–Манкреса: пример (продолжение) Если P = {(x2, y2 ), (x4, y4 )}, то F = {x1, x3, x5 }. При построении чередующихся цепей, начиная с F, мы захватим еще вершины y2, y4 и x2, x4. Таким образом, S = X, T = {y2, y4 }.

В T нет свободных вершин по множествам S = X и Y \ T = {y1, y3, y5 } вычисляем = 2. Обновляем метки вершин; новый граф GW,f с текущим паросочетанием выглядит как на рис. 8.

По-прежнему F = {x1, x3, x5 }. При построении чередующихся цепей немедленно находим свободную вершину y1, перекрашиваем цепь x3 y из одного ребра и возвращаемся на шаг 3.

Теперь F = {x1, x5 }; при построении чередующихся цепей находим увеличивающую цепь x1 y2 x2 y5, перекрашиваем ее и возвращаемся на шаг 3, имея F = {x5 }. Текущее паросочетание изображено на рис. 9 (см. следующий слайд).

Алгоритм Куна–Манкреса: пример (окончание) Имеем F = {x5 } и строим S = X и T = {y1, y2, y4, y5 }. В T нет свободных вершин; согласно (2), находим = 1 и изменяем метки. В новом графе GW,f (см. рис. 10) находим увеличивающую цепь x5 y3 длины (красное ребро на рис. 10) и, перекрасив ее, получаем совершенное паросочетание в текущем подграфе равенств, т. е. оптимальное паросочетание в исходном взвешенном графе.

Алгоритм Куна–Манкреса: обсуждение примера Представляет интерес интерпретация найденного нами оптимального паросочетания P с точки зрения неформальной постановки задачи об оптимальном назначении. В P входит ребро (x2, y5 ). Это значит, что мы назначили претендента x2 на должность y5. В соответствии с матрицей выгода от этого назначения равна 2. Между тем претендент x2 мог бы с большей выгодой, равной 4, быть назначен на должность y2. Аналогично, на должность y4 назначен претендент x4. Выгода от этого назначения равна 4, в то время как на должность y4 можно было бы с выгодой назначить претендента x3. Вообще, только два претендента (x1 и x4 ) назначены на наиболее подходящие для них должности, и только на три должности (y1, y3 и y5 ) назначены наилучшие для них претенденты. Однако суммарная выгода от сделанных назначений, равная 15, является максимально возможной.

Б.М.Верников, А.М.Шур Лекция 8: Алгоритмы для задач о паросочетаниях

Похожие работы:

«ЛЕКЦИЯ 3 ОБЩИЕ ПУТИ ОБМЕНА ВЕЩЕСТВ, ЦИКЛ ТРИКАРБОНОВЫХ КИСЛОТ. БИОЛОГИЧЕСКОЕ ОКИСЛЕНИЕ И ОКИСЛИТЕЛЬНОЕ ФОСФОРИЛИРОВАНИЕ. 1. Обмен веществ. Обмен веществ (или метаболизм) - это совокупность биохимических реакций превращения химических соединений, которые происходят в живых организмах. Обмен веществ состоит из нескольких последовательных стадий: 1. Поступление биополимеров (белков, липидов, углеводов), витаминов, минеральных элементов, воды в организм в составе продуктов питания. 2. Превращение...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ КАФЕДРА ЭКОНОМИКИ ПРЕДПРИЯТИЯ И ПРОИЗВОДСТВЕННОГО МЕНЕДЖМЕНТА КРАТКИЙ КОНСПЕКТ ЛЕКЦИЙ ПО УЧЕБНОЙ ДИСЦИПЛИНЕ СТРАТЕГИЧЕСКИЙ И КОНКУРЕНТНЫЙ АНАЛИЗ Часть 2 ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

«Андрей Белянин Галина Черная Профессиональный оборотень. ГЛАВА 1 Вечер был довольно холодный. Да оно и закономерно январь месяц. Темнело по-прежнему рано, и возвращаться пришлось уже во мраке позднего вечера. Один раз даже в задумчивости чуть было не налетела на фонарный столб с соответственно разбитыми плафонами. Вот черт! Понаставили тут. прямо на дороге. Со злости не удержалась и пнула столб ногой. Настроение и так было никакое, теперь еще и мизинец ушибла. Полчаса назад в институте я...»

«Федеральное государственное образовательное учреждение высшего профессионального образования Чувашский государственный университет имени И.Н. Ульянова Батыревский филиал Кафедра экономических дисциплин КОНСПЕКТ ЛЕКЦИЙ по дисциплине Теория статистики Составитель: кандидат сельскохозяйственных наук, доцент Баданов Геннадий Павлович Батырево - 2009 Содержание 1. ПОНЯТИЕ О СТАТИСТИКЕ 1.1. ПРЕДМЕТ И МЕТОД СТАТИСТИКИ 1.2. СТАТИСТИЧЕСКОЕ НАБЛЮДЕНИЕ 1.3. СВОДКА И ГРУППИРОВКА СТАТИСТИЧЕСКИХ ДАННЫХ 1.4....»

«Е.В. Савицкая КУРС ЛЕКЦИЙ ПО МИКРОЭКОНОМИКЕ МОСКВА — 2002 Оглавление. Раздел I. Теория поведения потребителя. Глава 1. Отношение предпочтения, функция полезности и бюджетное 3 ограничение потребителя. Глава 2. Оптимальный выбор потребителя 23 и функции индивидуального спроса. 50 Глава 3. Сравнительная статика спроса. 75 Глава 4. Рыночный спрос. Эластичность спроса. Раздел II. Теория поведения производителя. Глава 5. Производственная функция. Глава 6. Издержки производства. Глава 7. Предложение...»

«Траумель – препарат, регулирующий воспалительный процесс IAH AC Траумель – препарат, регулирующий воспалительный процесс © IAH 2007 Настоящая лекция посвящена препарату Траумель в качестве новой категории препаратов для лечения воспалительных процессов. Фактически Траумель – не классическое НПВС, а препарат, регулирующий воспалительный процесс. Доводы в пользу этой гипотезы являются базой настоящей лекции. 1 Физиологические процессы • Большинство физиологических процессов в человеческом...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО РЫБОЛОВСТВУ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ О. Д. Мачкарина ФИЛОСОФИЯ КУРС ЛЕКЦИЙ Допущено Ученым советом университета в качестве учебного пособия по дисциплине Философия Мурманск 2009 УДК 1 (47+57) ББК 87.3 М 37 Рецензенты: С.Г. Лутонина, кандидат философских наук, доцент Л.Н. Каратаева, кандидат философских наук,доцент Мачкарина, О. Д. Философия. Курс лекций...»

«Лекция. Искусствоведение. Фотография Я пришел к тому, что есть изображение. Поверхностный слой этого изображения – это информация. Вот мы говорим: здесь идет электричка и переход лесом. Дело в том, что это главный тезис. На эту тему можно снять 10000 разных фотографий. И эта чем-то отличается, т.е. эта фотография имеет какие-то конкретные отличия и чем-то выделяется из этого числа. Она лучше или хуже, или она не такая, или она такая, как все. Значит, мы нашли в ней какие-то качества, которые...»

«Д. А. Паршин, Г. Г. Зегря Физика Колебания Лекция 16 ЛЕКЦИЯ 16 Hелинейные колебания. Фазовый портрет математического маятника. Осциллятор Дуффинга. Удвоение периода. Переход к хаосу. Отобpажение Пуанкаpе. Понятие о фpакталах. Пpедсказуемость хаотического движения. Нелинейные колебания Если амплитуда колебаний не мала, то в pазложении потенциальной энеpгии U (q) в pяд Тейлоpа по отклонению от положения pавновесия x = q q0 необходимо учитывать степени x выше втоpой. Физическая пpичина наличия...»

«Биологический факультет (Специальность биофизика) 2006/2007 Общая и неорганическая химия ЛЕКЦИИ Лекция 4. Агрегатные состояния вещества. Многокомпонентные системы. Растворы неэлектролитов. Агрегатные состояния вещества Многие вещества могут, в зависимости от внешних условий (температура, давление), находиться в трех агрегатных состояниях – твердом, жидком и газообразном. Простейшее определение: газы не имеют постоянных объема и формы при постоянной температуре; жидкости имеют постоянный объем,...»

«НОУ ВПО ИВЭСЭП НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ИНСТИТУТ ВНЕШНЕЭКОНОМИЧЕСКИХ СВЯЗЕЙ, ЭКОНОМИКИ И ПРАВА ПРАВОВОЕ РЕГУЛИРОВАНИЕ РЫНКА ЦЕННЫХ БУМАГ УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС по специальности 030501.65 Юриспруденция САНКТ-ПЕТЕРБУРГ 2011 ББК 67.402 П 68 Правовое регулирование рынка ценных бумаг: учебно-методический комплекс / Автор - составитель: С. Е. Шурупов. – СПб.: ИВЭСЭП, 2011. – 55 с. Утвержден на заседании кафедры...»

«ШКОЛА ПСИХО-АНТРОПОЛОГИИ Лекция № 1 Эти лекции представляют собой непосредственную и неисправленную запись курса лекций, прочитанных учащимся Школы Психо-Антропологии. Они предназначены исключительно для личного использования. Для более полного изучения обращаться к произведениям собрания ПСИХО-АНТРОПОЛОГИЯ издательства Эдисьон де ля Люмьер. СУЩНОСТЬ И ЛИЧНОСТЬ. ДВОЙНАЯ БИОГРАФИЯ ЧЕЛОВЕЧЕСКОГО СУЩЕСТВА (Б-4.10.94) От классической психологии Психо-Антропологию отличает то, что она обращается...»

«Лекция 3. Информационные системы управления предприятием 1. Понятие эффективного управления ИТ. Черты предприятий, осуществляющих эффективное управление ИТ: четко представляют стратегии бизнеса и роль ИТ в их реализации, ведут учет средств, затрачиваемых на ИТ, распределяют ответственность за организационные изменения, отличаются активностью вырабатывания набора управления ИТ. Эффект от использования аналитических систем обусловлен следующими факторами: – сокращение разрыва между аналитиком и...»

«Самостоятельное изучение иностранных языков с помощью интернет-ресурсов Максим Ильяхов Описание лекции Неформальная, ритмичная, динамичная лекция для школьников, призванная возбудить искренний интерес к самостоятельному изучению иностранных языков. Центральная идея подхода — отношение к школьникам как к взрослым, способным принимать самостоятельные решения, уважение их желаний и провозглашение их желаний и действий главным фактором их успеха. Одновременно с этим показываются очень интересные и...»

«ГОУВПО Федерального агентства по здравоохранению и социальному развитию (заведующая кафедрой - профессор М.В.Дегтярева) М.В.Дегтярева И м м у н и т е т новорожденных в норме и п р и патологии. И м м у н о т е р а п и я ликопидом. (обзор клинических исследований) Лекция для практикующих врачей М о с к в а 2010 3 И м м у н и т е т новорожденных в норме и при патологии. И м м у н о т е р а п и я ликопидом. (обзор клинических исследований) М.В. Дегтярева ГОУВПО Федерального агентства по...»

«А. А. ШАХМАМЕТЬЕВ МЕЖДУНАРОДНОЕ НАЛОГОВОЕ ПРАВО УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС для подготовки магистров по направлению 030500.68 Юриспруденция МОСКВА 2009 УДК ББК Ш 31 Ш 31 ШАХМАМЕТЬЕВ А. А. Международное налоговое право: Учебнометодический комплекс. – М.: Тровант, 2009. – 140 с. ISBN 978-5-89513-171-8 Автор: Шахмаметьев Алексей Алимович, доцент кафедры финансового права Государственного университета – Высшей школы экономики при Правительстве Российской Федерации, старший научный сотрудник Центра...»

«Негосударственное образовательное учреждение высшего профессионального образования ИНСТИТУТ ГОСУДАРСТВЕННОГО АДМИНИСТРИРОВАНИЯ Кафедра Государственно-правовых дисциплин Направление 030900.62 Юриспруденция ТАМОЖЕННОЕ ПРАВО Лекционный материал Составитель: Иткина В.Ю. Москва 2013 Лекция 1. Введение в курс таможенного права. Основы государственного регулирования внешнеторговой деятельности в РФ. 1. Понятие таможенного права. Предмет и метод правового регулирования 2. Таможенные правоотношений 3....»

«Лекция № 22 Усталость материалов. Предел выносливости. Диаграммы усталости. Расчеты на прочность при повторнопеременных напряжениях. 22. ПРОЧНОСТЬ МАТЕРИАЛОВ ПРИ ЦИКЛИЧЕСКИ МЕНЯЮЩИХСЯ НАПРЯЖЕНИЯХ 22.1. Понятие об усталости материалов К динамическим нагрузкам, несмотря на отсутствие значительных инерционных сил, можно отнести периодические многократно повторяющиеся (циклические) нагрузки, действующие на элементы конструкции. Такого рода нагружения характерны для большинства машиностроительных...»

«Электронные ресурсы библиотеки Электронный каталог. Стратегия поиска в базах данных библиотеки. Полнотекстовые ресурсы библиотеки. ЭБС Айбукс. Сайт библиотеки в локальной сети ВолГУ. Полнотекстовые базы данных, доступные через Интернет. Цель занятия – ознакомиться с электронными ресурсами библиотеки, правилами поиска в электронном каталоге библиотеки, другими доступными для читателей библиотеки электронными ресурсами. План занятия. Правила пользования залом электронных ресурсов, порядок...»

«ПРОБЛЕМА РАЗВИТИЯ И ИННОВАИЦОННАЯ ЭКОНОМИКА, лекция П.Г. Щедровицкого (20.04.01, ЛЭТИ) Щедровицкий. Эта лекция вторая из цикла, который представляет Центр стратегических разработок Северо-Запад. Первая лекция касалась проблем современного мышления. Та, которую я буду читать сегодня, в основном будет связана с проблематикой развития и, наконец, третья, которая пройдет 11-го мая, будет посвящена проблемам современной государственности. Я бы хотел представить вам несколько тезисов, которые...»









 
2014 www.konferenciya.seluk.ru - «Бесплатная электронная библиотека - Конференции, лекции»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.