В. Ю. Наумов Введение в информатику
 Скачать 2.05 Mb.
|
|
Каналы ввода/вывода – устройства, через которые производится обмен данными с периферийными устройствами. Жесткий диск – внешнее запоминающее устройство, служащее для долгосрочного хранения информации. При выключении питания ЭВМ информация на нем не теряется и может быть в дальнейшем многократно использована. По-английски жесткий диск называют HDD (Hard Diskette Driver). Жесткий диск – самый главный носитель информации в системе. На нем хранятся все программы и данные, которые в настоящий момент не Процессор Внутренняя память Информационная магистраль ( шина данных + адресная шина + шина управления) Периферийные устройства ( монитор, дисковод, клавиатура, принтер, мышь, сканер, модем и т.д.) Каналы ввода/вывода Рис. 1.4. Магистрально-модульный принцип построения компьютера 26 находятся в оперативной памяти. Накопитель на жестких дисках часто просто называется жестким диском, так как он состоит из вращающихся алюминиевых или керамических пластин, покрытых слоем ферро- магнетика. Размеры винчестеров могут быть разные. Емкость памяти дисковода жестких дисков зависит от плотности, размеров и количества пластин. В большинстве настольных компьютеров сегодня используются дисководы с жесткими дисками, рассчитанными на формфактор 3,5”, в то время как в большинстве портативных компьютеров (в лэптопах и ноутбуках) используются жесткие диски с формфактором 2,5” и даже 1”. Накопители на жестких дисках обычно называют винчестерами. Этот термин появился в 60-е годы ХХ века, когда фирма IBM выпустила высокоскоростной накопитель с одним несъемным и одним сменным дисками емкостью по 30 Мбайт. Этот накопитель состоял из пластин, которые вращались с высокой скоростью, и «парящих» над ними головок, а номер его разработки – 30-30. Такое цифровое обозначение (30-30) совпало с обозначением популярного нарезного оружия Winchester, поэтому сам термин вскоре стал применяться в отношении любого стационарно закрепленного жесткого диска. Сегодня имеется тенденция назвать винчестером любое внутреннее устройство долговременного хранения больших объемов информации. Последние модели вообще являются полностью твердотельными (полупроводниковыми) и не имеют в своем составе механических подвижных частей. Монитор – устройство для отображения визуальной информации. В большинстве систем монитор помещен в собственный корпус, отдельно от системного блока. В портативных компьютерах монитор встраивается в корпус системного блока компьютера. Мониторы обычно классифицируются по трем параметрам: размеру диагонали (в дюймах), разрешающей способности (в пикселях) и частоте регенерации 27 изображения в герцах (Гц). Разрешающая способность – от 640х480 (сначала указывается размер по горизонтали, а затем – по вертикали) до 1600х1200 пикселей, а последнее время и больше. Каждый пиксель в мониторе состоит из трех элементов-точек, по одной для каждого цвета – красного, синего и зеленого. Средний монитор способен регенерировать изображение 60−100 раз в с. (частота 60−100 Гц), в то время как частота регенерации в более качественных мониторах превосходит эти значения. Частота регенерации показывает, как часто дисплей повторно отображает на экране содержимое видеопамяти. Сегодня мониторы на электронно- лучевых трубках становятся частью истории. В пришедших им на смену ЖК-панелях (LCD – Liquid Crystal Display – дисплей на жидких кристаллах) частота регенерации изображения уже не играет такой роли как раньше 8 , поскольку физические принципы его формирования несколько иные. К динамическим характеристикам можно отнести время переключения пикселя из одного состояния в другое. Кроме этого, существует еще масса разных характеристик, влияющих на качество отображаемой монитором информации. 8 Частота регенерации ЭЛТ-мониторов и утомляемость глаз находятся в тесной зависимости, поскольку при частотах меньших, либо равных 60 Гц, глаз ощущает мерцание, что является негативным раздражающим фактором для нервной системы. Особенно чувствительно к динамике периферическое зрение. Ради интереса можете выставить 60 Гц на ЭЛТ-мониторе и направить взгляд чуть выше. Такие физиологические особенности являются следствием эволюционного развития зрения человека, поскольку помогают быстрее реагировать на опасность. Чтобы не было «страшно», рекомендуется ставить частоту развертки в 100 Гц и выше. 28 2. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ. АЛГОРИТМИЗАЦИЯ. ЛОГИКА 2.1. Этапы решения задач на ЭВМ При решении любой задачи с использованием ЭВМ принято выделять восемь основных этапов: 1. Постановка задачи. На этом этапе определяются цели, кото- рые необходимо достичь. Уточняются начальные (граничные) условия. За- дача делится на несколько подзадач. Из них выделяются те, которые необ- ходимо решать численно (на ЭВМ) и те, которые невозможно или нерационально решать с использованием вычислительной машины. 2. Построение математической модели. Определяются анали- тические зависимости различных факторов, влияющих друг на друга, т. е. записываются различные уравнения, как логические (равенства, неравен- ства, в том числе с использованием логических операций), так и алгебраи- ческие. 3. Анализ и оптимизация математической модели. На этом этапе математическая модель приводится к такому виду, который позволя- ет увеличить скорость расчета при заданной точности. 4. Разработка алгоритма. С использованием полученной мате- матической модели строится вычислительный алгоритм. На данном этапе обычно используют один из домашинных способов его описания. 5. Программирование. Полученный алгоритм записывается на одном из машинных языков программирования (Pascal, Delphi, C, C++, C#, Fortran, BASIC, Assembler, Java, Lisp, Python и т. д.). 6. Отладка программы. Даже самый опытный программист в процессе написания более или менее сложной программы допускает ошибки. Если это синтаксические ошибки, то, например, как это происхо- 29 дит в IDE Microsoft Visual Studio, компилятор сам укажет на них. Но часто возникают и алгоритмические ошибки, например, неверная последова- тельность вычислительных шагов или использование не той функции, ко- торая необходима. Такие ошибки не видны сразу. Для того чтобы выявить их, необходимо подать на вход тестирующий набор данных и независимо (без использования полученного алгоритма) получить набор выходных данных, например, на калькуляторе. Полученные таким образом выходные данные можно считать эталонными. Если они совпадают с выходными данными, полученными с использованием тестируемого алгоритма, то он работает верно, и программа с определенной степенью вероятности счита- ется отлаженной. Совокупность тестирующих входных и эталонных вы- ходных данных называют тестовым или проверочным примером. Для все- объемлющей проверки программы необходимо подготовить такое количество тестовых примеров, которое позволит проверить все ветви те- стируемого алгоритма (с учетом всех развилок и циклов). 7. Использование программы для получения выходных данных. Решая поставленную задачу, мы преследуем определенную цель – получе- ние некоторого набора (наборов) выходных данных. На данном этапе эта цель достигается, т. е. проводятся расчеты с использованием полученной программы. 8. Интерпретация результатов. На этом этапе результаты ре- шения различных подзадач собираются воедино, из них формируется все- объемлющий ответ на поставленную задачу и проводится анализ всего ре- шения в целом. Вероятно обнаружение некоторых новых закономерностей или глобальных ошибок, в результате чего возможно повторение каких- либо этапов с учетом полученных уточнений. 30 2.2. Алгоритмизация Алгоритм – это строго заданная последовательность шагов, в результате исполнения которых набор входных данных преобразуется в набор результатов решения задач (выходных данных). Другими словами, алгоритм можно определить как метод или механизм, который предписывает, каким образом можно достичь поставленной цели. Слово «algorithm» произошло от имени аль-Хорезми 9 – автора известного арабского учебника по математике (от его имени также произошли слова алгебра и логарифм). Алгоритм следует отличать от некого эвристического правила. Эвристическое правило лишь предлагает, каким образом можно достигнуть цели, но не дает четкой последовательности действий. Например, задача найти дискриминант, чтобы выделить корни квадратного уравнения, является эвристическим правилом для компьютера. Если мы хотим, чтобы она была решена, нужно составить подробную последовательность действий, понятных тому устройству, которое будет ее решать. Таким образом, эвристическим правилом можно назвать некий недетализированный алгоритм, или алгоритм, составленный на языке непонятном машине, которая будет решать нашу задачу. Классический алгоритм обладает рядом свойств: 1) дискретность. В один момент времени может выполняться лишь один вычислительный шаг. Одновременное выполнение двух и более шагов невозможно; 2) детерминизм. Постоянство результатов при постоянстве входных значений. Обрабатывая несколько раз один и тот же набор вход- 9 Мухаммед бен Муса аль-Хорезми (787 – ок. 850) – среднеазиатский ученый, чьи основополагающие труды по арифметике и алгебре оказали большое влияние на развитие математики в Западной Европе. 31 ных данных, алгоритм каждый раз должен получать один и тот же набор выходных данных. Но стоит отметить, что этим свойством может не обла- дать алгоритм, использующий так называемый генератор случайных чисел (например, выбор числа из квазислучайной последовательности); 3) элементарность каждого вычислительного шага. Каждый шаг алгоритма должен быть наипростейшим, т. е. его нельзя разделить на более мелкие шаги; 4) массовость. Алгоритм должен быть универсален на опреде- ленном классе задач. Например, алгоритм решения квадратного уравнения должен выдавать результат при решении любого квадратного уравнения, но он не применим при решении дифференциальных урав-нений; 5) конечность. Работа любого вычислительного алгоритма должна быть завершена в обозримое время. К примеру, алгоритм не счита- ется конечным, если результат может быть получен за промежуток време- ни, сравнимый с возрастом вселенной. Это требование весьма условно, по- скольку не всегда удается оценить примерное время работы алгоритма. Более того, бывают принципиально бесконечные алгоритмы, как, напри- мер, алгоритм поиска всех простых чисел. Существует два основных класса способов описания алгоритма: домашинные и машинные. Выделяют пару наиболее часто используемых домашинных способов: описание с помощью естественного языка (например, русского) и с помощью блок-схем. Машинный способ – описание алгоритма на одном из языков программирования (программа). Промежуточным вариантом между машинным и естественным способом задания алгоритма могут считаться так называемые R-схемы или 32 синтаксические диаграммы, предложенные Н. Виртом 10 для описания синтаксиса создаваемого им языка программирования Pascal. Естественный язык используется для описания, например, алгоритмов приготовления кулинарных блюд (рецепт), действий рабочих в тех или иных ситуациях на производстве (инструкции), решения квадратного уравнения в математике и т. д. Преимущество данного способа только в том, что для описания алгоритма нет необходимости в каких-то специальных знаниях (специальные обозначения, условные слова и т. д.), но есть ряд существенных недостатков, таких как отсутствие наглядности и проблемы восприятия при чтении более или менее сложных алгоритмов, описанных этим способом. ПРИМЕР Рассмотрим пример описания алгоритма решения квадратного уравнения с помощью естественного языка. Уравнение имеет вид: 2 0 ax bx c Алгоритм решения квадратного уравнения, описанный с помощью естественного языка: 1) задать значения коэффициентов , , a b c ; 2) если 0 a , то выполнять шаг 8; 3) вычислить дискриминант 2 4 D b ac ; 4) если 0 D , то выполнять шаг 17; 5) вычислить действительные корни 1 2 , 2 2 b D b D x x a a ; 6) распечатать значения 1 2 , x x ; 10 Никлаус Вирт (р. 1934) – швейцарский ученый, ведущий специалист в области информатики. Один из родоначальников структурного программирования. Создатель языков программирования Pascal, Modula-2, Oberon. 33 7) выполнить шаг 18; 8) если 0 b , то выполнить шаг 12; 9) вычислить действительный корень c x b ; 10) распечатать значение x ; 11) выполнить шаг 18; 12) если 0 c , то выполнить шаг 15; 13) распечатать комментарий « 0, 0, 0 a b c , , решений нет»; 14) выполнить шаг 18; 15) распечатать комментарий « 0, 0, 0 a b c , , «существует бесконечное множество решений»; 16) выполнить шаг 18; 17) распечатать комментарий «действительных корней не существует»; 18) окончание алгоритма. Описание алгоритмов с помощью блок-схем основано на графическом представлении последовательности действий. Для этого используют ряд специальных обозначений – блоков, – которых существует достаточно много. Вообще, программирование относится к инженерной деятельности и потому совершенно естественным является тот факт, что правила составления программной документации регламентированы. Для этого существует целый ряд ГОСТов, которые называются ЕСПД (Единая система программной документации): ГОСТ 19.002–80, ГОСТ 19.003–80; ГОСТ 19.701–90. Ради упрощения решения задач построения блок-схем здесь приводится ограниченный набор обозначений (табл. 2.1). 34 Таблица 2.1 Условные графические обозначения блок-схем Графическое обозначение Название и предназначение Блок начала и конца алгоритма (терминатор) Является точкой рождения и уничтожения потока Блок ввода/вывода В этом блоке отражаются все диалоги с поль- зователем (когда у него нужно что-либо спросить или что-нибудь ему показать) Блок обработки данных Различные действия, скрытые от глаз пользователя Блок логического выражения (предикатный узел) Здесь записывается проверяемый предикат Блок модификации Используется для описания заголовка цикла с параметром Блок вызова подпрограммы Описывает сложный предопределенный процесс, описание которого содержится в том же документе, где он встречается Точки соединения Точки разрыва и сочленения поточных линий Направление выполнения вычислительных шагов (поточные линии) Показывают направление алгоритмического про- цессса Межстраничный переход Внутри записывается номер перехода и направление (номер страницы, на которую или с которой осу- ществляется переход) Комментарии Пояснения к отдельным блокам или группам блоков 2.3. Понятие переменной и операции присваивания Выше в примере алгоритма решения квадратного уравнения проводились некоторые вычисления, результаты которых обозначались букво-цифросочетаниями латинского алфавита. Это так называемые 35 переменные. Вообще, понятие переменной – одно из ключевых в теории алгоритмизации, особенно в случае вычислительных процессов. Переменная – именованная область памяти, способная хранить некоторые данные. При этом возможно обращение к ней по ее имени для чтения или модификации содержимого. Переменным следует давать осмысленные имена, а не обозначать их безликими буквами или непонятным набором символов. Если, например, нужно найти максимум, то и переменной, хранящей его значение, нужно дать имя Max. Если это греческая буква, то и ее можно обозначить таким образом, чтобы имелось фонетическое сходство с оригиналом (Alfa, Beta, Fi и т. д.) Понятие переменной дано; однако есть еще одно понятие программирования, тесно связанное с понятием переменной – понятие операции присваивания. Операция присваивания – операция прямой модификации содержимого переменной. Поскольку это операция, то у нее существуют операнды. Присваивание – операция с двумя операндами. Слева записывается имя переменной, которую подвергают модификации, а справа - выражение, результат которого будет перемещен в область памяти, хранящей содержимое переменной слева. Операция присваивания всегда происходит справа налево. То есть, вначале вычисляется выражение, стоящее справа, и лишь после этого происходит перемещение результата вычисления в переменную слева. На блок-схемах операции присваивания обычно обозначают знаком «=» или «:=». В этой книге принято обозначение «=», т.е. так как в языке С. В разных языках программирования присвоение записывается по- разному. Наиболее распространенными являются записи «=» и «:=». В некоторых ассемблерах операция присвоения вообще может иметь несколько различных модификаций, записанных в виде процессорных инструкций, например, |