Дерева целей примеры: Дерево целей – как создать и применять?

сущность метода и правила построения

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

Проблемы и цели как двигатели развития

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

Представьте себе любую уникальную задачу, которую вам нужно решить в кратчайшие сроки. Например, улучшение жилищных условий. Рассмотрим данный пример как прообраз проекта. Если взять лист бумаги и в заголовках столбиков написать: «мечта», «цель», «задача» и «проблема», то обязательно выстроится ассоциативный ряд, возникнут определенные образы. Попробуйте это выполнить реально.

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

Модель универсальных средств управления

Используя наш пример и размышляя над ассоциациями, можно обнаружить очевидные тренды понятийной динамики. От мечты к проблеме позитив, утрачиваясь, переходит от «радужной» к черно-белой картинке. Проблема максимально конкретна, она «здесь и сейчас», задачи и цели постепенно утрачивают конкретность, уходя в будущее, мечта же далека и расплывчата. Таким образом, наблюдаются три разнонаправленных вектора.

1. Угасание негатива и рост позитива.
2. Рост конкретики.
3. Движение в будущее.

Как же это связано с проектами и деревом целей? На мой взгляд, связь существенная. Но, действуя по порядку, дадим для начала определения рассматриваемым понятиям. Мечта мною понимается как метафорическая предтеча прообразов видения и миссии в бизнесе. Миссии я не могу дать достойного определения, зато хорошо воспринимаю через метафору мечты. Цель – это то, ради чего затевается дело (проект), некий объект намерения, который человек или компания стремится достичь. Метафорой цели является мишень для стрельбы, а официальное определение понятия в проектном управлении приведено далее.

Определение цели проекта, программы. Источник: НТК

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

Соотношение проблем и целей в построении иерархий

Как это ни парадоксально, представленная выше понятийная динамика универсальна как для обыденного сознания, так и в случае с крупным бизнесом. Причина в том, что лица, принимающие решения, – люди, и ничто человеческое им не чуждо. Осмысливая дерево целей проекта, я не могу не затронуть вопрос проблематики бизнеса, потому что проблема и цель в социальной жизни, как и в бизнесе, связаны тесно. В этом отношении заслуживают внимания труды И.В. Бестужева-Лады и его коллег.

Научные работы данного автора посвящены социальному моделированию и прогнозированию. Однако достаточно просто провести параллели между социальными проблемами, целями и теми же объектами в бизнес-среде. К слову сказать, и проблемы, и цели, и задачи я считаю средствами управления бизнесом в целом и проектами в частности. Вернемся к социальной прогностике. У И.В. Бестужева-Лады есть очень занятная модель, называемая проблемно-целевым ромбом, его схема приведена ниже.

Проблемно-целевой ромб. Источник: Бестужев-Лада И.В. Социальное прогнозирование. Курс лекций.— М.: Педагогическое общество России 2002. — 392 с

Приведенное в конце предыдущего раздела определение проблемы, в первую очередь, относится к формированию стратегических целей. Речь идет о некой корневой проблеме бизнеса, требующей для разрешения противоречия буквально смены концепции управления или стратегических преобразований. Поэтому стратегическая цель всегда связана с ключевым затруднением, и далее она декомпозируется вниз на подцели, которым следуют декомпозированные проблемы. Впрочем, в теории управленческих решений считается, что на низовых управленческих уровнях проблем уже нет, а есть только задачи. С этим частично можно согласиться.

Вместе с тем, малые проблемы порождают большие, а значит, ключевая проблема также может быть декомпозирована, или, как утверждает И.В. Бестужев-Лада, дезагрегирована. Весьма ценное замечание, что линия соприкосновения между целями и проблемами находится на низовом уровне – там, где конкретика максимальна. По утверждению ученого, построение дерева целей идет сверху, а назревание корневой проблемы начинается с широкого базиса небольших затруднений. Моя же позиция состоит в том, что раскол всегда происходит на высших уровнях принятия решений, который потом постепенно спускается вниз, становясь в низовых проблемах все очевиднее.

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

Плоскостная развертка деревьев целей, задач и проблем

Пирамида задач, целей и проблем

Пирамида целей и задач проекта

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

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

И только, когда дерево целей удается развернуть до уровня, и нижестоящая цель обретает однозначный результат, под нее появляются ресурсы, а среди них – ответственные ресурсы (персонал), низовые проблемы начинают естественным образом «отваливаться». Намерение обретает силу, события начинают выстраиваться в логическую последовательность, а «пазлы» задач более высокого уровня – складываться в гармоничную картину результатов, приводящих к цели.

Поэтому в парадигме проектного управления объединенная пирамида целей и задач выглядит как треугольник, верхнюю часть которого венчают миссия и стратегические цели проекта, а нижнюю часть определяют задачи и этапы проекта, опирающиеся на работы. Нужно только помнить, что задачи, цели и проблемы – категории статические. Они уже есть здесь и сейчас (проблемы) и выстроены в будущем как некие событийно-результирующие точки, адекватные в понимании: достигнуто или не достигнуто (задачи и цели). В то же время, этапы и работы – категории динамические, процессуальные, они ценны внутренним содержанием, имеют начало и конец, управление и механизмы реализации (методология IDF0).

Модель пирамиды целей и задач проекта

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

Методология дерева целей проекта

Часто понятие дерева целей подменяется образом пирамиды целей и задач. Действительно, такое может быть, когда проект небольшого масштаба. В таком случае дерево целей как таковое просто отсутствует за ненадобностью, его вполне может заменить иерархическая структура работ, потому что целей проекта одна-три, не более. Однако, если проектная задача крупная, масштабная, то в разработке дерева целей имеется прямая необходимость. Ниже представлен пример подобного проекта и разработанного под него иерархии целей. Это проект строительства торгово-логистического центра в городе N.

Пример дерева целей проекта

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

1. Созвать рабочую группу для процедуры целеполагания по проекту.
2. Уточнить стратегическую цель компании, которой следует проект.
3. Сформулировать миссию проекта в соответствии со следуемой стратегической целью проекта.
4. Произвести постановку и набор целей первого уровня вложенности. В ходе мозгового штурма и с применением методов логического структурирования (локализации) объекта исследования сформировать состав гипотез целей. К методам логического структурирования относятся диаграмма Исикавы, метод контрольных вопросов, метод синектики и т.п. Цель обычно формулируется в качественном формате, начиная с глагола неопределенной формы: улучшить, обеспечить, выполнить, создать, внедрить и т.п.
5. Выявить действующие ограничения и проанализировать варианты формулировок целей.
6. Скорректировать формулировки и состав целей первого уровня вложенности, применяя логические правила деления понятий. Такие правила можно найти в любом учебнике по логике. К ним относятся: деление целей по единственному выбранному основанию, попарная несовместимость делимых целей, исчерпание объема исходного понятия, непрерывность и соразмерность деления.
7. Задать вопрос: «А действительно ли достижение этих целей приведет к успеху стратегической цели проекта?». Если «Нет», то повторить пункты 4, 5, 6 и вопрос пункта 7. Если «Да», то перейти к пункту 8.
8. Для каждой цели первого уровня повторить действия пунктов 4-7.

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

Дерево целей на примере организации

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

Миссия и цель

У любого предприятия есть своя миссия – главная задача, которая оправдывает все его существование. Для благотворительной компании это, к примеру, помощь раковым больным. Для коммерческой компании – получение максимальной прибыли. Для социальной – достижение социально значимой задачи, например, адаптация детей-инвалидов в современном обществе.

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

