Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
1. Замена псевдоуказателей классами. Хотя все алгоритмы, которые были написаны для старых версий VB, все еще работают, многие из тех, что были написаны с применением псевдоуказателей (описанных во 2 главе), гораздо проще понять, используя классы.
2. Инкапсуляция. Классы позволяют заключить алгоритм в компактный модуль, который легко использовать в программе. Например, при помощи классов можно создать несколько связных списков и не писать при этом дополнительный код для управления каждым списком по отдельности.
3. Объектно‑ориентированные технологии. Использование классов также позволяет легче понять некоторые объектно‑ориентированные алгоритмы. В главе 13 описываются методы, которые сложно реализовать без использования классов.
Как пользоваться этим материалом
В главе 1 даются общие понятия, которые используются на протяжении всего изложения, поэтому вам следует начать чтение с этой главы. Вам стоит ознакомиться с этой тематикой, даже если вы не хотите сразу же достичь глубокого понимания алгоритмов.
В 6 главе обсуждаются понятия, которые используются в 7, 8 и 12 главах, поэтому вам следует прочитать 6 главу до того, как браться за них. Остальные главы можно читать в любом порядке.
=============xvi
В табл. 1 показаны три возможных учебных плана, которыми вы можете руководствоваться при изучении материала в зависимости от того, насколько широко вы хотите ознакомиться с алгоритмами. Первый план включает в себя освоение основных методов и структур данных, которые могут быть полезны при разработке вами собственных программ. Второй кроме этого описывает также основные алгоритмы, такие как алгоритмы сортировки и поиска, которые могут понадобиться при написании более сложных программ.
Последний план дает порядок для изучения всего материала целиком. Хотя 7 и 8 главы логически вытекают из 6 главы, они сложнее для изучения, чем следующие главы, поэтому они изучаются несколько позже.
Почему именно Visual Basic?
Наиболее часто встречаются жалобы на медленное выполнение программ, написанных на Visual Basic. Многие другие компиляторы, такие как Delphi, Visual C++ дают более быстрый и гибкий код, и предоставляют программисту более мощные средства, чем Visual Basic. Поэтому логично задать вопрос — «Почему я должен использовать именно Visual Basic для написания сложных алгоритмов? Не лучше было бы использовать Delphi или C++ или, по крайней мере, написать алгоритмы на одном из этих языков и подключать их к программам на Visual Basic при помощи библиотек?» Написание алгоритмов на Visual Basic имеет смысл по нескольким причинам.
Во‑первых, разработка приложения на Visual C++ гораздо сложнее и проблематичнее, чем на Visual Basic. Некорректная реализация в программе всех деталей программирования под Windows может привести к сбоям в вашем приложении, среде разработки, или в самой операционной системе Windows.
Во‑вторых, разработка библиотеки на языке C++ для использования в программах на Visual Basic включает в себя много потенциальных опасностей, характерных и для приложений Windows, написанных на C++. Если библиотека будет неправильно взаимодействовать с программой на Visual Basic, она также приведет к сбоям в программе, а возможно и в среде разработки и системе.
В-третьих, многие алгоритмы достаточно эффективны и показывают неплохую производительность даже при применении не очень быстрых компиляторов, таких, как Visual Basic. Например, алгоритм сортировки подсчетом,
@Таблица 1. Планы занятий
===============xvii
описываемый в 9 главе, сортирует миллион целых чисел менее чем за 2 секунды на компьютере с процессором Pentium с тактовой частотой 233 МГц. Используя библиотеку C++, можно было бы сделать алгоритм немного быстрее, но скорости версии на Visual Basic и так хватает для большинства приложений. Скомпилированные при помощи 5‑й версией Visual Basic исполняемые файлы сводят отставание по скорости к минимуму.
В конечном счете, разработка алгоритмов на любом языке программирования позволяет больше узнать об алгоритмах вообще. По мере изучения алгоритмов, вы освоите методы, которые сможете применять в других частях своих программ. После того, как вы овладеете в совершенстве алгоритмами на Visual Basic, вам будет гораздо легче реализовать их на Delphi или C++, если это будет необходимо.
=============xviii
Глава 1. Основные понятияВ этой главе содержатся общие понятия, которые нужно усвоить перед началом серьезного изучения алгоритмов. Начинается она с вопроса «Что такое алгоритмы?». Прежде чем углубиться в детали программирования алгоритмов, стоит потратить немного времени, чтобы разобраться в том, что это такое.
Затем в этой главе дается введение в формальную теорию сложности алгоритмов (complexity theory). При помощи этой теории можно оценить теоретическую вычислительную сложность алгоритмов. Этот подход позволяет сравнивать различные алгоритмы и предсказывать их производительность в разных условиях. В главе приводится несколько примеров применения теории сложности к небольшим задачам.
Некоторые алгоритмы с высокой теоретической производительностью не слишком хорошо работают на практике, поэтому в данной главе также обсуждаются некоторые реальные предпосылки для создания программ. Слишком частое обращение к файлу подкачки или плохое использование ссылок на объекты и коллекции может значительно снизить производительность прекрасного в остальных отношениях приложения.
После знакомства с основными понятиями, вы сможете применять их к алгоритмам, изложенным в последующих главах, а также для анализа собственных программ для оценки их производительности и сможете предугадывать возможные проблемы до того, как они обернутся катастрофой.
Что такое алгоритмы?
Алгоритм – это последовательность инструкций для выполнения какого‑либо задания. Когда вы даете кому‑то инструкции о том, как отремонтировать газонокосилку, испечь торт, вы тем самым задаете алгоритм действий. Конечно, подобные бытовые алгоритмы описываются неформально, например, так:
Проверьте, находится ли машина на стоянке.
Убедитесь, что машина поставлена на ручной тормоз.
Поверните ключ.
И т.д.
==========1
При этом по умолчанию предполагается, что человек, который будет следовать этим инструкциям, сможет самостоятельно выполнить множество мелких операций, например, отпереть и открыть дверь, сесть за руль, пристегнуть ремень, найти ручной тормоз и так далее.
Если же составляется алгоритм для исполнения компьютером, вы не можете полагаться на то, что компьютер поймет что‑либо, если это не описано заранее. Словарь компьютера (язык программирования) очень ограничен и все инструкции для компьютера должны быть сформулированы на этом языке. Поэтому для написания компьютерных алгоритмов используется формализованный стиль.
Интересно попробовать написать формализованный алгоритм для обычных ежедневных задач. Например, алгоритм вождения машины мог бы выглядеть примерно так:
Если дверь закрыта:
Вставить ключ в замок
Повернуть ключ
Если дверь остается закрытой, то:
Повернуть ключ в другую сторону
Повернуть ручку двери
И т.д.
Этот фрагмент «кода» отвечает только за открывание двери; при этом даже не проверяется, какая дверь открывается. Если дверь заело или в машине установлена противоугонная система, то алгоритм открывания двери может быть достаточно сложным.
Формализацией алгоритмов занимаются уже тысячи лет. За 300 лет до н.э. Евклид написал алгоритмы деления углов пополам, проверки равенства треугольников и решения других геометрических задач. Он начал с небольшого словаря аксиом, таких как «параллельные линии не пересекаются» и построил на их основе алгоритмы для решения сложных задач.
Формализованные алгоритмы такого типа хорошо подходят для задач математики, где должна быть доказана истинность какого‑либо положения или возможность выполнения каких‑то действий, скорость же исполнения алгоритма не важна. Для выполнения реальных задач, связанных с выполнением инструкций, например задачи сортировки на компьютере записей о миллионе покупателей, эффективность выполнения становится важной частью постановки задачи.
Анализ скорости выполнения алгоритмов
Есть несколько способов оценки сложности алгоритмов. Программисты обычно сосредотачивают внимание на скорости алгоритма, но важны и другие требования, например, к размеру памяти, свободному месту на диске или другим ресурсам. От быстрого алгоритма может быть мало толку, если под него требуется больше памяти, чем установлено на компьютере.
Пространство — время [RP1]
Многие алгоритмы предоставляют выбор между скоростью выполнения и используемыми программой ресурсами. Задача может выполняться
быстрее, используя больше памяти, или наоборот, медленнее, заняв меньший объем памяти.
===========2
Хорошим примером в данном случае может служить алгоритм нахождения кратчайшего пути. Задав карту улиц города в виде сети, можно написать алгоритм, вычисляющий кратчайшее расстояние между любыми двумя точками в этой сети. Вместо того чтобы каждый раз заново пересчитывать кратчайшее расстояние между двумя заданными точками, можно заранее просчитать его для всех пар точек и сохранить результаты в таблице. Тогда, чтобы найти кратчайшее расстояние для двух заданных точек, достаточно будет просто взять готовое значение из таблицы.
При этом мы получим результат практически мгновенно, но это потребует большого объема памяти. Карта улиц для большого города, такого как Бостон или Денвер, может содержать сотни тысяч точек. Для такой сети таблица кратчайших расстояний содержала бы более 10 миллиардов записей. В этом случае выбор между временем исполнения и объемом требуемой памяти очевиден: поставив дополнительные 10 гигабайт оперативной памяти, можно заставить программу выполняться гораздо быстрее.
Из этой связи вытекает идея пространственно‑временной сложности алгоритмов. При этом подходе сложность алгоритма оценивается в терминах времени и пространства, и находится компромисс между ними.
В этом материале основное внимание уделяется временной сложности, но мы также постарались обратить внимание и на особые требования к объему памяти для некоторых алгоритмов. Например, сортировка слиянием (mergesort), обсуждаемая в 9 главе, требует больше временной памяти. Другие алгоритмы, например пирамидальная сортировка (heapsort), которая также обсуждается в 9 главе, требует обычного объема памяти.
Оценка с точностью до порядка
При сравнении различных алгоритмов важно понимать, как сложность алгоритма соотносится со сложностью решаемой задачи. При расчетах по одному алгоритму сортировка тысячи чисел может занять 1 секунду, а сортировка миллиона — 10 секунд, в то время как расчеты по другому алгоритму могут потребовать 2 и 5 секунд соответственно. В этом случае нельзя однозначно сказать, какая из двух программ лучше — это будет зависеть от исходных данных.
Различие производительности алгоритмов на задачах разной вычислительной сложности часто более важно, чем просто скорость алгоритма. В вышеприведенном случае, первый алгоритм быстрее сортирует короткие списки, а второй — длинные.
Производительность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность порядка O(f(N)) (произносится «О большое от F от N»), если время выполнения алгоритма растет пропорционально функции f(N) с увеличением размерности исходных данных N. Например, рассмотрим фрагмент кода, сортирующий положительные числа:
For I = 1 To N
'Поиск наибольшего элемента в списке.
MaxValue = 0
For J = 1 to N
If Value(J) > MaxValue Then
MaxValue = Value(J)
MaxJ = J
End If
Next J
'Вывод наибольшего элемента на печать.
Print Format$(MaxJ) & ":" & Str$(MaxValue)
'Обнуление элемента для исключения его из дальнейшего поиска.
Value(MaxJ) = 0
Next I
===============3
В этом алгоритме переменная цикла I последовательно принимает значения от 1 до N. Для каждого приращения I переменная J в свою очередь также принимает значения от 1 до N. Таким образом, в каждом внешнем цикле выполняется еще N внутренних циклов. В итоге внутренний цикл выполняется N*N или N2 раз и, следовательно, сложность алгоритма порядка O(N2).
При оценке порядка сложности алгоритмов используется только наиболее быстро растущая часть уравнения алгоритма. Допустим, время выполнения алгоритма пропорционально N3+N. Тогда сложность алгоритма будет равна O(N3). Отбрасывание медленно растущих частей уравнения позволяет оценить поведение алгоритма при увеличении размерности данных задачи N.
При больших N вклад второй части в уравнение N3+N становится все менее заметным. При N=100, разность N3+N=1.000.100 и N3 равна всего 100, или менее чем 0,01 процента. Но это верно только для больших N. При N=2, разность между N3+N =10 и N3=8 равна 2, а это уже 20 процентов.
Постоянные множители в соотношении также игнорируются. Это позволяет легко оценить изменения в вычислительной сложности задачи. Алгоритм, время выполнения которого пропорционально 3*N2, будет иметь порядок O(N2). Если увеличить N в 2 раза, то время выполнения задачи возрастет примерно в 22, то есть в 4 раза.
Игнорирование постоянных множителей позволяет также упростить подсчет числа шагов алгоритма. В предыдущем примере внутренний цикл выполняется N2 раз, при этом внутри цикла выполняется несколько инструкций. Можно просто подсчитать число инструкций If, можно подсчитать также инструкции, выполняемые внутри цикла или, кроме того, еще и инструкции во внешнем цикле, например операторы Print.
Вычислительная сложность алгоритма при этом будет пропорциональна N2, 3*N2 или 3*N2+N. Оценка сложности алгоритма по порядку величины даст одно и то же значение O(N3) и отпадет необходимость в точном подсчете количества операторов.
Поиск сложных частей алгоритма
Обычно наиболее сложным является выполнение циклов и вызовов процедур. В предыдущем примере, весь алгоритм заключен в двух циклах.
============4
Если процедура вызывает другую процедуру, необходимо учитывать сложность вызываемой процедуры. Если в ней выполняется фиксированное число инструкций, например, осуществляется вывод на печать, то при оценке порядка сложности ее можно не учитывать. С другой стороны, если в вызываемой процедуре выполняется O(N) шагов, она может вносить значительный вклад в сложность алгоритма. Если вызов процедуры осуществляется внутри цикла, этот вклад может быть еще больше.
Приведем в качестве примера программу, содержащую медленную процедуру Slow со сложностью порядка O(N3) и быструю процедуру Fast со сложностью порядка O(N2). Сложность всей программы будет зависеть от соотношения между этими двумя процедурами.
Если процедура Slow вызывается в каждом цикле процедуры Fast, порядки сложности процедур перемножаются. В этом случае сложность алгоритма равна произведению O(N2) и O(N3) или O(N3*N2)=O(N5). Приведем иллюстрирующий этот случай фрагмент кода:
Sub Slow()
Dim I As Integer
Dim J As Integer
Dim K As Integer
For I = 1 To N
For J = 1 To N
For K = 1 To N
' Выполнить какие‑либо действия.
Next K
Next J
Next I
End Sub
Sub Fast()
Dim I As Integer
Dim J As Integer
Dim K As Integer
For I = 1 To N
For J = 1 To N
Slow ' Вызов процедуры Slow.
Next J
Next I
End Sub
Sub MainProgram()
Fast
End Sub
С другой стороны, если процедуры независимо вызываются из основной программы, их вычислительная сложность суммируется. В этом случае полная сложность будет равна O(N3)+O(N2)=O(N3). Такую сложность, например, будет иметь следующий фрагмент кода:
Sub Slow()
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48
