86134

Библиотека алгоритмов на графах для платформы .NET

Курсовая

Информатика, кибернетика и программирование

На сегодняшний день программная платформа .NET является современным развитым средством решения прикладных задач. Microsoft .NET Framework — программная технология, предназначенная для создания, как обычных программ, так и веб-приложений.

Русский

2015-04-03

131.5 KB

3 чел.

Библиотека алгоритмов на графах для платформы .NET

Введение

Одной из сложнейших и интереснейших тем системного программирования является построение трансляторов. Кафедра системного программирования Мат-Меха СПбГУ [] не остаётся в стороне и ещё со времён своей предшественницы — Лаборатории системного программирования, активно участвует в решении задач из данной области.

На сегодняшний день программная платформа .NET является современным развитым средством решения прикладных задач. Microsoft .NET Framework — программная технология, предназначенная для создания, как обычных программ, так и веб-приложений. Целью данной работы является расширение опыта создания трансляторов  на .NET.

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

Среди проектов кафедры в области построения трансляторов стоит отметить библиотеку работы с графами  PranLib []. Она хорошо зарекомендовала себя благодаря высокой производительности и удобству использования. Авторы библиотеки считают, что во многом этим PranLib обязан языку реализации — Ocaml.

OCaml (Objective Caml) [] — современный объектно-ориентированный язык функционального программирования общего назначения. Был разработан в 1996 как реализация языка Caml с объектно-ориентированными конструкциями, модулями и функторами. В данный момент Ocamlopen source проект, поддерживаемый французским институтом INRIA (Institut national de recherche en informatique et en automatique). Инструментарий включает в себя компилятор в машинный код (для 9 самых известных архитектур), компилятор в байт-код, а также интерактивный интерпретатор для быстрой разработки. К достоинствам Ocaml относят:

  •  строгую типизацию;
  •  развитую систему модулей;
  •  автоматическую сборку мусора;
  •  эффективность;
  •  кроссплатформенность.

Сейчас основной функциональный АЯВУ, предлагаемый Microsoft для платформы .NETF#, основанный на OCaml. Причём компилятор F# способен понять простые программы на Ocaml без каких-либо изменений. Как и у OCaml, к преимуществам F# можно причислить практически те же пункты. Конечно, система модулей не реализована в F#, но этот недостаток компенсируется generic’ами .NET, поскольку классы .NET могут содержать не только поля и методы, но и вложенные классы. Сборка мусора выполняется средствами среды .NET. Что касается производительности, программа на F# может быть написана как «калька» соответствующей программы на С#, основного ЯП платформы, а значит производительность ограничена лишь особенностями самой платформы.1

Ядром PranLib является сторонняя библиотека OcamlGraph [], также как и Ocaml разрабатываемая INRIA. Она содержит типы для представления графов, реализацию наиболее известных алгоритмов, а так же функции для сериализации/десериализации графов. При этом OcamlGraph – библиотека бесплатная и с открытыми исходными кодами.

Мы приняли решение, как и в случае PranLib, не реализовывать такие базовые вещи, как представление графа, заново, а использовать что-то готовое, дописав поверх свои структуры и алгоритмы. Стоит отметить, что FCL (Framework Class Library) не содержит никакого API для работы с графами. Поэтому пришлось искать сторонние библиотеки для .NET. Причём, благодаря возможностям CLR,  не имеет значения, на каком языке они написаны. Например, служба, написанная на Managed C++ для Microsoft .NET, может обратиться к методу класса из библиотеки, написанной на Delphi; на C# можно написать класс, наследованный от класса, написанного на Visual Basic .NET, а исключение, брошенное методом, написанным на C#, может быть перехвачено и обработано в Delphi. Это достигается компиляцией программы на любом .NET языке в CIL (Common Intermediate Language) – объектно-ориентированный ассемблер, созданный Microsoft. К сожалению, единственным вариантом оказалась набирающая популярность библиотека QuickGraph [].

