Министерство образования и науки Украины
Харьковский национальный университет
им. В.Н. Каразина
Методические рекомендации по курсу "Информатика и компьютерная техника"
Составители: Епишев Сергей Николаевич
Иванов Валентин Васильевич
Чуркина Людмила Георгиевна
Введение
Методические указания по курсу “Информатика и компьютерная техника”. Выпуск I. Основы ЭВМ /Состав. С.Н. Епишев, Ю.Г. Гузненков, Л.Г. Чуркина –Харьков: ХНУ, 2005. –7хх с.
Методические указания предназначены для ознакомления студентов с курсом “Информатика и компьютерная техника”. В них рассматриваются вопросы, связанные с преобразованием информации, методами ее обработки и хранения с помощью компьютерных технологий. В цифровых вычислительных машинах информация представляется в виде наборов двоичных кодов. Существует много способов кодирования числовой информации. Некоторые из них основываются на переводе чисел из десятичной системы счисления в двоичную. Перевод чисел из десятичной системы счисления в двоичную и наоборот рассматривается в данных указаниях довольно подробно. Современные компьютеры обладают мощным программным обеспечением, позволяющим решать различные задачи. В методических указаниях приводится классификация средств программного обеспечения и назначение его отдельных групп. Большое внимание уделено вопросам алгоритмизации задач решаемых на ЭВМ, поскольку даже при наличии хорошего программного обеспечения, иногда приходится составлять программы при решении некоторых задач. Для закрепления материала курса, в конце каждого параграфа приведены контрольные вопросы.
Рекомендовано кафедрой экономической кибернетики и прикладной экономики экономического факультета Харьковского национального университета им. В.Н. Каразина для студентов экономических специальностей всех форм обучения.
Понятие информатики. Источники и предпосылки информатики
Становление информатики как научной дисциплины относится к 60-годам нашего столетия. В самом общем смысле под информатикой понимают фундаментальную естественную науку, изучающую процессы передачи, накопления и обработки информации.
Термин «Informatique» был введен французами на рубеже 60-70-х годов. Но еще раньше американцами был введен в употребление термин «ComputerScience» для обозначения науки о преобразовании информации, базирующийся на вычислительной технике. В настоящее время термины «Informatique» и «ComputerScience» употребляются в эквивалентном смысле.
В нашей стране для обозначения новой научной дисциплины применялись термины «вычислительные науки» или «вычислительное дело», использование же термина «информатика» сдерживалось употреблением его в области, связанной с документалистикой. Начиная с 60-х годов, название информатика
в нашей стране получила иная научная дисциплина – теория научной информации и научно-информационной деятельности. И хотя для обозначения этой отрасли знания в русском языке предлагались и другие термины (вначале «теория научной информации», затем «документалистика»), очень скоро абсолютно доминирующим стал термин информатика
. Этому во многом способствовал выход фундаментального труда ведущих специалистов в данной области – А.И. Михайлова, А.И. Черного и Р.С. Гиляревского – под названием «Основы информатики». Новое толкование этого термина относится к 1976 году, когда появился русский перевод книги Ф. Бауэра и Г. Гооза «Введение в информатику». Волну широкого интереса к информатике вызвал выход летом 1982 года монографии академика В.М. Глушкова «Основы безбумажной информатики». Окончательное утверждение термина «информатика» связанно с созданием в марте 1983 года Отделения информатики, вычислительной техники и автоматизации Академии Наук.
В качестве источников информатики обычно называют две науки: документалистику
и кибернетику
.
Документалистика сформировалась в конце XIX века в связи с бурным развитием производственных отношений. Ее расцвет пришелся на 20-30 –е годы XXв., а основным предметом стало изучение рациональных средств и методов повышения эффективности документооборота.
Основы близкой к информатике технической науки кибернетики были заложены трудами по математической логике американского математика Норберта Винера, опубликованными в 1948 г., а само название происходит от греческого слова kyberneticos
– искусный в управлении.
Впервые термин кибернетика ввел французский физик Андре Мари Ампер в первой половине XIX в. Он занимался разработкой единой системы классификации всех наук и обозначил этим термином гипотетическую науку об управлении, которой в то время не существовало, но которая, по его мнению, должна существовать.
Сегодня предметом кибернетики являются принципы построения и функционирования систем автоматического управлении, а основными задачами – методы моделирования процессов принятия решений, связь между психологией человека и математической логикой, связь между информационным процессом отдельного индивидуума и информационными процессами в обществе, разработка принципов и методов искусственного интеллекта. На практике кибернетика во многих случаях опирается на те же программные и аппаратные средства вычислительной техники, что и информатика, а информатика, в свою очередь, заимствует у кибернетики математическую и логическую базу для развития этих средств.
Предмет и задачи информатики
Что же это за наука, или даже более того – область человеческой деятельности – информатика?
Приведем определение информатики, данное Международным конгрессом в Японии в 1978 г.: «Понятие информатики охватывает области, связанные с разработкой, созданием, использованием и материально-техническим обслуживанием систем обработки информации, включая машины, оборудование, математическое обеспечение, организационные аспекты, а также комплекс промышленного, коммерческого, административного, социального и политического воздействия».[1]
Известно определение информатики данное академиком А.П. Ершовым: «…фундаментальная естественная наука, изучающая процессы передачи и обработки информации»[2]
.
В.С. Михалевич в работе «Информатика – новая область науки и практики» дает следующее определение: «Информатика – комплексная научная и инженерная дисциплина, изучающая все аспекты разработки, проектирования, создания, оценки, функционирования машинизированных (основанных на ЭВМ) систем переработки информации, их применения и воздействия на различные области социальной практики».
Современные учебники информатики определяют ее предмет следующим образом.
«Информатика, самостоятельная научная дисциплина, предметом которой стали свойства информации, ее поведение в техногенных, социальных и биологических системах, а также методы и технологии, ориентированные на сбор, обработку, хранение, передачу и распространение информации, или, кратко, информационной технологии».[3]
Приведена формулировка предмета информатики не единственная. Популярным является определение согласно которому, «Информатика – это наука об описании, представлении, интерпретации, формализации и применении знаний, накопленных с помощью вычислительной техники, с целью получения новых знаний».
Приведем еще несколько определений фигурирующих в наших отечественных украинских учебниках.
«Информатика – наука, которая изучает информационные процессы, методы и средства получения, преобразования, передачи, хранения и использования информации, применения информационных технологий».[4]
«Інформатика – комплексная научная и инженерная дисциплина, которая изучает все аспекты проектирования, создания, оценивания, функционирования компьютерных систем обработки информации, их применения и влияния на различные отрасли социальной практики».[5]
Следуя Симоновичу С.В. («Информатика для экономистов и юристов», СПб: Питер, 2004. -688с.) будем считать, что «Информатика – это техническая наука, систематизирующая приемы создания, обработки и передачи данных средствами вычислительной техники, а также принципы функционирования этих средств и методы управления ими.
В настоящее время информатика выходит за рамки узкой технической дисциплины, относящейся к средствам вычислительной техники и информационным технологиям. Отныне ее предмет становится шире. Информатика в XXI веке становится естественной наукой, занимающей положение между другими естественными, техническими и общественными науками. Ее предмет составляют информационные процессы, протекающие в природе, обществе и технических системах. Ее методы в своем большинстве основаны на взаимодействии программных и аппаратных средств вычислительной техники с другими техническими системами, с человеком и обществом. Ее цель – научное обоснование эффективных приемов создания, распределения и потребления всех трех типов информационных ресурсов и методологическое обеспечение разработки новых информационных систем. Ее центральная роль заключается в представлении своего аппарата и понятийной базы другим естественным, общественным и техническим дисциплинам».
Информатика и информационные технологии
До появления электронной вычислительной техники были известны две информационные технологии: рукописная и книгопечатание. Технология как строго научное понятие означает определенный комплекс научных и инженерных знаний, воплощенных в способах, приемах труда, наборах материально-вещественных факторов производства, способов их соединения для создания какого-то продукта или услуги. В таком понимании термин технология неразрывно связан с машинизацией того или иного производственного или социального процесса. Появление компьютеров, их использование для обработки информации и решения разнообразных задач привело к появлению нового научного направления – «компьютерной информатики»
и новой «электронной информационной технологии»
, связанной с автоматизированной обработкой информации.
«Информационная технология в своем полном виде должна отвечать следующим требованиям:
1. Высокая степень расчленения процесса на стадии (фазы), что открывает новые возможности для рационализации всего процесса и перевода его на машинную технику. Это – важнейшая характеристика технологического процесса, возникающего на базе машин.
2. Системная полнота (целостность) процесса, который должен включать весь набор элементов, обеспечивающих необходимую завершенность действий человека в достижении поставленной цели. Требуется также определенная пропорциональность в соотношении различных звеньев технологической цепи и в уровне их развития. Опыт показывает, в частности, что как ни улучшай отдельные элементы информационно-перерабатывающего процесса на базе электронно-вычислительных машин, это не дает целостной технологии и не дает, следовательно, требуемого эффекта.
3. Регулярность процесса и однозначность его фаз, позволяющие применить средние величины при характеристике этих фаз и, следовательно, их стандартизацию и унификацию. В результате появляется возможность учета, планирования, диспетчеризации информационных процессов. В такой развитой форме, имеющей все отмеченные признаки, информационно-коммуникационные процессы выступают на высокой исторической стадии развития – в машинизированных кибернетических системах».[6]
Доступность персональных компьютеров, ориентированных на людей, не имеющих специального образования в области информатики и навыков работы с компьютером, вызвали повышенный интерес к компьютерной информатике представителей разных профессий. Диапазон эффективного применения компьютеров для автоматизированной обработки информации постоянно возрастает.
«Информатика как самостоятельная наука вступает в свои права тогда, когда для изучаемого фрагмента мира построена так называемая информационная модель. И хотя общие методологические принципы построения информационных моделей могут быть предметом информатики, само построение и обоснование информационной модели является задачей частной науки. Понятия информационной и математической моделей очень близки друг к другу, поскольку и та и другая являются знаковыми системами. Информационная модель – это сопряжение, через которое информатика вступает в отношение с частными науками, не сливаясь с ними и в то же время не вбирая их в себя».[7]
«Отсюда уже следует состав информатики – это три неразрывно и существенно связанные части: технические средства, программные и алгоритмические … Важно не забывать, что без алгоритмов предмета информатики не существует».[8]
Проблемы компьютерной информатики
сводятся к разработке:
– информационной модели задачи;
– алгоритма обработки информации;
– программы, реализующей алгоритм на языке компьютера.
Таким образом, структура системы компьютерной информатики базируется на триаде: модель – алгоритм – программа
.
Теоретической основой компьютерной информации
является методология решения задач с помощью компьютера.
Решение задач обработки информации связано с выполнением различных операций над информацией, обеспечивающих получение требуемого результата. Для автоматизации этого процесса необходимо прежде всего формализовать условие задачи и разработать методы поиска решения, в результате чего полученную формализованную информационную модель задачи и алгоритм поиска ее решения можно программно реализовать на компьютере.
Качество решения задач с использованием компьютеров определяется теми алгоритмами обработки информации, которые в них закладываются человеком. Компьютеры выполняют роль инструмента, с помощью которого реализуются эти алгоритмы.
Поэтому общая методология решения задач с помощью компьютера связана с разработкой эффективных методов формализации задачи, алгоритмов их решения.
Контрольные вопросы
1. Дайте определение понятия «информатика».
2. Чем вызван повышенный интерес к компьютерной информатике?
3. Какова структура системы компьютерной информатики?
4. В чем суть электронной информационной технологии решения задач?
5. Что является теоретической основой компьютерной информатики?
6. Что понимается под информационной моделью задачи?
7. Какова роль человека и компьютера в процессе решения задачи?
Информация и ее структура
«Кто владеет информацией, тот владеет миром» – знаменитый афоризм, принадлежащий «отцу» кибернетики Норберту Виннеру. Слово «информация» переводится на русский язык как сведения.
В последние годы оно стало употребляться в различных сферах и при этом приобрело многозначное толкование.
В энциклопедическом словаре приводится следующее ее определение: информация – это новые сведения об окружающем мире, получаемые в процессе взаимодействия с ним
.
С точки зрения кибернетики под информацией следует понимать только те сведения, которые нужны пользователю и полезны ему. Можно сказать, что информация неотделима от процесса информирования человека. Сведения становятся информативными только тогда, если они новы, достоверны, и уменьшают неопределенность
по интересующему вопросу (объекту).
С точки зрения науки информатики «информация» – это предмет обработки, то есть предмет труда.
Поэтому мы будем исходить из того, что информация – это сведения об условиях задачи и методах ее решения, зафиксированные на том или ином носителе информации (бумаге, диске и т.п.).
Одна из разновидностей информации – экономическая
, возникающая в процессе производственно-хозяйственной деятельности объекта, отображающая явления экономической жизни общества и используемая для управления этой деятельностью.
Чтобы более точно определить место информации в различных понятиях, связанных с ней, дадим следующие три определения:
Данные
– любые сведения о ком-либо или о чем-либо;
Информация
– любые новые, полезные для пользователя, сведения;
Знания –
структурированные данные, способные вызывать машинные программы для выполнения операций над своими элементами и обозначать другую информацию и ее структурные элементы. В знаниях содержатся сведения о порядке обработки данных, что позволяет автоматизировать процесс их обработки.
Для удобства обработки информационных совокупностей информацию (данные) структурируют, то есть выделяют различные конструкции, имеющие экономический
смысл. Наиболее простым структурным элементом информации является реквизит.
Реквизит
– сочетание букв, цифр и символов, имеющих смысловое содержание и не поддающееся дальнейшему делению, не теряя при этом смысла. Каждый реквизит имеет форму и содержание.
Форма
– это наименование реквизита (строки или графы документа), а содержание
– его значение. Одному наименованию реквизита может соответствовать множество его значений.
Реквизиты по своему назначению подразделяются на два вида: реквизиты-признаки
и реквизиты-основания
. Признаки
характеризуют качественную сторону (объекта), хозяйственной операции, т.п., а основания
– количественную (цена, количество, сумма и т.п.).
Реквизиты неоднородны по характеру выполняемых над ними действий: в процессе обработки над основаниями выполняются арифметические действия или логические типа сравнения (=, > и т.п.), над признаками – логические (поиск, выборка, группировка).
Реквизиты, объединяясь, образуют составные единицы информации (СЕИ) более высокого уровня.
Показатель
– информационная совокупность с минимальным составом реквизитов, достаточным для образования документа. Каждому показателю соответствует одно основание и относящиеся к нему признаки:
П→ (Р1
, Р2
…, Рn
, Q), где
Q – основание; Р1
, Р2
,…, Рn
– признаки.
Основным средством отображения экономической информации является документ.
Документ
– составная структурная единица информации, состоящая из нескольких показателей, структура и значение которых удостоверено ответственным лицом.
Как правило, в документе показатели связаны некоторыми логическими отношениями. В документе столько показателей, сколько оснований.
На основании однотипных документов формируются информационные массивы
, хотя сам документ также может содержать массивы показателей, а показатели – массивы значений реквизитов.
Совокупность информационных массивов и программ по их ведению, обработке, хранению и т.п. образуют базы данных
.
Таким образом, структура информации
– это конкретные информационные образования (единицы), наделенные экономическим смыслом.
Иерархический принцип выделения информационных образований (единиц) позволяет при использовании компьютерной техники эффективно перейти к машинным структурам информации.
Пример 1
.
Дана форма документа «Накладная», содержащая информацию о поступлении товарно-материальных ценностей от поставщиков на склад предприятия (организации).
Организация Р1
Предприятие |
Шифр | |||||
| грузополучателя | постав- щика |
склада (секция) |
вида операции |
|||
| Р2
|
Р3
|
Р4
|
Р5
|
|||
Р7
» Р8
20_
Р9
_года
Накладная № Р6
Отправитель Р10
Получатель Р11
Основание Р12
| Номер прейскуранта ему | Шифр товара, тары | Наименование товарно-материальных ценностей | Единица намерения | Сорт | Количество (вес) | Цена | Сумма | |
| Брутто | Нетто | |||||||
| Р13
|
Р14
|
Р15
|
Р16
|
Р17
|
Q1
|
Q2
|
Q3
|
Q4
|
Отпустил Разрешил
Получил _________________________
Требуется:
1) определить в документе количество реквизитов, в том числе: признаков (Р) и оснований (Q);
2) установить количество показателей К(П);
3) перечислить операции, выполняемые над реквизитами-признаками и основаниями.
Порядок выполнения задания:
1) в приведенной форме документа всего 21 реквизит и 3 подписи заверяющие документ и подтверждающие правомерность оформляемой хозяйственной операции – поступления товарно-материальных ценностей от поставщика на склад предприятия или организации. В документе 3 реквизита являются сложными (составными). Так, реквизиты Р2
:Р5
составляют реквизит «шифр», реквизиты Р7
:Р9
– «дату», а Основания Q1
и Q2
–«количество» (вес). Реквизитов-признаков в «Накладной» насчитывается 17, а оснований – 4. Признаки характеризуют место свершения хозяйственной операции (отправитель, получатель, их шифры), время (дата) и качественную характеристику товарно-материальных ценностей (номер прейскуранта, шифр и наименование товара, единица измерения, сорт). Основания дают информацию о величине поставок товарно-материальных ценностей в количественном (натуральном) и стоимостном выражении (сумме), об их цене.
2) В документе столько показателей, сколько оснований, то есть 4: количество (брутто, нетто), цена, сумма (К(П)=4). Например, показателю цена товара соответствует (Р13
, Р14
, Р15
, Р16
, Р17
,Q3
).
3) Операции, выполняемые над реквизитами и признаками:
3а) над реквизитами-признаками выполняются следующие логические операции. Документированный массив информации целесообразно группировать по шифрам поставщика, склада, вида операции и шифру товара с целью составления различных ответов о движении товарно-материальных ценностей;
3б) над основаниями в документе выполняются арифметические операции. Так, по каждой строке документа производится операция таксировка:
В целом по документу «Накладная» определяется также итог по графе
«Сумма» путем суммирования данных по указанной графе:
где:n
– количество заполненных строк в документе (i
=1,n).
Итоги могут быть получены и по группировочным признакам (поставщику, складу, шифру товара), если это необходимо для учетного и аналитического процессов.
Контрольные вопросы
1. Дайте определение понятий «информация» и «экономическая информация».
2. Что понимается под структурой экономической информации?
3. Дайте определение информационных единиц: реквизита, документа.
4. Чем отличается реквизит-признак от реквизита-основания?
5. Дайте определение составных единиц информации: показателя массива.
6. Какие основные операции выполняются над признаками и основаниями при обработке экономической информации?
7. Взять любую форму первичного документа по какому-либо участку работ и выполнить анализ структуры документа, как это сделано в примере.
Системы счисления
Под системой счисления
понимают совокупность приемов наименования и обозначения (записи) чисел. Условные знаки, применяемые для обозначения чисел называют цифрами. Кроме цифр применяются также разделители (+,- ,,
, .
и т.п.). Как и обычный язык, язык чисел имеет свой алфавит. Общепринятым языком чисел стала десятичная система счисления. Любое число в ней представляется с помощью набора из десяти цифр: 0,1,2,3,4,5,6,7,8,9. Причем, значение каждой цифры в записи числа зависит от позиции, которую она занимает в числе. Так, например, в записи 555,5 цифра 5 встречается четыре раза, но в каждой позиции она имеет разный смысл: крайняя левая цифра 5 означает количество сотен и имеет значение 500, следующая цифра 5 означает количество десятков, 5, стоящая перед запятой, означает количество единиц и, наконец, цифра 5 после запятой – количество десятых долей единицы. Десятичная система счисления является позиционной.
Позиционная система счисления
– это система, у которой при записи чисел одна и та же цифра имеет различные значения в зависимости от позиции, которую она занимает в числе. В любой позиционной системе счисления используется определенное количество различных цифр (символов) для обозначения чисел. Поэтому они различаются своим базисом и основанием.
Базис
системы счисления – набор различных цифр, применяемых для написания чисел в данной системе. Количество цифр в базисе называется основанием
системы счисления.
Позиционные системы счисления именуются соответственно своему основанию: десятичная – основание 10, восьмеричная – основание 8, двоичная – основание 2. Могут быть системы счисления, использующие более 10 цифр. Например, в шестнадцатеричной системе счисления применяются шестнадцать цифр.
Широкое распространение десятичной системы счисления, по-видимому, связано с физиологическим строением рук (ног) человека (10 пальцев на руках (ногах)). Была бы у нас дюжина (12) пальцев на руках, то, скорее всего мы бы пользовались двенадцатиричной системой.
Поскольку за основание позиционной системы счисления можно взять любое целое положительное число большее единицы, то таких систем можно создать очень много.
Для оценки пригодности той или иной системы счисления в качестве основы для конструирования вычислительной машины имеет значение, кроме простоты осуществления арифметических операций в ней, также и то, что обычно называют экономичностью
системы. Под этим понимается тот запас чисел, которые можно записать в данной системе с помощью определенного количества знаков. Чтобы в десятичной системе счисления записать 1000 чисел (от 1 до 999), необходимо 30 знаков (по 10 цифр для каждого разряда). А в двоичной системе можно с помощью 30 знаков записать 215
различных чисел (так как для каждого двоичного разряда нужны только цифры 0 и 1, то с помощью 30 цифр мы можем записать числа, содержащие до 15 двоичных разрядов). Но 215
>1000, поэтому, имея 15 различных разрядов, можно записать больше различных чисел, чем с помощью трех десятичных разрядов. В общем случае, если взять n
знаков, а за основание системы счисления принять некоторое число x
, то получится n/
x
разрядов, и количество чисел которые при этом можно записать, будет равно xn
/
x
. Рассмотрим это выражение как функцию переменной x
. Максимум этой функции достигается при x
=2,718281828459045…. Это число есть основанием натуральных логарифмов. Но оно не является целым. Ближайшими целыми к этому числу будут 3 и 2. В силу простоты технической реализации имитирования цифр двоичной системы (0,1) в ЭВМ наиболее часто используется двоичная система счисления, хотя известны реализации ЭВМ с троичной системой счисления, например «Сетунь» созданная в МГУ.
Чтобы определить, в какой системе счисления записано число, ее основание записывают в скобках внизу после числа. Например, 708(10)
, 36(8)
, 101(2)
.
В любой позиционной системе счисления ее основание записывается как 10, то есть единица в старшем разряде и 0 в младшем.
Все позиционные системы счисления строятся по одному общему принципу
: выбирается некоторое целое положительное число Р>1 - основание системы счисления; запись любого числа М представляется в виде полинома, т.е. комбинации степеней основания системы счисления Р с коэффициентами а0
, а1
, а2
, …, аk
, принимающими значения от 0 до Р-1, т.е. из базиса системы:
М(р)
=
а
k
×
р
k
+ а
k
-1
· р
k
-1
+...+ а0 ·
р0
+ а-1
·р-1
+...+ а-
m
·р-
m
…
Если при записи числа опустить степени основания системы счисления, то число можно записать в следующем компактном виде:
M(р)
= а
k
а
k
-1
...а1
, а0
а-1
... a-
m
…
Компактность представления чисел, а также удобные алгоритмы выполнения операций сложения, умножения, обусловили широкое распространение позиционных систем счисления.
Непозиционные системы счисления
построены иначе. Например, в системе римских цифр имеется набор символов: единица I, пять V, десять X, пятьдесят L и т.д., комбинация которых позволяет представить любое число. Так, число 77 в этой системе счисления запишется так: LXXVII
. В этой системе значение каждого символа не зависит от того места, на котором он стоит
. В приведенной записи числа 77 цифра X используется 2 раза, и каждый раз обозначает одну и ту же величину – десять единиц.
Один из первых создателей электронных вычислительных машин профессор Атанасов А. предложил использовать в ЭВМ двоичную систему счисления. Набор символом, используемых для представления и обработки информации в компьютере минимален. Он включает всего два символа – 0 и 1, с помощью комбинации которых (последовательностей единиц и нулей) можно записать любое число, причем при этом может потребоваться различное число бит (двоичных разрядов), что и указано в таблице 1. Использование в современных ЭВМ двоичного представления информации, как было отмечено выше, объясняется удобством технической реализации устройств хранения и обработки информации.
Таблица 1. - Изображение чисел в позиционных системах счисления, применяемых в компьютерах
| Десятичное
Р=10 |
Двоичное Р=2 |
Восьмеричное Р=8 |
Шестнадцатеричное Р=16 |
| 1 | 2 | 3 | 4 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 |
0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 |
0 1 2 3 4 5 6 7 8 9 А В С D E F |
| 16 | 10000 | 20 | 10 |
Перевод чисел из одной системы счисления в другую
При решении задач на ЭВМ исходные данные обычно задаются в десятичной системе счисления; в этой же системе, как правило, нужно получить и результат решения задачи. Но если ЭВМ работает в какой-либо другой системе счисления, например в двоичной, то возникает необходимость перевода чисел из одной системы счисления в другую. При рассмотрении правил такого перевода мы ограничимся только такими системами счисления, у которых базисными числами являются последовательные целые числа от 0 до P-1 включительно, где P – основание системы счисления.
При переводе числа из десятичной системы счисления в систему счисления с основанием Р перевод целой и дробной части числа производится отдельно. Перевод целого числа из десятичной системы счисления в любую другую с основанием
Р производится многократным делением десятичного числа на основание Р, пока частное не станет меньше Р. Последнее частное будет старшим разрядом числа, а остаток от первого деления на Р – младшим. На практике удобно пользоваться следующей схемой, которую проиллюстрируем при переводе числа 56 из десятичной системы счисления в двоичную, восьмеричную и шестнадцатеричную:
56(10)
→ (2)
→ (8)
→ (16)
| 56 | 2 | ||
| 56 | 28 | 2 | |
| 0 | 28 | 14 | 2 |
| 0 | 14 | 7 | 2 |
| 0 | 6 | 3 | 2 |
| 1 | 2 | 1 последнее частное | |
| 1 | |||
Ответ: 56(10)
=111000(2)
;
| 56
|
8
|
| 56
|
7
|
| 0
|
Ответ: 56(10)
=70(8)
.
| 56
|
16
|
| 48
|
3
|
| 8
|
Ответ: 56(10)
=38(16)
.
Чтоб
ы перевести правильную дробь из десятичной системы счисления в любую другую с основанием
P, ее последовательно умножают на P, при этом каждый раз умножается только дробная часть образовавшегося произведения. Процесс перевода продолжается либо до достижения заданной точности, либо до обнаружения периода. Дробь в системе счисления с основанием P записывается в виде дроби из целых частей образовавшихся произведений, начиная с первого.
Перевод десятичных дробей удобно производить по схеме, которую проиллюстрируем на примерах.
Перевести:
1) 0,75(10)
→(8)
0, |
75 8 |
| 6, | 00 |
Ответ: 0,75(10)
=0,6(8)
2) 0,7(10)
→(16
)
0, |
7 16 |
| 11, | 2 |
| 16 | |
| 3, | 2 |
Ответ: 0,7(10)
=0,В(3)(16)
2) 0,4(10)
→(2)
0, |
4 2 |
0, |
8 2 |
| 1, | 6 |
Ответ: 0,4(10)
=0,01(2)
Примеры для отработки навыков
1) 0,45(10)
→(2)
;2) 0,6(10)
→(8)
;3) 0,95(10)
→(16)
;
4) 425,6(10)
→(8)
;5) 147,4(10)
→(2)
;6) 5827,8(10)
→(16).
Перевод числа, записанного в системе счисления
P, в десятичную систему
выполняется с учетом веса каждого разряда или путем записи числа в виде разложения по степеням основания P. Например,
1) 1101(2)
→(10)
1101(2)
=1· 103
+ 1· 102
+ 0·101
+ 1· 100
(2)
→1·8+1·4+0·2+1(10)
=13(10)
;
или по схеме:
двоичное число 1 1 0 1(2)
десятичное число
8 4 2 1
1х1=1
0х2=0
1х4=4
1х8=8
Ответ: 13(10)
Во втором случае перевод выполняется с учетом веса каждого разряда.
2) 354,4(8)
=3·82
+5·81
+4·80
+4·8-1
(10)
=192+40+4+0,5(10)
=236,5(10)
;
3) A1F,8(16)
=A·162
+1·161
+F·160
+8·16-1
(16)
= 10·162
+1·16+15+8/16(10)
= =2591,5(10)
.
Примеры для отработки навыков.
1) 1А0,Е(16)
→ (10)
;2) –1011101,101(2)
→ (10)
; 3) 101,1(8)
→ (10)
Переход из двоичной в восьмеричную и шестнадцатеричную системы счисления и обратно
Поскольку основание восьмеричной системы 8=23
, то разложение числа по степеням 8 легко переводится в разложение по степеням 2 и наоборот. При этом каждая цифра восьмеричной системы (0,…,7) имеет свое разложение по степеням 2. Например,
2(8)
=0·22
+1·21
+0·20
=(010)2
6(8)
=1·22
+1·21
+0·20
=(110)2
Тогда переход от восьмеричного представления числа в двоично-восьмеричное осуществляется путем замены каждой восьмеричной цифры соответствующей двоичной триадой.
720(8)
=7·82
+2·81
+0·80
=(1·22
+1·2+1·20
)26
+(0·22
+1·2+0·20
)·23
+(0·22
+0·21
+0·20
)=1·28
+1·27
+1·26
+0·25
+1·24
+0·23
+0·22
+0·21
+0·20
=111010000(2)
=11 010 000(2)
.
7 2 0
Для представления двоичного числа в восьмеричной системе надо число разбить на двоичные триады влево и вправо от запятой и затем заменить каждую триаду, соответствующей ей восьмеричной цифрой.
101 111 011, 001 100(2)
= 573,14(8)
Четыре двоичных разряда позволяют закодировать любую десятичную цифру и получить 16 различных кодовых комбинаций, из которых 10 (от 0000 до 1001) используются для представления десятичных цифр. Кодовые комбинации, соответствующие числам 10 и более, условно обозначаются первыми буквами латинского алфавита (графа 4 таблицы 1). Так получается шестнадцатеричная система счисления. В программах для ЭВМ, чтобы не выписывать длинную вереницу нулей и единиц, вместо каждых четырех разрядов (тетрад) записывается их шестнадцатеричный эквивалент. Например, шестнадцатеричный эквивалент числа 0101 0001 1111 0011 будет 51F3.
Арифметические операции в электронных вычислительных машинах
В вычислительных машинах вся информация представляется в двоичной форме, а для выполнения вычислений используется непосредственно двоичная система счисления.
Арифметические операции с двоичными числами производятся так же, как с десятичными, с той лишь разницей, что в десятичной системе цифры каждого разряда возрастают в порядке 1,2,…,8,9, а при достижении величины 10 в этом разряде записывается 0 и делается перенос единицы в старший разряд. В двоичной системе используются только два символа 0 и 1, поэтому цифры в каждом разряде могут изменяться только в пределах этих двух значений, после этого происходит перенос в более старший разряд.
Таблица 1. -Таблица сложения двух бинарных чисел, имеет следующий вид:
Здесь 10 – это 2 в двоичной системе счисления.
Например:
1110,01(2)
10111,011(2)
+ 1010,10(2)
+ 11101,101(2)
11000,11(2)
110101,000(2)
Обычно для представления положительных и отрицательных чисел используются величины со знаками, причем при представлении положительных чисел знак «+» можно опускать, а знак «–» при изображении отрицательных чисел должен ставиться, что для реализации на вычислительных машинах неудобно. В вычислительных машинах используется форма представления чисел в дополнительных кодах, а знаки «+» и «–» используются для указания арифметических операций.
В двоичной системе счисления числа могут быть представлены в форме дополнения до основания системы счисления, то есть до 2. В двоичном дополнительном коде всем положительным числам предшествует 0, а отрицательным числам – единица. Таким образом, при представлении чисел в дополнительном коде крайний левый бит (старший) является знаковым: 0 означает положительное число, а 1 – отрицательное.
1011 1100 101 110 111 000 001 010 011 0100 0101
-5 -4 -3 -2 -1 0 1 2 3 4 5
Числа, стоящие по разные стороны от нуля, являются взаимно дополнительными, то есть их сумма всегда равна 0. Чтобы представить двоичное число в дополнительной форме, его инвертируют (заменяют 0 на 1, а 1 – на 0) прибавляют к нему 1
. Операция вычитания выполняется путем сложения дополнительных кодов.
Пример:
Выполнить вычитание 10111,1–1010,1.
На первом этапе необходимо указанные числа выровнять по значности (они должны иметь одинаковое количество разрядов) и представить в дополнительном коде.
[10111,1]доп.= 0 10111,1
[ –01010,1]доп.= 1 10101,0 + 00000,1 = 1 10101,1.
На втором этапе выполняется вычитание как сложение с дополнительным числом, то есть:
0 10111,1
+ 1 10101,1
0 01101,0 = 1101.
Операции умножения, деления, возведения в степень и вычисления функций процессор не выполняет, их необходимо выполнять программным путем, используя сдвиги влево и вправо. Сдвиг двоичного числа на одну позицию влево приводит к его удвоению подобно тому, так сдвиг десятичного числа на одну позицию вправо – к его уменьшению на 10. Сдвиг двоичного числа на одну позицию вправо делит его пополам.
Контрольные вопросы и примеры
1. Что понимается под системой счисления?
2. Чем отличается позиционная система счисления от непозиционной?
3. Дайте определение базиса и основания позиционной системы счисления.
4. Как перевести число из 10→ 2, из 10→ 16?
5. Как перевести число из 2→ 10, из 8→10, из 16→10?
6. Каков принцип построения позиционных систем счисления?
7. Как изображаются числа в дополнительном коде?
8. Опишите схему вычитания чисел с помощью дополнительного кода.
9. Перевести числа из одной системы счисления в другую:
а) 625(10)
→(2)
;б) 3628,5(10)
→(16)
;в) 1024,4(10)
→ (8)
;
г) 134,6(8)
→(10)
;д) –ВСО(16)
→(10)
.
10. Записать числа в дополнительном коде:
а) 1563,04(10)
г) –3А01(16)
б) –2,149(10)
д) –01010,101(2)
в) –0,1001101(2)
е) –37,54(8)
11. Выполните арифметические операции в двоичной системе:
а) 1011,11б)1011,101
+ 101,11 - 110,11
12. Комплексное задание: в таблице 2 приведены по вариантам числа в десятичной, двоичной и восьмеричной системах счисления:
Таблица 2.Системы счисления
| № варианте | Десятичная система | Двоичная система | Восьмеричная система |
| 1 | 2 | 3 | 4 |
| 1 | 107.99 | 1100101.100100 | 152.01 |
| 2 | 357.94 | 1000111.011111 | 204.31 |
| 3 | 273.66 | 1111001.001110 | 110.44 |
| 4 | 845.76 | 1111010.100101 | 243.25 |
| 5 | 214.38 | 1110010.010101 | 743.56 |
| 6 | 584.16 | 1010101.100111 | 676.43 |
| 7 | 343.37 | 1101100.010011 | 114.53 |
| 8 | 128.69 | 1110101.000111 | 631.04 |
| 9 | 513.76 | 1010111.111001 | 204.33 |
| 10 | 778.47 | 1111001.010111 | 301.75 |
Выполнить:
1) перевести число из 10-ой системы счисления в двоичную, восьмеричную и шестнадцатеричную;
2) перевести число из 2-ой системы счисления в десятичную и восьмеричную;
3) перевести число из восьмеричной системы счисления в десятичную и двоичную системы;
4) выполнить сложение чисел, находящихся в 2 и 4 графах таблицы 2, пользуясь двоичной арифметикой;
5) выполнить вычитание двоичных чисел, находящихся в тех же графах таблицы 2.
Основы математической логики
В математических и других рассуждениях постоянно встречаются повествовательные предложения, образованные путем видоизменения некоторого предложения с помощью слова не
или связывания предложений с помощью слов и
, или
, если
…, то
(или влечет
), тогда и только тогда
, когда
. Эти пять слов или комбинаций слов называются сентенциональными связками
. Они являются основой для построения сложных предложений
(т.е. таких повествовательных предложений в которых содержится одна или более чем одна связка), составленных их простых предложений
(т.е. таких, каждое из которых или не содержит связку, или рассматривается как «неразложимое»).
Повествовательное предложение о котором можно сказать истинно оно или ложно мы будем называть высказыванием
. Множество повествовательных предложений и сентенциональных связок образует исчисление высказываний. Если обозначать высказывания большими латинскими буквами и ввести для сентенциональных связок условные обозначения (значки), то можно перейти к логическим формулам результатом которых будут логические значения – истина или ложь.
Дадим определения для основных логических операций.
1. Конъюнкцией
(или операцией логического умножения) двух высказываний A
и B
называют высказывание C
, которое истинно тогда и только тогда, когда истины оба высказывания входящие в конъюнкцию. Конъюнкция (иногда логическое «и») обозначается значком и записывается так: A
B
.
2. Дизъюнкцией
(или операцией логического сложения) двух высказываний A
и B
называют высказывание C
, которое ложно тогда и только тогда, когда ложны оба высказывания входящие в дизъюнкцию. Дизъюнкция (иногда логическое «или») обозначается значком Ú и записывается так: A
ÚB
.
3. Отрицанием
высказыванияA
называют высказывание B
которое ложно тогда и только тогда когда истинно исходное высказываниеA
, обозначают (иногда ØA
).
4. Импликация
высказываний (или условное предложение
) обозначается A
ÞB
и задается с помощью следующей таблицы, называемой таблицей истинности
для импликации:
| A
|
B
|
A
ÞB |
| Истина | Истина | Истина |
| Истина | Ложь | Ложь |
| Ложь | Истина | Истина |
| Ложь | Ложь | Истина |
4. Эквиваленция
или эквивалентность двух высказываний обозначается A
ÛB
и задается следующей таблицей истинности:
| A
|
B
|
A
ÛB |
| Истина | Истина | Истина |
| Истина | Ложь | Ложь |
| Ложь | Истина | Ложь |
| Ложь | Ложь | Истина |
Среди всех сложных высказываний или логических формул наибольший интерес представляют такие, которые принимают значение истина при любых истинностных значениях входящих в них логических переменных (высказываний). Они называются тождественно истинными
высказываниями
или тавтологиями
, обозначаются значком . Для доказательства общезначимости
логических формул (того, что формула есть тавтология) пользуются таблицами истинности или применяют основные законы эквивалентности
математической логики, которые также доказываются применением таблиц истинности.
Законы эквивалентности
1. Законы коммутативности (они позволяют переставлять операнды Ù,Ú и Û):
(A
ÙB
)Û(B
ÙA
)
(A
ÚB
)Û(B
ÚA
)
(A
ÛB
)Û(B
ÛA
)
2. Законы ассоциативности (они позволяют нам пренебрегать скобками):
(A
ÙB
) ÙС
ÛA
Ù(B
ÙC
)
(A
ÚB
) ÚС
ÛA
Ú(B
ÚC
)
3. Законы дистрибутивности (они позволяют раскрывать скобки):
A
Ú(B
ÙС
)Û (A
ÚB
)Ù(A
ÚC
)
A
Ù(B
ÚС
)Û (A
ÙB
)Ú(A
ÙC
)
4. Законы де Моргана:
Ø(A
ÙB
)ÛØA
ÚØB
Ø(A
ÚB
)ÛØA
ÙØB
5. Закон отрицания:Ø(ØA
) ÛA
6. Закон исключенного третьего: A
ÚØA
Û истина
7. Закон противоречия: A
ÙØA
Û ложь
8. Закон импликации: (A
ÞB
)Û( ØA
ÚB
)
9. Закон равенства: (A
ÛB
)Û (A
ÞB
)Ù(B
ÞA
)
10. Законы упрощения Ú:
A
ÚA
ÛA
A
ÚИстина ÛИстина
A
ÚЛожьÛА
А
Ú(А
ÙВ
)ÛА.
11. Законы упрощения Ù:
А
ÙА
ÛА
А
ÙИстинаÛА
А
ÙЛожьÛЛожь
А
Ù(А
ÚВ
)ÛА
12. Закон тождества:
А
ÛА
.
Операции математической логики имеют свое старшинство, т.е. порядок их выполнения: 1) Ø, 2) Ù, 3) Ú, 4) Þ, 5) Û.
Пример 1. Доказать общезначимость формулы:
(АÛВ)Ù(ВÛС)Þ(АÛС)
Для доказательства воспользуемся таблицей истинности. Заметим, что количество строк в такой таблице равно 8 (2n
– где, n – количество логических переменных).
Будем в таблице истину обозначать – и
, а ложь – л
.
| А | В | С | АÛВ | ВÛС | (АÛВ)Ù(ВÛС) | АÛС | Вся формула |
| и | и | и | и | и | и | и | и |
| и | и | л | и | л | л | л | и |
| и | л | и | л | л | л | и | и |
| л | и | и | л | и | л | л | и |
| и | л | л | л | и | л | л | и |
| л | и | л | л | л | л | и | и |
| л | л | и | и | л | л | л | и |
| л | л | л | и | и | и | и | и |
Пример 2. Используя основные законы эквивалентности доказать эквивалентность формул U и V, когда
| U = XÞ(XÙY)Þ((XÞY)ÞY)ÞZ
|
| V = YÞ(XÞZ) |
Применяя основные законы эквивалентности к каждой формуле в отдельности покажем, что они дают одно и то же логическое выражение (формулу). Далее, на основании равенства правых частей сделаем заключение о равенстве левых.
Рассмотрим V:
| V = YÞ(XÞZ) |
| ØYÚ(ØXÚZ) |
| ØYÚØXÚZ |
Рассмотрим U:
| U = XÞ(XÙY)Þ((XÞY)ÞY)ÞZ |
| ØXÚ(ØXÚØYÚ((Ø(ØXÚØY)ÚY)ÙZ)) |
| ØXÚØXÚØYÚ(((XÙØY)ÚY)ÙZ) |
| ØXÚØYÚ(((XÚY)Ù(ØYÚY)ÙZ) |
| ØXÚØYÚ((XÚY)Ù Z) |
| ØXÚØYÚ((XÙZ)Ú(YÙZ)) |
| ØXÚØYÚ(XÙZ)Ú(YÙZ) |
| (ØXÚ(XÙZ))Ú(ØYÚ(YÙZ)) |
| ((ØXÚX)Ù(ØXÚZ))Ú((ØYÚY)Ù(ØYÚZ)) |
| (ØXÚZ)Ú(ØYÚZ) |
| ØXÚZÚØYÚZ |
| ØXÚØYÚZ |
Тем самым эквивалентность доказана.
Пример 3. Записать логическое выражение принимающее значение истина
в случае когда точка с координатами (x
,y
) находится внутри заштрихованной области. На рисунке даны окружность с единичным радиусом и парабола у=х2
.
Рис.1. - Окружность с единичным радиусом
Выражение имеет следующий вид: (X2
+Y2
£1)Ù(Y£X2
).
Пример 4. Записать логическое выражение, принимающее значение истина
в случае когда точка с координатами (x
,y
) находится внутри заштрихованной области. На рисунке даны окружность с единичным радиусом и парабола у=х2
.
Рис.2. - Окружность с единичным радиусом
Выражение имеет следующий вид:
((X£0)Ù(X2
+Y2
£1)Ù(Y£X2
))Ú((X2
+Y2
£1)Ù(Y£X2
)Ù(Y³0)).
Контрольные вопросы
1. Что такое сентенциональные связки?
2. Дайте определение высказывания.
3. Как определяются основные логические операции?
4. Что значит общезначимость логической формулы?
5. Выпишите основные законы эквивалентности.
6. Какие приоритеты имеют логические операции?
7. Пользуясь основными законами эквивалентности доказать общезначимость формулы:
(AÞB)Þ((BÞC)Þ(AÞC)).
Используя таблицу истинности доказать следующий закон эквивалентности:
(A
ÞB
)Û( ØA
ÚB
).
8. Записать логическое выражение принимающее значение истина
в случае когда точка с координатами (x
,y
) находится внутри заштрихованной области.
Структурная схема ЭВМ
Общая структурная схема персонального компьютера представлена на рис. 1. Для простоты на этой схеме показано лишь одно устройство ввода и одно устройство вывода. Основная память компьютера состоит из двух частей – оперативного запоминающего устройства (ОЗУ) и постоянного запоминающего устройства (ПЗУ).
Рис. 1. Общая структурная схема персонального компьютера.
Микропроцессор является главным компонентом компьютера. Характеристики микропроцессора – длина разрядной сетки (или разрядность слова), набор выполняемых команд, быстродействие и другие – в основном определяют характеристики компьютера. Микропроцессор выполняет следующие функции: управление и координация работы всех других компонентов компьютера; выборка команд и обрабатываемых данных из основной памяти; декодирование команд; выполнение с помощью арифметического устройства арифметических, логических и других операций, закодированных в командах; передача данных между микропроцессором и основной памятью, а также между микропроцессором и устройствами ввода-вывода; обработка сигналов от устройств ввода-вывода, в том числе обработка сигналов прерывания с этих устройств.
Микропроцессор – сложное цифровое электронное устройство. К основным элементам, влияющим на временные характеристики выполнения программ, относятся: форматы и системы команд микропроцессора; длительность выполнения разных команд; имена (или номера) программно-доступных регистров (так называются регистры, которые могут использоваться в составляемых программах); длина разрядной сетки (разрядность); правила адресации внешних устройств и особенности выполнения операций ввода-вывода; размер адресного пространства; схема обработки прерываний.
Перечисленные элементы образуют основу архитектуры микропроцессора и в совокупности представляют собой модель микропроцессора. Для разных типов микропроцессоров существует своя модель.
Рис. 2. Микропроцессор и его связи с основной памятью.
В состав микропроцессора входят: устройство управления (УУ), арифметическо-логическое устройство (АЛУ) и набор регистров.
Устройство управления предназначено для управления работой всех компонентов микропроцессора и обеспечения должного взаимодействия различных компонентов друг с другом. Управление осуществляется с помощью импульсных сигналов, посылаемых УУ на соответствующие входы управляемых компонентов. Кроме того, УУ может получить ответные сигналы с управляемых компонентов.
Физически УУ представляет собой цифровую электронную схему, на вход которой поступают коды подлежащих выполнению операций, а выходом являются серии импульсных управляющих сигналов. Таким образом, восприняв код той или иной операции, УУ формирует цепочку управляющих сигналов и подает их в нужные точки микрокомпьютера.
Число выходов УУ, по которым выдаются управляющие сигналы, обычно довольно велико. Например, УУ, показанное на рис. 3, имеет 16 выходов.
Рис.3. Устройство управления микропроцессора.
Надо иметь в виду, что импульсные сигналы на выходах в общем случае появляются не одновременно, а со сдвигом во времени. Так, УУ на рис.3 может выдать импульс сначала на выходе 3, затем на выходе 1, следом – одновременно на выходах 2 и 5, потом на выходе 4 и т.д. После выдачи последнего импульса в данной цепочке управляющих сигналов текущая операция считается законченной, и вслед за этим на вход УУ может быть подан код новой операции.
Арифметико-логическое
устройство предназначено для исполнения арифметических и логических операций. Основу АЛУ составляет операционный блок –
цифровое электрическое устройство, которое может настраиваться на различные операции и непосредственно осуществлять их. Настройка операционного блока на конкретную операцию и последовательность шагов ее выполнения обеспечивается с помощью управляющих сигналов УУ.
Регистры
являются важными элементами микропроцессора. Регистр
– это электронное цифровое устройство для временного запоминания информации в форме двоичного числа, или кода. Запоминающим элементом в регистре является триггер, который может находиться в одном из двух состояний. Одно из этих состояний соответствует запоминанию двоичного нуля, другое – запоминанию двоичной единицы. В общем случае регистр содержит несколько связанных друг с другом триггеров – по одному триггеру на каждый запоминаемый разряд двоичного числа. Число триггеров в регистре называется разрядностью
регистра. Например, регистр из восьми триггеров – это 8-разрядный, или 8-битовый, регистр (так как каждый разряд регистра обеспечивает хранение одного бита информации).
Регистры, используемые не только для хранения информации, но и для ее преобразования, называются управляемыми
. Например, управляемый регистр может осуществлять замену всех хранящихся в нем двоичных единиц нулями, а нулей – единицами (операция инвертирования кода
), прибавление единицы к числу, хранящемуся в регистре, вычитание единицы и т.п. Операции над числом в регистре реализуются с помощью управляющих сигналов от УУ.
Многие регистры специализированны по своей функции. Так существует регистр-аккумулятор, или просто аккумулятор, программный счетчик, регистр команд, регистр адреса памяти и т.д. Аккумулятор входит в АЛУ и предназначен для хранения одного из операндов перед выполнением операции в АЛУ или для кратковременного запоминания результата операции. Операнд – это данное, используемое в текущей операции. Например, в операции суммирования операндами являются оба слагаемых.
Программный счетчик
(счетчик команд, регистр адреса команды
) служит для формирования и запоминания адреса очередной выполняемой команды. После выполнения каждой команды программный счетчик содержит адрес следующей команды, по которому эта команда хранится в памяти компьютера.
Регистр команд
используется для хранения кода текущей выполняемой команды. Входящий в состав команды код операции используется, как уже говорилось, для формирования в УУ определенной серии управляющих сигналов, зависящей от конкретного кода операции. Оставшаяся часть кода команды может содержать информацию об адресах операндов, участвующих в выполнении данной команды.
Регистр адреса памяти
служит для запоминания адреса команды, операнда или результата операций в память. Регистр адреса памяти может входить не в состав микропроцессора, а в состав элементов памяти компьютера.
Изменить роль специализированных регистров или даже узнать их содержимое программным путем нельзя, т.е. эти регистры, как говорят, программно-недоступны. Но в состав микропроцессора входят и регистры, которые программист может использовать в своей программе. Такие регистры микропроцессора называют программно-доступными
. Состав и назначение их различны в разных типах микропроцессоров. Однако среди них почти всегда имеется регистр слова состояния процессора (РССП) и несколько регистров общего назначения (РОН).
Регистр слова состояния процессора
хранит слово состояния процессора (ССП), отражающее информацию о состоянии микропроцессора и выполняемой им программы в каждый данный момент времени. В частности, в РССП обычно запоминаются признаки результата выполнения команды (отрицательного результата, переполнения разрядной сетки и т.п.). Таким образом, хотя РССП и предназначен для особых функций, он программно-доступен, т.е. с помощью соответствующих команд, заложенных в программу, можно читать и даже частично изменять его содержимое.
Регистры общего назначения обычно не имеют конкретного функционального назначения. Программист может в своей программе задействовать их так, как он считает нужным. Например, результат выполнения некоторой команды можно не посылать в основную память, а временно запомнить в каком-нибудь РОНе с тем, чтобы позднее, в другой команде, использовать этот результат. Чтобы отличить РОНы друг от друга, им присвоены уникальные имена
(или номера
), которые и записываются в программе. Существуют микропроцессоры, в которых РОНы применяются и для специальных целей. Например, один из РОНов может выполнять функции программного счетчика, или счетчика команд, хранящего в каждый момент времени адрес очередной команды программы, другой – функции указателя стека, необходимого при обработке прерываний и т.д.
На персональных компьютерах используются микропроцессоры фирмы Intel, а также совместимые с ними фирм AMD, Cyrix, IBM. Исторически на IBMPC-совместимых компьютерах применялись и применяются следующие микропроцессоры: Intel-8088, 80286, 80386 (модификации SX и DX), 80486 (модификации SX, SX2, DX, DX2, DX4), Pentium, PentiumPro, PentiumII (и его модификации Celeron и т.д.). Основная память.
Основная память
– важнейший компонент персонального компьютера. Название «основная» отличает эту память от внешней памяти
, которая организуется на некотором внешнем устройстве (например, на НГМД). Это название говорит о том, что микропроцессор может обрабатывать только те данные, которые хранятся в основной памяти. Основная память обычно состоит из двух частей – ОЗУ и ПЗУ.
Оперативное запоминающее устройство
(ОЗУ) обеспечивает чтение находящихся в нем данных и запись в него новых данных. В компьютерах ОЗУ обычно реализуется как энергозависимая память
, т.е. такая память, содержимое которой разрушается («стирается») при выключении питания компьютера. Часто для обозначения оперативной памяти используют аббревиатуру RAM (randomaccessmemory), т.е. память с произвольным доступом. Микросхемы ОЗУ собираются в блоки различной емкости. Наиболее распространены емкости 16, 32, 64 и 128 мегабайт. В зависимости от способа работы микросхем памяти они бывают SIMM или DIM, последние наиболее распространены. Для убыстрения доступа к оперативной памяти на быстродействующих компьютерах используется еще и дополнительная специальная сверхбыстродействующая память, так называемая кэш-память. Она хранит копии наиболее часто используемых участков оперативной памяти и как бы занимает промежуточное положение между микропроцессором и оперативной памятью. Кэш-память может располагаться или внутри микропроцессора, или в виде отдельной платы. Так микропроцессоры серий 486 и Pentium содержат небольшую внутреннюю кэш-память. Часто кэш-память, располагаемую отдельно от микропроцессора называют кэш-памятью второго уровня (leveltwocache, L2 cache). В микропроцессоре PentiumPro,например, кэш-память второго уровня содержится в едином с ним корпусе. Микропроцессоры 486 серии и Pentium обычно оснащаются кэш-памятью емкостью 256 Кбайт.
Постоянное запоминающее устройство
(ПЗУ) обеспечивает только чтение данных, которые однажды были записаны в ПЗУ. Таким образом, содержимое ПЗУ не может быть изменено компьютером, оно постоянно (отсюда и название вида памяти). Это устройство создается как энергозависимая память: ее содержимое не «стирается» при выключении питания компьютера. Запись нужных данных в ПЗУ осуществляется на специальных устройствах, вне компьютера. В ПЗУ обычно помещаются некоторые особо важные или не подлежащие изменению программы и разнообразные константы. Такой вид памяти часто называют ROM (readonlymemory), или память только для чтения. Поскольку большая часть этих данных, программ связана с обслуживанием ввода-вывода, то часто содержимое ПЗУ называют BIOS (BasicInput-OutputSystem), базовая система ввода-вывода. В компьютере имеется также небольшой участок полупостоянной памяти для хранения параметров конфигурации компьютера. Ее называют CMOS-памятью. Содержимое этой памяти не изменяется при выключении компьютера, так как ее питание осуществляется от небольшого специального аккумулятора. Для изменения значения параметров конфигурации компьютера в BIOS имеется специальная программа SETUP.
Интерфейсы для устройств ввода и вывода.
Они представляют собой блоки сопряжения с устройствами соответственно ввода и вывода. Не останавливаясь пока на описании устройств ввода и вывода, отметим лишь, что термин «интерфейс» означает приблизительно «сопряжение двух устройств друг с другом с помощью аппаратных и программных средств». Необходимость интерфейсов, или, как их еще называют, интерфейсных блоков (контроллеров)
, вызывается тем, что устройства ввода и вывода (например, дисплей, печатающее устройство, НГМД и т.д.) нельзя непосредственно подключать к компьютеру. Одной из причин этого является то, что количество и характер сигналов, передаваемых и принимаемых по системной магистрали, с которой связаны все компоненты компьютера, как правило, отличаются от количества и типа сигналов, формируемых или воспринимаемых устройством ввода-вывода. Соответствующий интерфейсный блок обеспечивает должное согласование сигналов системной магистрали и устройства ввода-вывода.
На любом персональном компьютере имеются контроллеры для управления клавиатурой, монитором, дисководами для дискет, жестким диском и т.д. Некоторые из контроллеров размещаются на основной системной или материнской плате компьютера, тогда они называются встроенными
или интегрированными
; а другие на отдельных электронных платах – платах контроллеров
. Эти платы соединяются (вставляются) с материнской с помощью специальных разъемов – слотов
.
Внешние устройства.
Они предназначены для ввода обрабатываемых данных, вывода результатов обработки или вычислений и долговременного запоминания программ и данных.
Основным средством ввода данных на персональном компьютере всегда служит клавиатура. Из других средств ввода-вывода отметим следующие:
1. Накопители (или дисководы) для гибких магнитных дисков, используемые для чтения и записи на гибкие магнитные дискеты. В настоящее время используются дискеты емкостью 1,4 Mb и 2 Mb.
2. Накопитель на жестком магнитном диске, предназначенный для записи и чтения на несъемный жесткий магнитный диск (винчестер). Сейчас применяются в основном винчестеры емкостью в 5-10 GB.
3. Устройства для чтения с компакт дисков, так называемые CDROMы. Емкость таких дисков обычно составляет 640 Mb. Различаются они скоростью считывания информации, которая может быть сравнена со скоростью работы винчестеров. Они позволяют также проигрывать музыкальные компакт диски.
4. К другим внешним устройствам можно отнести модемы и факс-модемы – для обмена информацией с другими компьютерами через телефонную сеть; стримеры – для хранения данных на магнитной ленте; звуковая карта – для воспроизведения и записи звуков (музыки, голоса и т.д.).
Перечисленные устройства чаще всего размещаются в едином корпусе. Туда же вставляется материнская плата, контроллеры, блок питания . Корпус этот – системный блок
по существу и есть компьютер. Из других внешних устройств следует отметить монитор
– для вывода информации в графическом и текстовом виде и принтер
– для распечатывания документов, манипулятор мышь
– для работы в графическом режиме практически незаменима.
Системная магистраль.
Обычно она содержит магистрали адресов, данных и управления. Каждый из них состоит из набора проводников, по которым микропроцессор передает или принимает определенные электрические сигналы. Магистраль адреса предназначена для передачи цифрового адреса ячейки памяти или внешнего устройства, магистраль данных – для передачи и приема данных (например, передача информации из микропроцессора в ОЗУ происходит по магистрали данных). Магистраль управления используется для передачи сигналов управления, которые сопровождают любую передачу адреса или данных.
В современных компьютерах чаще всего используются две магистрали (шины
) передачи данных между оперативной памятью и контроллерами:
1. Шина ISA для контроллеров с низкой скоростью обмена данными – клавиатура, мышь, дисководы для дискет и т.д.
2. Шина PCI для контроллеров быстрых устройств – жесткие диски, видеоконтроллеры, устройства чтения с компакт дисков и т.д.
Некоторые устройства используют другие шины, например сканер может использовать шину типа SCSI.
<
Обычно источник питания формирует выпрямленные стабилизированные напряжения +12, -5 и +15 в. Этот набор напряжений может изменяться для различных классов микропроцессоров.
Контрольные вопросы
1. Изобразите структурную схему персонального компьютера.
2. Каким является типовое устройство микропроцессора (модель)?
3. Какие типы микропроцессоров применяются на персональном компьютере?
4. Что такое регистр? Приведите примеры регистров микропроцессора.
5. Устройство управления микропроцессора, что это такое?
6. Какие типы памяти Вы знаете?
7. Что представляет собой кэш-память?
8. Что представляет собой CMOS память?
9. Что такое контроллер, какие типы контроллеров бывают?
10. Какие внешние устройства компьютера Вы знаете?
11. Что такое системная магистраль и какие основные магистрали данных используются в персональном компьютере?
12. Системный блок компьютера, что он включает?
13. Дайте сравнительную характеристику внешних устройств персонального компьютера.
Программное обеспечение ЭВМ
Современные информационно-вычислительные системы, применяемые для решения научно-технических, учетно-плановых и управленческих задач включают две взаимосвязанные, но качественно различные компоненты: комплекс средств вычислительной техники и программное (математическое) обеспечение.
Программное обеспечение (ПО) можно разделить на две части: системное программное обеспечение (СПО) и прикладное программное обеспечение (ППО).
Системное программное обеспечение
(СПО) – это комплекс управляющих и обрабатывающих программ, описаний и инструкций, которые обеспечивают техническое функционирование вычислительной системы, а также разработку, отладку и выполнение программ пользователей. Набор программ системного программного обеспечения мало зависит от характера решаемых задач пользователей.
Прикладное программное обеспечение
(ППО) представляет собой совокупность программ решения конкретных задач, которые систематически используются в интересах данного предприятия, учреждения или органа управления для обеспечения его производственной, научной или административной деятельности.
Специализированные комплексы программ решения конкретных задач называют пакетами прикладных программ
. При создании прикладных программ применяют методы специальных научных, инженерных и экономических дисциплин, а также общие методы вычислительной математики, теории оптимизации, теории информационного поиска и программирования для вычислительных машин.
Разработкой системного программного обеспечения занимается особая дисциплина – системное программирование
. Предмет системного программирования – теория и методы разработки и эксплуатации программ системного ПО.
По функциональному назначению и применяемым методам внутри системного программного обеспечения можно выделить две системы программ: операционную систему
и систему программирования
.
Операционная система
есть комплекс управляющих программ, которые обеспечивают техническое функционирование вычислительной системы, включая диагностику неисправностей, планирование использования ресурсов системы и решение задач по управлению заданиями пользователя. Кроме того, на операционную систему часто возлагают управление вводом-выводом и обменом данными между различными компонентами системы (например, между оперативной и внешней памятью), а также ведение архива, т.е. размещение данных во внешней памяти и обеспечение доступа к ним.
Операционную систему можно рассматривать как программное продолжение и расширение аппаратурной части вычислительной системы.
Основной задачей операционной системы является управление выполнением программ пользователей с целью максимального повышения производительности машины.
От выбора операционной системы зависит производительность работы пользователя, степень защиты его данных, необходимое аппаратное и программное обеспечение.
На персональных компьютерах типа IBM PC чаще всего применяются следующие операционные системы:
1. Операционная система MS DOS фирмы Microsoft или совместимые с ней операционные системы – PC DOS фирмы IBM или Novell DOS фирмы Novell;
2. Операционная система Windows 98, Windows NT Workstations или самая новая операционная система Windows 2000 фирмы Microsoft;
3. Операционная система OS/2 Warp одной из версий фирмы IBM;
4. Операционная система Unix или одна из ее модификаций Linux, FreeBSD и т.д.
Помимо операционной системы к системному программному обеспечению относят также драйверы, программы-оболочки, вспомогательные программы или утилиты.
Драйверы
являются важнейшим классом системных программ, поскольку они расширяют возможности операционной системы, позволяя ей работать с новыми внешними устройствами. Обычно операционная система содержит некоторый набор драйверов, но чаще всего драйверы поставляются разработчиками новых устройств и контроллеров.
Программы-оболочки
обычно представляют собой более удобные средства для общения с ЭВМ, чем стандартные средства ОС. Так для MSDOS это – NortonCommander, для Windows – NortonNavigator и т.д. Причем, чаще всего программы-оболочки не стараются заменить операционную систему, а наоборот пополняют ее новыми, более удобными функциями.
Утилиты
или программы обслуживания объединяют большое количество системных программ вспомогательного назначения:
1. Антивирусные программы
– основные функции которых - предотвращение заражения компьютера вирусами и ликвидация последствий таких заражений. Различают антивирусные программы детекторы, вакцины, полифаги - в зависимости от их способов борьбы с компьютерными вирусами. В нашей стране наибольшее распространение получили программы AidsTest и Dr.Web.
2.
Программы архиваторы
или упаковщики позволяют создавать резервные копии файлов, путем уменьшения их размеров за счет выполнения сжатия, уплотнения информации. Наиболее распространены Arj, Zip, Rar для операционных систем MSDOS и Windows.
3.
Программы для диагностики технического состояния
компьютера, которые позволяют проверять исправность всех устройств компьютера;
4.
Программы для оптимизации дисков
позволяют обеспечить более быстрый доступ к информации на диске за счет оптимизации размещения данных на диске;
5. Программы ограничения доступа
позволяют защитить хранящиеся на компьютере данные от несанкционированного доступа.
Система программирования
есть комплекс средств, обеспечивающих автоматизацию программирования и отладки программ. К системе программирования относят библиотеку стандартных подпрограмм, языки программирования и трансляторы, а также отладочные программы. Эти средства предназначены для обеспечения и повышения труда программистов.
Программные компоненты системы программирования выполняются под управлением операционной системы наравне с прикладными программами пользователей. Эти системы обычно включают компилятор
, осуществляющий преобразование программ на языке программирования в программу в машинных кодах, или интерпретатор
, осуществляющий непосредственное выполнение программы на языке программирования высокого уровня, редактор текстов программ, библиотеки подпрограмм, отладчики и вспомогательные программы.
Для персонального компьютера имеются системы программирования для всех популярных языков программирования, таких как Си, С++, Паскаль, Фортран, Бейсик и т.д. В настоящее время стали распространяться системы программирования с языка Java, позволяющие создавать программы-сценарии для Web-страниц в Интернет.
Особым классом систем программирования являются системы разработки приложений типа клиент-сервер
. Они позволяют быстро создавать информационные системы для подразделений и предприятий, с использованием средств визуального программирования. Как правило, эти системы позволяют работать с самыми разными базами данных. Наиболее популярными являются системы Delphi, VisualBasic, C-Builder, Sybase, PowerBuilder, SQLWindows.
Прикладное программное обеспечение
насчитывает в своем составе сотни тысяч программ для различных применений. Из всего многообразия прикладных программ можно вычленить следующие группы программ, получивших наибольшее распространение:
1.
Редакторы документов
, позволяющие подготавливать различные документы высокого качества. Они полностью заменили пишущую машинку, да еще позволили дополнительно выполнять целый ряд функций по подготовке высококачественных документов: управление шрифтами, абзацами, перенос слов, проверка орфографии, вставка рисунков, диаграмм и т.д. Наиболее популярны для ОС MSDOS ЛЕКСИКОН, MicrosoftWord, WordPerfect, а для Windows – MicrosoftWord, CorelWordPerfect, WordPro фирмы Lotus, JustWrite фирмы Symantec.
2. Табличные процессоры
, представляющие документ в виде таблицы из прямоугольных клеток, в которых могут храниться числа, формулы, пояснительные тексты. Все распространенные табличные процессоры позволяют производить перевычисление значений, строить различные графики, включать в таблицы рисунки, использовать макрокоманды, работать с базами данных. Наибольшей популярностью пользуются Microsoft Excel, Lotus 1-2-3, Quattro Pro.
3. Издательские системы
предназначены для подготовки рекламных буклетов, оформления газет, журналов, книг. Их основная функция – верстка, т.е. размещение текста, рисунков и пр. на страницах документа. Наибольшую популярность получили издательские системы – PageMaker фирмы Adobe и QuarkXpress фирмы Quark.
4. Программы подготовки презентаций
могут оформлять слайды для презентаций, помещая туда красивые диаграммы, рисунки, надписи, включать звуковое сопровождение и показывать презентации на компьютере. Наиболее известны программ – PowerPoint фирмы Microsoft, HarvardGraphics фирмы SoftwarePublishing.
5. Графические редакторы
, позволяющие работать с графическими объектами – рисунками, фотографиями. Наиболее известны - Adobe PhotoShop, Corel Draw.
6.
Анимационные программы
позволяют создавать трехмерные движущиеся модели объектов, создавать анимационные фильмы. Примером может служить программа 3D Studio фирмы Autodesk.
7.
Программы для создания компьютерного видео
при наличии соответствующего оборудования производить монтаж видеофильмов, накладывать титры, видеоэффекты. Пример такой программы – Adobe Premiere.
8.
Бухгалтерские программы
позволяют вести бухгалтерский учет, подготавливать финансовую отчетность. Наибольшее распространение получили – 1С-бухгалтерия, Инфо-Бухгалтер. Для предприятий с большим объемом хозяйственных операций, многие из которых уже не относятся к бухгалтерскому учету – складской учет, учет торговых операций, контроль за выполнением договоров, управленческий учет, финансовый анализ деятельности предприятия, целесообразно применение программных комплексов: Парус, Инфософт, Инфин и т.д.
9.
Правовые базы данных
содержат тексты нормативных документов и предоставляют возможности поиска и распечатки, например, Гарант, Кодекс, Юрисконсульт.
10.
Персональные информационные менеджеры
позволяю назначать разовые и повторяющиеся мероприятия, напоминать о делах, встречах, облегчают звонки по телефону. Пример таких программ: Lotus Organizer, Sidekick фирмы Starfish Software.
11.
Программы планирования
позволяют составлять план-графики работ, например, MicrosoftProject, TimeLine фирмы Semantic.
12.
Программы распознавания символов
позволят вводить с помощью сканера напечатанные тексты, рисунки, графики, фотографии. У нас получила наибольшее распространение программа FineReader фирмы Бит.
13.
Программы переводчики
позволяют переводить с одного языка на другой с более менее пристойным качеством, например, Stylus фирмы ПроМТ, Сократ фирмы АрсеналЪ.
14.
Программы словари
(Мультилекс фирмы МедиаЛингва, Контекст фирмы Информатик, Лингво фирмы Бит) – это электронные версии обычных словарей с некоторыми дополнительными возможностями.
15.
Системы управления базами данных
позволяют управлять большими информационными массивами. Так, весьма мощны и удобны в использовании LotusApproach, DataEase, Paradox, FoxPro, Access. Для создания больших и многопользовательских информационных систем типа клиент-сервер
широко используются Oracle, MicrosoftSQLServer, SybaseSQLServer, Iformix.
16.
Системы автоматического проектирования
(САПР) позволяют осуществлять черчение и конструирование различных предметов и механизмов с помощью компьютера. Среди систем малого и среднего класса наиболее популярна система AutoCad фирмы AutoDesk. Системы более высокого класса включают средства трехмерного моделирования, процессов механобработки, программирования оборудования с числовым программным управлением. Здесь можно отметить системы «Компас» фирмы Аскон и T-FlexCAD фирмы Топсистемы.
17.
Программы для Интернет.
Сюда включается великое множество программ по поиску информации, осуществления связи в реальном времени, созданию Web-страниц, всевозможные броузеры и средства для электронной почты. Интернет непрерывно развивается, с ним получает мощнейшее развитие и вся программная индустрия для Интернет.
Большинство программ для персонального компьютера распространяется на коммерческой основе, но имеются и другие формы распространения программ. Так получила большое распространение бесплатная форма распространения программ (freeware) сети Интернет и электронных досок объявлений (BBS). Промежуточное положение между бесплатными и коммерческими программами занимают условно бесплатные программы (shareware). Их можно получить и опробовать некоторое время бесплатно, но при систематическом их использовании необходимо уплатить разработчику определенную (чаще всего небольшую) сумму. В наше использование чаще всего попадают пиратские
копии программ (незаконные, взломанные копии коммерческих и условно бесплатных программ), не имеющие ни документации, ни гарантии правильной работы.
Контрольные вопросы
1. На какие части делится программное обеспечение для персонального компьютера?
2. Что такое системное программное обеспечение? Какое программное обеспечение оно включает?
3. Что такое система программирования?
4. Какие классы наиболее распространенного прикладного программного обеспечения вы знаете?
5. Каковы основные функции операционной системы?
6. Приведите примеры наиболее распространенных операционных систем для персонального компьютера?
7. В чем отличие компилятора от интерпретатора?
8. Что такое технология клиент-сервер?
9. Приведите примеры наиболее распространенных антивирусных программ.
10. Дайте классификацию антивирусных программ.
11. Каково назначение программ-архиваторов?
12. Какие основные способы распространения программного обеспечения Вы знаете?
Алгоритмы. Определение и свойства алгоритмов
Широкая известность понятия алгоритма в наше время обусловлена развитием и широким применением электронно-вычислительной техники. Использование ЭВМ способствовала уяснению того, что разработка алгоритма – необходимый этап в процессе решения задачи на ЭВМ и что в связи с этим алгоритмы представляют самостоятельную ценность как интеллектуальные ресурсы общества.
Понятие алгоритма, относящиеся к фундаментальным концепциям информатики, возникло задолго до появления ЭВМ и стало одним из основных понятий математики.
Слово «алгоритм» произошло от имени среднеазиатского (узбекского) математика аль-Хорезми (IХ в.) и использовалось в математике для обозначения правил выполнения четырех арифметических действий: сложения, вычитания, умножения, деления. В настоящее время понятие алгоритма используется не только в математике. Его применяют во многих областях человеческой деятельности, например говорят об алгоритме управления производственным процессом, алгоритме игры в шахматы, алгоритме пользования бытовым прибором, алгоритме поиска пути в лабиринте, алгоритме управления полётом ракеты и т.п.
Для пояснения понятия «алгоритм» важное значение имеет определение понятия «исполнитель алгоритма». Алгоритм формулируется в расчете на конкретного исполнителя, например человека, специально дрессированное животное, особую машину – автомат и т.д. Алгоритм является руководством к действию для исполнителя, поэтому значение слова «алгоритм» близко по смыслу к значению слов «указание» или «предписание». Можно сказать, что алгоритм
– понятное и точное предписание (указание) исполнителю совершить определённую последовательность действий для достижения указанной цели или решения поставленной задачи. Сказанное не является определением в математическом смысле, а лишь отражает интуитивное понимание алгоритма, сложившееся за долгие годы.
Пример
1
. Пусть имеется текст на русском языке, подготовленный специальным образом, который заканчивается специальным символом @, больше нигде в тексте не встречающемся. Необходимо подсчитать число гласных букв в данном тексте.
Для решения этой задачи можно предложить такой способ подсчета числа гласных букв: читать последовательно символ за символом и каждый раз, когда очередной символ есть гласная буква русского алфавита, прибавлять к счетчику единицу (предполагается, что исполнитель данного алгоритма умеет различать гласные и не гласные буквы). Счет начинать с нуля и продолжать до тех пор, пока не будет прочитан символ @, обозначающий конец текста. Приведенное выше описание дает лишь идею алгоритма, но, чтобы превратить его в понятное и точное предписание исполнителю, его необходимо уточнить.
Во–первых, объектами алгоритма являются символы текста и числа. Над символами текста производятся операции чтения, поиска следующего символа, сравнения символа с символом @ и сравнение символа с одной из гласных букв русского алфавита. Над числами производится операция прибавления единицы.
Во–вторых, символы текста читаются последовательно один за другим, начиная с первого символа до символа @ включительно. Чтобы не ошибиться при чтении, будем предполагать, что наш абстрактный исполнитель имеет в своем распоряжении указатель, который можно перемещать по тексту и который указывает на очередной читаемый символ. Поэтому поиск следующего символа сводится к перемещению указателя на следующий по порядку символ текста.
В–третьих, счет числа гласных букв начинается с нуля, поэтому до начала работы счетчик числа гласных должен содержать нуль.
Учитывая эти замечания, сформулируем алгоритм в виде такой последовательности действий:
1. Записать в счетчик 0.
2. Установить указатель на первый символ текста.
3. Если символ не есть @, то перейти к п.4, иначе перейти к пункту 7.
4. Если символ – гласная буква русского алфавита, то увеличить счетчик на единицу.
5. Перевести указатель на следующий символ текста.
6. Перейти к п.3.
7. Взять число, находящееся в счетчике, в качестве ответа. Стоп.
Обратим внимание на основные особенности (свойства
) алгоритма.
1
. Алгоритм имеет некоторое число входных
величин – аргументов
, задаваемых до начала работы (в приведенном выше примере входными данными являются символы текста и возможно набор гласных букв).
Цель выполнения алгоритма – получение результата
(результатов
), имеющего вполне определенное отношение к исходным данным.
В данном примере результат – число, обозначающее число гласных букв в исходном тексте.
Для алгоритма можно брать различные наборы входных данных, т.е. применять один и тот же алгоритм для решения целого класса однотипных задач, различающихся исходными данными. Это свойство алгоритма обычно называют массовостью
. Рассмотренный в примере алгоритм применим к различным текстам на русском языке. Вместе с тем существуют и такие алгоритмы, которые применимы только к единственному набору исходных данных. Например, для алгоритма пользования автоматическим турникетом при входе в метро существует единственный вариант исходного данного – тридцати копеечный жетон. Поэтому понятие массовости требует уточнения. Можно считать, что для каждого алгоритма существует свой класс объектов, допустимых в качестве исходных данных. Тогда свойство массовости
означает применимость алгоритма ко всем объектам этого класса. А количество объектов класса (конечное или бесконечное) – свойство самого класса исходных данных.
2
. Чтобы алгоритм можно было выполнить, он должен быть понятен исполнителю. Приведенный в примере алгоритм подсчета гласных букв может быть понятен человеку, знающему русский язык. Чтобы этот алгоритм мог быть также выполнен человеком, не знающим русского языка, необходимо записать алгоритм на языке понятном исполнителю, и сообщить ему дополнительные сведения: перечислить явно гласные буквы русского алфавита.
Понятность
алгоритма
означает знание исполнителя о том, что надо делать для исполнения этого алгоритма.
Таким образом, при формулировке алгоритма необходимо учитывать возможности и особенности исполнителя, на которого рассчитан алгоритм.
3
. Алгоритм представлен в виде конечной последовательности шагов. Говорят, что алгоритм имеет дискретную структуру
.
Следовательно, его исполнение расчленяется на выполнение отдельных его шагов, выполнение каждого очередного шага начинается после завершения предыдущего.
4
. Выполнение алгоритма заканчивается после выполнения конечного числа шагов. При выполнении алгоритма некоторые его шаги могут повторяться многократно. В рассмотренном выше примере многократно повторяются шаги с третьего по шестой. Однако выполнение алгоритма все же закончится за конечное число шагов, так как текст имеет конечную длину и в нем имеется символ @. При чтении этого символа будет выполнен седьмой шаг алгоритма, завершающий его выполнение.
В математике существуют вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности
. Так, можно сформулировать процедуру вычисления числа Пи. Такая процедура описывает бесконечный процесс и никогда не завершится. Если же ее искусственно прервать, например ввести условие завершения процесса вычислений вида: «Закончить вычисления после получения N десятичных знаков числа Пи», то получится алгоритм вычисления N десятичных знаков числа Пи. На этом принципе основано получение многих вычислительных алгоритмов: строится бесконечный, сходящийся к искомому решению процесс. Он обрывается на некотором шаге, и полученное значение принимается за приближенное решение рассматриваемой задачи. При этом точность приближения зависит от числа шагов.
5
. Каждый шаг алгоритма должен быть четко и недвусмысленно определен и не должен допускать произвольной трактовки исполнителем. При исполнении алгоритма исполнитель должен действовать строго в соответствии с его правилами и у него не должно возникать потребности предпринимать какие-нибудь действия, отличные от предписанных алгоритмом. Иными словами, алгоритм рассчитан на чисто механическое исполнение
. Эта очень важная особенность означает, в частности, что если один и тот же алгоритм поручить для исполнения разным исполнителям, то они придут к одному и тому же результату, лишь бы эти исполнители понимали алгоритм. Именно определенность
алгоритма дает возможность поручить его исполнение автомату, не обладающему «здравым смыслом».
B приведенном выше примере, действие перемещения указателя на следующий символ достаточно точно определено, если текст расположен на длинной узкой ленте и вытянут в одну строку (например, напечатан на узкой телетайпной ленте). Если же текст разбит на строки и страницы (т.е. имеет сложную структуру), то действие перемещения указателя на следующий символ уже не является столь очевидным. В этом случае необходимы указания, как поступать исполнителю, когда закончится очередная строка или очередная страница текста.
Таким образом, формулировка алгоритма должна быть так точна, чтобы полностью определять все действия исполнителя.
6
. Каждый шаг алгоритма должен быть выполнен точно и за конечное время. В этом смысле говорят, что алгоритм должен бытьэффективным
,
т.е. действия исполнителя на каждом шаге исполнения алгоритма должны быть достаточно простыми, чтобы их можно было выполнить точно и за конечное время. Поэтому, например, указание вида: «Если любое целое число, большее 6, можно представить в виде суммы трех простых чисел, то счетчик увеличить на 1, иначе счетчик уменьшить на 1» – неэффективно, так как не известен способ доказательства истинности или ложности утверждения, содержащегося в нем. Следовательно, исполнитель не может выполнить этот шаг алгоритма, пока не найдет соответствующего доказательства.
Обычно отдельные указания исполнителю, содержащиеся в каждом шаге алгоритма, называют командами
. Таким образом, эффективность алгоритма связана с возможностью выполнения каждой команды за конечное время. Исполнители отличаются друг от друга своими возможностями, т.е. репертуаром команд, которые они «понимают» и могут выполнять. Совокупность команд, которые могут быть выполнены конкретным исполнителем, называется системой команд исполнителя
. Следовательно, алгоритм, рассчитанный на конкретного исполнителя, должен быть сформулирован так, чтобы содержать только те команды, которые входят в систему команд этого исполнителя.
Кроме того, эффективность
означает, что алгоритм может быть выполнен не просто за конечное, а за разумное конечное время (обычно важно, чтобы задача по разработанному алгоритму решалась как можно быстрее). Вот почему при разработке алгоритмов должны учитываться и возможности конкретных физических исполнителей алгоритма.
Приведенные выше комментарии поясняют интуитивное понятие алгоритма, но само это понятие не становиться от этого более четким и строгим. Тем не менее математики долгое время довольствовались этим понятием. Лишь с выявлением алгоритмически неразрешимых задач. т.е. задач, для решения которых невозможно построить алгоритм, появилось настоятельная потребность в построении формального определения алгоритма, соответствующего известному интуитивному понятию.
Интуитивное понятие алгоритма в силу своей расплывчатости не может быть объектом математического изучения, поэтому для доказательства существования или не существование алгоритма решения задачи было необходимо строгое формальное определение алгоритма.
Построение такого формального определение было начато с формализации объектов (операндов) алгоритма, так как в интуитивном понятии алгоритма его объекты могут иметь произвольную природу. Ими могут быть, например, числа, показания датчиков, фиксирующих параметры производственного процесса, шахматные фигуры и позиции и т.п. Однако, предполагая, что алгоритм имеет дело не с самими реальными объектами, а с их изображениями, можно считать, что операнды алгоритма
есть слова в произвольном алфавите. Тогда получается, что алгоритм преобразует слова в произвольном алфавите в слова того же алфавита. Дальнейшая формализация понятия алгоритм связана с формализацией действий над операндами и порядка этих действий. Одна из таких формализаций была предложена английским математиком А.Тьюрингом в 1936 году, который формально описал конструкцию некоторой абстрактной машины (машины Тьюринга) как исполнителя алгоритма и высказал тезис о том, что всякий алгоритм может быть реализован соответствующей машиной Тьюринга.
Мы будем придерживаться неформального определения алгоритма, формулируемого следующим образом:
Алгоритм
- это упорядоченная последовательность указаний, выполнение которой приводит от исходных данных к требуемому результату.
Другими словами алгоритм это план решения задачи, записанный в виде последовательности указанийили групп указаний.
Приведем пример алгоритма Евклида, выполняя который определяется общий наибольший делитель двух положительных целых чисел a
и b.
Пример 2.
Алгоритм Евклида, нахождения наибольшего общего делителя двух положительных чисел.
1. Проверитьa>
b.
Если да, то перейти к указанию 2, иначе – к указанию 3.
2. Взять за новое значение a
разностьa-
b
. Перейти к указанию 1.
3. Проверить b>
a
. Если да, то перейти к указанию 4, иначе - к указанию 5.
4. Взять за новое значение b
разность b-
a
, перейти к указание 1.
5. За результат взять последнее значение a (
b)
. Перейти к указанию 6.
6. Закончить процесс.
В приведенном выше алгоритме, предполагается, что его может выполнить любой человек или вычислительная машина, который умеет выполнять операции сравнения и вычитания двух чисел. Напомним, что в школе наибольший общий делитель определяется как произведение общих простых делителей чисел. В данном алгоритме о произведении и понятии делителя числа нет даже упоминания и, тем не менее, следуя ему, всегда определяется наибольший общий делитель двух целых положительных чисел. Это факт говорит о том, что получить результат можно разными способами с применением операций, которые, на первый взгляд, не имеют к решаемой проблеме никакого отношения, что позволяет среди всех возможных вариантов решения задачи, искать наиболее эффективный. В дальнейшем рассматриваются алгоритмы для вычислительных машин. Современные компьютеры с мощным программным обеспечением могут выполнять различные операции: от простых арифметических операций, производимых над двумя числами до решения сложных задач из многих сфер деятельности людей. Если на компьютере имеется программа, позволяющая решить требуемую задачу, то алгоритм решения такой задачи сводится к описанию процесса ввода исходных данных, обращения к требуемой программе и получения результатов в нужном виде. В тоже время для очень многих простых задач нет готовых программ их решения. По-видимому, нельзя на все случаи, да и нет такой необходимости, хранить в памяти необходимые программы. Но практически все программные системы, применяемые на компьютерах, имеют реализованные языки программирования, позволяющие с небольшими затратами составить самостоятельно программу решения довольно сложной задачи. Для реализации такой возможности надо уметь составлять алгоритмы и знать правила (синтаксис) записи указаний на алгоритмическом языке. В дальнейшем мы предполагаем, что «машина умеет» выполнять все арифметические операции, операции сравнения, логические операции, а также может вычислять практически все элементарные функции. Кроме этого она может ввести в память необходимые данные, а также напечатать или вывести на дисплей результаты.
Таким образом, алгоритмы должны обладать такими основными свойствами: массовостью (результативностью); понятностью; дискретностью; конечностью; определенностью; эффективностью
.
Среди других свойств алгоритмов, следует отметить оптимальность и элегантность
. Правда понятие оптимальности в алгоритмах имеет компромиссный характер, так как можно оптимизировать количество необходимых для получения результата операций, или объем требуемой памяти, или скорость выполнения и даже понятность алгоритма. Поэтому, составляя алгоритм, следует определиться, что надо оптимизировать в первую очередь и как этого достичь. Составление алгоритмов является не только трудоемким процессом, но и, в некотором смысле искусством, поэтому так ценятся хорошие элегантные алгоритмы. Составление алгоритма предполагает от составителя следующего:
· Ясное понимание хода решения задачи, а лучше нескольких вариантов, получения решения, начиная с ввода (определения) исходных данных.
· Знание возможностей исполнителя по выполнению тех указаний, с помощью которых записывается данный алгоритм.
· Если алгоритм составляется под написание программы на алгоритмическом языке, то желательно для составителя алгоритма иметь хорошее представление о синтаксисе языка и наборе операторов языка.
Виды и способы записи алгоритмов
Различают три основных вида алгоритмов:
А) линейные; -
Б) разветвляющиеся;
В) циклические.
Алгоритм называется линейным
, если его указания выполняются последовательно в том порядке, в котором они записаны.
Алгоритм— разветвляющийся
, если в процессе решения требуется проверять некоторые условия и в зависимости от их выполнения или невыполнения, выполняются те или иные группы указаний.
Алгоритм -
циклический
, если в нем имеется хотя бы одна группа указаний, которая в процессе выполнения повторяется.
Для реальных задач, как правило, алгоритмы обладают всеми тремя видами, т.е. в них существуют и линейные группы указаний, и разветвляющиеся участки, и циклические группы. Существует несколько способов записи алгоритмов, которые применяются при составлении программ для решения задач на ЭВМ:
· операторная схема алгоритма;
· блок-схема алгоритма;
· программа, запись алгоритма на алгоритмическом языке.
Операторные схемы алгоритмов
Группа указаний, которая имеет свой законченный смысл, называется оператором.
Операторы мы будем обозначать большими буквами с индексами, Ai
и т.п. Операторы классифицируется следующим образом.
1) По структурным свойствам:
а) простой; б) составной; в) циклический.
2) По характеру выполняемых действий:
а) арифметический; б) логический; в) оператор перехода (передачи управления); г) оператор ввода информации в машину; д) оператор вывода информации из машины; е) оператор обмена информацией; ж) оператор остановки и др.
Почти каждый алгоритм можно разделить на несколько групп указаний различных по назначению, т.е. операторов. Обозначив, операторы буквами, и указав последовательность выполнения операторов стрелками,мы получим операторную схему алгоритма.
Пример 3
. Пусть требуется вычислить величины:
(1)
(2)
Исходными данными для решения задачи является значения переменных x
,
a
. Обозначим оператор ввода исходных данных через B
1
.
Оператор вывода результата (значений y
,
z
) через –
B
2
.
Оператор вычисления значения y
по формуле (I) - через A
1
. Оператор вычисляющий z-
по формуле (2), через – A
2
. Оператор остановки процесса решения через O
1
. Переход между операторами обозначим стрелками. Тогда операторную схему алгоритма решения данной задачи можно представить следующим образом:
т.е. вначале следует ввести значения исходных данных –x
,
a
(оператор B
1
);
затем вычислить значение y
(оператор A
1
); вычислив значение y,
требуется вычислить значение z
(оператор A
2
); напечатать результат - значения y
,
z
(оператор B
2
) и остановить процесс – оператор О1
.
Если операторы выполняются в том порядке, в котором они записаны, то стрелки можно опустить, т.е. операторную схему можно записать в следующем сокращенном виде: .
Это пример линейного алгоритма. Приведем пример разветвляющегося алгоритма.
Пример 4
.
Написать операторную схему алгоритма по определению корней квадратного уравнения при . Опишем процесс (план) решения задачи:
1) вычисляем значение дискриминанта, ;
2) сравниваем значения дискриминанта с нулем;
3) если , то вычисляем x
1
,
x
2
по формулам
; ,
печатаемполученные значения,
и останавливаем процесс решения;
4) если,
то выводим фразу«Действительных корней нет»
иостанавливаем процесс решения.
Запишем теперь операторную схему,
Обозначим:
B1
- оператор ввода значений a, b, c;
A1
- оператор вычисляющий дискриминант D;
P1
- оператор проверяющий условие D<0;
A2
- оператор вычисляющий значение x1;
A3
- оператор вычисляющий значение x2;
B2
- оператор вывода значений x1
, x2
;
B3
- оператор вывода фразы «Действительных корней нет»;
O1
, O2
- операторы остановки.
|
Тогда операторную схему алгоритма вычисляющего значение корней уравнения можно записать следующим образом:
|
A2
A3
B2
O1
B1
A1
P1
B3
O2
Циклические алгоритмы
Как было указано выше, циклическим алгоритмом является тот, у которого имеется хотя бы одна группа указаний, которая повторяется в процессе решения. Такая группа указаний называется циклическим оператором.
Различают два вида циклических операторов:
1) Циклический оператор с заданным количеством повторений;
2) Итерационный циклический оператор.
|
Схематически оба эти операторы имеют одинаковую структуру, которую можно изобразить следующим образом:
A0
A1
P1 (продолжение)
A
0
-
оператор или операторы подготовки цикла
.
A1
-
группа основных операторов
, которые требуется повторить. Эту группу операторов обычно называют телом цикла.
Р1
- условный оператор
, который проверяет некоторое условие и если оно выполняемся, то заставляет повторяться еще операторы тела цикла, если нет, то передает управление на продолжение алгоритма.
Управление повторением оператора цикла осуществляется с помощью некоторой переменной, которую называют параметром цикла
.
В циклическом операторе первого вида параметр цикла изменяется от одной границыL1
до второй границы L2
с некоторым постоянным интервалом (шагом) h за каждым повторением. В этом случае легко вычислить количество повторений k:
В итерационном цикле параметр цикла также меняет свое значение при повторениях, но интервал изменения может быть не задан заранее и выбираться в процессе повторений, а с другой стороны оператор Р ,
может проверять условие, момент невыполнения, которого заранее нельзя предсказать.
В операторе A0
осуществляется подготовка цикла, т.е. параметр цикла и величины, которые изменяются в цикле, этими операторами приводятся в исходные значения.
Оператор P может стоять после тела цикла, как в приведенной выше схеме, или до основных операторов, т.е. перед A1
. В зависимости от этого циклические операторы разделяют на два типа: циклический оператор с постусловием
и циклический оператор с предусловием
. Принципиальное отличие этих операторов состоит в том, что в операторе с постусловием группа основных операторов выполнится хотя бы один раз, а в операторе с предусловием тело цикла может ни разу не выполниться.
Если некоторый цикл расположен внутри другого цикла, то говорят, что имеется двойной цикл
. При этом цикл, расположенный внутри, называется внутренним, а цикл, который охватывает его, внешним циклом. При двойном цикле при одном изменении .параметра внешнего цикла, параметр внутреннего цикла пробегает все свои значения. Могут быть тройные и большего количества уровней цикли.
Относительно расположения вложенных циклов существуют такие правила:
1. Внутренний цикл должен быть строго внутренним.
2. Не допускается пересечений циклов.
Для передач управления из цикла в цикл приняты следующие правила:
1. Передача управления в цикл может быть осуществлена только через его начало;
2. Выход из цикла может быть осуществлен до окончания цикла;
3. Передачи управления внутри цикла допускаются.
Операторные схемы являются довольно компактным средством изображения процесса решения задачи. Но они имеют один довольно существенный недостаток, который заключается в малой наглядности выполняемых действий. В силу этого, в настоящее время, операторные схемы, для описания алгоритмов, применяются довольно редко. Более распространенными являются блок-схемы алгоритмов. Поэтому приводить пример циклического алгоритма в виде операторной схемы мы не будем, а приведем его в виде блок-схемы, к рассмотрению которых мы переходим.
Блок-схема алгоритма
Блок-схемой алгоритма
называется геометрическое представление операторной схемы алгоритма, в котором операторы изображаются в виде плоских геометрических фигур, а последовательность их выполнения указывается стрелками
.
При построении блок-схемы алгоритма принята стандартная система геометрических фигур, применяемых для различных видов операторов. В таблице 1 приведены основные операторы и их геометрическое представление, соответствующее принятому стандарту.
Таблица 1. Основные операторы и их геометрическое представление, соответствующее принятому стандарту.
Приведем пример блок-схемы алгоритма начисления заработной платы по заданной ставке с учетом вычета подоходного налога, величина которого определяется по тарифной сетке (заметим, что пример является условным, и поэтому цифры и сама тарифная сетка не соответствуют реальности).
Пример 5.
Условие задачи опишем следующим образом:
Пусть х
– величина произвольной ставки. В зависимости от конкретного значения х
, начисляется подоходный налог у
, по следующему правилу (тарифной сетке):
· Если х
меньше или равен а,
то подоходный налог не начисляется, т.е. у
=0.
· Если х
больше а,
но меньше или равен b
,
то подоходный налог равен 10% от х.
· Если х
больше b
,
но меньше или равен c
,
то подоходный налог равен 15% от х.
· Если х
больше c
,
то подоходный налог равен 20% от х.
Значение заработной платы, с учетом вычитаемого подоходного налога, будет z
=
x
–
y
.
Если описанный процесс обозначить математическими формулами, то будем иметь следующую запись:
,
.
Исходными данными для рассматриваемой задачи являются значения x
,
a
,
b
,
c
. Результатом будет значение z
.
Заметим, что в зависимости от требуемого, результатом может быть величина подоходного налога у
и заработная плата z
.
Выводить на печать можно также вместе с результатами и значение х.
Блок схема алгоритма решения данной задачи представлена на рис. 4.
Алгоритмы обладают некоторыми свойствами, которые позволяют облегчить их составление для различных задач. Во-первых, многие различные по смыслу задачи, имеют сходные алгоритмы. Во-вторых, сложные алгоритмы имеют блоки (участки) алгоритмы которых известны и, при составлении общего алгоритма, достаточно вставить такой блок в свою схему, возможно с небольшими изменениями. В третьих, в сложных алгоритмах, как правило, существуют сходные участки (блоки), которые можно переписать практически без изменений. В четвертых, существует сравнительно небольшой набор, стандартных по конструкции, операторов, с помощью которых строятся сложные алгоритмы. Построение алгоритма подобно возведению здания из набора типовых конструкций.
Рис. 4. Блок-схема задачи начисления подоходного налога.
Наиболее часто используемым методом построения блок-схем алгоритмов является метод последовательной декомпозиции. Суть его заключается в том, что вначале строят укрупненную схему алгоритма, каждый блок которой может представлять решение довольно сложной задачи. Затем последовательно, шаг за шагом, производят разукрупнение блоков до последовательности указаний (операторов), которые легко можно перевести в программу на алгоритмическом языке.
Пример 6.
Проиллюстрируем метод декомпозиции на составлении блок-схемы алгоритма решения квадратного уравнения:
Укрупненная схема алгоритма следующая:
1. Исходными данными для задачи являются значения коэффициентов уравнения a
,
b
,
c
. Разукрупнять блок «Ввод исходных данных
» не надо, т.к. этот ввод можно осуществить одним оператором.
2. Блок «Нахождение решения уравнения
». Для определения решения уравнения надо вначале вычислить дискриминант . Затем проверить знак дискриминанта. Если дискриминант больше нуля, то уравнение имеет два корня, которые вычисляются по формулам:
; .
В этом случае результатом будет значения этих корней.
Если дискриминант равен нулю, то уравнение имеет один корень, который вычисляется по формуле: . Это значение и будет результатом в этом случае.
Если дискриминант меньше нуля, то уравнение не имеет действительных корней. В этом случае результатом будет фраза «Уравнение не имеет действительных корней».
Декомпозиция этого блока следующая:
3. Блок «Вывод результатов
». В зависимости от значения дискриминанта, мы можем получить три результата. Поэтому этот блок по сути состоит из трех разных операторов вывода:
Приведем примеры циклических алгоритмов
Пример 7.
Составим блок-схему алгоритма начисления процентов по вкладам.
Рис. 5. Блок-схема алгоритма начисления процентов по вкладам.
Описание постановки задачи:
Имеется n
записей z
1
,
z
2
,…
zn
, характеризующих вклады. Среди характеристик имеются следующие: si
– величина вклада; di
– дата последнего начисления процентов. Если по вкладу не было начислений процентов, то эта дата совпадает с датой вложения. Требуется произвести начисление процентов из условия p
процентов годовых. Начисление проводится в конце некоторого периода (года, квартала) на дату, которую обозначим D. Кроме начислений по каждому вкладу, требуется определить общую сумму начисленных процентов. Суть алгоритма заключается в следующем: просматриваем записи, поочередно, начиная с первой. Для каждой записи находим количество дней, прошедших после последнего начисления процентов. Пусть это количество равно ki
для i
-ой записи. Тогда соответствующая сумма процентов будет определяться по формуле:
Эту сумму добавляем к si
и в общую сумму начисленных процентов, которую обозначим Sp
. Блок-схема алгоритма представлена на рис.3.
Пример 8.
Блок–схема алгоритма сортировки. (Метод «Пузырек»).
Пусть а1
,а2
,…,а
n
есть массив записей, описывающих некоторое множество объектов. Например, а
i
– анкета i
-го работника учреждения. Требуется упорядочить множество элементов а
i
по возрастанию признака pi
, например, по возрасту или стажу работы.
Для сортировки используем алгоритм «Пузырек». Суть его состоит в том, что вначале просматриваются поочередно все соседние пары элементов (ai
-1
,
ai
, i
=2,3,…,
n
) и сравниваются признаки, по которым ведется сортировка. Если pi
-1
<
pi
, то пара пропускается, и переходят к просмотру следующей пары (ai
,
ai
+1
). Если pi
-1
>
pi
, то в такой паре меняются местами элементы ai
-1
и ai
. После просмотра последней пары, элемент обладающий наибольшим значением признака сортировки, автоматически переместится (всплывет) на последнее место. Затем просматриваются все пары без последней (an
-1
,
an
). За каждым таким шагом, количество просматриваемых пар уменьшается на единицу. Просмотр заканчивается, когда остается одна пара.
Введем обозначения:
n
– количество элементов в множестве. (входной параметр).
a
1
,…,
an
– элементы (записи) множества (входной массив и он же результат).
p
1
,…,
pn
– значения признака, по которому производится сортировка.
k
–
граница просмотра на каждом шаге (k
=2,…,
n
).
i
- текущий номер просматриваемой пары (i
=2,…,
k
).
Блок-схема алгоритма представлена на рис.6.
Рис. 6. Блок-схема алгоритма сортировки, метод «Пузырек».
Пример 9
.
Написать блок-схему алгоритма произведения двух матриц (пример алгоритма с тройным циклом).
Рис. 7. Блок-схема алгоритма перемножения двух матриц
Напомним, что перемножать можно матрицы, у которых количество столбцов первой матрицы равно количеству строк второй матрицы. Пусть имеется матрица А
, размера n
xm
и матрица В
, размера m
xp
. Тогда произведением этих матриц будет матрица С=АВ
, элементы которой определяются по формуле:
(3)
Формировать матрицу С
будем по строкам. Вначале организуем цикл перебора строк. Внутри этого цикла будем перебирать столбцы. Внутри этих циклов организуем цикл накопления суммы произведений элементов i
–й строки матрицы А
,
на элементы j
-го столбца матрицы В
.
Контрольные вопросы
1. Что подразумевается под выражением: составить алгоритм решения задачи?
2. Важно ли понятие исполнителя при формулировании алгоритма?
3. Опишите свойства алгоритмов.
4. Что подразумевается под определенностью алгоритма?
5. Представляют ли ценность алгоритмы не обладающие свойством массовости? Почему?
6. Какие бывают виды алгоритмов?
7. Дайте определение оператора и опишите структурную классификацию операторов.
8. Опишите классификацию операторов по назначению.
9. Какие Вы знаете операторы цикла?
10. Опишите правила передачи управления внутрь цикла и из цикла.
11. Что такое операторная схема алгоритма?
12. Что такое блок-схема алгоритма?
13. Опишите основные конструкции, применяемые при составлении блок-схем алгоритмов.
14. Опишите структуры операторов цикла с предусловием и постусловием.
15. Какая структура обеспечивает в алгоритме ветвление по нескольким направлениям?
16. Какие методы конструирования алгоритмов Вы знаете?
17. Что такое последовательная декомпозиция алгоритма?
Контрольные задания
Задание 1
1. Дайте определение понятий «информация» и «экономическая информация».
2. Перевести два числа в двоичную систему счисления и найти их двоичную сумму:
145,875; 1581,5
3. Составить алгоритмы решения следующих задач:
1. Напечатать таблицу перевода температуры из градусов по шкале Цельсия (С) в градусы шкалы Фаренгейта (F) для значений от 15°С до 30°С с шагом 1°С. (Перевод осуществляется по формуле F=l,8C+32.)
2. В области 10 районов. Известны площади, засеваемые пшеницей, и средняя урожайность (ц/га) в каждом районе. Определить количество пшеницы, собранное в области, и среднюю урожайность по области.
Задание
1. Дайте определение информационных единиц: реквизита, документа.
2. Перевести два числа в шестнадцатеричную систему счисления и найти их шестнадцатеричную сумму:
4096; 1581,5
3. Составить алгоритмы решения следующих задач:
1. Напечатать таблицу соответствия между весом в фунтах и весом в кг для значений от 1 до 10 фунтов с шагом 1 фунт (1 фунт =400г).
2. Задан алфавитный список участников соревнований по плаванию и их результаты. Напечатать фамилии по убыванию результатов.
Задание 3
1. Какие основные операции выполняются над признаками и основаниями при обработке экономической информации?
2. Выполнить операцию умножения над двумя двоичными числами:
100011,1(2)
; 1101,01(2)
3. Составить алгоритмы решения следующих задач:
1.Дана ведомость результатов сдачи экзаменов по трем предметам в группе, состоящей из 25 студентов. Напечатать отличников.
2.Составить алгоритм, в котором определяется наименьший элемент матрицы А
(
n
,
m
),
а затем его значение вычитается из всех элементов этой матрицы.
Задание 4
1. Дайте определение составных единиц информации: показателя, массива.
2. Перевести числа в десятичную систему:
1000111,01(2)
; 1675, 4(8)
3. Составить алгоритмы решения следующих задач:
1. Вычислить приближенно площадь одной арки синусоиды, разделив отрезок от 0 до на 10 частей и суммируя площади десяти прямоугольников с основанием /10 и высотой, равной значению функции на правой границе каждого интервала.
2. Составить алгоритм определения сумм элементов столбцов матрицы А
(
n
,
m
).
Задание 5
1. В чем суть электронной информационной технологии решения задач?
2. Найти разность двух двоичных чисел:
10000100,1(2)
; 1011101,01(2)
.
3. Составить алгоритмы решения следующих задач:
1. Начав тренировки, спортсмен в первый день пробежал 10 км. Каждый следующий день он увеличивал дневную норму на 10 % от нормы предыдущего дня. Какой суммарный путь пробежит спортсмен за 7 дней?
2. Пусть имеется ряд наблюдений х1
,х2
,…,х
n
. Составить алгоритм для нахождения цепных приростов, цепных темпов роста, среднего прироста, среднего темпа роста.
Задание 6
1. Что является теоретической основой компьютерной информатики?
2. Перевести два числа в шестнадцатеричную систему счисления и найти их двоичную сумму:
145,875; 1581,5
3. Составить алгоритмы решения следующих задач:
1. Информация о количестве осадков выпадавших в течение месяца, и о температуре воздуха задана в виде двух массивов. Определить, какое количество осадков выпало в виде дождя, какое в виде снега. (Считать, что идет дождь, если температура воздуха >0°С).
2. Составить алгоритм определения наибольшего элемента матрицы А
(n,m)
с указанием его номера строки и столбца.
Задание 7
1. Что понимается под информационной моделью задачи?
2. Перевести два числа в шестнадцатеричную систему счисления и найти их шестнадцатеричную сумму:
2096; 681,5
3. Составить алгоритмы решения следующих задач:
1. Одноклеточная амеба каждые 3 часа делится на 2 клетки. Определить сколько клеток будет через 3, 6, 9, 12, ..., 24 часа.
2. Рост учеников класса представлен в виде массива. Рост девочек кодируется знаком “+”, рост мальчиков знаком “-”. Определить средний рост мальчиков.
Задание 8
1. Опишите основные конструкции, применяемые при составлении блок-схем алгоритмов.
2. Выполнить операцию умножения над двумя двоичными числами:
1101011,1(2)
; 101101,101(2)
3. Составить алгоритмы решения следующих задач:
1. В ЭВМ поступают результаты соревнований по плаванию для трех спортсменов. Выбрать и напечатать лучший результат. Решить задачу для следующих наборов данных: 1) 11,3; 10,6; 11; 2) 10; 10,9; 13; 3) 16; 18; 13.
2. Составить алгоритм определения наименьшего элемента матрицы А
(n,m)
с указанием его номера строки и столбца.
Задание 9
1. На какие части делится программное обеспечение для персонального компьютера?
2. Перевести числа в десятичную систему:
1А1F,1(16)
; 34075, 4(8)
3. Составить алгоритмы решения следующих задач:
1. Вводя в цикле по 4 оценки, полученные студентами и сессию, определить число неуспевающих студентов и средний балл группы по всем экзаменам.
2.
Заданы две выборки х1
,х2
,…,х
n
; у1
,у2
,…,у
n
.
Составить алгоритм определения выборочного коэффициента корреляции
,
где: - среднее значение наблюдений первой выборки;
- несмещенное среднее квадратичное отклонение наблюдений первой выборки. Аналогично и для второй выборки.
Задание 10
1. Что такое системное программное обеспечение? Какое программное обеспечение оно включает?
2. Доказать общезначимость формулы:
AÙ(AÞB)ÞB
3. Составить алгоритмы решения следующих задач:
1. В области 10 районов. Заданы площади, засеваемые в каждом районе пшеницей, и урожай, собранный в каждом районе. Определить среднюю урожайность пшеницы по каждому району и по области в целом.
2.
Изменение основных фондов отрасли описывается разностным уравнением:
.
Задан план инвестиций I
0
,
I
1
,…,
In
и начальное значение основных фондов К1
. Составить алгоритм для определения значений К2
,…,К
n
, а также нахождения цепных приростов, цепных темпов роста основных фондов.
Задание 11
1. Что такое система программирования?
2. Перевести два числа в двоичную систему счисления и найти их двоичную сумму:
1045,075; 1634,25
3. Составить алгоритмы решения следующих задач:
1. Определить, сколько различных сигналов может быть подано m
флажками различных цветов. Отличие сигналов заключается в порядке расположения разноцветных флажков на мачте. Решить при m
=6.
2.
Пусть имеется ряд наблюдений х1
,х2
,…,х
n
. Составить алгоритм определения среднего значения хср
и среднего квадратичного отклонения sx
по формулам:
;
Задание 12
1. Какие классы наиболее распространенного прикладного программного обеспечения вы знаете?
2. Показать, что формула является тавтологией:
ØAÙ(AÚB)ÞB.
3. Составить алгоритмы решения следующих задач:
1. В ЭВМ по очереди поступают результаты соревнования по плаванию, в которых участвует п
спортсменов. Выдавать на печать лучший результат после ввода результата очередного спортсмена.
2. Составить алгоритм определения будущего значения накопленного капитала по известной процентной ставке р
%, начальному вкладу А0
и известным периодическим платежам bi
,(
i
=0,1,…,
n
-1).
Ai+1
=p(Ai
+bi
).
Задание 13
14. Изобразите структурную схему персонального компьютера.
15. Выполнить операцию умножения над двумя двоичными числами:
1001,0101(2)
; 10111,1101(2)
3. Составить алгоритмы решения следующих задач:
1. Около стены наклонно стоит палка длиной x
. Один ее конец находится на расстоянии y
от стены. Определить значение угла между палкой и полом для значений x
= 4,5 м и y
, изменяющегося от 2 до 3 м с шагом 0,2 м.
2. Составить программу для обработки результатов кросса на 500 м для женщин. В кроссе участвует не более 100 студенток. Для каждой участницы внести фамилию, шифр группы, фамилию преподавателя, результат. Получить результирующую таблицу, упорядоченную по результатам, в которой содержится также информация о выполнении нормы 1 разряда. Определить суммарное количество студенток, выполнивших эту норму.
Задание 14
1. Каким является типовое устройство микропроцессора (модель)?
2. Перевести числа в десятичную систему:
B0345(16)
; 4625,14(8)
3. Составить алгоритмы решения следующих задач:
1. Задано п
троек чисел а, Ь, с
. Вводя их по очереди и интерпретируя как длины сторон треугольника, определить, сколько троек может быть использовано для построения треугольника (числа а,
b
, с
при вводе расположить в порядке возрастания).
2. Для формирования сборной страны по хоккею предварительно выбрано 30 игроков. На основании протоколов игр (всего 10 игр) составлена таблица, в которой содержится штрафное время каждого игрока по каждой игре (штрафное время может составлять 2, 5 или 10 мин). Составить программу, которая составляет предварительный список кандидатов в сборную и определяет для каждого из них суммарное и штрафное время. Игроки, оштрафованные хотя бы один раз на 10 мин, из кандидатов в сборную исключаются.
Задание 15
1. Какие типы микропроцессоров применяются на персональном компьютере?
2. Найти разность двух восьмеричных чисел:
120405,6(8)
; 17526,71(8)
.
3. Составить алгоритмы решения следующих задач:
1. Написать программу, которая спрашивала бы сокращенное имя, а печатала полное (например, Саша - Александр) для пяти ваших друзей. Ввод незнакомого имени должен провоцировать заявление типа: “Я с Вами не знакома”. Необходимые данные задать самостоятельно.
2. Сформировать из матрицы А(10,10) матрицу В(10,10) по следующим правилам:
а) элементы матриц А и В принимают только значения 0 или 1;
б) соседями элемента аij
считаются все элементы, расположенные рядом с данным по горизонтали, вертикали или диагонали;
в) если сумма S значений соседей элемента aij
меньше двух или больше трех, то bij
=0;
г) если сумма S значений соседей равна двум, то bij
=аij
;
д) если сумма S значений соседей равна трем, то bij
=1.
По окончании формирования матрицы В значения элементов построчно вывести на печать, заменяя 0 - символом “ “; 1 - символом *.
Задание 16
1. Что такое регистр? Приведите примеры регистров микропроцессора.
2. Пользуясь таблицей истинности доказать тавтологию:
(AÞB)Ù(BÞC)Þ(AÞC)
3. Составить алгоритмы решения следующих задач:
1. Составить программу, реализующую эпизод сказки: спрашивает, куда предпочитает пойти герой (налево, направо или прямо), и печатает, что его ждет в каждом случае. Ответ ЭВМ присвоить символьной переменной и напечатать. Текст вопросов и ответов ЭВМ задать самостоятельно.
2. В соревнованиях участвуют три команды по 6 человек. Результаты соревнований в виде мест участников каждой команды (1-18) размещены в трех массивах, содержащих по 6 компонент. Определить команду - победителя, вычислив количество баллов, набранное каждой командой. Участнику, занявшему 1-е место, начисляется 5 баллов, 2-е - 4, 3-е - 3, 4-е - 2, 5-е - 1, остальным - 0 баллов.
Задание 17
1. Какие типы памяти Вы знаете?
2. Перевести два числа в шестнадцатеричную систему счисления и найти их шестнадцатеричную сумму:
3025; 4612,25
3. Составить алгоритмы решения следующих задач:
1. Начав тренировки, спортсмен в первый день пробежал 10 км. Каждый следующий день он увеличивал дневную норму на 10 % от нормы предыдущего дня. Через сколько дней спортсмен пробежит суммарный путь 150 км?
2. Известно, что и Москве самыми теплыми являются дни с 15 июля по 15 августа. Для проведения фестиваля были выбраны 7 следующих подряд дней, наиболее теплых по данным за последние 10 лет. Составить программу для выполнения этой работы на ЭВМ.
Задание 18
1. Что представляет собой кэш-память?
2. Выполнить операцию умножения над двумя двоичными числами:
110101,01(2)
; 10111,11(2)
3. Составить алгоритмы решения следующих задач:
1. Составить программу для определения подходящего возраста кандидатуры для вступления в брак, используя следующее соображение: возраст девушки равен половине возраста мужчины плюс 7, возраст мужчины определяется соответственно как удвоенный возраст девушки минус 14. Данные для проверки работы программы задать самостоятельно.
2. Японская радиокомпания провела опрос 250 радиослушателей по вопросу: “Какое животное Вы связываете с Японией и японцами?”. Составить программу получения пяти наиболее часто встречающихся ответов и их долей (в %).
Задание 19
1. Что такое контроллер, какие типы контроллеров бывают?
2. Пользуясь законами эквивалентности упростить:
XÚ(YÚX)ÚY
3. Составить алгоритмы решения следующих задач:
1. В киоске продается газета стоимостью 70 коп. и журнал стоимостью 1 грн. 20 коп. Составить программу, которая спрашивает о желании покупателя (журнал или газета?), принимает деньги (сумма денег вводится с клавиатуры) и печатает причитающуюся сдачу. Исходные данные задать самостоятельно.
2. Составить программу для ведения протокола баскетбольной игры. Во время игры машина ведет учет набранных очков и фолов каждого игрока. Игрок, получивший 5 фолов, удаляется из игры (эта информация должна появляться на экране). В конце игры должна выводиться информация о сумме очков, набранных каждым игроком, в порядке убывания.
Задание 20
1. Какие внешние устройства компьютера Вы знаете?
2. Найти разность двух двоичных чисел:
11010000,01(2)
; 1011101,11(2)
.
3. Составить алгоритмы решения следующих задач:
1. Вводя в цикле по 5 оценок каждого студента, получить число студентов, не имеющих оценок 2 и 3. В группе учится п
, студентов.
2. Результаты переписи населения хранятся в памяти ЭВМ. Используя массивы фамилий и года рождения, напечатать фамилии и подсчитать общее число жителей, родившихся раньше 1928 года.
Задание 21
1. Что такое системная магистраль и какие основные магистрали данных используются в персональном компьютере?
3. Пользуясь законами эквивалентности упростить:
(XÚY)Ù(XÚØY)
3. Составить алгоритмы решения следующих задач:
1. В 1995 году урожай ячменя составил 20ц с га. В среднем каждые 2 года за счет применения передовых агротехнических приемов урожай увеличивается на 5 %. Определить, через сколько лет урожайность достигнет 25ц с га.
2. Результаты соревнований фигуристов по одному из видов многоборья представлены оценками судей в баллах (от 0 до 6). По результатам оценок судьи определяется место каждого участника у этого судьи. Места участников определяются далее по сумме мест, которые каждый участник занял у всех судей. Составить программу, определяющую по исходной таблице оценок фамилии и сумму мест участников в порядке занятых ими мест. Число участников не более 15, число судей не более 10.
Задание 22
1. Системный блок компьютера, что он включает?
2. Перевести два числа в шестнадцатеричную систему счисления и найти их шестнадцатеричную сумму:
1034; 2032,5
3. Составить алгоритмы решения следующих задач:
1. Определить средний рост девочек и мальчиков одного класса. В классе учится п
учеников.
2. В памяти ЭВМ хранятся списки номеров телефонов и фамилий абонентов, упорядоченные по номерам телефонов, для каждого из пяти телефонных узлов города. Один телефонный узел включает несколько АТС (не более 10), Номера АТС (первые две цифры номера телефона), относящихся к каждому телефонному узлу, также хранятся в памяти ЭВМ. Составить программу, обеспечивающую быстрый поиск фамилии абонента по заданному номеру телефона.
Задание 23
1. Опишите свойства алгоритмов.
4. Пользуясь законами эквивалентности упростить:
ØXÞ(XÙY)
3. Составить алгоритмы решения следующих задач:
1. Определить суммарный объем в литрах 12 вложенных друг в друга шаров со стенками 5 мм. Внутренний диаметр внутреннего шара равен 10 см. Считать, что шары вкладываются друг в друга без зазоров.
2. При выборе места строительства жилого комплекса при металлургическом заводе необходимо учитывать “розу ветров” в данной местности. На основании данных ежедневного определения направления ветра, проводимого в течение года, определить целесообразное взаимное расположение промышленной и жилой зоны.
Указание. Направление ветра кодируется следующим образом:1 – северный; 2 – южный; 3 – восточный; 4 – западный; 5 - северо-западный;
6 - северо-восточный; 7 - юго-западный; 8 - юго-восточный
Задание 24
1. Дайте определение оператора и опишите структурную классификацию операторов.
2. Перевести числа в десятичную систему:
1010101,0111(2)
; 10705,014(8)
3. Составить алгоритмы решения следующих задач:
1. Начав тренировки, спортсмен в первый день пробежал 10 км. Каждый следующий день он увеличивал дневную норму на 10 % от нормы предыдущего дня. Через сколько дней спортсмен будет пробегать в день больше 20 км?
2. Составить результирующую таблицу первенства по футболу, в котором участвуют 10 команд. В качестве исходной информации задан счет: количество забитых (пропущенных) мячей в каждой проведенной игре. Для получения итогового результата необходимо по заданной таблице забитых (пропущенных) мячей составить таблицу очков (выигрыш - 3, ничья - 1, проигрыш - 0). Далее определить сумму очков для каждой команды и в соответствии с этим распределить команды по местам. Если сумма очков у двух команд одинакова, то сравниваются разности забитых и пропущенных мячей.
Задание 25
1. Что такое блок-схема алгоритма?
2. Записать логическое выражение, которое принимает значение истина, если точка с координатами (x,y) попадает в заштрихованную область. На рисунке окружности имеют радиусы: большая – 9, меньшая – 5, центр первой имеет координаты (1,4), а второй – (-2,0). Прямая пересекает ось ОХ в точке (11,0), а ось ОУ в точке (0,9).
3. Составить алгоритмы решения следующих задач:
а) Составить таблицу стоимости порций сыра весом 50, 100, 150, ..., 1000 грамм (цена 1 кг 15 грн.).
б) Фамилии участников соревнований по фигурному катанию после короткой программы расположены в порядке, соответствующем занятому месту. Составить список участников в порядке их стартовых номеров для произвольной программы (участники выступают в порядке, обратном занятым местам).
[1]
Годичное Общее собрание Академии наук СССР //Вестн. АН СССР, 1983. №6. с.3-60.
[2]
А.П. Ершов. Информатика: предмет и понятие. // В сб. Кибернетика. Становление информатики. – М.: Наука, 1986. -192с.
[3]
Экономическая информатика, /Под ред. П.В. Конюховского и Д.Н. Колесова. –СПб:Питер, 2000. -560с.
[4]
Дибкова Л.М. Інформатика та комп’ютерна техніка: Посібник для студентів вищих навчальних закладів. –К.: Видав. Центр «Академія», 2002. -320с (Альма-матер).
[5]
Інформатика: Комп’ютерна техніка. Комп’ютерні технології: Підручник /За ред.. О. І. Пушкаря. –К.: Вид. центр «Академія», 2002. -704с. (Альма-матер).
[6]
В.С. Михалевич, Ю.М. Каныгин, В.И. Гриценко Информатика –новая область науки и практики. // В сб. Кибернетика. Становление информатики. –М.: Наука, 1986. -192с.
[7]
А.П. Ершов Информатика: Предмет и понятие. // В сб. Кибернетика. Становление информатики. – М.: Наука, 1986. -192с.
[8]
А.А. Дородницын Информатика: Предмет и задачи. . // В сб. Кибернетика. Становление информатики. – М.: Наука, 1986. -192с.