Виды целей

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

Как устанавливаются цели?

Цели перед организацией в целом и перед отдельными ее подразделениями могут устанавливаться центром, а могут – на местах, руководителями отделов (централизованно и децентрализовано). Это зависит от принятой на предприятии системы управления.

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

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

Дерево целей на примере организации

Модель целей организации очень удобно представлять в графическом отображении в виде дерева. Это позволяет упорядочить иерархию целей. Существуют определенные принципы построения этого графика.

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

Разумеется, набор целей каждой организации сугубо индивидуален. Но, все-таки, можно выделить несколько сфер ее деятельности, в которой у каждой компании найдется немаловажный интерес.

• Доходы и финансы.

• Политика продаж.

• Политика в отношении персонала.

• Производство.

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

Примеры конкретных целей компании

Рассмотрим некоторые примеры целей организации в различных сферах ее деятельности.

Маркетинг

• Продвижение на рынке.

• Расширение ассортимента продукции.

Производство

• Снижение издержек.

• Повышение эффективности производства.

• Улучшение конкурентоспособности продукции.

• Разработка и внедрение новых технологий.

Персонал

• Повышение квалификации.

• Оптимизация кадров предприятия.

• Система стимулирования.

• Повышение производительности труда.

Финансы

• Эффективное управление финансами компании.

• Улучшение платежеспособности и рентабельности.

• Повышение инвестиционной привлекательности.

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

Мезенцева Василиса

Поделитесь записью с друзьями:

S.M.A.R.T. цели и Дерево Целей

СМАРТ цели – это метод постановки и проверки состоятельности цели. Дерево целей – это метод планирования и визуальной наглядности в достижении цели. А что если эти два мощнейших метода совместить?

Прежде, чем продолжить:

По ссылкам выше, соответственный материл о этих методах.

Общий шаблон – пример для S.M.A.R.T. и Дерево Целей

Увеличить: клик мышкой по изображению

По сути, это поэтапное дробление цели по критериям:

Цель – то, что мы хотим в итоге. Это наша, возможно, стратегическая или глобальная цель. Ответ на вопрос: Что мы хотим достигнуть? (или чтоб было и т.п.)

Измеримость №1…№3 – показатели цели или ее характеристика. Как мы поймем, что цель достигнута? В чем это отобразится?

Достижение  – согласно измеряемым показателям цели, ответ на вопрос: Как мы это будем достигать? Благодаря чему? Обладаем ли мы нужными ресурсами для этого?

Задача №1… или Схема: Цели/Задачи – это конкретные цели и задачи, распланированные по времени. Это ответ на вопрос: Что нужно конкретно в каждом из случаев сделать (или делать постоянно)? На данном этапе также принято проверить наши возможности в реализации этих подцелей.

В зависимости от целей, это дерево может изменятся. Для большей наглядности и понимания, ниже пример дерева целей в смарт интерпретации.

Пример Дерева Целей и СМАРТ. Цель: Похудеть за 10 месяцев, улучшить свою физическую форму

В целом, что мы имеем в конкретном случае в виде дерева целей с применением СМАРТ критериев:

Похудеть и улучшить физическую форму – что это значит? Это значит, что мои физические данные улучшаться, работа сердца нормализуется, я буду хорошо себя чувствовать.

Физические данные измерять буду в размере талии и веса (60см и 58 кг жаланные), для этого буду выполнять: пресс, обруч…

И так далее. Чем описывать, проще увидеть на схеме выше. Вот в чем и преимущество построения дерева целей с применением СМАРТ критериев…

Метод «дерева целей» и его использование в практике управления — Студопедия

Студопедия

Категории

Авто
Автоматизация
Архитектура
Астрономия
Аудит
Биология
Бухгалтерия
Военное дело
Генетика
География
Геология
Государство
Дом
Журналистика и СМИ
Изобретательство
Иностранные языки
Информатика
Искусство
История
Компьютеры
Кулинария
Культура
Лексикология
Литература
Логика
Маркетинг
Математика
Машиностроение
Медицина
Менеджмент
Металлы и Сварка
Механика
Музыка
Население
Образование
Охрана безопасности жизни
Охрана Труда
Педагогика
Политика
Право
Программирование
Производство
Промышленность
Психология
Радио
Регилия
Связь
Социология
Спорт
Стандартизация
Строительство
Технологии
Торговля
Туризм
Физика
Физиология
Философия
Финансы
Химия
Хозяйство
Черчение
Экология
Эконометрика
Экономика
Электроника
Юриспунденкция

Предметы

Авиадвигателестроения

Административное право

Административное право Беларусии

Алгебра

Архитектура

Безопасность жизнедеятельности

Введение в профессию «психолог»

Введение в экономику культуры

Высшая математика

Геология

Геоморфология

Гидрология и гидрометрии

Гидросистемы и гидромашины

История Украины

Культурология

Культурология

Логика

Маркетинг

Машиностроение

Медицинская психология

Менеджмент

Металлы и сварка

Методы и средства измерений

электрических величин

Мировая экономика

Начертательная геометрия

Основы экономической теории

Охрана труда

Пожарная тактика

Процессы и структуры мышления

Профессиональная психология

Психология

Психология менеджмента

Современные фундаментальные и
прикладные исследования

в приборостроении

Социальная психология

Социально-философская проблематика

Социология

Статистика

Теоретические основы информатики

Теория автоматического регулирования

Теория вероятности

Транспортное право

Туроператор

Уголовное право

Уголовный процесс

Управление современным производством

Физика

Физические явления

Философия

Холодильные установки

Экология

Экономика

История экономики

Основы экономики

Экономика предприятия

Экономическая история

Экономическая теория

Экономический анализ

Развитие эко

Get SMART: как наконец достичь своих целей с помощью процесса SMART

Вы один из тех людей, которые ставят перед собой цель, но никогда не достигают ее? Не волнуйтесь, вы не одиноки. Исследование Университета Скрэнтона показывает, что только 8% людей, которые ставят цели, действительно их достигают.

Так как же ты можешь быть частью этих 8%?

Ставьте УМНЫЕ цели.

Устанавливая цели SMART, вы можете сосредоточиться на том, чего действительно хотите, и каждый раз добиваться своих целей.Согласно исследованию Университета штата Мичиган, 76% людей, которые записали свои цели и свой образ действий, успешно достигли своих целей — только 43% из тех, кто поставил неписаные цели, успешно их достигли.

Что такое SMART-цели?

Чем SMART-цели отличаются от обычных? Цели SMART побуждают вас превратить ваши стремления в более действенные цели, чтобы вы могли четко видеть прогресс, которого вы достигли. Чтобы убедиться, что вы можете достичь цели, вы должны спросить, является ли ваша цель:

• S специальные
• M для измерения
• A опорный
• R элевант
• T в обязательном порядке

Метод SMART избавляет от расплывчатых частей традиционной постановки целей и привносит структуру.Например, когда вы устанавливаете цель обычными методами, процесс останавливается, как только вы ее устанавливаете. Процесс SMART разбивает вашу цель и создает шаги для ее достижения.

Если ваша цель не соответствует всем критериям SMART, вы можете подумать о корректировке своего курса действий. Если вы выбрали конкретные измеримые цели, которые соответствуют вашей работе или интересам, но у вас нет времени или ресурсов, необходимых для их достижения, это не SMART.