QuickGraph полностью написан на C#, исходные коды, как и в случае с OcamlGraph, открыты. Функциональности обеих библиотек схожи: структуры для представления графов, алгоритмы, сериализация/десериализация графов. Библиотека активно поддерживается. Доступна версия QuickGraph 2.0 для использования в среде .NET Framework 2.0, а также более современная QuickGraph 3.5. Правда последняя может работать только в среде .NET Framework 3.5 и выше, поскольку использует некоторые нововведения (например, Extension Methods).

Но важнейший вопрос, который необходимо проанализировать сначала, это проверить, не является ли использование QuickGraph путём тупиковым. Если вдруг по каким-то причинам QuickGraph написан не оптимальным образом, то вся дальнейшая работа с ней теряет смысл. Следовательно, необходимо создать некоторые тесты для OcamlGraph и QuickGraph. Сравнение производительности и последующий анализ результатов этих двух библиотек – это задача курсовой работы.


Решение задачи

Самая первая задача – это установка необходимого программного обеспечения. Все действия, описанные далее, выполнялись в операционной системе Windows XP SP3.Для сборки библиотек Pranlib и Ocamlgraph необходим компилятор Ocaml версии 3.10.2. Он был собран с помощью GODI [] – программной среды для Ocaml, под Cygwin.

Стоит отметить, что компилятор Ocaml также входит в Cygwin. Поэтому теоретически кроме установки Cygwin ничего не требуется. Однако в библиотеку входит не последняя версия. Причём настолько не последняя, что Ocamlgraph 1.0 не может быть скомпилирован ею.

Для программирования на платформе .NET была выбрана версия Microsoft .NET Framework 3.5. Соответственно версия QuickGraph также для .NET 3.5 (кроме неё есть версии для .NET 2.0 и Silverlight). Стоит отметить, что функциональность версий 2.0 и 3.0 одинакова. Структуры данных внутри классов библиотеки тоже совпадают. Но с версией 3.0 более удобно работать в связи с некоторыми новинками в .NET 3.5 (Extension methods).

Среда для разработки – Microsoft Visual Studio 2008 Standard Edition. Впрочем, иметь среду разработки для выполнения всех шагов совсем не обязательно. С официального сайта Microsoft можно бесплатно скачать и установить .NET последней версии, а также .NET SDK (Software Development Kit). С его помощью любой проект можно собрать утилитами из командной строки.

Таким образом список используемого ПО:

  •  Ocamlgraph 1.0;
  •  Компилятор Ocaml 3.10.2 под Cygwin;
  •  QuickGraph 3.5;
  •  .NET Framework 3.5;
  •  Microsoft Visual Studio 2008 Standard Edition или .NET SDK;

Далее нужно переходить к написанию самих тестов. Нам необходимо протестировать эффективность алгоритмов и структур для графов в QuickGraph, поверх которых далее были бы написаны основные алгоритмы, необходимые для создания транслятора. Таким образом, необходимо найти в библиотеках реализации одного и того же алгоритма и измерить скорость исполнения. Ясно, что алгоритмам нужно подать на вход граф и, следовательно, нам также потребуется генератор графов. В итоге получаем 3 этапа:

  •  создание генератора графов;
  •  поиск алгоритма, реализованного в QuickGraph и OcamlGraph;
  •  запуск и замер скорости исполнения выбранного алгоритма для каждой библиотеки

Итак, первым этапом является создание генератора графов. Соответствующие функции для генерации доступны в обеих библиотеках. Но необходимо проанализировать форматы, поддерживаемые QuickGraph и OcamlGraph, поскольку граф должен быть прочитан  программами на разных языках. OcamlGraph способен работать с двумя форматами:

  •  DOT формат – текстовый формат описания графа. Он достаточно удобен для восприятия человеком, поскольку просто описывает список вершин и дуг. Вот пример ориентированного графа с 4 вершинами и 3 дугами:

digraph graphname {

    a -> b;

    a -> c;

    b -> d;

}

  •  GML – также текстовый формат, но с немного более нагруженным синтаксисом:

