учебное пособие. Часть1. Информатика
.pdfМультимедийные функции (multimedia functions) – цифровая фильтрация и масштабирование видео, аппаратная цифровая компрессия (сжатие) и декомпрессия (развертка) видео, ускорение графических операций, связанных с трехмерной графикой (3D), поддержка живого видео на мониторе, наличие композитного видеовыхода, вывод TV–сигнала (телевизионного) на монитор.
Общая шина (bus topology, common bus) –топология сети, при которой ее узлы подключены к общему линейному информационному каналу.
Пакет (packet) – часть сообщения, удовлетворяющая некоторому стандарту, последовательность битов, содержащая данные и сигналы управления, передаваемые и коммутируемая как одно целое.
Пакетная технология (packet technology) –обработка данных или выполнение заданий, накопленных заранее, таким образом, что они объединяются в пакет и затем обрабатываются. При этом пользователь не может влиять на обработку, пока она продолжается.
Пиктограмма (icon) – условное изображение информационного объекта или операции.
Платформа (platform) – тип процессора и ОС, на которых можно установить новый программный продукт.
Пользовательский интерфейс (user interface) – набор приемов взаимодействия пользователя с приложением.
Порт (port) – многоразрядный вход или выход в устройстве. Почтовый ящик (mail box) – специально организованный файл для
хранения корреспонденции.
Почтовый сервер (mail server) – ЭВМ в роли сетевого почтового отделения, которое получает, хранит и пересылает сообщения дальше по сети.
Приложение (application) – совокупность программ, реализующих обработку данных в определенной области применения.
Разделение времени (time sharing) – режим работы, при котором процессорное время предоставляется различным приложениям последовательно квантами. По истечении кванта времени приложение возвращается в очередь ожидания обслуживания.
Растр (raster) – множество точечных элементов, с помощью которых знак фиксируется на бумажном носителе или отображается на экране дисплея.
Сервер (server) – любая ЭВМ, выполняющая определенные функции обслуживания пользователей. В сетях сервер управляет использованием распределенных ресурсов: баз данных, внешней памяти, принтеров и др.
Сервер базы данных (database server) –содержит базу данных, сетевую операционную систему, сетевую СУБД для обеспечения многопользовательских запросов.
Сетевая операционная система (network operational system) – система,
осуществляющая реализацию протоколов с реализацией управления серверами.
141
Сетевой сервер (network server) – поддерживает выполнение функций сетевой операционной системы: управление сетью, планирование задач, распределение ресурсов, доступ к сетевой файловой системе, защита информации.
Сортировка (sorting) – распределение упорядоченных данных по возрастанию или убыванию значений признака сортировки; упорядочение записей файла по одному или нескольким ключам.
Тезаурус гипертекста (hypertext thesaurus) – автоматизированный словарь, отображающий семантические отношения между лексическими единицами дескрипторного информационно–поискового языка и предназначенный для поиска слов по их смысловому содержанию.
Технологический процесс (technological process) – упорядоченная последовательность взаимосвязанных операций по сбору, передаче, накоплению, хранению, обработке, анализу, отображению и размножению информации.
Трафик (traffic) – поток сообщений в сети передачи данных. Уровень сети (network level) – совокупность станций одинакового
ранга, входящих в одну и ту же иерархическую сеть.
Шлюз (gateway) – устройство соединения сети с другими сетями, например, ЛВС с глобальной сетью.
Экспертная система (expert system) – система искусственного интеллекта, включающая базу знаний с набором правил и механизмом вывода, позволяющим на основании правил и предоставляемых пользователем фактов распознать ситуацию, поставить диагноз, сформулировать решение или дать рекомендацию для выбора действия.
Электронная почта (electronic mail) – система хранения и пересылки сообщений между пользователями сети ЭВМ.
Электронный офис (electronic office) – интегрированный ППП,
включающий предметные программы и ИТ, обеспечивающие реализацию задач предметной области.
HTML (Hypertext Markup Language) –язык гипертекстовой развертки,
используемый для создания документов, содержащих специальные команды форматирования и гипертекстовые ссылки и предназначенных для размещения в система WWW.
HTTP (Hypertext Transfer Protocol) – протокол передачи гипертекста,
служащий для установления связи с документами HTML независимо от его местонахождения с помощью указателей URL.
Host–ЭВМ – ЭВМ, установленная в узлах сети и решающая вопросы коммутации сети, доступа к сетевым ресурсам: модемам, факс–модема, большим ЭВМ и др.; главная, ведущая, центральная ЭВМ.
Hub – концентратор, хаб. Устройство, обеспечивающее преобразование передаваемых сигналов таким образом, что сеть может быть дополнена новыми рабочими станциями.
142
OLE–технология (Object Linked and Embedding) – технология,
позволяющая вставлять ранее созданные объекты (рисунки, графики, таблицы) во вновь создаваемые.
SILK (Spech Image Language Knowledge) –интерфейс, обеспечивающий перемещение на экране по речевой команде от одних поисковых образов к другим по смысловым (семантическим) связям.
SMTP (Simple Management Transfer Protocol) – упрощенный протокол передачи почтовых сообщений системами электронной почты.
SQL (Structured Query Language) специализированный язык структурированных запросов, используемый при организации запросов, обновлении и управлении реляционными базами данных.
SQL–сервер – сервер.
TCP/IP (Transmission Control Protocol / Internet Protocol) – протокол управления передачей сообщений /межсетевой протокол, охватывающий средства доступа к среде, средства транспортировки пакетов, сеансовые коммуникационные средства, средства передачи файлов, средства электронной почты и средства терминальной эмуляции.
URL (Uniform Resource Locator) – универсальный локатор ресурсов, характеризующий полный путь к конкретному документу или разделу на компьютере, подключенном к сети Internet, а также метод доступа к нему, т.е. протокол работы с программами–серверами, функционирующими на удаленном компьютере.
UUCP (Unix–to–Unix–Copy–Programm) –программное обеспечение,
облегчающее передачу информации в сети между Unix–системами, использующими последовательные соединения, прежде всего обычную телефонную сеть.
WIMP (Windows Image Menu Pointer) –интерфейс, обеспечивающий размещение на экране окон, содержащих образы программ и меню действий.
Web page – Web–страница в системе WWW. Web server – Web–сервер системы WWW.
WWW (World Wide Web) – глобальная сетевая система, объединяющая серверы Internet, «всемирная паутина».
143
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1.Информатика: Базовый курс / Под ред. С.В. Симоновича. – СПб.:
Питер, 2002. – 640 с.
2.Королёв Л.Н., Миков А.И. Информатика. Введение в компьютерные науки. – М.: Высшая школа, 2003. – 341 с.
3.Острейковский В.А. Информатика. – М.: Высшая школа, 2004. –
511 с.
4.Информатика: Учебное пособие для студентов пед. вузов / Под ред. Е.К. Хеннера. – М.: Изд. центр “Академия”, 2001. – 816 с.
5.Абрамов В.А., Белянина О.Н., Венедиктов М.Д. Аудиоинфор– матика в вопросах и задачах. – М.: МТУСИ, 2002. – 28 с.
6.Петраков А.В. Основы практической защиты информации. – М.: Радио и связь, 1999. – 368 с.
7.Самойлов А.Г., Самойлов С.А. Информатика: Учеб. пособие / Владим. гос. ун–т – Владимир, 2004. – 133 с.
8.Вигдорчик Г.В., Воробьев А.Ю., Праченко В.Д. Основы программирования на
9.ассемблере для СМ ЭВМ. – М.: Финансы и статистика, 1987.
10.Вирт Н. Алгоритмы и структура данных. – М.: Мир, 1989.
11.Власов В.К., Королев Л.Н., Сотников А.Н. Элементы информатики /Под ред.
12.Л.Н.Королева. – М.: Наука, Гл. ред. физ. мат. лит., 1988.
13. Вопросы прикладной информатики (сборник научных трудов) /Под ред.
14.P.M. Юсупова. –С.–Петербург: СПИИРАН, 1993.
15.Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.:
16.Мир, 1981.
17.Информатика. Энциклопедический словарь для начинающих. – М.: Педагогика–Пресс, 1994.
18.Кричевский Р.Е. Сжатие и поиск информации. – М.: Радио и
связь, 1989.
19.Лихачева Г.Н. Информационные технологии в экономике. – М.:
МЭСИ, 1998.
20.Мейер Б., Бодуэн К. Методы программирования. – М.: Мир, 1982.
21.Нардюжев В.И. Лабораторный практикум по курсу «Информатика и основы
22.работы на персональном компьютере». – Обнинск: Обнинский институт атомной энергетики, 1996.
23.Першиков В.И., Савинков В.М. Толковый словарь по информатике. – М.: Финансы и статистика, 1991.
24.Словарь по кибернетике / Под ред. B.C. Михалевича. – 2–е изд. –
Киев.: Гл.
144
25.ред. УСЭ им. Бажана, 1989.
26.Экономическая информатика и вычислительная техника /Под. ред. В.П. Ко–
27.сырева, А.Ю. Королева. – М.: Финансы и статистика, 1996.
28.Электронные вычислительные машины. В 8 кн. Кн.2. Основы информатики
29./ Под. ред. А.Я.Савельева. – М.: Высшая школа, 1991.
145
Вторая часть пособия посвящена изучению основ программирования. Формирование алгоритмического мышления является одной из важ-
нейших составляющих информационной культуры и главной задачей курса информатики.
Технология решения задач на ЭВМ – это не только и не столько коди- рование программы и получение загрузочного модуля, но и проектирование математической модели, составление алгоритма и доказательство правильно- сти программы. В этой части детально описано, как надо программировать: как разрабатывать программу, как ее кодировать, как тестировать, какие средства выбирать.
Компьютерные эксперименты позволяют проверить работоспособность алгоритма, таким образом, способствуя развитию алгоритмического мышле- ния.
Реализация алгоритмических конструкций демонстрируется на класси- ческом языке программирования высокого уровня C++, который, несмотря на появление все новых технологий, на сегодняшний день остается одним из самых распространенных языков программирования.
ВВЕДЕНИЕ
Язык С давно завоевал особую популярность у программистов благо-
даря уникальному сочетанию возможностей языков высокого и низкого уровней. Язык С разработан в 1972 г. Д. Ритчи во время работы над операци- онной системой Unix. Изначально предполагалось, что этот язык будет ис- пользоваться профессиональными программистами. Но со временем, благо- даря гибкости и лаконичности, язык С стал использоваться для решения ши- рокого круга задач. Главное преимущество языка С заключается в библиоте- ках, поддерживаемых компилятором, и библиотеках, создаваемых програм- мистами.
Знаменательной вехой в эволюции языка С стало появление системы Турбо С, получившей признание как одно из самых удачных инструменталь- ных средств для персональных компьютеров. Язык С называют скромным, быстрым, удобным. Иногда его называют вероломным [1], потому как про- граммы на С беззащитны для класса ошибок, от которых другие языки за- щищают. На такие ошибки в пособии обращается особое внимание. Язык С − относительно мобильный язык. Программы, написанные на этом языке для одной операционной системы, с небольшими доработками могут использо- ваться в другой операционной системе.
На основе языка программирования С был разработан Бьерном Страу- струпом язык С++, который с небольшими изменениями сохраняет С как
146
подмножество. Сначала язык С++ назывался "язык Си с классами" и, в об- щем-то С становится С++ с введением объектно-ориентированного програм- мирования.
Для того чтобы хорошо овладеть программированием, необходимо знать, устройство компьютера. Слово "компьютер" означает "вычислитель", т. е. устройство для вычислений. Потребность в автоматизации обработки данных, в том числе вычислений, возникла очень давно. Многие тысячи лет назад для счета применялись счетные палочки, камешки и т.д. В дальнейшем стали использовать счеты. В 1642 г. Блез Паскаль разработал устройство, ме- ханически выполняющее сложение чисел, а в 1673 г. Готфрид Вильгельм Лейбниц сконструировал арифмометр, позволяющий механически выполнять четыре арифметических действия. В XIX в. математик Чарльз Беббидж по- пытался построить вычислительное устройство, которое должно было вы- полнять вычисления без участия человека, т. е. уметь исполнять программы. Но осуществить эту мечту удалось ученым только в ХХ в., когда для по- строения вычислительных устройств начали использовать электромеханиче- ские реле. С 1943 г. группа специалистов под руководством Джона Мочли и
Преспера Экерта в США начала конструировать вычислительную машину на основе электронных ламп. Машина работала достаточно быстро, но для зада- ния её программы приходилось в течение нескольких часов или даже не- скольких дней соединять провода. Вот тогда и стали конструировать маши- ну, которая могла бы хранить программу в своей памяти. К этой работе был привлечен знаменитый математик Джон фон Нейман, который ясно и просто сформулировал основные принципы функционирования универсальных вы- числительных устройств. Первый компьютер, в котором воплощены принци- пы фон Неймана, был построен в 1949 г. английским исследователем Мори- сом Уилксом. С той поры компьютеры стали гораздо более мощными, но по-
давляющее большинство из них работает в соответствии с принципами фон Неймана [2]. Согласно принципам фон Неймана компьютер должен иметь следующие устройства (рис.1):
•процессор, осуществляющий арифметические и логические опера- ции, а также организующий процесс выполнения программ;
•запоминающее устройство, или память для хранения программ и дан-
ных;
• внешние (периферийные) устройства для ввода/вывода информации.
Память должна состоять из некоторого количества пронумерованных ячеек, в каждой из которых могут находиться или обрабатываемые данные, или инструкции программ. Все ячейки памяти должны быть одинаково дос- тупны для других устройств компьютера.
На рис. 1 одинарные линии показывают управляющие связи, двойные – информационные.
147
ПАМЯТЬ
ПРОЦЕССОР
ПЕРИФЕРИЙНЫЕ
УСТРОЙСТВА
Рис. 1. Структура ЭВМ
В общих чертах работу компьютера можно описать так. Вначале с по- мощью какого-либо периферийного устройства в память компьютера вводит- ся программа. Процессор считывает содержимое ячейки памяти, где нахо- дится первая инструкция (команда) программы, и организует её выполнение.
Эта команда может задавать выполнение арифметических или логических операций, чтение из памяти данных для выполнения арифметических или ло- гических операций или запись их результатов в память, ввод данных из внешнего устройства в память или вывод данных из памяти на внешнее уст- ройство.
Как правило, после выполнения одной команды процессор начинает обрабатывать команду из ячейки памяти, которая находится непосредственно за только что выполненной командой. Однако этот порядок может быть из- менен с помощью команд управления (перехода). Эти команды указывают процессору, что ему следует продолжить выполнение программы, начиная с команды, содержащейся в некоторой другой ячейке памяти. Такой "скачок", или переход, осуществляется в программе не всегда, а только при соблюде- нии некоторых условий. Например, если некоторые числа равны, если в ре- зультате предыдущей арифметической операции получился нуль. Это позво-
ляет использовать одни и те же последовательности команд в программе много раз (организовывать циклы), выполнять различные последовательно- сти команд в зависимости от соблюдения определенных условий и т.д., од- ним словом, создавать сложные программы.
Таким образом, процессор выполняет инструкции программы автома- тически, без вмешательства человека. Он может обмениваться информацией с памятью и внешними устройствами компьютера. Поскольку внешние уст- ройства, как правило, работают значительно медленнее, чем остальные части
148
компьютера, процессор может приостанавливать выполнение программы до завершения операции ввода-вывода с внешним устройством. Все результаты
выполненной программы должны быть ею выведены на внешние устройства компьютера, после чего компьютер переходит к ожиданию каких-либо сиг- налов внешних устройств.
Современный компьютер – это не просто вычислительное устройство, а целая вычислительная система – совокупность аппаратных и программных средств, обеспечивающих выполнение возложенных на систему функций.
Многие современные быстродействующие компьютеры осуществляют параллельную обработку данных на нескольких процессорах одновременно, обрабатывают прерывания от внешних устройств, тем не менее, в основных чертах соответствуют принципам фон Неймана.
Совокупность программных средств можно разделить на три кате- гории [2]:
•прикладные программы, непосредственно обеспечивающие выпол- нение необходимых пользователям работ: редактирование текстов, рисова- ние картинок, обработка информационных массивов и т. д.;
•системные программы, к которым в первую очередь следует отнести операционные системы, и программы, выполняющие различные вспомога- тельные функции, например, создание копий используемой информации, вы- дача справочной информации о компьютере, проверка работоспособности устройств компьютера, обеспечивающие диалог с пользователем и т.д.;
•инструментальные системы (системы программирования), обеспечи- вающие создание новых программ для компьютера.
Одной из важнейших системных программ является операционная сис- тема. Операционная система – это программа, которая загружается при включении компьютера. Она осуществляет диалог с пользователем, управле- ние компьютером, его ресурсами (оперативной памятью, местом на дисках и т. д.), запускает другие (прикладные) программы на выполнение. Операцион-
ная система обеспечивает пользователю и прикладным программам удобный способ общения (интерфейс) с устройствами компьютера. Для компьютеров
типа IBM PC чаще всего используется операционная система MS DOS, Unix, OS/2, Windows.
Важным классом системных программ являются программы-драйверы. Они расширяют возможности DOS по управлению устройствами ввода- вывода электронной вычислительной машины (ЭВМ) (клавиатурой, жестким диском, мышью и т. д.). С помощью драйверов можно подключать к компью- теру новые устройства или нестандартно использовать имеющиеся устройст- ва.
Интегрированная среда С++ относится к инструментальным системам и включает в себя как язык программирования, так и среду, предназначенную для редактирования, отладки и запуска программ.
149
1. ЭТАПЫ РЕШЕНИЯ ЗАДАЧИ НА ЭВМ
Так как ЭВМ является "слепым" исполнителем программ, то успешное решение задачи полностью определяется квалификацией программиста.
В общем случае решение задачи на ЭВМ можно разбить на следующие эта-
пы:
•постановка задачи;
•разработка алгоритма;
•составление программы;
•трансляция программы;
•отладка и выполнение программы;
•анализ результатов.
Постановка задачи является самым важным этапом. От того, насколько правильно поставлена задача, зависит весь дальнейший ход ее решения. На этом этапе определяются все входные данные, основные выполняемые функ- ции и выходные данные (результаты).
Слово "алгоритм" произошло от имени узбекского математика Аль Хо- резми, который в IX в. разработал правила четырех арифметических дейст- вий над числами в десятичной системе счисления. Примерами алгоритмов могут служить врачебные и кулинарные рецепты, способы решения квадрат- ных и дифференциальных уравнений.
В программировании используется следующее определение алгоритма: алгоритм – точное предписание исполнителю совершить определенную по-
следовательность действий для достижения поставленной цели за конечное число шагов [3]. Под исполнителем алгоритмов понимается либо устройство,
выполняющее алгоритмы, либо человек. Одним из наиболее гибких и уни-
версальных исполнителей алгоритмов, наряду с человеком, является компь- ютер.
Алгоритм должен обладать следующими основными свойствами:
•детерминированность (определенность) – при заданных исходных данных обеспечивается однозначность искомого результата;
•массовость – пригодность для задач данного типа при исходных дан-
ных, принадлежащих заданному подмножеству;
•результативность – реализуемый вычислительный процесс выполня- ется за конечное число этапов с выдачей осмысленного результата;
•дискретность – разбиение на отдельные этапы, выполнение которых не вызывает сомнений.
Под программой понимают описание алгоритма, воспринимаемое ЭВМ
идостаточное для решения определенной задачи. Для создания программы используются искусственные языки, называемые языками программирова- ния. ЭВМ, как правило, непосредственно воспринимает и выполняет про- граммы, написанные только на одном из языков программирования – ма-
150