Научно-методический журнал издается при участии Академии информатизации образования
Вид материала | Научно-методический журнал |
СодержаниеКолмогоровская алгоритмическая Сложность программ |
- Научно-методический журнал издается при участии, 1713.39kb.
- 10) [Текст]: научно-аналитический журнал (издаётся с 2007 г.), 5535.4kb.
- [Текст]: научно-аналитический журнал (издаётся с 2007 г.), 3560.33kb.
- 11) [Текст]: научно-аналитический журнал (издаётся с 2007 г.), 3594.13kb.
- 9) [Текст]: научно-аналитический журнал (издаётся с 2007 г.), 9826.34kb.
- [Текст]: научно-аналити-ческий журнал (издаётся с 2007 г.), 4433.08kb.
- Социальный конфликт научно-практический журнал, 1318.28kb.
- 8) [Текст]: научно-аналитический журнал серия «Право» (издаётся с 2007 г.), 15457.76kb.
- Журнал издается с 1991, 2949.78kb.
- Академии Медицинской Информациологии (на правах отделения Международной Академии Информатизации), 728.99kb.
Колмогоровская алгоритмическая Сложность программ
Программирование как целенаправленная деятельность обладает своей спецификой, а программные продукты не похожи ни на какую другую продукцию. Создание индустрии программных средств (ПС) наталкивается на значительные трудности, связанные прежде всего со сложностью ЭВМ, разобщенностью в процессе промышленного производства ПС между различными его элементами по содержанию, структуре, терминологии, времени исполнения, а также с технологическими, организационными и экономическими факторами. Основной стратегией производства ПС в развитых странах является выбор оптимального управления, планирования и экономического стимулирования развития качества, базирующегося на стремлении к нулевому уровню дефектности.
При оценке качества программных продуктом одним из важнейших показателей является сложность [3, 4]. Согласно А.Н. Колмогорову относительной сложностью объекта у при заданном х считается минимальная длина l(р) «программы» р получения у из х. Это определение зависит от «метода программирования». Метод программирования – это функция FI(р,х)=у, ставящая в соответствие программе р и объекту х объект у [2]:
![](images/293697-nomer-m3fc6b9f0.gif)
Рассмотрим это колмогоровское определение сложности применительно к программам. Пусть даны две программы Р1 и Р2, написанные на одном и том же языке программирования А. Нужно определить, какая из программ Р1 или Р2 сложнее. Исследуя тексты программ, написанных на языке программирования А, определяем таблицу частот употребления символов языка А в порядке их убывания. Эту последовательность символов
![](images/293697-nomer-m4c30c5f.gif)
![](images/293697-nomer-3e1b3e1b.gif)
![](images/293697-nomer-54aa4475.gif)
![](images/293697-nomer-m70dd5f98.gif)
![](images/293697-nomer-m583c9b73.gif)
![](images/293697-nomer-m1e92ac09.gif)
![](images/293697-nomer-m583c9b73.gif)
![](images/293697-nomer-m1e92ac09.gif)
![](images/293697-nomer-m583c9b73.gif)
![](images/293697-nomer-m1e92ac09.gif)
![](images/293697-nomer-2cc1697f.gif)
![](images/293697-nomer-m63ee02ac.gif)
![](images/293697-nomer-me78d1fd.gif)
![](images/293697-nomer-58a160e9.gif)
![](images/293697-nomer-m50ee3915.gif)
Очевидно, что
![](images/293697-nomer-m324511af.gif)
Считается, что программа Р1 сложнее Р2 , если z3>z4. Причем Р1 и Р2 могут быть реализациями как одного алгоритма, так и равных алгоритмом, т.е. возможно сравнение сложностей программ и алгоритмов. Точно определить относительную сложность программы К трудно, однако можно оценить верхнюю Кup и нижнюю Кlow границы К. Кup оцениваем по алгоритму, суть которого состоит в следующем. Если для программы Р=Р1Р2...Рn имеем последовательность символов S=
![](images/293697-nomer-7e3968e5.gif)
Изложенный подход позволяет сравнивать равные языки программирования. Действительно, пусть дан алгоритм, написанный на двух разных языках программирования А1 и А2 и реализованный в виде программ Р1 и Р2. Строим последовательности символов S1 и S2 для Р1 и Р2 соответственно. По каждому из символов из S1 и S2 берем среднее арифметическое их частот появления в программах, и таким образом получаем последовательность символов S0 для объединения языков А1 и А2. Строим расширения Р1 и Р2 до Р1* и Р2* соответственно. Далее проводится анализ, аналогичный анализу проведенному в случае двух программ, написанных на одном и том же языке программирования. Если программы достаточно длинные, то таблицы частот употребления символов языка можно расширить операторами, модулями программ или другими комбинациями символов языка, программирования.
Таким образом, изложенный подход позволяет дать численную оценку сложности программ и сравнить между собой сложность программ, алгоритмов и языков программирования.
Литература
- Ван дер Варден. Алгебра. – М.: Мир. – 1976.
- Колмогоров. А.Н. Алгоритм, информация, сложность. – М.: Знание. – 1991.
- Николис Г., Пригожин И. Познание сложного. – М: Мир. – 1990.
-
Boehm B.W. Software Engineering Economics. Prentice Hall, Inc., Englewood Cliffs, New Jersey, 1981.
сообщения
Е.А. Кашина
Нижнетагильский филиал Уральского гостехуниверситета
И.Е. Подчиненов
Уральский госпедуниверситет