graph [

   comment "This is a sample graph"

   directed 1

   label "Hello, I am a graph"

   node [

       id 1

   ]

   node [

       id 2

   ]

   edge [

       source 1

       target 2

   ]

]

Библиотека QuickGraph поддерживает больше способов сериализации:

  •  .NET Serialization – запись в бинарный файл, используя стандартные механизмы
  •  GraphML – специальный формат, по характеристикам напоминающий GML, но основанный на XML
  •  Xml – запись в xml файл. Можно задать теги для графа, вершин и дуг.
  •  DOT формат, но только для записи! Предполагается, что с помощью DOT файла граф можно будет просмотреть с помощью стороннего инструмента.

Анализируя всё вышесказанное, получается, что единственный способ – это написать генератор на .NET в DOT формат для OcamlGraph и в любой формат для QuickGraph. Но здесь возникла неожиданная проблема. Хотя обе библиотеки пишут в DOT формат, файлы одной другая не понимает. Типичное описание дуги в файле, полученном из QuickGraph:

21655 -> 11 [];

А OcamlGraph печатает его следующим образом:

21655 -> 11;

В квадратных скобочках по спецификации должны идти атрибуты дуги. Видно, что в текущем примере атрибутов нет. Интересно, что согласно спецификации DOT формата [] оба способа уместны! Вот фрагмент грамматики для описания дуги и её атрибутов:

edge_stmt : (node_id | subgraph) edgeRHS [ attr_list ]

attr_list : '[' [ a_list ] ']' [ attr_list ]

К счастью, QuickGraph не пишет в файл напрямую. Метод, который генерирует текст в DOT формате, принимает в себя интерфейс IDotEngine, единственный метод которого должен записать полученную строку в файл. В QuickGraph есть класс FileDotEngine, который реализует IDotEngine. И его реализация тривиальна – записать данную строку в данный файл. Поскольку атрибуты дуг нам не нужны, то лишние квадратные скобочки стоит убрать.

Был выбран язык C#, так как все примеры в документации QuickGraph написаны на нём.

Этапы создания генератора следующие. Нужно выбрать тип для вершины. По идее вершиной может быть всё что угодно, поскольку в QuickGraph везде используется механизм generics (шаблоны в .NET). Т.е. ни один алгоритм не использует точный тип графа, вершин и рёбер. Единственное, что от них требуется – это реализовывать некоторые интерфейсы. В нашем случае вершины – это числа Int32. Количество вершин и рёбер – это константы, вынесенные из кода. Эти параметры подбирались в дальнейшем. За генерацию графа отвечает класс RandomGraphFactory. Он способен генерировать ориентированные графы. Для теста на .NET сохраняется граф в бинарном формате, используя механизм .NET сериализации. Чтобы сохранить DOT файл пришлось создать свою реализацию IDotEngine, которая содержит всего одну дополнительную строчку:

dotData = dotData.Replace("[]", "");

Таким образом, лишние скобочки удаляются, а результат попадает в файл. После завершения работы генератора на выходе получаем два файла: output.bin и output.dot. Для QuickGraph и OcamlGraph соответственно.

Далее в обеих библиотеках необходимо выбрать один и тот же алгоритм и запустить его на одном и том же графе. Причём возможно несколько раз, чтобы время теста не было слишком маленьким. Если работа какого-то алгоритма занимает, скажем, 50мс, то сравнивать производительность вообще некорректно. Поскольку это число сопоставимо с разрешением счётчика, то в другой раз ответ может быть 0мс. Иными словами, как повезёт.

Логичным кажется взять очень известный алгоритм Дейкстры поиска минимального пути между вершинами (каждая дуга имеет вес). Этот алгоритм есть и в QuickGraph, и в OcamlGraph. Но, к сожалению, использовать его для сравнения невозможно. Дело в том, что интерфейсы в библиотеках разные. В OcamlGraph функция принимает две вершины и выдаёт кратчайший путь между ними. В QuickGraph метод принимает одну вершину и ищет расстояния сразу до всех. Понятно, что если мы нашли кратчайший путь из v1 в v2, то, хотим мы того или нет, мы знаем кратчайший путь из v1 до любой вершины на найденном пути. Поэтому заставлять OcamlGraph искать пути от данной до всех вершин по очереди, теряя на каждом шаге предыдущие результаты, и потом сравнивать с QuickGraph абсолютно некорректно.

