Алгоритмизация, алгоритмы, языки и программы. Алгоритмизация и программирование Основы алгоритмизации и языки программирования

1. Понятие алгоритма

Алгоpитм – это точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Название "алгоритм " произошло от латинской формы имени среднеазиатского математика аль-Хорезми - Algorithmi.

Исполнитель алгоритма - это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Исполнителя характеризуют: среда, элементарные действия, система команд, отказы. Среда (или обстановка) - это "место обитания" исполнителя. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка - системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. После вызова команды исполнитель совершает соответствующее элементарное действие . Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.

В информатике универсальным исполнителем алгоритмов является компьютер.

2. Свойства алгоритмов

Можно выделить следующие основные свойства алгоритмов:

1) Понятность для исполнителя - т.е. исполнитель алгоритма должен знать, как его выполнять.

2) Дискретность (прерывность, раздельность) - т.е. алгоритм должен представлять процесс решения задачи как последовательное выполнение простых или ранее определенных шагов.

3) Определенность - т.е. каждое правило алгоритма должно быть четким, однозначным и не оставлять места для разночтений.

4) Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.

5) Массовость - означает, что алгоритм решения задачи pазpабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма .

3. Формы представления алгоритмов

Наиболее распространенными формами представления алгоритмов являются: словесная, графическая, псевдокоды и программная.

1) Словесная форма записи представляет собой описание последовательных этапов обработки данных на естественном языке (например, на русском).

Пример. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

Алгоритм: 1) задать два числа; 2) если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; 3) определить большее из чисел; 4) заменить большее из чисел разностью большего и меньшего из чисел; 5) повторить алгоритм с шага 2.

Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи за конечное число шагов.

Словесный способ не имеет широкого распространения, поскольку такие описания:

а) строго не формализуемы;

б) страдают многословностью записей;

в) допускают неоднозначность толкования отдельных предписаний.

2) Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. При графическом исполнении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного из действий. Такое графическое представление называется схемой алгоритма или блок-схемой . В блок-схеме каждому типу действий соответствует геометрическая фигура, называемая блочным символом. Блочные символы соединяются линиями переходов , определяющими очередность выполнения действий.

Подробнее об этом ниже…

3) Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языками.

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

Пример. 1) задать два числа x и y; 2) ЕСЛИ x=y, ТО НОД=x и КОНЕЦ; 3) ЕСЛИ x>y, ТО x=x-y, ИНАЧЕ y=y-x; 4) ПЕРЕЙТИ в пункт 2.

4) Программная форма представляет собой тексты программ, написанных на различных языках программирования.

Ниже приведены графические обозначения на блок-схемах.

Структура “следование”

Полная развилка

Неполная развилка

Цикл с предусловие

(цикл ПОКА)

Цикл с постусловием (цикл ДО)

Цикл с параметром

На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе - по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ - параметр цикла, НЗ - начальное значение параметра цикла, КЗ - конечное значение параметра цикла, Ш - шаг изменения параметра цикла.

Начало и конец алгоритма на блок-схемах обозначают овалом, вводимые и выводимые переменные записываются в параллелограмме.

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

Мотивирующее изображение:

Проблема

Обычно в разработчики переходят новоиспеченные специалисты до 30-ти лет. И сразу же возникает несколько серьезных проблем:

5-6 лет потерянных на изучение предметов и наук, которые больше никогда не понадобятся;
Необходимая смена мышления с гуманитарного\технического на логическое\цифровое;
Освоение 5-6 лет программы технического вуза в кратчайшие сроки;
Создание угрозы жизни и благополучия людей, компаний, бизнеса...

Время

Спрашивается, зачем человек изучал несколько лет не нужные ему науки? Зачем подвергал себя таким умственным нагрузкам? Чтобы потом все бросить и начать все с начала? Даже 5 лет это много. За это время можно стать миллиардером или же получить Нобелевскую премию, так нет, человек изучает то что ему не интересно, спит на парах и говорит, что философия - это полнейший бред!