Предположим, ваша компания хочет увеличить выручку на 10% до конца квартала, чтобы опередить конкурентов.Вы и ваша команда работаете вместе, чтобы создать расписание, план действий и способ отслеживать свой прогресс. Пока что цель конкретная, измеримая, актуальная и привязанная ко времени. Однако вы понимаете, что квартал заканчивается всего через две недели, и у вас недостаточно времени, чтобы увеличить свой доход так сильно. Ваша цель больше недостижима.

Чтобы убедиться, что ваши цели соответствуют SMART, создайте контрольный список, включающий критерии SMART, и сравните с ними свою цель. Используйте приведенный ниже шаблон в качестве вдохновения.

Контрольный список целей SMART (Щелкните изображение, чтобы изменить в Интернете)

Как использовать метод SMART

После того, как вы определили общую цель, которую хотите достичь, пора разбить ее на части с помощью метода SMART.

Особый

Вам нужно точно знать, чего вы хотите достичь. Попробуйте ответить на пять W:

• Кто причастен?
• Чего я хочу добиться?
• Когда я хочу этого добиться?
• Где находится моя цель?
• Почему важна цель?

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

Древовидная диаграмма целей SMART (щелкните изображение, чтобы изменить в Интернете)

Измеряемые

Самая большая цель SMART-целей — создать цель, которую вы можете достичь. Но как этого добиться, если у вас нет возможности отслеживать свой прогресс?

Чтобы установить успешные измерения, вам необходимо иметь конкретное свидетельство. Быть счастливее — это не конкретная задача.Не курить больше и не есть овощи каждый день. Буква «M» в SMART идет рядом с буквой «S» — если у вас есть способ измерить свою цель, вы можете сделать ее более конкретной. Например, если вы хотите увеличить доход, вы должны привязать к этой цели сумму в долларах или процент.

достижимо

Ваша цель — это то, что вы действительно можете сделать? Нам часто не удается достичь целей, потому что они изначально были недостижимы. Чтобы выяснить, достижима ли ваша цель, спросите себя, сможете ли вы достичь ее с учетом имеющихся у вас времени и ресурсов.

Если у вас нет нужных ресурсов, откорректируйте. Найдите то, чего вы можете достичь тем, что у вас есть. Хорошая цель должна выходить за рамки ваших возможностей, но при этом быть достижимой.

Соответствует

Цель должна быть достаточно важной для вас, чтобы вы хотели ее достичь. Если вы говорите, что хотите пробежать марафон, но ненавидите бег, вам нужно оставаться дома и смотреть Netflix каждый раз, когда вам нужно пойти в спортзал и потренироваться. В этом случае осознайте, что вас действительно волнует, — ведите более здоровый образ жизни или худейте, — и выберите цель в фитнесе, которую вы не будете ненавидеть.Чтобы помочь вам определить, актуальна ли ваша цель, ответьте на следующие вопросы:

• Это кажется стоящим?
• Сейчас подходящее время?
• Совпадает ли эта цель с другими моими целями?
• Правильно ли я работаю над этим?

Если вы ответите «нет» на любой из этих вопросов, пересмотрите свою цель.

с ограничением по времени

Одна из главных причин, по которой люди не достигают своих целей, заключается в том, что у цели нет конечной даты, по которой человек будет отвечать.Мы можем сказать, что хотим похудеть или увеличить объем продаж вдвое, но не назначаем себе дату, к которой нужно стремиться. В процессе SMART дата окончания имеет решающее значение для достижения ваших целей.

Чтобы не сбиться с пути, создайте временную шкалу в Lucidchart. Этот шаблон может помочь вам спланировать вашу цель от начала до конца. Затем вы можете вернуться и сослаться на него в любое время, чтобы увидеть, насколько вы близки к достижению своей цели.

Хронология достижения целей SMART (Нажмите на изображение, чтобы изменить в Интернете)

Что дальше?

Теперь, когда вы понимаете, каковы цели SMART, пора претворить их в жизнь.Это самая сложная часть процесса постановки целей: перестать планировать и начать действовать.

Метод SMART может повысить вашу уверенность, потому что вы подтвердили, что можете достичь цели и привести план в действие.

Чтобы помочь вам начать работу, воспользуйтесь шаблонами, доступными в Lucidchart.

.

на пути к получению проверочных свойств | DeepAI

1 Введение

«При всех таких подходах возникают две ключевые проблемы: (1) какие свойства мы проверяем

; и (2) где
откуда берутся вероятности.

Первый из них остается проблемой для всех формальных методов анализа и, очевидно,
необходимо проделать значительную работу по отражению требований системы в формальном и логическом
путь.» [5] (курсив наш)

При формальной проверке программного обеспечения используются математические методы для установления того, что программное обеспечение обладает определенными свойствами.Например, что
поведение программной системы S удовлетворяет некоторым логически заданным свойствам. Распространенный подход — модель
проверка [2] , которая принимает модель системы (M)) и свойство ϕ (обычно указывается в некоторых
темпоральная логика) и может возвращать либо гарантию того, что поведение M удовлетворяет ϕ, либо контрпример: возможное
поведение M, нарушающее ϕ.

Формальные методы имеют долгую историю [4, 3, 1] , но, как предполагает начальная цитата,
Повторяющееся предположение состоит в том, что свойство ϕ известно или предоставляется как часть процесса выявления требований.

В данной рабочей заметке рассматривается вопрос: откуда взялось ϕ?

Наш ответ на этот вопрос прагматический: мы определяем процесс , который можно использовать для систематической идентификации набора
проверка свойств.

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

Например, представьте себе робота, который помогает пожилому человеку, живущему в их доме. Одно свойство высокого уровня («принцип») может быть
что человек должен быть в безопасности (то есть в безопасности и здоровым). Это свойство высокого уровня явно не может быть указано
формально. Однако мы можем тщательно (и систематически) рассмотреть все способы, которыми человек мог бы прийти к
вред, учитывая контекст системы и ее функциональные возможности, а также знания предметной области.Это может позволить нам (неформально)
получить определенные свойства, например, что человека сопровождают, если он выходит из дома, и что ему напоминают
медикамент.

Теперь мы определим процесс высокого уровня более подробно. Мы предполагаем (см. Рис. 1), что хорошо определенная
выполняется процесс проектирования (A), в результате которого создаются некоторые модели дизайна (B), которые затем дорабатываются и внедряются (C),
создание кода на каком-либо подходящем языке программирования, таком как агент-ориентированное программирование BDI (Belief-Desire-Intention)
язык (D).

Процесс, которому мы следуем, затем принимает в качестве входных данных высокоуровневые общие свойства («принципы») (E), а также знания предметной области (F),
и информацию о конструкции (B) и, возможно, даже о реализации (D), и использует информацию о предметной области и конструкции для
контекстуализировать и уточнить (G) высокоуровневые свойства до более конкретных свойств (H). Эти специфические свойства и
программное обеспечение можно проверить на модели. Обратите внимание, что этот процесс переходит от неформального к формальному.

Рисунок 1: Процесс высокого уровня

В оставшейся части этого документа мы делаем следующие предположения о конкретных формах этих различных артефактов.

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

Для реализации (D) нам фактически не нужно делать никаких предположений, пока (B) имеет целевую модель. Если нет,
затем, если реализация использует понятие целей, то мы можем извлечь дерево целей из реализации, показанное пунктирной линией
линия на рисунке 1.

Для постулатов (E) мы предполагаем просто английский текст. Мы не верим, что можно эффективно формализовать высокий уровень
такие понятия, как «не причиняет вреда», на самом деле, весь смысл предлагаемого нами процесса состоит в том, чтобы позволить уловить такие свойства
формально, делая их более конкретными в контексте рассматриваемой системы.