Для сравнения был выбран алгоритм проверки наличия циклов. В QuickGraph у класса графа есть соответствующий метод IsDirectedAcyclicGraph. В OcamlGraph в модуле Graph.Pack.Digraph есть функция Marking.has_cycle. Теперь о графе-примере. Это обязательно должен быть граф без циклов. Ведь при удачном стечении обстоятельств цикл можно найти сразу, не обходя все дуги. Интересная особенность обнаружилась при тестировании разных графов. Допустим, мы фиксируем число вершин – 100000. Если генерируется граф с 100000 рёбер, то OcamlGraph очень быстро находит цикл. Если взять меньше дуг, то цикл ищется дольше в несколько раз. Оптимальным оказалось число дуг – 50000. Граф получается разряженный и без циклов. Таким образом, мы гарантируем, что алгоритм «прогуляется» по всем вершинам и дугам.

Число дуг

Время исполнения 100 итераций (мс)

100000

0,375

80000

1,141

50000

2,600

40000

2,200

Все описанные запуски производились на процессоре Intel Core 2 Quad 2.5 GHz. Никакие другие ресурсоёмкие задачи параллельно не исполнялись. Алгоритм запускался в цикле 100 раз на Ocaml и на C#. Программа на Ocaml была скомпилирована в машинный код командой «ocamlopt graph.cmxa camlTest.ml». Версия под .NET – также релизная, с параметром «/optimize».

По логике код на C# также должен быть скомпилирован в ассемблер перед запуском. В противном случае по ходу алгоритма неизбежно тратилось бы время на JIT компиляцию CIL кода. Каждый метод компилируется в момент первого обращения к нему. Поэтому на старте доля JIT компиляции может достигать 100%. Но обойтись без JIT компиляции можно.

Вместе с .NET SDK поставляется утилита ngen, которая компилирует сборку и все её зависимости в машинный код. После этого результат кладётся в специально устроенный кэш (Native image cache). Исходная сборка (в нашем случае exe файл) никак не меняется. Но если теперь пользователь запустит этот файл, .NET Framework поищет уже скомпилированный образ в кэше, найдёт его, загрузит и будет исполнять ранее скомпилированный. Если не найдёт или поймёт, что сборка изменилась, то как и раньше будет запущен JIT компилятор.

Вопрос об ускорении программы  после использования ngen достаточно глубокий. С одной стороны, может наблюдаться ускорение программы на старте, т.к. не нужно запускать компилятор. С другой стороны, может замедлиться вызов между сборками. Поскольку при JIT компиляции абсолютные адреса вызываемых методов уже известны, то JIT-компилятор генерирует ассемблерную инструкцию наподобие «call 0x7C90DADE». Ngen сделать то же самое чаще всего не способен, поэтому в этом месте могут возникнуть заглушки. Это не оптимально. В нашем случае один и тот же код вызывается 100 раз, поэтому уже после первой итерации всё, что нужно, будет скомпилировано. Следовательно, ожидать ощутимой выгоды от ngen не приходится. И действительно результаты с использованием ngen и без него примерно одинаковы.

Результаты следующие. Ocaml выполнил 100 итераций в среднем за чуть меньше чем 2,6 сек. C# код исполнялся 5,5 сек… Время на загрузку графа конечно же не учитывалось. Обе программы выдали одинаковый результат – отсутствие циклов. Любопытно, что в примере с циклами (100000 дуг) Ocaml управлялся за 1/2 секунды! C# тратил 7 секунд. Очевидно, что алгоритм не остановился после нахождения первого цикла, а выполнил полный проход в глубину. Такой результат наводит на мысли о плохой реализации алгоритма. Впрочем, для графа без циклов это совсем не обязательно. Оптимизируя программу на .NET необходимо помнить о сборке мусора. Ведь то, что заявлено, как преимущество платформы, может обернуться ахиллесовой пятой.