Хорошо, если он обучается на платном отделении, а если за счет государства? Это значит, что кто-то, мечтавший стать архитектором, менеджером, финансистом, военным, не попал на это место. Ему пришлось искать другое место под солнцем, возможно, он пошел учиться на программиста.

Там же все просто!

Сколько таких новоявленных «программистов», прочитавших о JAVA у Брюса Эккеля. Все они считают себя гениями программирования, а ООП, MVC, Agile, двоичная система исчисления, теория сложности вычислений… не для них.

Приведу несколько жизненных примеров:

«Программист» пишет вторую версию программы. В первой - была одна форма на 50 кнопок. Вторая версия обладает большей функциональностью, но ее логика не так прозрачна. Планируется писать программу пару месяцев. В функционал заложено порядка 100 кнопок на одной форме. После 10-и минутного введения в теорию графов количество кнопок сократилось до одной (удаление точки), срок написания программы сократился до двух дней.
«Программисту» дали задание написать программу-конвертер. Логика простая: приходит пакет вида ключ=значение, надо по специальной таблице конвертировать его в пакет2 вида ключ2=значение2 и отправить дальше. После двух месяцев «изучения платформы» ему был передан каркас приложения (прием пакета, трансформация, отправка пакетов) старшими товарищами. Через месяц конвертер был готов!
Множество реализованных велосипедов;
Говорящий за себя http://govnokod.ru ;

Могу сказать только одно: если бы программирование было таким простым, то ему бы не учили в университетах по пять лет. Достаточно было бы и трехмесячных курсов .

Таланты

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

«Найди себе дело по душе и ни единой минуты в жизни ты не будешь работать» - Конфуций. Важно не потратить на поиск этого дела всю жизнь, иначе придется всю жизнь «вкалывать».

Запах пороха

Очень хорошая идея показать, что представляет собой разработка. Понюхать пороха, так сказать! Вот уже и мэры начали изучать JS .

В одной компании, моей знакомой и всему отделу по работе с клиентами показали, как верстать страницы, рассказали, что такое теги. Они даже сверстали простые странички.

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

Заключение

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

Все же, думаю, большинство «новых программистов» стремятся больше зарабатывать: сидишь себе - деньги получаешь. Правда, потом такие люди сильно подводят свою команду, работают не в полную силу. А если еще и начальство закроет на это глаза (да, да, такое бывает!), то с ними каши не сваришь, google не разработаешь.

Как показывают исследования . IT в России - не самая высокооплачиваемая отрасль. Она занимает лишь третье место. На втором месте сырьевые отрасли, а на первом - высший менеджмент . Из-за специфики IT, программист никогда не достигнет ступеньки высшего менеджмента. Максимум, на что стоит рассчитывать, это должность руководителя отдела, ведущего направления, директора собственной компании.

Поэтому делайте выводы. Смена рода деятельности серьезный шаг, он должен быть обдуман. Минимум, надо будет изучить современный курс программирования, и это займет не один год.

P.S. В комментариях спрашивают про цели заметки: серьезнее относиться в выбору профессии, заниматься только любимым делом, учиться тому что нравится, профессионально расти, а не пробовать все понемногу без определенной цели. Удивляют люди, которые в 30-40 лет так и не смогли найти себе занятие по душе.

Бураков П.В., Косовцева Т.Р. Информатика. Алгоритмы и программирование. Учебное пособие.-СПб НИУ ИТМО, 2013. – 83с.

Учебное пособие предназначено для студентов экономических специальностей специальности 080100 «Экономика» гуманитарного факультета, изучающих дисциплину «Информатика». Пособие представляет собой вводный курс по построению алгоритмов и по программированию на языке Турбо Паскаль. Пособие содержит много примеров. Подробно излагаются теоретические аспекты построения алгоритмов и основ программирования. Во второй части учебного пособия приводтся лабораторный практикум.

