Оптимальные программы вычисления выражений
Страница: [1]
Введение.
В наше время электронно-вычислительные машины и информационные технологии стали неотъемлемой частью промышленности и прочно вошли в быт простых граждан. И хотя современные компьютеры способны выполнять гораздо более сложные задачи чем могли их предкис 60-х годов двадцатого века, все равно математическая обработка информации была, есть и в будущем будет основой их работы. Каждый современный компьютер — или он применяется для обработки изображений, или для проектирования автомобилей, выступает в роли игрового автомата — все равно, в первую очередь, он является вычислительной машиной. Арифметические и логическиевыражения является неотъемлемой частью практически всех, даже узкоспециализированных, компьютерных программ и поэтому нужно иметь в наличии алгоритмы, которые распознают и вычисляют их как можно быстрее и эффективнее. Тема вычисления выражений проходит через большую часть программирования; с ней связаны синтаксис и семантика алгоритмических языков, компиляция, формальныеязыка, структуры данных, логика, рекурсия и вычислительная сложность. Поэтому научные разработки данного направления являются важными не только сейчас — они сохранят свою актуальность и в будущем.
Какая цель ставилась при написании данной работы? Среди основных целей можно назвать следующие:
систематизировать и обобщить существующие в настоящее время сведенияпо теории анализа и вычисления выражений;
выявить полезные с практической точки зрения критерии оптимальности программ и рассмотреть эффективность различных алгоритмов вычислений относительно этих критериев;
рассмотрев сильные и слабые стороны каждого алгоритма определить класс задач, на которых этот алгоритм имеет преимущества перед другими;
наметить основныеспособы оптимизации.
Поскольку критерием истины является практика, то не менее важным моментом данной дипломной работы является практическая реализация алгоритмов вычисления выражений на одном из языков программирования и проверка на практике эффективности методов оптимизации.
§ 1. Основные положения.
Существует по крайней мере три различных способа определенияарифметических выражений. Учебники по программированию для начинающих, как правило, подают их на примерах. Вполне логическая основа этого подхода заключается в том, что можно научиться писать правильные выражения, просмотрев достаточное количество примеров. Это в большой степени похоже на обучение некоторой не родной для человека иностранному языку. Так как было замечено, что большинствопрограммистов используют в своих программах достаточно простые выражения, то этот подход в большинстве случаев оказывался вполне приемлемым.
Более формальный подход состоит в том, что синтаксис и семантику арифметических и логических выражений задают с помощью контекстно-свободных правил преобразования, как это сделано в описании Алгол. Промежуточный подход, сохраняянекоторую долю математической точности определений и в значительной степени рассчитан на интуицию, заключается в определении этих выражений индуктивно или рекурсивно.
Арифметический выражение индуктивно определяется следующим образом:
Произвольная переменная является арифметическим выражением.
Произвольная константа является арифметическим выражением.
Произвольное ссылка на арифметическуюфункцию является арифметическим выражением.
Если Х — арифметическое выражение, то (Х) — тоже арифметическое выражение.
Если Х и У обеих есть арифметическими выражениями, то арифметическими выражениями также будут (Х + У ), (Х-У), (Х * У), (Х / У), (Х ^ В).
Ни один объект не является арифметическим выражением, если тот факт, что он является арифметическим выражением не следует из конечного числа примененийправил 1 — 5.
Это определение дает набор эффективных правил, пригодных для построения произвольного арифметического выражения в терминах переменных, констант, ссылок на функции и операций +, -, *, /, ^.
Страница: [1]
версия для печати
Читайте также:
— Два направления создания памяти будущего
— Суть и особенности вексельного обращения в условиях переходной экономики
— Методологические основы моделирования маркетинговой системы здравоохранения
— Турция
— Николай Хвылевой
|
|