Знание предметной области (F) может быть представлено несколькими способами. Мы предполагаем (следуя [10] )
что он представлен как набор значений.Однако мы могли бы также изучить использование графической модели вместо
логические формулы. Обратите внимание, что знания предметной области также уточняются и расширяются как часть процесса (G), обозначенного значком
двунаправленная стрелка между (G) и (F).

Проверяемые свойства (H) представляют собой логические формулы. Можно использовать широкий спектр логик, но для данной статьи мы просто
принять линейную временную логику (LTL). Могут быть использованы и другие более богатые логики, но существует стандартный компромисс: чем богаче
логика, тем сложнее становится проверка.

В оставшейся части этого документа представлен эскиз возможного процесса, проиллюстрированный на рабочем примере. Этот процесс
ранний набросок и предназначен в качестве отправной точки для обсуждения и уточнения.

Прежде чем продолжить, стоит вкратце упомянуть ключевой документ, который информирует об этой работе.

Процесс определения способов компрометации принципа имеет сходство с работой ван Ламсверде и
Летье (далее «vLL») [10] .Вкратце, они начинаются с конечных целей (т.е. требований,
которые формализованы в логике), и вывести препятствий этим требованиям, используя знания предметной области.

Хотя отправная точка иная, формально заданная системная цель в их подходе по сравнению с неформальным общим принципом в
В нашем случае общая идея получения более подробного препятствия для отправной точки с использованием знаний предметной области аналогична. Заметка
что иногда при выводе препятствий в их методе используется не знание предметной области, а общий шаблон, который цель G может
пойти не так, как надо, из-за того, что его не сделали вообще, или из-за того, что сделали неправильно, где «сделано неправильно» может относиться к любому аспекту цели.Так,
например, если цель состоит в том, чтобы отправить сообщение, то оно может пойти не так из-за того, что сообщение не будет отправлено, или оно может быть отправлено
неправильный получатель или отправлено с неправильным содержанием.

Одно отличие заключается в том, что, хотя они начинаются с конкретной цели, мы начинаем с принципа высокого уровня. Это потому, что принципы
мы заботимся и хотим обеспечить, хотя не все цели важны. Например, в сценарии с роботом для ухода на дому,
проверка того, что холодильник не оставлен открытым, не так уж и важна, в то время как обеспечение того, чтобы человек, о котором заботятся, напоминал
принимать их лекарства очень важно.

2 Артефакта

В этом разделе кратко описаны артефакты, которые играют роль в этом процессе. Как показано на рисунке 1,
Процесс (G) включает в себя принципы (E), модель проектирования, в частности, дерево целей (B) и знания предметной области (F). В результате формально
указанные свойства для проверки (H).

Мы уже отметили, что принципы (E) — это просто общие утверждения высокого уровня на английском языке, например «не навреди
люди »или« убедиться, что система может продолжать функционировать ».

Мы также уже отметили, что проверяемые формулы (H) указаны в линейной временной логике (LTL), но другие
логика тоже возможна.

Теперь обратим внимание на дерево целей (B) и знания предметной области (F). Мы также определяем промежуточную структуру данных:
дерево уточнения (см. раздел 2.3). На рисунке 2 показан процесс вместе с ключом
артефакты.

Рисунок 2: Увеличение на шаге G

2.1 Дерево целей

Модель проекта, которую мы используем, представляет собой дерево целей (см. Пример на рисунке 3).Это дерево, в котором узлы
являются (под) целями, а стрелки связывают цели с их подцелями. Отношение цели к ее дочерним элементам обозначается как
либо «И», либо «ИЛИ» (в примере на рисунке 3 все отношения — «И»). Такие деревья могут быть
сконструированы и усовершенствованы, задавая вопрос «Почему?» определить родителей целей и спросить «Как?» идентифицировать детей
цели [9, 6] . Такие деревья обычно используются в методологиях разработки автономных
системы [11] .

Дерево на рисунке 3 относится к сценарию Care-O-bot [7] .Этот сценарий
вовлекает робота в дом пожилого человека. Робот напоминает человеку, что нужно есть, пить и принимать лекарства.
возможность отслеживать их и при необходимости предупреждать медицинские органы, а также выполнять ряд других вспомогательных задач (например, проверка
если дверь холодильника оставлена ​​открытой, вместе смотрят телевизор, следуют приказам принести вещи, открывают дверь).

Рисунок 3: Пример дерева целей

2.2 Знание домена

Третий артефакт — это знания предметной области, которые мы моделируем как импликации в подходящей логике (например, LTL, следуя
vLL).

Один пример правила знаний предметной области показывает, что напоминания (например, о приеме лекарств) обычно приводят к выполнению задачи в
вопрос делается. На самом деле это сложно формализовать точно, поскольку напоминания фактически не гарантируют
соблюдение. Для простоты формализуем чрезмерно сильное свойство, напоминание обеспечит соответствие:

Конечно, это слишком сильно, и более тонкая формализация может включать логику с вероятностями, позволяющую
запомните, что напоминания уменьшают вероятность забывания, но не устраняют ее полностью.

И наоборот, мы также можем знать, что напоминания имеют ценность, потому что человек, о котором заботятся, забывчив и с большей вероятностью
не забудьте выполнить задание, если им напомнили. Опять же, для правильной формализации потребуются вероятности, но пока мы
формализовать, используя слишком сильное свойство, что напоминания необходимы (т.е. без напоминаний человек забудет):

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

Примечание: для удобства мы принимаем соглашение (используемое vLL), согласно которому A⇒B является сокращенным обозначением для □ (A → B), что позволяет нам записать первое знание предметной области выше как простое напоминание (X) ⇒do (X ).

Другие примеры знаний предметной области включают определение концепций высокого уровня, например что «недоедание» означает
менее трех приемов пищи в день (и, очевидно, должны быть определенные условия в отношении того, что это за приемы пищи), и что «не пить
достаточно »составляет менее 1,2 литра в день. Мы используем «≡» для определения таких эквивалентностей, которые логически трактуются как
двунаправленное значение.

.

Кроме того, обратите внимание, что дерево целей можно рассматривать как указывающее на подразумеваемые знания предметной области, например, если цель G0 имеет
дочерняя цель G1, то это означает, что G1 является частью достижения G0.Однако в подробном процессе, представленном ниже, мы
держите дерево целей отдельно, а не отображайте его в правила знания предметной области.

2.3 Дерево уточнения

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

Корень дерева уточнения — это принцип, и после завершения процесса каждый его лист становится свойством LTL. Каждый узел в
дерево уточнения — это описание (формальное или неформальное) набора поведения . То есть узел определяет подмножество
возможное поведение системы. Подмножество вариантов поведения описывается с помощью условия, которое, поскольку оно может быть
мгновенно или за определенный период времени формализуется (в конечном итоге) в LTL.

Связь между узлом и его дочерними узлами — это импликация : если узел B является дочерним по отношению к узлу A, это означает, что
любое поведение, удовлетворяющее B, будет также удовлетворять A. Так, например, если узел «недостаточно еды», с дочерним
узел «<3-х разовое питание», это подразумевает. Поскольку менее 3-х разовое питание является (согласно домену Уравнение знания 3) определение недостатка пищи, любое поведение, отвечающее условию трехразовое питание по определению также соответствует условию недоедания.Аналогично рассмотрим узел «Вред» с двумя дочерними узлами: «не поддерживается» и «подвергается риску». Поведение, удовлетворяющее одному из они, либо не сохраняя человека здоровым, либо подвергая его риску, также считаются соответствующими определению причиняя им вред.