В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет». Министерством образования и науки Российской Федерации была утверждена Программа развития государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный университет информационных технологий, механики и оптики» на 2009– 2018 годы.


Постановка задачи.........................................................................................................................
Разработка математической модели............................................................................................
Выбор метода численного решения.............................................................................................
Разработка алгоритма и структуры данных................................................................................
Реализация алгоритма в виде программы...................................................................................
Отладка и тестирование программы............................................................................................
Решение задачи на компьютере...................................................................................................
ПОСТРОЕНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ.............................................................................
Описание алгоритма......................................................................................................................
Схема алгоритма..........................................................................................................................
Структурированные схемы алгоритмов....................................................................................
СРЕДСТВА РЕАЛИЗАЦИИ АЛГОРИТМА..........................................................................................
Критерии выбора языка программирования.............................................................................
СТРУКТУРА ПРОГРАММЫ И ЕЕ ЭЛЕМЕНТЫ.................................................................................
Основные элементы программирования...................................................................................
Алфавит и словарь языка TurboPascal (TPascal).......................................................................
Структура программы.................................................................................................................
ТИПЫ ДАННЫХ......................................................................................................................................
Скалярные типы данных.............................................................................................................
Структурированные типы данных.............................................................................................
ВВОД-ВЫВОД ДАННЫХ.......................................................................................................................

Процедуры ввода-вывода...........................................................................................................
ОПЕРАТОРЫ............................................................................................................................................
Общие сведения...........................................................................................................................
Простые операторы.....................................................................................................................
Структурные операторы.............................................................................................................
Условные операторы...................................................................................................................
Операторы цикла.........................................................................................................................
МАССИВЫ................................................................................................................................................
Действия над массивами.............................................................................................................
Действия над элементами массива............................................................................................
Операции с матрицами................................................................................................................
ПРОЦЕДУРЫ И ФУНКЦИИ...................................................................................................................
Необходимость структуризации в программировании............................................................
Подпрограммы в языке ТPascal..................................................................................................
Процедуры....................................................................................................................................
Функции.......................................................................................................................................
Механизм передачи параметров................................................................................................
ФАЙЛЫ.....................................................................................................................................................
Общие сведения...........................................................................................................................
Описания файлового типа..........................................................................................................
Средства обработки файлов.......................................................................................................
Текстовые файлы.........................................................................................................................

ЛАБОРАТОРНЫЙ ПРАКТИКУМ..........................................................................................................
Лабораторная работа 1.		Программирование линейных и	разветвляющихся
вычислительных процессов.............................................................................................................
Лабораторная работа № 2.	Циклические вычислительные процессы...................................
Лабораторная работа № 3.		Операции с массивами.................................................................
Лабораторная работа № 4.	Операции с файлами.....................................................................
Лабораторная работа 5. Процедуры и функции......................................................................
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.....................................................................................................

ЭЛЕМЕНТЫ ТЕХНОЛОГИИ РЕШЕНИЯ ПРАКТИЧЕСКИХ ЗАДАЧ НА КОМПЬЮТЕРЕ

Решение задач с применением персонального компьютера включает следующие основные этапы.

1. Постановка задачи.

2. Разработка математической модели.

3. Выбор метода численного решения для расчетных задач.

4. Разработка алгоритма решения и структуры данных.

5. Реализация алгоритма в виде программы.

6. Отладка и тестирование программы.

7. Решение задачи на компьютере, численные эксперименты и анализ результатов.

Постановка задачи

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

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

Требуется определить длину пути, который проходит тело, движущееся с переменной скоростью. Начальная скорость тела равна 0. С определенной степенью степенью достоверности движение можно считать равноускоренным. Использование пакетов стандартных программ не предполагается.

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

Разработка математической модели

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

Математической моделью задачи, сформулированной в примере 1 является формула: S = 0,5 a t 2 , где в качестве основной переменной выступает время t , параметром движения является ускорение а . Формула показывает зависимость между длиной пути и временем в соответствии с законом механики.

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