Сборка мусора работает следующим образом. При вызовах new выделяются последовательные блоки требуемой длины, поэтому new в основном работает очень быстро.  Кроме того, все эти блоки принадлежат поколению 0. Как только памяти в куче поколения 0 не хватает, происходит сборка мусора в поколении 0. Строится дерево достижимых объектов (корни дерева – глобальные переменные и указатели на стеке). Все недостижимые объекты считаются мусором. Достижимые объекты уплотняются и переводятся в поколение 1. Причём это может спровоцировать сборку мусора в поколении 1 по той же схеме. Поколение 0 теперь пусто.  Всего поколений 3. Реже всего сборка мусора происходит в 2 поколении, чаще всего в 0.  Размеры поколений вручную не устанавливаются и могут быть изменены сборщиком мусора по ходу исполнения программы. Совершенно ясно, что все потоки должны быть приостановлены на время сборки мусора. Или хотя бы на время уплотнения кучи, т.к. физические адреса объектов меняются, и указатели нужно обновлять. Существуют 3 стратегии для сборки мусора в .NET:

  •  Server. Для приложения в конфигурационном файле (app.config) нужно установить параметр «gcServer enabled» в true. Предполагается, что приложение исполняется на нескольких процессорах, у каждого своя куча. В момент сборки мусора все потоки останавливаются, на каждом процессоре запускается высокоприоритетный поток, который чистит свою кучу. Никакого выигрыша этот способ нам дать не способен, т.к. и так работает один поток. Наш пример при нём замедляется до 6 секунд.
  •  Workstation, concurrent. Это значение по умолчанию. Но можно также выставить gcServer  = false и gcConcurrent  = true. Дерево достижимых объектов строится параллельно. Но потоки всё равно останавливаются. Именно при таком значении тест длился чуть меньше 5,5 секунд.
  •  Workstation, Non-concurrent. Параметры gcServer и gcConcurrent нужно установить в false. Вся сборка мусора одним потоком. По сравнению с предыдущим параметром наблюдается незначительное падение производительности – примерно на 50мс.

Посмотреть статистику по сборке мусора можно с помощью встроенных performance counters.

Жирным выделен график процента процессорного времени, затраченного на сборку мусора. Синий – график размера кучи для больших объектов. Зелёный – график размера кучи поколения 1. Работа алгоритма началась в тот момент, когда прервались горизонтальные линии. До этого момента – простой. Пики у всех графиков совпадают. Максимальный процент сборки мусора на этом графике – 4%, в других запусках доходил до 14%. Но в остальное время он близок к 0. Размер кучи больших объектов достигает 32,5 Мб. Далее стабилизируется на уровне 9Мб. Максимальный размер кучи 1 поколения на данном графике меньше 1 Мб. Хотя при других запусках он достигал нескольких мегабайт.

Итак, на сборку мусора не уходит много времени. Мы решили написать свой вариант этого алгоритма. Для поиска цикла нужно запустить поиск в глубину и остановиться в тот момент, когда очередная дуга ведёт в какую-то обрабатываемую вершину. Результат оказался 3,3 сек, что вполне сравнимо с Ocaml.

Таким образом, причина долгой работы – неоптимальный алгоритм  или недостатки конкретной реализации. Оставим это за рамками данной работы.

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

В Ocamlgraph соответствующая функция лежит в модуле Graph.Sig_pack.Components. В QuickGraph соответствующий класс StronglyConnectedComponentsAlgorithm  лежит пространстве имён Algorithms.ConnectedComponents. Как и раньше, алгоритм запускается 100 раз.