3 Процесс

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

• «Какие цели способствуют / противоречат этому принципу?»

• «Как (в этом контексте) этот принцип мог быть нарушен?»

• «Что это означает (в данном контексте)?»

Этот процесс повторяется до тех пор, пока не будут формализованы все листовые узлы. Результаты (листовые узлы) инвертируются, давая набор
свойства для проверки.Также можно использовать вывод препятствий a la vLL для изучения допущений, лежащих в основе
достижение этих свойств.

По сути, процесс принимает отрицательный принцип и выводит набор свойств, так что каждое из свойств, если оно
придерживается, подразумевает отрицание этого принципа. Следовательно, для того, чтобы желаемый принцип соблюдался, отрицание , каждого из
свойства должны удерживаться. Например, учитывая принцип, согласно которому мы хотим избежать причинения вреда человеку, мы могли бы получить набор
(официально указанные) свойства, которые включают в себя то, что мы напоминаем пожилому человеку съесть свой обед, и что мы гарантируем, что
лекарства, которые они принимают, соответствуют прописанным.

На высоком уровне подробный процесс выглядит следующим образом (где числа слева обозначают различные случаи, обсуждаемые ниже):

Инициализировать корневой узел N с отрицанием принципа

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

Выберите листовой узел N

0.
Если N можно формализовать, то формализуйте его.

1.
Elseif может уточнить N, используя знания предметной области, а затем сделать это (см. Раздел 3.2)

2.
Elseif может уточнить N с помощью дерева целей, а затем сделать это (см. Раздел 3.3)

3.
еще

3а.

Если можно уточнить дерево целей, добавив соответствующие цели

затем сделайте это (см. раздел 3.4)

3b.

Иначе получить дополнительные релевантные знания в предметной области (см. Раздел 3.5)

EndRepeat

Вернуть отрицания листовых узлов

Теперь рассмотрим разные случаи. «Базовый случай» — это когда узел достаточно специфичен, чтобы его можно было напрямую формализовать.
(случай 0), и в этом случае мы просто формализуем узел. Другие случаи: уточнение с использованием знаний предметной области (1), использование цели
дерево (2) и расширение либо дерева целей (3a), либо знаний предметной области (3b). Обратите внимание, что в ситуации, когда узел N может быть
уточнены путем применения либо знаний предметной области, либо знаний, подразумеваемых деревом целей, тогда процесс устанавливает приоритет области
знания, поскольку они более общие (связанные с проблемой и предметной областью), тогда как дерево целей более конкретное
(связанный с конкретным решением).

3.1 Формализация (случай 0)

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

Написание формулы может потребовать некоторого внимания к реализации, какой информации можно отслеживать и в какой (логической) форме.
форма предоставляется. Например, при выдаче лекарств реализация (т.е. убеждения агента) может предоставлять такие предикаты.
как выдано (M), указывающее, что лекарство M было выпущено, и этот предикат будет использоваться при формализации узла
указав, что было выдано правильное лекарство.С другой стороны, если использованное убеждение было, скажем,
лекарство Выдано (M, P, D, T), указывая, что лекарство M было выдано пациенту P в день D и время T, затем
вместо этого следует использовать этот предикат.

Мы предполагаем, что формализация возможна в следующих случаях в нашем рабочем примере. Некоторые из приведенных ниже формализаций могут
быть улучшенным, чтобы сделать его более точным. Например, вместо Emergency⇒alerted нам может потребоваться
в случае возникновения чрезвычайной ситуации в течение определенного временного окна отправляется предупреждение.

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

Здесь мы определяем Φ (X) (когда X — это еда) как истинное, если во время этого приема пищи либо человек ест, либо
система собирается выдать напоминание:

Мы также определяем Ψ как истинное, если система регулярно напоминает человеку пить.В частности, выполняется, если и когда
прошло более 2 часов («2 ч») с момента последнего напитка, либо система выдала напоминание в течение последних 15
минут («⧫ <15м»), или система собирается выдать напоминание. Другими словами, если человек не пил в течение последних двух часов, то напоминания выдаются каждые 15 минут (пока они не выпьют).

3.2 Уточнение по отношению к предметным знаниям (случай 1)

При уточнении в отношении знаний предметной области мы следуем процессу vLL: дано правило знания предметной области в форме □ (A → P ′) и узел N, содержащий P (где P находится в положительном контексте, и ∃θ.Pθ = P′θ), то уточняем N с помощью N [P / Aθ] (т.е. заменяем P на Aθ). Это дает нам желаемое соотношение между
узел и его дочерний элемент: если A → P, то N [P / A] → N.

Аналогичным образом, если P

встречается в отрицательном контексте (т.е. в рамках нечетного числа отрицаний), то правило

□ (P → A) может применяться для замены P на A, что дает желаемое отношение импликации. : поскольку P → A, то (¬A) → (¬P) и, следовательно, (¬N [P / A]) → (¬N), что и нужно.

Обратите внимание, что в любом случае, если новый узел имеет форму ¬ (N1∧… ∧Ni), мы разбиваем его на несколько
узлы ¬Ni. Например, мы можем использовать знание предметной области, что сохранение здоровья человека означает (уравнение 6), что
у них достаточно еды, питья и правильных лекарств. Когда мы дорабатываем узел, чтобы он оставался здоровым, мы заменяли
это с узлом ¬ (достаточно еды ∧ достаточно пить правильные лекарства), который затем
разбит на три узла.

Обратите внимание, что если знания предметной области представлены в форме определения (P′≡A), то при Pθ = P′θ мы можем
замените P на Aθ в любом контексте.Обратите внимание, что это правило можно применять многократно, давая цикл, заменяя A на
П. Мы избегаем этого, предполагая, что определения являются направленными: определение чего-либо в терминах чего-то другого, более конкретного,
и что человек, следящий за процессом, идет только в направлении увеличения специфичности. Например, было бы разумно
чтобы преобразовать «недостаточно еды» в «<3-разовое питание», но не наоборот.

Однако то, что мы хотим идентифицировать в результате всего этого процесса, — это не просто некоторые способы, которыми
(Е.грамм. «Без вреда») может быть нарушено, но все способов, которыми это может быть нарушено. Поэтому при переработке мы
рассмотрим не только одно правило области вида □ (X → Y), но и все такие правила.

Конкретно после доработки задаем вопрос: «А это комплектно?». В частности, учитывая узел N и его уточнения
N1… Ni, уточнения завершены, если (следуя vLL) (¬N1∧… ∧¬Ni) → ¬N. Конечно, поскольку уточняемые узлы еще не формализованы, это нельзя проверить формально, а неформально, используя
вопрос: «Если все эти уточнения не выполняются, обязательно ли не выполняется исходный узел?».

Например, при уточнении «не сохраняется здоровым» мы разбиваем его на три подузла: «недостаточно еды»,
«Недостаточно пить» и «нет / неправильное лекарство». Затем мы рассматриваем вопрос: «достаточно еды, достаточно
пить и правильно ли принимать лекарства, чтобы гарантировать хорошее здоровье? ». В этом случае мы можем считать, что ответ — «нет»,
потому что здоровье также требует физических упражнений и внимания к психологическому благополучию (например, общение, социальная активность и
смысл смысла). Эти дополнительные узлы могут быть добавлены (не показаны на рисунке 5) и доработаны.