S = ∫ V (t) dt ,

при этом закон изменения скорости V(t) в зависимости от времени может быть достаточно сложным и определить значение интеграла аналитически не удается. Поэтому в большинстве случаев практически целесообразно использовать приближенные методы решения.

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

Выбор метода численного решения

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

∫ f (x ) dx ≈ ∆ x ∑ f (x i ) , где ∆х - шаг интегрирования (const), ∆х=(b-a)/n,

x i+1 =xi +∆ х, x1 =a , xn+1 =b

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

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

Разработка алгоритма и структуры данных

Если выбранный для решения задачи численный метод реализован в виде стандартной библиотечной подпрограммы, то алгоритм обычно сводится к описанию и вводу исходных данных, вызову стандартной подпрограммы и выводу результатов на экран или на печать. Более характерен случай, когда стандартные подпрограммы решают лишь какую-то часть задачи.

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

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

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

Реализация алгоритма в виде программы

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

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

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

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

Отладка и тестирование программы

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

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

По данным разных авторов, этап отладки и тестирования программы занимает от 50 до 70 % времени, затрачиваемого на все этапы создания программы и получения решения. В связи с важностью и трудоемкостью этапа отладки все современные системы программирования имеют специальные средства, помогающие в обнаружении и устранении ошибок. Уже на этапе разработки алгоритма полезно предусмотреть простейшие средства контроля, встраиваемые в разрабатываемую программу: печать введенных данных непосредственно после их считывания в память машины (эхо-печать), печать промежуточных результатов в узловых точках. Но главное - надо максимально упрощать структуру программы за счет расчленения ее на модули, реализуемые в виде подпрограмм или процедур, и использования конструкций языка, наиболее простых и освоенных программистом.

Решение задачи на компьютере

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

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

Контрольные вопросы

1. Какие факторы влияют на эффективность решения задач на компьютере?

2. Перечислите этапы решения задач на компьютере.

3. Каковы основные требования к математической модели задачи?

4. Назовите главные характеристики алгоритмов.

5. Какие особенности следует учитывать при разработке программ на компьютере?

6. Чем завершается разработка алгоритма?

ПОСТРОЕНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

Описание алгоритма

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

Определенность. Все действия, которые необходимо произвести должны быть строго определены.

Понятность. Все действия, которые необходимо произвести, должны быть однозначно поняты и выполнены каждым исполнителем алгоритма. Это свойство может быть интерпретировано как однозначность алгоритма, под которой понимается единственность толкования исполнителем правил выполнения действий и порядка их выполнения.

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

Результативность . Если алгоритм применим к данной задаче, то после конечного числа шагов должен быть получен результат.

Массовость. Возможность применения данного алгоритма для решения класса задач, отвечающих общей постановке задачи.

Правильность . Способность алгоритма давать правильные результаты решения поставленных задач.

Каждое правило алгоритма записывается в виде повелительного предложения, понимаемого исполнителем алгоритма как команда на выполнение.

Рассмотрим алгоритмы решения нескольких задач. Задача 1 . Составить алгоритм вычисления x по формуле

x = a (r − q ) 2 , где p ≠ -12.

p + 12

1. Начало;

2. Вычислить b:= p + 12;

3. Вычислить c:= r – q;

4. Вычислить d:= c c;

5. Вычислить e:= a d;

6. Вычислить x:= e / b;

7. Записать результат: x;

В записи алгоритма решения задачи 1 введены буквенные обозначения

– переменные. Так, через b обозначено p + 12 , через c – разность r – q. Запись

b:= p+12 означает, что вначале должна быть найдена сумма p + 12 при определенных значениях p, а затем это значение присваивается переменной b.

