по Общей теории систем и системный анализ (стр. 13 из 13)
Proc SimpleCountingSort
For i=0 to k-1 do
Count[i]=0;
For i=0 to n-1 do
Count[A[i]]=Count[A[i]]+1;
For i=0 to k-1 do
Count2[i]:=Count[i];
Sum=0;
For i=1 to k-1 do
Begin
Sum=Sum+Count2[i-1];
Count[i]=Sum;
End;
For i=0 to n-1 do
Begin
c=A[i];
B[Count[c]]=c;
Count[c]=Count[c]+1;
End;
EndProc
9.2 Алгоритм со списком
Этот вариант (англ. pigeonhole sorting, count sort) используется, когда на вход подается массив структур данных, который следует отсортировать по ключам (key). Нужно создать вспомогательный массив C[0..k - 1], каждый C[i] в дальнейшем будет содержать список элементов из входного массива. Затем последовательно прочитать элементы входного массива A, каждый A[i] добавить в список C[A[i].key]. В заключении пройти по массиву C, для каждого
в массив A последовательно записывать элементы списка C[j]. Алгоритм устойчив.ListCountingSort
for i = 0 to k - 1
C[i] = NULL;
for i = 0 to n - 1
C[A[i].key].add(A[i]);
b = 0;
for j = 0 to k - 1
p = C[j];
while p != NULL
A[b] = p.data;
p = p.next();
b = b + 1;
9.3 Устойчивый алгоритм
В этом варианте помимо входного массива A потребуется два вспомогательных массива — C[0..k - 1] для счётчика и B[0..n - 1] для отсортированного массива. Сначала следует заполнить массив C нулями, и для каждого A[i] увеличить C[A[i]] на 1. Далее подсчитывается число элементов меньше или равных текущему. Для этого каждый C[j], начиная с C[1], увеличивают на C[j - 1]. На последнем шаге алгоритма читается входной массив с конца, значение C[A[i]] уменьшается на 1 и в каждый B[C[A[i]]] записывается A[i]. Алгоритм устойчив.
StableCountingSort
for i = 0 to k - 1
C[i] = 0;
for i = 0 to n - 1
C[A[i]] = C[A[i]] + 1;
for j = 1 to k - 1
C[j] = C[j] + C[j - 1];
for i = n - 1 to 0
C[A[i]] = C[A[i]] - 1;
B[C[A[i]]] = A[i];
9.4 Обобщение на произвольный целочисленный диапазон
Возникает несколько вопросов. Что делать, если диапазон значений (min и max) заранее не известен? Что делать, если минимальное значение больше нуля или в сортируемых данных присутствуют отрицательные числа? Первый вопрос можно решить линейным поиском min и max, что не повлияет на асимптотику алгоритма. Второй вопрос несколько сложнее. Если min больше нуля, то следует при работе с массивом C из A[i] вычитать min, а при обратной записи прибавлять. При наличии отрицательных чисел нужно при работе с массивом C к A[i] прибавлять |min|, а при обратной записи вычитать.
Анализ
В первых двух алгоритмах первые два цикла работают за Θ(k) и Θ(n), соответственно; двойной цикл за Θ(n + k). В третьем алгоритме циклы занимают Θ(k), Θ(n), Θ(k) и Θ(n), соответственно. Итого все три алгоритма имеют линейную временную трудоёмкость Θ(n + k). Используемая память в первых двух алгоритмах равна Θ(k), а в третьем Θ(n + k).
9.5 Квадратичный алгоритм сортировки подсчётом
Также сортировкой подсчётом называют немного другой алгоритм. В нём используются входной массив A и вспомогательный массив B для отсортированного множества. В алгоритме следует для каждого элемента входного массива A[i] подсчитать количество элементов меньших него c1 и количество элементов, равных ему, но стоящих ранее c2 (c = c1 + c2). B[c] присвоить A[i]. Алгоритм устойчив.
SquareCountingSort
for i = 0 to n - 1
c = 0;
for j = 0 to n - 1
if A[j] < A[i]
c = c + 1;
for j = 0 to i - 1
if A[i] == A[j]
c = c + 1;
B[c] = A[i];
Анализ
Очевидно, временная оценка алгоритма равна Θ(n2), память Θ(n).
ЗАКЛЮЧЕНИЕ
Необходимым условием возможности использования многокритериального подхода является измерение эффективности пути в одинаковых единицах или наличие способа приведения к этому условию.
Процесс управления сложными иерархическими многоуровневыми системами невозможен без применения информации, которая не может быть выражена количественно. Это семантическая информация, не имеющая количественного выражения, но обладает определенным количественным смыслом.
Критерии эффективности. При реализации систем управления весьма важным вопросом является выбор критерия их эффективности. Под критерием эффективности понимается степень достижения целей системой управления.
Многокритериальные оценки эффективности – независимые, самостоятельные критерии эффективности.
Необходимым условием возможности использования многокритериального подхода является измерение эффективности пути в одинаковых единицах или наличие способа приведения к этому условию.
При принятии решений выработка рационального (оптимального) решения является результатом реализации объективного аналитического процесса.
В процессе реализации рационального подхода к принятию решений решаются задачи поиска, распознавания, классификации, упорядочения и выбора. Для этого могут применяться различные математические методы и модели с целью рационализации (оптимизации) выходных результатов. В целях оказания помощи при подготовке решений могут привлекаться эксперты.
Многокритериальные оценки эффективности – независимые, самостоятельные критерии эффективности. Для многих сложных систем управления выбрать критерии эффективности первого и второго рода, представляющие собой скалярные критерии, не представляется возможным. В этом случае используются векторные критерии, обеспечивающие выбор функций управления, оптимальных по Парето. Множество функций управления, оптимальных по Парето, включают в себя фактически не сравнимые по скалярным критериям функции управления, то есть такие, о которых нельзя сказать, какие из них являются наилучшими.
В этом случае применяются многокритериальные оценки эффективности систем управления с выделением наиболее лучших и наименее эффективных функций управления.
Эта многоплановость реальной жизни имеет важные последствия для системного анализа. С одной стороны, системный анализ имеет междисциплинарный характер. Системный аналитик привлекает к исследованию системы данные из любой отрасли знаний, привлекает экспертов любой специальности, если этого потребуют интересы дела. С другой стороны, перед ним встает неизбежный вопрос о допустимой минимизации описания явления.
Начиная с некоторого уровня сложности, систему легче изготовить и ввести в действие, преобразовать и изменить, чем отобразить формальной моделью, поскольку имеется принципиальная ограниченность формализованного описания развивающихся самоорганизующихся систем.
В соответствии с гипотезой фон Неймана простейшим описанием объекта, достигшего некоторого порога сложности, оказывается сам объект, а любая попытка его строгого формального описания приводит к чему-то более трудному и запутанному.
Адаптивность. В зависимости от степени организованности выделяют классы хорошо организованных систем (их свойства можно описать в виде детерминированных зависимостей), плохо организованных (или диффузных) и самоорганизующихся (включающие активные элементы)
Проблемы и цели. Первые шаги в системном анализе связаны с формулированием проблемы. Хотя необходимость системного анализа возникает тогда, когда проблема уже не только существует, но и требует решения, когда инициатор системного анализа («заказчик») уже сформулировал свою проблему, системный аналитик знает, что первоначальная формулировка – лишь очень приблизительный намек на то, какой именно должна быть действительная рабочая формулировка проблемы. На самом деле любая исходная формулировка проблемы является лишь «нулевым приближением». Системное исследование всякой проблемы начинается с расширения ее до проблематики, то есть нахождения системы проблем, существенно связанных с исследуемой, без учета которых она не может быть решена.
Важность правильно выбранной цели состоит в том, что выбор неправильной цели приводит не столько к решению проблемы, сколько к появлению новых проблем.
Индивидуальный потенциал в связке с целями организации. Самый лучший способ максимизировать эффект от результатов труда отдельных сотрудников на доходность предприятия, это связать этот труд со стратегическими целями организации. Такие связи должны разрабатываться целенаправленно и таким образом, чтобы они впоследствии гарантировали коммерческий успех фирмы.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Мыльник В.В., Титаренко Б.П., Волочиенко В.А. Исследование систем управления: Учебное пособие для вузов. – 2-е изд., перераб. и доп. – М: Академический Проект; Екатеринбург: Деловая книга – 2003. – 352 с. – («Gaudeamus»).
2. Подиновский В.В., Ногин В.Д. Паретооптимальные решения многокритериальных задач. М., Наука, 1982.
3. Ларичев О.И. Теория и методы принятия решений. М., 2000.
4. Ногин В.Д. Использование количественной информации об относительной важности критериев в принятии решений.// «Научно-технические ведомости СПбГТУ», 2000, № 2, с. 89-93.
5. Психология человека в современном мире. Том 2. Проблема сознания в трудах С. Л. Рубинштейна, Д. Н. Узнадзе, Л. С. Выготского. Проблема деятельности в отечественной психологии. Исследование мышления и познавательных процессов. Творчество, способности, одаренность (Материалы Всероссийской юбилейной научной конференции, посвященной 120-летию со дня рождения С. Л. Рубинштейна, 15–16 октября 2009 г.) / Ответственные редакторы: А. Л. Журавлев, И. А. Джидарьян, В. А. Барабанщиков, В. В. Селиванов, Д. В. Ушаков. – М.: Издво «Институт психологии РАН», 2009. – 404 с.
6. Анохин Петр Кузьмич. Принципиальные вопросы общей теории функциональных систем 1973 год
7. Фролов С.С. Цели организации http://www.iteam.ru/articles.php?tid= 2&pid=1&sid=27&id=119
8. Петухов Д.В. Стратегический менеджмент Часть 1 Учебный курс (учебно-методический комплекс) http://www.e-college.ru/xbooks/xbook103/book/index/index.html?go=part-006*page.htm
Приложения (при необходимости).
[1] Вильфредо Парето (1848-1923) – итальянский социолог и экономист.
[2] Минимизация компоненты равносильна максимизации этой компоненты, взятой с обратным знаком.