3.3 Уточнение по отношению к целям (случай 2)

При уточнении по отношению к целям мы выводим процесс, рассматривая дерево целей как указание «подразумеваемой» области
знание. По сути, отношение цель-подцель вида G0⟶G1 (т.е.G1 является подцелью G0), является
читается как подразумевающее знание предметной области, что создание G1 подразумевает G0. В случае, когда G0 имеет несколько дочерних элементов, тогда
когда декомпозиция ИЛИ, каждый дочерний элемент подразумевает родителя, а когда деко

.

Деревья

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

6.1 Двоичные деревья

Определение.
Бинарное дерево
является либо внешним узлом, либо
внутренний узел, присоединенный к упорядоченной паре двоичных деревьев, называемых
левое поддерево и правое поддерево этого узла.3}} \ Bigl (1 + O ({1 \ over N}) \ Bigr). $$
Доказательство.

6.2 Леса и деревья

В двоичном дереве ни один узел не имеет более двух дочерних узлов. это
характеристика делает очевидным, как представлять и манипулировать такими
деревья в компьютерных реализациях, и это естественно относится к
Алгоритмы «разделяй и властвуй», которые разделяют проблему на две
подзадачи. Однако во многих приложениях (и в более традиционных
математическое использование), нам нужно рассмотреть общих деревьев:

Определение.
Дерево (также называется общим деревом )
— это узел (называемый корнем), связанный с последовательностью непересекающихся деревьев.
Такая последовательность называется лес .

Используем ту же номенклатуру
что касается бинарных деревьев: поддеревья узла являются его дочерними элементами, корнем
узел не имеет родителей и т. д. Деревья — более подходящие модели
чем бинарные деревья для некоторых вычислений.

Теорема.
(Перечень общих деревьев)
Пусть $ G_N $ будет количеством общих деревьев с $ N $ узлами.2 = z $ и, следовательно, $ G (z) = zT (z) $, поскольку обе функции
удовлетворяют тому же функциональному уравнению. То есть количество деревьев с
$ N $ узлов равно количеству двоичных деревьев с $ N $ внешними узлами.

6.3 Комбинаторные эквивалентности деревьям и двоичным деревьям

Следующие комбинаторные объекты находятся в соответствии 1-1.
и поэтому считаются по каталонским числам.

• Бинарные деревья с $ N $ внешними узлами.
• Деревья с $ N $ узлами.
• Правовые последовательности $ N $ пар скобок.
• Триангулированные $ N $ -угольники.
• Последовательности разорения игрока.

Вот примеры этих объектов для небольших $ N $:

6.4 Свойства деревьев

Определение.
В дереве $ t $:

• размер $ | t | $ есть
  его количество узлов
• уровень узла — его расстояние от корня
  (который находится на уровне 0)
• длина пути $ \ pi (t) $ — это сумма
  уровни каждого из узлов в $ t $
• высота $ \ eta (t) $
  максимальный уровень среди всех узлов
• листья узлы
  без детей

Определение.
В двоичном дереве $ t $:

• размер $ | t | $ есть
  его количество внутренних узлов
• уровень узла — его расстояние от корня
  (который находится на уровне 0)
• длина внутреннего пути $ \ pi (t) $ — это сумма
  уровни каждого из внутренних узлов в $ t $
• длина внешнего пути $ \ xi (t) $ — это сумма
  уровни каждого из внешних узлов в $ t $
• высота $ \ eta (t) $
  максимальный уровень среди всех внешних узлов
• оставляет (внутренние) узлы
  с обоими детьми внешний

Рекурсивные определения.
Часто бывает удобно работать с рекурсивными определениями дерева
параметры. В двоичном дереве $ t $ мы определили следующие параметры:
все $ 0 $, если $ t $ — внешний узел; в противном случае, если корень $ t $ равен
внутренний узел и левое и правое поддеревья, соответственно, обозначаются
по $ t_l $ и $ t_r $ имеем следующие рекурсивные формулы:
$$ \ eqalign {
| t | & = | t_l | + | t_r | +1 \ cr
\ pi (t) & = \ pi (t_l) + \ pi (t_r) + | t | -1 \ cr
\ xi (t) & = \ xi (t_l) + \ xi (t_r) + | t | +1 \ cr
\ eta (t) & = 1+ \ max (\ eta (t_l), \ eta (t_r)).\ cr} $$
Легко видеть, что они эквивалентны приведенным выше определениям.
Эти формы служат основой для вывода функциональных
уравнения на ассоциированные производящие функции при анализе дерева
параметры. Они также способствуют индуктивному доказательству
отношения между параметрами.

Пример. Длины пути в любом двоичном дереве $ t $ удовлетворяют
$ \ xi ({t}) = \ pi ({t}) + 2 | t | $. Вычитая уравнение
$ \ pi (t) = \ pi (t_l) + \ pi (t_r) + | t | -1 $
из уравнения
$ \ xi (t) = \ xi (t_l) + \ xi (t_r) + | t | + 1 $
сразу дает основу для доказательства по индукции.

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

6.5 Примеры древовидных алгоритмов