Придавая a, p, q, r разные значения, будем получать различные задания на вычисление x . Поэтому алгоритм обычно позволяет решать не одну, а целый класс задач. Такую особенность алгоритма называют массовостью алгоритма. Возможны алгоритмы, решающие только единственную задачу.

Величины a, p, q, r, 12 составляют исходные данные для алгоритма, 12

– постоянную составляющую, a, p, q, r – переменную составляющую информации. Величины b, c, d, e являются вспомогательными переменными, x – результат исполнения алгоритма.

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

Следует отметить, что сама формула не является алгоритмом, так как не указан однозначный порядок исполнения операций.

Задача 2 . По формуле

x = − b ± b 2 − 4 ac составить алгоритм решения квадратного уравнения

ax2 + bx + c = 0 (a ≠ 0).

1. Начало;

2. p:= 2a;

3. D:= b 2 – 4ac;

4. Если D ≥ 0, то перейти к п. 5, иначе к п. 10;

5. d:= D ;

6. x 1 : = − b − d ; p

7. x 2 : = − b + d ; p

8. Записать результат: x 1 , x2 ;

9. Перейти к п. 11;

10. Записать результат: уравнение действительных корней не имеет;

11. Конец.

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

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

В командах условного перехода обязательно присутствует логическое условие типа: если α ◊ β , то …(где ◊ - один из операторов > , ≥ , < , ≤ , = , ≠ ).

Схема алгоритма

Схема алгоритма представляет собой графическое изображение алгоритма с помощью определенным образом связанных между собой блоков. Каждый блок изображается определенной фигурой. Блоки в схеме соединяются дугами. Дуги указывают порядок следования блоков при исполнении алгоритма. Типы блоков представлены на рисунке 1.

Рис.1 . Типы блоков

Прямоугольник вместе с заключенным в нем этапом вычисления S называют функциональным блоком , или процессом (рис.1, а). Ромб с заключенным в нем условием P называют блоком проверки условия , или решением (рис.1, б). Он используется для управления порядком исполнения блоков в схеме алгоритма. Из функционального блока выходит одна стрелка, а из блока проверки условия – две. Последнее объясняется тем, что в результате исполнения команды проверки условия получаем либо выполнение (да), либо невыполнение (нет) заданного условия P. Информационный блок (рис.1, в) используется для ввода и вывода А. Блоки (рис.1, г) и (рис.1, д) называют соответственно начальным и конечным . Блок-схема решения задачи начинается в начальном блоке и заканчивается в конечном.

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

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

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

На рисунках 2 и 3 изображены схемы алгоритмов решения задачи нахождения суммы n - чисел: a1 , a2 , a3 , a4 ,.., an .

Алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово X=xx... x[n] и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l... l[n], где l[i]=длина слова l(x...х[i]) (функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x...x[i], одновременно являющегося его концом.

Какое отношение все это имеет к поиску подслова?

Другими словами, как использовать алгоритм КМП для определения того, является ли слово A подсловом слова B?

Решение. Применим алгоритм КМП к слову A#B, где # - специальная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A.

Описать алгоритм заполнения таблицы l...l[n].

Решение. Предположим, что первые i значений l...l[i] уже найдены. Мы читаем очередную букву слова (т.е. x) и должны вычислить l.

Другими словами, нас интересуют начала Z слова x...x . Слово Z" является началом и концом слова x...x[i]. Однако не любое слово, являющееся началом и концом слова x...x[i], годится - надо, чтобы за ним следовала буква x.

Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова x...x[i], являющиеся одновременно его концами. Из них выберем подходящие - те, за которыми идет буква x. Из подходящих выберем самое длинное. Приписав в его конец х, получим искомое слово Z. Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции l из предыдущего раздела.

Вот что получается:

{таблица l..l[i] заполнена правильно}

while i <> n do begin

{len - длина начала слова x..x[i], которое является

его концом; все более длинные начала оказались

неподходящими}

while (x<>х) and (len>0) do begin

if x=x do begin

{х..x - самое длинное подходящее начало}

{подходящих нет}

Доказать, что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C.

Решение. Это не вполне очевидно: обработка каждой очередной буквы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней мере на 1, и в этом случае l окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу величина l[i] может возрасти не более чем на 1, так что часто и сильно убывать она не может - иначе убывание не будет скомпенсировано возрастанием.

Более точно, можно записать неравенство

(число итераций на i-м шаге)<= l[i]-l+1

Остается сложить эти неравенства по всем i и получить оценку сверху для общего числа итераций.

Будем использовать этот алгоритм, чтобы выяснить, является ли слово X длины n подсловом слова Y длины m. (Как это делать с помощью специального разделителя #, описано выше.) При этом число действий будет не более C(n+m}, и используемая память тоже. Придумать, как обойтись памятью не более Cn (что может быть существенно меньше, если искомый образец короткий, а слово, в котором его ищут - длинное).

Решение. Применяем алгоритм КМП к слову А#В. При этом: вычисление значений l,...,l [n] проводим для слова X длины n и запоминаем эти значения. Дальше мы помним только значение l[i] для текущего i - кроме него и кроме таблицы

l...l[n], нам для вычислений ничего не нужно.

На практике слова X и Y могут не находиться подряд, поэтому просмотр слова X и затем слова Y удобно оформить в виде разных циклов. Это избавляет также от хлопот с разделителем.

Написать соответствующий алгоритм (проверяющий, является ли слово X=x...x[n] подсловом слова Y=y...y[m]

Решение. Сначала вычисляем таблицу l...l[n]как раньше. Затем пишем такую программу:

{len - длина максимального качала слова X, одновременно

являющегося концом слова y..j[j]}

while (len<>n) and (j<>m) do begin

while (x<>у) and (len>0) do begin

{начало не подходит, применяем к нему функцию l}

{нашли подходящее или убедились в отсутствии}

if x=y do begin

{x..x - самое длинное подходящее начало}

{подходящих нет}

{если len=n, слово X встретилось; иначе мы дошли до конца

слова Y, так и не встретив X}

Алгоритм Бойера - Мура

Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвертую букву слова: если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. (В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы.)

Мы приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть x...х[n] - образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором х[k]=s. Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам будет удобно положить pos[s]=0 (мы увидим дальше, почему).

Как заполнить массив pos?

положить все pos[s] равными 0

for i:=1 to n do begin

В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале last=n (длина образца), затем last постепенно увеличивается.

{все предыдущие положения образца уже проверены}

while last<= m do begin {слово не кончилось}

if x[m]<>y then begin {последние буквы разные}

last:=last+(n-pos]);

{n - pos] - это минимальный сдвиг образца,

при котором напротив y встанет такая же

буква в образце. Если такой буквы нет вообще,

то сдвигаем на всю длину образца}

если нынешнее положение подходит, т.е. если

x[i]..х[n]=y..y,

то сообщить о совпадении;

Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s],

т.е. число букв в образце справа от последнего вхождения буквы Возможны разные модификации этого алгоритма. Например, можно строку

заменить на

last:=last+(n-u),

где u - координата второго справа вхождения буквы x[n] в образец.

Как проще всего учесть это в программе

Решение. При построении таблицы pos написать

написать

last:=last+n-pos];

Приведенный упрощенный вариант алгоритма Бойера-Мура в некоторых случаях требует существенно больше n действий (число действий порядка mn), проигрывая алгоритму Кнута-Морриса-Пратта.

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

Решение. Пусть образец имеет вид baaa... aa, а само слово состоит только из букв а. Тогда на каждом шаге несоответствие выясняется лишь в последний момент.

Настоящий (не упрощенный) алгоритм Бойера-Мура гарантирует, что число действий не превосходит C(m+n) в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z (являющийся концом образца) совпал, а затем обнаружилось различие: перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нем обнаружен фрагмент, равный Z, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, все это (вычисление таблицы сдвигов и ее использование) можно уложить в C(m+ n) действий.

