16)_Опорный конспект по теме "Жадные алгоритмы"_ 11 класс_учеб. К.Поляков

Практическая работа «Жадные алгоритмы. Алгоритм Дейсктры»

1. Найти и выписать в тетрадь основные определения, прочитав материал:

1).https://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC

2). http://habrahabr.ru/post/120343/

3). http://ruza-gimnazia.ru/index.php/matem/340-2012-12-19-15-58-21

- граф;

- матрица смежности;

- весовая матрица;

- жадный алгоритм;

2. Всегда ли жадный алгоритм приводит к правильному решению?

3. Приведите три примера жадных алгоритмов. Опишите своими словами их суть.

1).

2).

3).

4. Определить по формулировке задачи является ли она задачей жадного алгоритма (вопрос задачи формулируется подобно задачам жадных алгоритмов. Например, как в задачах презентации к параграфу 44: inf/KADET300/11класс/11-6_СтруктурыДанных.ppt)?

Монетный двор выпускает монеты номиналом 25, 10, 5, 2, 1 копеек. Разработать программу, которая позволяла бы сумму в  N копеек разменять данными монетами.

5. Приведите примеры еще трех задач, решаемых жадными алгоритмами. Только названия.

1).

2).

3).