Что такое жадные программы

Содержание

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

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

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

Формальное определение

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

Преимущества жадных алгоритмов

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

Недостатки

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

В общем, жадные алгоритмы состоят из пяти компонентов:

Набор кандидатов, на основе которого создается решение

2. Функция выбора, которая выбирает лучшего кандидата для добавления в решение.

Жадность — это когда нас не любят

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

4. Целевая функция, которая присваивает значение решению или частичному решению.

5. Функция решения, которая укажет, когда мы нашли полное решение.

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

Задача коммивояжера
Алгоритм минимального остовного дерева Краскала
Алгоритм минимального остовного дерева Дейкстры
Проблема с рюкзаком
Проблема с расписанием работы

Давайте подробно обсудим, как решить проблему планирования работ.

Проблема с расписанием работы

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

Еврейская Притча о Жадности. «Сколько захочет сам»

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

Алгоритм

1) Sort all jobs in decreasing order of profit.2) Initialize the result sequence as the first job in sorted jobs.3) Do following for remaining n-1 jobs a) If the current job can fit in the current result sequence without missing the deadline, add the current job to the result. b) Else ignore the current job.

Код Java

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

В ближайшее время встретимся с еще одной интересной статьей.

Другие статьи о структуре данных и алгоритмах, которые могут вам понравиться

Источник: digitrain.ru

Вредоносные программы

Под вредоносными программами в статье 273 УК РФ понимаются программы, специально созданные для нарушения нормального функционирования компьютерных программ. Под нормальным функционированием понимается выполнение определенных в документации на программу операций.

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

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

Из перечисленных выше вредоносных программ шире всего распространены компьютерные вирусы.

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

По месту обитания можно выделить следующие виды вирусов:

вирусы, заражающие исполняемые файлы; вирусы, заражающие управляющие сектора дисков (boot сектор и/или master boot сектор); вирусы, заражающие flash-BIOS; комбинированные вирусы, которые заражают как файлы, так и управляющие сектора дисков; макровирусы, заражающие текстовые файлы Microsoft Word и Microsoft Exel; вирусы, заражающие объектные библиотеки; вирусы, заражающие исходные файлы, написанные на том или ином языке программирования; сетевые вирусы (вирусы-черви).

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

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

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

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

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

Жадные алгоритмы

Деньги

Доброго времени суток, хабр! Сегодня я бы хотел рассказать про жадные алгоритмы.

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

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

Жадность не порок

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

К слову, алгоритм Флойда, который тоже ищет кратчайшие пути в графе (правда, между всеми вершинами), не является примером жадного алгоритма. Флойд демонстрирует другой метод — метод динамического программирования.

Использование жадного алгоритма довольно стандартное. Рассмотрим его на примере следующей задачи:

Задача о расписании

Пусть программисту-фрилансеру Васе Пупкину дано n заданий. У каждого задания известен свой дедлайн, а также его стоимость(то есть если он не выполняет это задание, то он теряет столько-то денег). Вася настолько крут, что за один день может сделать одно задание. Выполнение задания можно начать с момента 0. Нужно максимизировать прибыль.

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

Получается следующий код:

//tasks — массив заданий
Arrays.sort(tasks); //сортируем по убыванию стоимости
TreeSet time = new TreeSet();
for ( int i = 1; i time.add(i);
>
int ans = 0;
for ( int i = 0; i < n; ++i) Integer tmp = time.floor(tasks[i].time);
if (tmp == null ) < // если нет свободного места в расписании, то в конец
time.remove(time.last());
> else < //иначе можно выполнить задание, добавляем в расписание
time.remove(tmp);
ans += tasks[i].cost;
>
>

Когда можно быть жадным?

Всегда Иногда может возникнуть искушение использовать жадину везде, где только это возможно, но на некоторых задачах это неприемлимо. К примеру, задача о рюкзаке: вор пробрался на склад, в котором хранятся три вещи весом 10 кг, 20 кг и 30 кг и стоимостью 60, 100 и 120 деревянных вечнозеленых нанорублей соответственно. Вор максимум может унести 50 кг. Нужно максимизировать прибыль вора. Если поступать здесь жадно и выбирать самую ценную вещь(то есть, 6 нанорублей за кг первой штуки, 5 нанорублей за кг второй и 4 нанорубля за кг третьей), то вор по-любому должен взять первую вещь, потом останется место для второй вещи, однако оптимальное решение составляет вторая и третья вещь.

Жизнь не матроид, жизнь — конечный автомат!

Как подсказывает википедия, матроид — это пара (X, I), где X — конечное множество, называемое носителем матроида, а I — некоторое множество подмножеств X, называемое семейством независимых множеств. При этом должны выполняться следующие условия:

Множество I непусто. Даже если исходное множество X было пусто — X = Ø, то I будет состоять из одного элемента — множества, содержащего пустое. I = >
Любое подмножество любого элемента множества I также будет элементом этого множества.
Если множества A и B принадлежат множеству I, а также известно, что размер А меньше B, то существует какой-нибудь элемент x из B, не принадлежащий А, такое что объединение x и A будет принадлежать множеству I. Это свойство является не совсем тривиальным, но чаще всего наиважшейшим из всех остальных.

Матроид называется взвешенным, если на множестве X существует аддитивная весовая функция w. Вес множества будет определяться как сумма весов его элементов.

первое свойство, очевидно, выполняется. Пустое множество выполненных заданий входит в наше множество. Ну и пофиг, что Вася не хочет зарабатывать деньги.
второе множество тоже выполняется. Почему это так: давайте отсортируем успешно выполненные задания в порядке увеличения дедлайна. В таком порядке они все равно будут успешно выполненными. В таком порядке очевидно, что любое подмножество успешно выполненных заданий будет успешно выполнено.
третье свойство, хоть и не очевидно, но выполняется. Пусть у нас есть два множества успешно выполненных заданий A и B, при чем известно, что |A| < |B|. Стандартно отсортируем задания в порядке увеличения дедлайна в обоих множествах. Возьмем задание из B, которого нет в A, и попробуем добавить его к множеству A. Это у нас получится, ведь если бы в А не было пробела, то данное задание должно было присутствовать.

К чему это я? Вся прелесть матроидов заключается в теореме Радо-Эдмондса: если доказать, что объект является матроидом, то жадный алгоритм будет работать корректно и выдавать правильный результат.

Сам по себе жадный алгоритм реализуется примерно вот так:

//отсортируем по весу
//вначале ответом будет пустое множество
for to
if then //если подходит
//то включаем в множество