Алгоритм Рабина

Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах длины n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам.

В чем выигрыш при таком подходе. Казалось бы, ничего - ведь чтобы вычислить значение функции на слове в окошечке, все равно нужно прочесть все буквы этого слова. Так уж лучше их сразу сравнить с образцом. Тем не менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция.

Привести пример удобной для вычисления функции.

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

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

Привести пример семейства удобных функций.

Решение. Выберем некоторое число p (желательно простое, смотри далее) и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается, таким образом, своя функция). Сдвиг окошка на 1 соответствует вычитанию старшего члена (хn-1 следует вычислить заранее), умножению на x и добавлению свободного члена.

Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же простое, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно, если p больше числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если и много меньше p, то случайному x мало шансов попасть в неудачную точку.

Подобные документы

Теоретические сведения. Основные понятия. Строка, её длина, подстрока. Понятие о сложности алгоритма. Алгоритмы основанные на методе последовательного поиска. Алгоритмы Рабина, Кнута - Морриса - Пратта, Бойера – Мура.

курсовая работа , добавлен 13.06.2007

Организация возможности просмотра текстовых файлов и осуществления поиска нужных слов в тексте. Редактирование текста (шрифт, размер). Алгоритм поиска подстроки в строке (метод Кнута-Морриса-Пратта). Загрузка текста из файла (с расширением.txt).

курсовая работа , добавлен 29.05.2013

Поиск в массивах и списках, ключ и произвольные данные. Линейный (последовательный) поиск. Бинарный поиск в упорядоченном массиве. Алгоритм Рабина-Карпа, простая и улучшенная хэш-функция. Алгоритм Бойера-Мура со сдвигом по стоп-символам и по суффиксам.

презентация , добавлен 19.10.2014

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

контрольная работа , добавлен 25.03.2013

Изучение определения, описания и вызова функций, указателей и ссылок на них. Написание функции умножения произвольного столбца двумерного массива на const. Умножение 2 столбцов массива на константы. Составление блок-схемы алгоритма и текста программы.

лабораторная работа , добавлен 09.01.2012

Основные свойства алгоритма. Формальный и неформальный исполнитель алгоритма, система его команд. Способы записи алгоритма. Словесное описание, построчная запись, опорный конспект. Характеристики алгоритмического языка. Выполнение алгоритма компьютером.

презентация , добавлен 04.04.2014

Теоретические и практические аспекты решения прикладных задач с применением функций и процедур структурного (модульного) программирования. Особенности разработки схемы алгоритма и программы для вычисления массива z на языке Turbo Pascal 7.0, их описание.

курсовая работа , добавлен 11.12.2009

Характеристика особливостей реалізації пошуку по масиву методами лінійним, бінарним, по "дереву Фібоначе" та екстраполярним на мові програмування Turbo Pascal. Використання алгоритма Рабіна-Карпа та Кнута-Морріса-Пратта для знаходження підрядка в рядку.

курсовая работа , добавлен 16.09.2010

Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов.

лабораторная работа , добавлен 03.12.2014

Разработка на языке ассемблера алгоритма контроля, на циклический CRC-код, массива данных хранящегося в некоторой области памяти. Сохранение кода для последующей периодической проверки массива данных. Сообщение об искажении данных. Описание алгоритма.

Аннотация: Предмет науки программирования. Пример и свойства алгоритма. Парадигмы программирования (директивное, объектно-ориентированное и функционально-логическое программирование).

Эта глава, с которой начинается изучение курса, служит двум основным целям:

подготовить необходимую теоретическую базу для последующего овладения различными методами обработки информации, навыками программирования в малом и построения правильных эффективных программ;
дать минимально необходимые для практического программирования знания о языке Java и предоставить образцы небольших типовых программ.