Деревья актуальны для изучения алгоритмов анализа не только
потому что они неявно моделируют поведение рекурсивных программ
но также потому, что они явно участвуют во многих основных алгоритмах
которые широко используются. Для типичных приложений нас интересует путь
длина и высота деревьев. Считать среднее значение
такие параметры, конечно, нам нужно указать модель, определяющую, что
означает случайное дерево .Для
такие приложения, как обход дерева и
оценка выражения
(или, в более общем смысле,
рекурсивное выполнение программы,
стоит рассмотреть модель, в которой деревья берутся с равной вероятностью.
Для этих приложений мы изучаем
так называемые каталонские модели , где каждая из
Бинарные деревья $ T_N $ размера $ N $ или общие деревья размера $ N + 1 $ берутся с
равная вероятность. Это не единственная возможность — во многих ситуациях
деревья индуцируются внешними данными, а другие модели
случайности уместны.Далее мы рассмотрим особенно важную
пример.

6.6 Деревья двоичного поиска

Одним из наиболее важных приложений двоичных деревьев является
поиск по двоичному дереву алгоритм, метод, использующий двоичные деревья
явно, чтобы обеспечить эффективное решение фундаментальной проблемы
в информатике. Для получения полной информации см.
Раздел 3.2 в «Алгоритмах», 4-е издание.
Анализ бинарного дерева
поиск показывает различие между моделями, в которых все деревья
одинаково вероятны и модели, в которых основное распределение
неоднородно.Сопоставление этих двух является одним из важнейших
концепции этой главы.

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

Мы изучаем деревья бинарного поиска при случайной перестановке
модель, где мы предполагаем, что каждая перестановка ключей в дереве
(все разные) одинаково вероятны как вход.Эта модель была
проверено во многих практических ситуациях. Множество разных перестановок
может отображаться в одно и то же дерево.
это
неверно, что каждое дерево с одинаковой вероятностью возникнет, если ключи
вставляется в случайном порядке в изначально пустое дерево.

Стоимость построения конкретного дерева прямо пропорциональна
длина его внутреннего пути, так как узлы не перемещаются после вставки, и
уровень узла — это именно то количество узлов, которое требуется для вставки
Это. Таким образом, стоимость построения дерева одинакова для каждого из
перестановки, которые могут привести к его построению.

Мы смогли получить среднюю стоимость строительства
добавив для всех $ N! $ перестановок внутренний путь
длина получившегося дерева (совокупная стоимость), а затем деление на $ N! $.
Кумулятивная стоимость также может быть рассчитана путем добавления для всех деревьев
произведение длины внутреннего пути и количества перестановок
которые приводят к построению дерева.
Это средняя длина внутреннего пути, которую мы ожидаем после $ N $
случайные вставки в изначально пустое дерево, но это
не
то же, что и средняя длина внутреннего пути случайного двоичного дерева,
согласно каталонской модели, где вероятность всех деревьев одинакова.Это требует
отдельный анализ. Мы рассмотрим случай каталонского дерева в следующем
и случай двоичного дерева поиска в Разделе 6.8.
В самом деле, к счастью, более сбалансированные
древовидные конструкции, поиск и строительство которых не требуют больших затрат, являются
более вероятны, чем древовидные структуры, затраты на которые
высокая. В ходе анализа мы определим это количественно.

6,7 Средняя длина пути в каталонских деревьях

Какова средняя длина пути дерева с $ N $
внутренние узлы, если
каждое дерево $ N $ -узлов считается одинаково вероятным? Наш анализ этого
важный вопрос является прототипом общего подхода к анализу
параметры комбинаторных структур, которые мы ввели в главе 3:

• Определите двумерную производящую функцию (BGF) с одним
  переменная, обозначающая размер дерева, а другая —
  длина внутреннего пути.
• Вывести функциональное уравнение, которому удовлетворяет BGF, или
  связанная с ней кумулятивная производящая функция (CGF).
• Извлечь коэффициенты для получения результата.

В случайном двоичном каталонском дереве с $ N $ узлами,
вероятность того, что левое поддерево
$ k $ узлов (а правое поддерево имеет $ N-k-1 $ узлов) равно
$ T_ {k} T_ {N-k-1} / T_N $ (где $ T_N = {2N \ choose N} \ bigm / (N + 1) $
это $ N $ -е каталонское число).
Знаменатель — это количество возможных деревьев $ N $ -узлов и
числитель подсчитывает количество способов составить дерево $ N $ -узлов
используя любое дерево с $ k $ узлов слева и любое дерево с $ N-k-1 $
узлы справа.Мы называем это распределение вероятностей как
Каталонский дистрибутив , показанный на этом рисунке.

Одним из поразительных фактов о распределении является то, что
вероятность того, что одно из поддеревьев пусто, стремится к
константа по мере роста $ N $: это $ 2T_ {N-1} / T_N \ sim 1/2 $. Действительно, около половины
узлы в случайном двоичном дереве, скорее всего, будут иметь пустое поддерево,
поэтому такие деревья не особенно хорошо сбалансированы.

Используя каталонское распределение, мы можем проанализировать длину пути
аналогично нашему анализу Quicksort.Средний внутренний
длина пути в случайном двоичном каталонском дереве описана
повторением
$$ Q_N = N-1 + \ sum_ {1 \ le k \ le N} {T_ {k-1} T_ {N-k} \ over T_N} (Q_ {k-1} + Q_ {N-k})
\ qquad \ hbox {для $ N> 0 $}
$$
с $ Q_0 = 0 $.
Аргумент, лежащий в основе этого повторения, является общим и может быть использован для
анализировать случайные бинарные древовидные структуры в рамках других моделей случайности,
путем замены каталонского дистрибутива другими дистрибутивами.
Например, как обсуждается ниже, анализ
деревьев бинарного поиска приводит к равномерному
распределение (размер каждого поддерева встречается с вероятностью $ 1 / N $) и
повторение соответствует повторению Quicksort.\ prime (z) = — T (z) + 1 / \ sqrt {1-4z} $. Их подстановка дает
явное выражение
$$ zC_T (z) = {z \ over 1-4z} — {1 -z \ over \ sqrt {1-4z}} + 1, $$
который расширяется, чтобы дать заявленный результат.

Этот результат иллюстрируется большим случайным двоичным деревом, показанным ниже:
асимптотически большое дерево примерно помещается в $ \ sqrt {N} $ — by — $ \ sqrt {N} $
квадрат.

Теорема. (Длина пути в общих деревьях)
Средняя длина пути в случайном общем дереве с $ N $ внутренних
узлы
$$ {N \ over 2} \ biggl ({4 ^ {N-1} \ over {2N-2 \ choose N-1}} — 1 \ biggr)
= {N \ over2} \ bigl (\ sqrt {\ pi N} -1 \ bigr) + O ({\ sqrt {N}}).N] G (z) $ приводит к заявленному результату.

6.8 Длина пути в деревьях двоичного поиска

Анализ длины пути в деревьях двоичного поиска — это фактически
изучение свойства перестановок , а не деревьев, поскольку мы начинаем
со случайной перестановкой. В главе 7 мы обсуждаем свойства
перестановки как комбинаторные объекты более подробно. Мы упоминаем
анализ длины пути в BST здесь не только потому, что
интересно сравнить это с анализом, приведенным только для случайных
деревья.2 $.

Асимптотически большой BST примерно вписывается в $ \ log {N} $ — by- $ N / \ log {N} $
прямоугольник.

6.9 Аддитивные параметры случайных деревьев.

Наши анализы
для длины пути обобщить простым способом, чтобы покрыть любые
аддитивный параметр , который можно выровнять с деревом
рекурсия следующим образом: значение параметра для дерева — это сумма
значений параметра для поддеревьев плюс дополнительный
термин для корня. Примеры дополнительных параметров включают размер, путь
длина и количество листьев.

6.10 Высота

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

6.11 Сводка средних результатов по свойствам деревьев

6.12 Инверсия Лагранжа

6.13 Неупорядоченные деревья с корнями

Ниже приведены четыре основных типа деревьев, которые
возникают при анализе алгоритмов, которые образуют иерархию:

• Свободное дерево , ациклический связный граф.
• Корневое дерево , свободное дерево с выделенным корневым узлом.
• заказанное дерево , корневое дерево, где порядок
  поддеревья узла имеет значение.
• Бинарное дерево является упорядоченным
  дерево, где каждый узел имеет степень 0 или 2.

На данный момент мы изучали упорядоченные и бинарные деревья.

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

Вот иллюстрация иерархии для деревьев с пятью узлами.
14 различных пятиузловых упорядоченных деревьев изображены на рисунке,
и они далее организованы в классы эквивалентности с использованием небольших
закрашенные и более крупные открытые прямоугольники. Есть 9 различных пятиузловых корневых
деревья (заштрихованные прямоугольники идентичны
корневые деревья) и 3 различных пятиузловых свободных дерева
(заключенные в большие прямоугольники идентичны свободным деревьям).

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

По мере того, как определения становятся более строгими, количество деревьев
которые считаются разными, становятся больше, поэтому для данного размера
корневых деревьев больше, чем свободных, упорядоченных деревьев больше, чем
корневые деревья и больше бинарных деревьев, чем упорядоченных деревьев. Оказывается
что соотношение между количеством укоренившихся деревьев и количеством
свободные деревья пропорциональны $ N $; соответствующее соотношение заказанных
деревья с корнями растут экспоненциально с $ N $; и соотношение
бинарные деревья к упорядоченным деревьям — константа.{3/2} $$

6,14 Деревья с маркировкой

6,15 Другие типы деревьев

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

В этой таблице показаны примеры восьми различных типов деревьев:
3-х и 4-х, 3-х и 4-х, 2-3 и 2-3-4, и
красно-черный и АВЛ.

Избранные упражнения

6,2

