Основными параметрами, характеризующими конструктивно технологические и схемотехнические особенности больших интегральных схем, являются: степень интеграции, функциональная сложность, интегральная плотность, функциональная плотность и информационная сложность . Степень интеграции, количественно определяемая десятичным логарифмом от числа элементов, расположенных на подложке и образующих микросхему, является наиболее общей характеристикой схем с высокой степенью интеграции. [17]
Понятие сложности для систем управления является таким же кардинальным понятием, как информация. Информационная сложность , согласно Колмогорову, — это длина самого короткого двоичного слова, содержащего всю информацию, необходимую-для восстановления рассматриваемого текста. Но при проектировании систем автоматического управления необходимо ввести понятие сложности, связанное не только с их информационными свойствами, но и с их техническими характеристиками. [18]
В настоящее время накоплен достаточно большой материал по оценкам сложности различных классов объектов при тех или иных формальных определениях понятия сложность. Это и информационная сложность ряда классов непрерывных экстремальных задач , и сложность синтеза основных классов так называемых управляющих систем ( схемы, формулы, алгоритмы), и алгоритмическая ( вычислительная) сложность дискретных объектов. Однако по-прежнему получение нижних оценок сложности и построение верхних оценок, близких к нижним, для новых неизученных классов задач остается весьма тонкой и трудоемкой аа-дачей. [19]
Сложность алгоритмов и методы оптимизации программ
При этом не учитываются реальные затраты времени, памяти и других ресурсов, требуемых для отыскания по результатам предыдущих наблюдений очередной точки х, в которой следует задать вопрос источнику информации или поставить эксперимент. Это значит, что информационная сложность является объективной оценкой трудоемкости решения задач данного класса, если трудности, связанные с обработкой результатов эксперимента и вы. [20]
Пусть comp ( L) обозначает сложность вычисления линейного функционала L. Ln ( f), при этом информационная сложность 92 задается равенством ( см. (3.4) гл. [21]
В последующих главах мы сформируем субоптимальные методы решения применительно к наиболее важным для приложений классам задач нелинейного программирования при разных допущениях об источниках информации. Это методы, трудоемкость которых по порядку совпадает с информационной сложностью соответствующего класса задач . Оценки, которые мы при этом получим, будут характеризовать минимальные затраты, гарантирующие требуемое качество решения любой задачи класса. [22]
Информационная сложность программ в первую очередь зависит от количества типов и структуры данных, поступающих на вход и выдаваемых программой. Число различных видов операндов, используемых в программе, достаточно полно характеризует ее информационную сложность . Для приближенных инженерных оценок в качестве меры информационной сложности применяется емкость памяти, необходимая для оперативного накопления и хранения данных, используемых при решении задачи. [23]
Информационная безопасность с нуля. Основы кибербезопасности
Теория информационной сложности класса задач предусматривает идентификацию индивидуальной задачи класса в процессе Диалога. Число шагов диалога, позволяющее выделить любую индивидуальную задачу класса, и определяет информационную сложность класса . В теории информационной сложности задача класса считается решенной, как только она идентифицирована. Каждой задаче класса соответствует решение, записанное, например, в таблице, входами которой служат исходные данные задачи. [24]
Во-первых, это факторы развития самого объекта исследования — народного хозяйства, его звеньев, элементов. Растет масштабность решаемых задач и вовлекаемых ресурсов, усложняются все виды связей и взаимодействия объектов, увеличиваются динамизм, научно-техническая, производственная и информационная сложность систем , растет цена принимаемых решений и, следовательно, цена допускаемых ошибок. [25]
Теория информационной сложности класса задач предусматривает идентификацию индивидуальной задачи класса в процессе Диалога. Число шагов диалога, позволяющее выделить любую индивидуальную задачу класса, и определяет информационную сложность класса. В теории информационной сложности задача класса считается решенной, как только она идентифицирована. Каждой задаче класса соответствует решение, записанное, например, в таблице, входами которой служат исходные данные задачи. [28]
Информационная сложность программ в первую очередь зависит от количества типов и структуры данных, поступающих на вход и выдаваемых программой. Число различных видов операндов, используемых в программе, достаточно полно характеризует ее информационную сложность. Для приближенных инженерных оценок в качестве меры информационной сложности применяется емкость памяти, необходимая для оперативного накопления и хранения данных, используемых при решении задачи. [29]
Проблема безопасности сооружения и эксплуатации сложных производственных систем нефтяной и газовой промышленности весьма актуальна ввиду большой стоимости ликвидации последствий аварии. Несмотря на наличие весьма удачных решений данной проблемы на разных уровнях и огромную работу по предупреждению травматизма, имеющиеся случаи проявления опасности заставляют искать эффективные методы комплексного решения этой проблемы. Проблема обеспечения без — — опасности в современных условиях предполагает глубокое изучение системы человек — машина — производительная среда, представляющей объект большой информационной сложности , который должен изучаться научными методами. [30]
Источник: www.ngpedia.ru
3_Вимоги_1 / 09.10.12 / 0_Проблемы БС / ! / Понятие сложности является многоплановым понятием
Понятие сложности является многоплановым понятием. Оно рассматривалось ранее применительно к оценке сложности алгоритма решения задачи (см. п. 1.2 юниты 1). При анализе программ с целью проверки их работоспособности различают два аспекта их сложности [1]:
сложность процесса разработки программ;
сложность самой программы и ее компонент.
Оценку сложности программы можно выполнять с точки зрения сложности процесса разработки программ, тогда под сложностью понимается трудоемкость проектирования программы (первый аспект). Однако чаще для оценки сложности используется второй аспект, который определяет сложность программы через количество вычислительных ресурсов, необходимых для реализации алгоритма решения соответствующей задачи [ 1 ].
Ресурсы, необходимые для реализации программы (например, тактовая частота процессора, размер кэш-памяти 1-го и 2-го уровней, объем оперативной и внешней памяти и т.п.), определяют три типа сложности [ 1 ]:
сложность самой программы;
Временная сложность определяется временем ее реализации на определенном компьютере и зависит от двух основных факторов:
1) вычислительной сложности алгоритма решения задачи (определяется, например, числом шагов алгоритма, необходимых для получения результата);
2) производительности компьютера, который используется для выполнения программы решения задачи (определяется, например, количеством подобного типа задач, решаемых в единицу времени).
Для оценки вычислительной сложности алгоритма используются различные характеристики. Например, для оценки количества шагов реализации алгоритма используется “сигнализирующая времени”, а для оценки числа ячеек памяти, к которым хотя бы раз происходит обращение в процессе реализации алгоритма, используется “сигнализирующая емкости”. Более подробная информация по оценке вычислительной сложности с помощью различных характеристик приведена в п.1.2 юниты 1.
Производительность компьютера в значительной степени влияет на временную сложность программы. Однако это утверждение справедливо только для программ, алгоритмы которых являются легкоразрешимыми, то есть решают любую задачу из этого класса за число шагов, не превышающее некоторый полином от размерности задачи. Несмотря на высокую производительность современных ЭВМ, для ряда задач, алгоритмы которых не являются легкоразрешимыми, нельзя получить точное решение в приемлемые сроки [1]. Более подробно вопросы оценки вычислительной сложности, а также особенности машинной реализации легкоразрешимых и трудноразрешимых алгоритмов приведены в п.1.2 юниты 1.
Программная сложность определяется через характеристики самой программы. В простейшем варианте оценить программную сложность можно по [ 1 ]:
числу символов в тексте исходного модуля программы;
числу операторов, необходимых для полного описания программы на выбранном языке программирования;
числу машинных команд, необходимых для реализации программы на выбранной архитектуре ЭВМ и т.п.
Оценка собственно программной сложности и сравнительный анализ программной сложности различных программных средств вызывает определенные трудности. Обусловлены эти трудности не только разнообразием языков программирования, но и различием машинных архитектур (для различных типов процессоров используется разная система команд).
Например, в процессорах фирмы Intel, начиная с Intel Pentium MMX (1997 г.), используется “мультимедийный” набор команд MMX (57 машинных команд для обработки целочисленных данных в графических приложениях). В то же время, в процессорах фирмы AMD, начиная с AMD K6-2 MMX (1998 г.), используется другой “мультимедийный” набор команд 3DNow (24 машинные команды для обработки вещественных данных в графических приложениях). Для приближенной оценки программной сложности в инженерной практике достаточно часто используется такая характеристика, как число машинных команд в программе [ 1 ].
Информационная сложность зависит от количества данных, используемых программой, и “разнообразия” их типов [ 1 ]. Чем больше исходных, промежуточных и итоговых данных использует программа, тем больший объем информации обрабатывается в программе и тем выше информационная сложность программы. Кроме того, информационная сложность непосредственно связана с типами используемых данных. Данные могут быть как простых типов (целые, вещественные, символьные и т.п.), так и сложных структурированных типов (массивы, множества, записи, файлы т.п.). Очевидно, что информационная сложность структурированных типов данных выше, чем данных простых типов. Но для любых типов данных оценка информационной сложности в конечном итоге сводится к количеству байт памяти, занимаемых данными программы. Поэтому в качестве меры информационной сложности при приближенных оценках достаточно часто используется емкость памяти, необходимая для оперативного хранения сегмента данных программы [ 1 ].
В качестве примера программы, сложность которой предлагается оценить, используется программа PRV “перевода” значения угла из градусов в радианы и наоборот.
GR, N : INTEGER;
WRITELN(‘Введите направление перевода’);
WRITELN(‘0 – из градусов в радианы; 1 – из радиан в градусы ‘);
Источник: studfile.net
Четыре проблемы сложности разработки ПО (часть 2)
Зачем возглавлять бардак, как тестировать 100 строк кода целую вечность и почему ИИ — наша «атомная бомба».
Связаться с нами
27 Ноября 2018
#ai #computer_science #theory #теория #теория_компьютерных_наук
Reading time: 5 min
Рекомендуем вам ознакомиться с первой частью данной статьи, если вы не сделали этого ранее. Вам будет в два раза интереснее и в восемь раз понятнее.
1. Алгоритмическая сложность
Ее так же называют вычислительной сложностью. В профильных вузах это понятие рассматривается достаточно подробно, мы же остановимся на краткой характеристике. Алгоритмическая сложность обозначает функцию зависимости объема работы, которая выполняется неким алгоритмом, от размера входных данных. Объем работы в данном случае обычно измеряется абстрактными понятиями времени и пространства, которые называются «вычислительные ресурсы».
Как алгоритмическая сложность влияет на разработку? Во-первых мы имеем многообразие структур данных и алгоритмов. Всевозможные стеки, деки, деревья, В-деревья, хеш-таблицы — все это разные способы представления информации. И выбор разработчик делает в зависимости от того, какие операции в данном случае чаще будут использоваться, соответственно, он обязан в этих структурах данных ориентироваться, как рыба в воде.
Еще одно проявление алгоритмической сложности — так называемая «проблема P=NP», она же — вопрос о равенстве классов сложности P и NP, а в русских источниках — «проблема перебора». Между прочим, уже более 30 лет держится наверху списка центральных открытых проблем теории алгоритмов.
Проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США, пишет нам «Вики».
Говоря простым языком, проблема равенства P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно довольно быстро проверить, правда ли, что ответ на этот вопрос можно довольно быстро найти? Или же, действительно решение задачи проверить не легче, чем его отыскать? Считается, что если на эти вопросы человечество сможет ответить «Да», то, теоретически, станет возможно многие сложные задачи решать гораздо быстрее, чем сейчас.
2. Трудоемкость разработки
На практике эта проблема выражается в том, что скорость разработки падает по мере роста проекта. Фактически — чем больше размер проекта, тем медленнее идет его разработка. Как это влияет на работу? Во-первых, как мы уже упоминали, невозможно верно спрогнозировать сроки. Во-вторых, стремительно меняются технологии.
В третьих, трудоемкость разработки становится причиной того, что программистов требуется все больше и больше, а делают они все меньше и меньше. Что с этим делать? Целый ряд компаний умудрился этот аспект сложности обернуть себе на пользу и построить бизнес на его основе. Нет, они, конечно, не зарабатывают на том, что срывают сроки.
Но они и не гонятся за конечным идеальным продуктом, а раз за разом выпускают все новые и новые версии, переделки своего ПО, которые достаются пользователям отнюдь не бесплатно. Как было сказано ранее, на помощь многим проектам приходит Agile, который в данном случае лучше всего описывается формулировкой «если бардак нельзя предотвратить, надо его возглавить». А затем найти в нем выгоду и обернуть ее на пользу клиенту.
Кроме того, чтобы поддерживать производительность на одном уровне, есть определенные правила, называемые SOLID-принципы. Если их придерживаться, то все-таки можно добиться того, что скорость работы на проекте не будет катастрофически падать. Единственная проблема как раз состоит в том, чтобы выдержать следование этим правилам. Их всего пять и это, определенно, отдельная тема для разговора в рамках объектно-ориентированного программирования.
3. Информационная сложность
Она же — Колмогоровская сложность. Это понятие ввел в 1939 году известный советский математик Андрей Николаевич Колмогоров. Коротко ее можно описать следующим образом: информационная сложность задачи/объекта определяется количеством символов, которые необходимо записать, чтобы эту задачу решить.
То есть, фактически, сложность задачи равна количеству символов, описывающих ее решение.
Что это значит для программистов? Это, по сути, размер программы, которую они напишут для решения задачи. Понятно, что все стремятся использовать различные обозначения и приемы, чтобы уменьшить количество символов. Отсюда возникает идея, что и эту сложность можно уменьшать.
Но на самом деле все обстоит так: доказано, что определить информационную сложность задачи — это алгоритмически неразрешимая проблема. То есть, для компьютера не существует такого алгоритма, который может нам сказать, какое минимальное количество символов необходимо для решения той или иной задачи. К чему это приводит?
Во-первых, невозможно оценивать, какого размера достигнут наши приложения.
Во-вторых, появляется все больше новых языков программирования. Возникают конструкции, которые призваны уменьшить количество символов в коде и сделать запись более компактной. И непонятно, когда этот процесс остановится: ведь мы не знаем, какое количество символов считать минимальным для описания какой-либо операции.
В-третьих, среди приверженцев различных языков регулярно возникают холивары, а также удивительно легко претворяется в жизнь «Парадокс Блаба», придуманный американским программистом Полом Грэмом. Суть в том, что программист, знающий некий язык (в данном случае, выдуманный язык «Блаб») «думает» на нем, выражает решение любой задачи его средствами, а более мощные средства другого языка обесцениваются в его глазах, так как он даже не осознает, как их применять. При этом, ограниченность «Блаба» сама по себе не может быть стимулом для изучения более мощного языка, так как для осознания этой ограниченности нужно уже знать такой язык.
Еще одна идея состоит в том, что чем больше предметная область, для которой пишется программа, чем больше задача — тем больше вырастает ее информационная сложность. И процесс по созданию более компактных записей все равно не успевает за потребностями бизнеса.
Так и получается, что программы становятся все более и более громоздкими, а задачи обладают все большей информационной сложностью.
Тут самое время вспомнить о проблеме математиков: есть теория о том, что к 2075 году доказательства станут настолько большими и длинными, что одному человеку будет не под силу за всю жизнь понять даже одно из них. Фактически — возникнет потребность в помощи компьютера, который будет эти доказательства строить.
По аналогии с математикой можно предположить, что скоро и программы станут настолько масштабными. Но предсказывать будущее с уверенностью мы не можем, поскольку вычислить их информационную сложность нельзя. Тем не менее, опять и опять возникает потребность в программах, которые будут писать за нас другие программы, а это и есть в нынешнем понимании машинное обучение. Но, как с математическими доказательствами, так и с написанием программ есть еще одна сложность — четвертая.
4. Сложность тестирования
Она говорит нам о том, что трудоемкость тестирования программы тоже растет нелинейно, очень быстро, по мере увеличения количества входных данных. Есть такая книга «Art of Software Testing» («Искусство тестирования программ», авторы — Гленфорд Майерс, Том Баджетт, Кори Сандлер), первое издание которой вышло в 1979 году.
В этой книге приведен пример программки буквально из ста строчек кода, которая имеет 10 в 10 степени вариантов выполнения. Если потратить на проверку каждого варианта по 5 секунд, то у тестировщика уйдет на эту работу больше времени, чем существует планет Земля. В общем, в масштабах человеческой жизни для нас это все равно что вечность.
В действительности, потребность в ресурсах по тестированию ПО тоже очень и очень высока. И, фактически, мы вынуждены мириться с тем, что в каждой программе может быть ошибка. И что все эти программы не совсем корректно работают, потому что мы не можем доказать обратного.
Экскурс в историю
Попытку найти выход из сложившейся ситуации предпринял в 1969 году Чарльз Хоар, выпустив статью «Аксиоматический базис языков программирования». Им была предпринята попытка аксиоматизации, то есть предъявления формальной логической системы, с помощью которой можно было бы доказывать корректность программ.
Изначально результаты были очень хорошие, пока все работали на уровне if-ов, циклов и т. д. Но при переходе к процедурному программированию все «сломалось». Выяснилось, что предлагаемые системы аксиом, описывающие процедуры, как правило, приводят к противоречию.
И в 80-м году вышла статья «Критика логики Хоара», которая с помощью контрпримеров поставила крест на его аксиоматическом базисе. На самом деле, противоречие в данном случае зашито в само понятие вычислимости и связано с проблемой остановки машины Тьюринга. Нет алгоритма, у которого по входным значениям можно было бы определить, зациклится он или нет. И вот эта проблема остановки машины Тьюринга как раз приводит к противоречивости аксиом, а противоречивая аксиома, увы, позволяет нам доказать абсолютно любое утверждение, как верное, так и не верное. Если бы аксиоматический подход оправдал себя, то можно было полностью автоматизировать процесс верификации программ, но в данный момент это невозможно.
В итоге мы имеем вот что: трудоемкость растет, размеры программ растут, возникает потребность в мета-программировании, в частности, в использовании «искусственного интеллекта», машинного обучения, но мы не можем гарантировать и того, что наш ИИ или «специально обученная» программа будет работать правильно, потому что не можем это досконально проверить. Таким образом, существуют 4 глобальных проблемы, которые сильно влияют на IT-отрасль, и пока есть только два выхода — либо бежать вперед как можно быстрее, как говорила Черная королева, либо «ничего не решать».
Это же бизнес, а значит будет постоянная потребность в программистах, которые будут писать и верифицировать что угодно, в том числе, ИИ. И справедливы сомнения о том, что искусственный интеллект вытеснит живых разработчиков, потому что по-прежнему любая подобная система не способна рефлексировать, то есть оценивать результаты своей деятельности, а значит нужен человек, чтобы хоть как-то понимать, работает ИИ верно или нет.
Звучит как сюжет фантастики, но, в противном случае в какой-то момент мы можем обнаружить, что наш искусственный интеллект считает, что люди — это лишнее звено на планете Земля. А почему нет? Загрязняют окружающую среду, растрачивают природные ресурсы, неконтролируемо размножаются и больше любят разрушать, чем созидать.
Тем не менее, мы для себя считаем это утверждение ложным, а ИИ сочтет его истинным. Но на самом деле, глобальный вопрос к искусственному интеллекту даже не в истинности и ложности его суждений, а в том, выгодны нам его утверждения или не выгодны. И это действительно сложно: тут просто проверить-то утверждение нельзя, а еще и выгоду нужно закладывать.
Также, в силу того, что в логике ИИ могут возникать ошибки, сложно говорить о том, что он в обозримом будущем появится в каких-то особо опасных отраслях. Но беда в том, что разрабатывая подобные системы, мы иногда забываем, что не обязательно давать машине возможность управлять атомной станцией, чтобы случилась катастрофа.
Для того, чтобы устроить апокалипсис, ИИ будет достаточно, например, по ошибке отключить электричество по всей планете. Или одновременно выключить все лифты. Или заказать пиццу. Оценить последствия любой ошибки в таких масштабах практически невозможно, информационная сложность нам не дает этого понимания. И если люди, с энтузиазмом ошибаясь ради общего блага, сами создают разрушительные для мира вещи, например, ядерное оружие, то с вычислительной мощью искусственного интеллекта помноженной на желание создать нечто выдающееся, уничтожить мир можно гораздо быстрее — и весьма нетривиальными способами.
Источник: hwdtech.ru