В процессе знакомства с теоретическим материалом главы может возникнуть ощущение его оторванности от нужд практики - решения конкретных задач на языке Java. С другой стороны, именно решение задач на программирование должно привести к осознанному пониманию того факта, что написать правильную и эффективную программу совсем не так просто, как это кажется на первый взгляд.

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

И последнее замечание - чисто технологическое. На первой стадии изучения языка Java полезно отвлечься от того факта, что он является объектно-ориентированным, и сосредоточиться на содержательных проблемах корректной реализации алгоритма. Однако это не так просто сделать - написание даже самой простейшей программы на нем невозможно без понимания основных концепций ООП. Для частичного решения этой проблемы используется созданный специально для этих целей класс Xterm , ограждающий начинающего программиста от сложностей реального мира языка Java.

Предмет науки программирования

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

Этот пример вполне объясняет, почему описания последовательности действий, предназначенные для автоматического устройства, должны быть совершенно однозначны и заданы с помощью некоторой формальной системы обозначений. Очень часто создание таких описаний связано со значительными техническими и принципиальными трудностями. Данная проблема стала чрезвычайно актуальной в связи с повсеместным распространением электронных вычислительных машин (ЭВМ), часто используемых в качестве .

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

Наука программирования (computer science) занимается исследованием свойств алгоритмов и разработкой методов построения программ. По своему положению и используемым методам она является областью прикладной математики. Все попытки подхода к программированию как к технической дисциплине, а к созданию программ как к промышленному производству, неизменно терпели неудачу.

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

Подход, когда некоторое не до конца четко определенное понятие активно используют, в науке весьма типичен. Например, точные определения натуральных и действительных чисел не рассматривают ни только в средней школе, но даже и в большинстве ВУЗов. Более того, говорят, что сороконожка даже ходить разучилась, когда задумалась над тем, в каком порядке она переставляет ноги.

Пример и свойства алгоритма

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

Задача 1.1 . Придумайте алгоритм, вводящий натуральное число, большее единицы,который находит наименьший простой делитель этого числа.

Алгоритм решения задачи .

Алгоритм П :

П1 : Положить целое число равным двум и перейти на шаг П2.

П2 : Если делится нацело на , то завершить работу алгоритма, выдав в качестве результата ; иначе перейти на шаг П3.

П3 : Увеличить значение на единицу и перейти на шаг П2.

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

k = 3	k = 4	k = 2
П1: i = 2	П1: i = 2	П1: i = 2
П2: i = 2	П2: i = 2	П2: i = 2
П3: i = 3
П2: i = 3

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

Основные свойства любого алгоритма - это конечность, определенность, вход (ввод), выход (вывод) и эффективность. Рассмотрим их последовательно более подробно.

Конечность . Алгоритм должен всегда заканчиваться после выполнения конечного числа шагов. Алгоритм П удовлетворяет этому условию, так как величина вначале меньше , ее значение увеличивается на единицу к каждому очередному выполнению шага П2, и поэтому выполнение алгоритма будет прекращено на шаге П2 при , если - простое число, или ранее при составном .

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

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

Вход (input) . Алгоритм всегда имеет некоторое (иногда равное нулю) количество входных данных, то есть величин, передаваемых ему до начала работы. В алгоритме П, например, одна входная величина - целое число , большее единицы. Примером алгоритма, имеющего пустое множество входных данных, может служить алгоритм, вычисляющий 1000-е простое число.

Выход (output) . Алгоритм всегда обязан иметь одну или несколько выходных величин. В случае алгоритма П такой величиной является число . Алгоритмы, не имеющие выходных данных, бесполезны на практике, и мы не будем их изучать.

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

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

Из вышесказанного следует, что на ЭВМ практически невозможно работать с действительными числами , что, по всей видимости, может показаться вам неправдоподобным. На самом деле это так. Более того, даже с настоящими целыми числами на компьютере работают не так уж и часто. Обычно вместо множеств целых и действительных чисел приходится работать с их заменителями