Род Стивенс

Книги → Delphi. Готовые алгоритмы → Глава 1. Основные понятия

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

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

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

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

Что такое алгоритмы

Алгоритм - это набор команд для выполнения определенной задачи. Если вы объясняете кому-то, как починить газонокосилку, вести автомобиль или испечь пирог, вы создаете алгоритм действий. Подобные ежедневные алгоритмы можно с некоторой точностью описать такого рода выражениями:

Проверьте, находится ли автомобиль на стоянке.

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

Поверните ключ

И т.д.

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

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

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

Если дверь заперта, то:

Вставьте ключ в замок

Поверните ключ

Если дверь все еще заперта, то:

Поверните ключ в другую сторону

Потяните за ручку двери

и т.д.

Эта часть кода описывает только открывание двери; здесь даже не проверяет­ся, та ли дверь будет открыта. Если замок заклинило или автомобиль оснащен про­тивоугонной системой, алгоритм открывания двери может быть гораздо сложнее.

← предущий раздел следующая →

Страницы раздела: 1 2 3 4 5 6 7 8 9 10 11

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.