Нетрудно предсказать, что в предыдущем примере без циклов число компонент 100000. C# выдал этот результат за 11,4 сек. Причём при использовании ngen результат улучшился до 11 сек. А вот Ocaml трудился 13 секунд! В следующем примере мы взяли 100000 вершин и дуг. В нём оказалось 99900 компонент. Разрыв по времени тоже около 2 секунд – 13,84 и 15,67. Последним оказался пример с 10000 вершин и 100000 рёбер. В нём 1 компонента. Это оказалось катастрофой для Ocaml. C# работал 4,15 сек, Ocaml – 8,5 сек! Причём походу работы .NET расходовал памяти в районе 25 мб, Ocaml выделил к концу работы около 60 Мб!

В данной ситуации результат действительно обусловлен сборкой мусора. В Ocaml память также освобождается автоматически. Причём в отличие от .NET параметры сборщику мусора можно выставлять. Мы выставили следующие параметры:

Gc.space_overhead = 3000;

Gc.minor_heap_size = 256*1024;

Gc.max_overhead = 1000000;

Gc.major_heap_increment = 2*1024*1024

Если не вдаваться в подробности, то это значит

  •  Куча не будет уплотняться
  •  Сборка мусора производится редко
  •  Приращение кучи при нехватке памяти – 4Мб

После чего результат Ocaml стал очень близок к .NET – 4,22 сек. Но при этом памяти расходуется свыше 200 Мб, что несопоставимо с результатом .NET.

Таким образом, автоматическая сборка мусора может крайне неблагоприятно влиять на скорость работы программы. При этом сборщик мусора .NET Framework, благодаря динамическому изменению размеров поколений, показал себя более гибким, чем у Ocaml.

Переходя к результатам. Библиотека QuickGraph показала приемлемый результат. Огромным плюсом в пользу выбора QuickGraph является постоянная поддержка разработчиков. В частности на официальном сайте QuickGraph в разделе “Discussions” ведётся постоянное обсуждение улучшения производительности тех или иных алгоритмов. Например, есть предложение альтернативной реализации генератора графов, дающее ускорение на порядок при большом количестве вершин/дуг. Другой пример – реализация алгоритма построения сильно связанных компонент для изменяющихся графов. Добавление этой функциональности позволит значительно быстрее получать результат в случае, если в граф добавили/удалили несколько рёбер. Все эти факты подтверждают, что QuickGraph является перспективной библиотекой. И её использование в дальнейших разработках кафедры поможет создать основу для решения задач построения трансляторов на .NET.

Использованные источники:

  1.  Сайт кафедры системного программирования СПбГУ. http://se.math.spbu.ru
    1.  Библиотека Pranlib. http://oops.tepkom.ru/projects/pranlib/
    2.  Язык Ocaml. http://caml.inria.fr/ocaml/index.en.html
    3.  Библиотека OcamlGraph. http://ocamlgraph.lri.fr/
    4.  Библиотека QuickGraph. http://www.codeplex.com/quickgraph/
    5.  Среда GODI. http://godi.camlcity.org/godi/index.html
    6.  Спецификация DOT формата. http://www.graphviz.org/doc/info/lang.html
    7.  Д. Рихтер «Программирование на платформе .NET Framework» ISBN:5-469-00820-7

1 Более подробную информацию можно найти на интернет ресурсах сообщества F# разработчиков:
http://cs.hubfs.net/forums/thread/3207.aspx
http://strangelights.com/blog/archive/2007/06/17/1588.aspx


 

А также другие работы, которые могут Вас заинтересовать

28698. Октябрьское вооруженное восстание 1917 г. и установление диктатуры пролетариата в России 13.87 KB
  Комитет состоял из представителей армии профсоюзов фабричнозаводских комитетов военных секций Советов и др. Важная роль в становлении Советского государства и государственного аппарата принадлежала Всероссийскому съезду Советов рабочих и солдатских депутатов. Ленин выдвинул идею – диктатуры пролетариата в виде республики Советов. Новый госный строй России – диктатуру пролетариата в виде республики Советов окончательно утвердила принятая 10 июля 1918 г.