Какая доля
бинарные деревья с $ N $ внутренними узлами имеют оба поддерева
из корня непустой? Для $ N = 4 $ ответ будет $ 4/14 $.

Какая доля
леса с $ N $ узлами не имеют деревьев, состоящих из одного узла?
Для $ N = 1,2,3, $ и 4 $ ответы равны 0, 1/2, 2/5, $ и 3/7 $ соответственно.

6,18

[Крафт-равенство] Пусть $ k_j $ будет количеством внешних узлов на уровне
$ j $ в двоичном дереве. Последовательность $ \ {k_0, k_1, \ ldots, k_h \} $
(где $ h $ —
высота дерева) описывает профиль дерева.n $ внешних узлов на уровне $ n $)
будет построено, если все последовательности вставки ключей $ N! $
одинаково вероятны?

Внутренние узлы в бинарных деревьях попадают в один из трех классов:
у них есть два, один или ноль внешних детей. Какая доля
узлы каждого типа в случайном двоичном каталонском дереве из $ N $ узлов?

6,43

Внутренние узлы в бинарных деревьях попадают в один из трех классов:
у них есть два, один или ноль внешних детей. Какая доля
узлы каждого типа в случайном двоичном дереве поиска из $ N $ узлов?

Вопросы к экзамену в классе

Q6.1

Дайте асимптотическое приближение (главный член) для числа унарно-бинарных деревьев с $ n $ узлами.

Q6.2

Расположите эти деревья в порядке их вероятной высоты для больших $ n $:
( a ) случайное каталонское дерево $ n $ _node
( b ) случайный $ n $ _node BST
( c ) случайное дерево $ n $ _node AVL
.

Примеры измеримых целей и задач

Часто ли вы замечаете, что излагаете большие планы, но терпите неудачу и отбрасываете план в сторону? Это обычное дело. К счастью, существует четко определенное решение, которому легко следовать. Он представлен в виде подробной системы измеримых целей и задач, которая направит вас на путь к успеху.

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

Давайте получим S.M.A.R.T.

Популярный мнемоник, S.M.A.R.T. помогает людям оставаться на пути к академическому, профессиональному и личному успеху. S.M.A.R.T. Система позволяет людям разработать надежный план с конкретными и измеримыми целями, не оставляя почти ничего на волю случая.

S.M.A.R.T. расшифровывается как «Конкретный», «Измеримый», «Достижимый», «Соответствующий» и «Ограниченный по времени».Давайте рассмотрим подробнее.

• Конкретный : Цели должны быть написаны максимально упрощенно, оттачивая один конкретный результат. Без этого основного принципа вам может быть трудно сосредоточиться и, в конце концов, вы почувствуете себя немотивированным.

• Плохо : Я хочу учиться лучше.

• Измеримый : Цели должны быть измеримыми таким образом, чтобы можно было представить материальные доказательства в процессе. Отслеживать свои вехи весело! Это может быть так же просто, как установить конкретную дату для вашего достижения.

• Плохо : Я собираюсь готовиться к тесту по математике в эту пятницу.

• Достижимо : Цели должны быть разработаны как хорошая тренировка. Они должны немного растягивать вас, чтобы вы чувствовали вызов, но не вызывали стресса или травм.

• Плохо : Я собираюсь сбросить 20 фунтов.

• Актуально : важно изучить свою цель. Убедитесь, что это актуально и реалистично.

• Плохо : Я хочу зарабатывать деньги на фондовом рынке.(Но вы ненавидите финансы.)

• Ограничение по времени : Цели должны быть привязаны к временным рамкам, которые создают практическое ощущение безотлагательности, создавая здоровую напряженность, которая будет двигать вас вперед.

• Плохо : Я хочу представить рассказ на конкурсе в следующем месяце.

Примеры S.M.A.R.T. Goals

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

Образец профессионального S.M.A.R.T. Цель

Общая цель : Я хочу вести собственный консалтинговый бизнес.

S.M.A.R.T. Цель : В течение одного месяца я найду своего первого клиента после разработки разумного плана рассылки презентаций.

• Особый : Используя свою сеть, я буду искать компании, нуждающиеся в моих консультационных услугах.

• Измеримый : Я буду предлагать своим первым трем клиентам в течение двух недель, а в дальнейшем буду предлагать пять презентаций в неделю.

• Достижимость : Я грамотно обрисую, что я могу сделать для бизнеса, я буду совершенствовать свою презентацию и работать над своим портфолио.

• Релевантно : Зная, что это то, в чем я хорош, я буду использовать свои связи и по-прежнему сосредоточен на своей мечте — заниматься работой, которая мне нравится.

• На основе времени : Я немедленно начну продвигать клиентов; через месяц у меня будет первый платящий клиент.

Образец академика С.M.A.R.T. Цель

Общая цель : Я хочу учиться лучше.

S.M.A.R.T. Цель : я буду стремиться к самому низкому среднему классу, чтобы повысить свой общий средний балл.

• Конкретный : Я хочу улучшить свой общий средний балл, чтобы я мог подать заявку на новую стипендию в следующем семестре.

• Измеримый : Я получу B или выше на промежуточном экзамене MAT 101.

• Достижимо : Каждую неделю я буду встречаться с репетитором по математике, чтобы помочь мне сосредоточиться на моих слабых местах.

• Релевантно : Я бы хотел сократить свои студенческие ссуды в следующем семестре. Воспитание этого среднего уровня низкого класса откроет для меня новые двери.

• На основе времени : у меня еще есть шесть недель до середины семестра. У меня остается достаточно времени, чтобы встретиться с репетитором и решить, нужны ли дополнительные шаги.

Образец личного S.M.A.R.T. Цель

Общая цель : Я хочу похудеть и улучшить свое здоровье.

S.M.A.R.T. Цель : Я сосредоточусь на своих пищевых привычках и начну вести более здоровый образ жизни.

• Особые : Я сокращу нездоровую пищу в качестве первого шага к общему хорошему здоровью.

• Измеримый : К декабрю у меня в кладовой будут только экологически чистые продукты и полезные закуски.

• Достижимо : Я пойду к диетологу, который разработает план здорового питания.

• Соответствует : Это вылечит некоторые из моих ноющих недугов e.грамм. повышенная утомляемость, боли в пояснице.

• По времени : в сентябре я изменю свои привычки в еде. В октябре начну больше ходить. К праздникам я смогу немного побаловать себя, не испортив новые здоровые привычки.

Вы обратили внимание на все случаи появления «Я буду» в приведенных выше примерах? Продолжайте говорить себе, что вы сделаете это с , что вы можете это сделать, а не просто то, что вам хотелось бы. Вы начали достигать своей цели в ту минуту, когда написали S.M.A.R.T. на этом свежем листе бумаги.

Это правда, что стресс не всегда оставляет место для мотивации. Однако, если мы будем постепенно отказываться от небольших проектов, следуя S.M.A.R.T. цели, мы будет , чтобы увидеть появление положительных изменений. Простой акт проверки вещей на наших таблицах целей очень полезен. Это маленькое действие может вызвать эффект домино на целый поток других действий.

Оставайтесь на правильном пути

Записывание измеримых целей и задач поможет вам не сбиться с пути и оставаться воодушевленным.Мечтайте настолько масштабно, насколько хотите. Просто убедитесь, что вы начинаете с конкретных и измеримых этапов, которые достижимы и актуальны. Постановка целей на временной основе означает, что на этот раз вы можете достичь их и увидеть, как ваши планы наконец обретают форму.

Примеры измеримых целей и задач.