Алгоритмы и программы, Решение олимпиадных задач, Порублев И.Н., Ставровский А.Б., 2007

Алгоритмы и программы, Решение олимпиадных задач, Порублев И.Н., Ставровский А.Б., 2007.

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

Алгоритмы и программы, Решение олимпиадных задач, Порублев И.Н., Ставровский А.Б., 2007


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

Обычно решения задачи программируют так, чтобы с помощью программы решить любой возможный экземпляр задачи. Например, экземпляры задачи “является ли заданное число простым?” — это задачи с конкретными числами: “является ли 997 простым?”, “является ли 2007 простым?” и т.д.

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

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

ОГЛАВЛЕНИЕ.
Предисловие.
Глава 1. Разминка (понемногу о разном).
Глава 2. Однопроходные алгоритмы.
Глава 3. Рекурсия.
Глава 4. Нестандартная обработка чисел.
Глава 5. Бинарный поиск, слияние и сортировка.
Глава 6. Вычислительная геометрия на плоскости.
Глава 7. Выметание.
Глава 8. Графы.
Глава 9. Графы клеток и графы с нагруженными ребрами.
Глава 10. Комбинаторика.
Глава 11. Перебор вариантов.
Глава 12. Жадные алгоритмы.
Глава 13. Динамическое программирование.
Глава 14. Игры двух лиц.
Глава 15. Японский кроссворд.
Приложение А. Указания по решению упражнений.
Список литературы.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Алгоритмы и программы, Решение олимпиадных задач, Порублев И.Н., Ставровский А.Б., 2007 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу



Скачать - pdf - Яндекс.Диск.
Дата публикации:





Теги: :: :: :: ::


 


 

Книги, учебники, обучение по разделам




Не нашёл? Найди:





2020-02-18 15:49:28