28699. II-ой Всероссийский съезд Советов, его состав. Исторические декреты съезда о мире и земле 12.38 KB
  IIой Всероссийский съезд Советов его состав. Исторические декреты съезда о мире и земле. Важная роль в становлении Советского гос0ва и государственного аппарата принадлежала Всероссийскому съезду Советов рабочих и солдатских депутатов. Съезд больш.
28700. Слом старого государственного аппарата после Октябрьского вооруженного восстания1917г Упразднение органов буржуазного самоуправления. Роспуск Учредительного собрания 12.77 KB
  Руководство этим процессом осуществляли Всероссийские съезды Советов Петроградский ВРК ВЦИК НКВД и другие органы. когда Декретом ВЦИК и СНН упразднялись все сословия и сословные организации и учреждения. Председатель ВЦИК Я. Свердлов от имени ВЦИК и ЦК партии большевиков зачитал и предложил принять Декларацию прав трудящегося и эксплуатируемого народа.
28701. Военно-революционный комитет Петрограда и его роль в переходе власти к Советам. Создание милиции, судебных органов, ВЧК и Красной Армии, их компетенции и борьба против контрреволюции 14.26 KB
  Создание милиции судебных органов ВЧК и Красной Армии их компетенции и борьба против контрреволюции.10 вводится в действие приказ По рабочей милиции. НКВД и Наркомюст утвердили совместную инструкцию Об организации советской рабочекрестьянской милиции. Руководство органами милиции осуществляло Главное управление рабочекрестьянской милиции НКВД РСФСР.
28702. «Декларация прав трудящегося и эксплуатируемого народа», ее содержание и значение 12.2 KB
  Декларация прав трудящегося и эксплуатируемого народа ее содержание и значение. Декларация Прав Трудящегося И Эксплуатируемого Народа важнейший конституционный акт Советской республики законодательно закрепивший завоевания Октябрьской революции и провозгласивший основные принципы и задачи социалистического государства. Декларация была утверждена III Всероссийским съездом рабочих солдатских и крестьянских депутатов. Декларация состояла из четырех разделов.
28703. «Декларация прав народов России», ее содержание и значение 15 ноября 1917 г. 11.56 KB
  Декларация прав народов России ее содержание и значение 15 ноября 1917 г. Исполняя волю съездов Совет Народных Комиссаров решил положить в основу своей деяти по вопросу о национальностях России следующие начала: 1 Равенство и суверенноcть народов России. 2 Право народов России на свободное самоопределение вплоть до отделения и образования самостоятельного государства. 4 Свободное развитие национальных меньшинств и этнографических групп населяющих территорию России.
28704. Мероприятия Советского государства по созданию новой экономики. Национализация банков связи, транспорта, внешней торговли, крупной промышленности 13.92 KB
  ВСНХ принял постановление согласно котму все частные предпря с числом рабочих свыше 5 при наличии механического двигателя на предприятии или 10 без двигателя человек объявлялись национализированными. органа по рукву эккой страны учреждался Высший совет народного хозва ВСНХ. ВСНХ действовал в качестве органа при правве. ВСНХ д.
28705. Основные направления в развитии гражданского, уголовного, колхозного и трудового права с конца 50-х и до середины 80-х гг. XX в. 13.31 KB
  СССР 1977 г. СССР регулировала также личную собствсть граждан. Закрепляя право на труд Конституция СССР 1977 г. Одновременно в Конституции содержались положения об обязанности каждого гражданина СССР добросовестно трудиться в избранной им области строго соблюдать трудовую и производственную дисциплину.
28706. Разработка и принятие Конституции СССР 1977 г. Ее основные положения. Закрепление однопартийной системы в стране 12.86 KB
  Политическую основу СССР составляют Советы народных депутатов, Основой эк-кой системы признана социалистическая собст-ть на средства пр-ва. В Конст. констатировались построение развитого социалистического общества и создание общенародного гос.ва. В ней закреплялись «руководящая и направляющая» роль Коммунистической партии и новые формы