Реферат: Информатика и компьютерная техника

Министерствообразования и науки Украины

Харьковскийнациональный университет

им. В.Н. Каразина

Методическиерекомендации по курсу «Информатика и компьютерная техника»

Составители:Епишев Сергей Николаевич

Иванов ВалентинВасильевич

Чуркина ЛюдмилаГеоргиевна


Введение

Методическиеуказания по курсу “Информатика и компьютерная техника”. Выпуск I. Основы ЭВМ/Состав. С.Н. Епишев, Ю.Г. Гузненков, Л.Г. Чуркина –Харьков: ХНУ, 2005. –7хх с.

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

Рекомендованокафедрой экономической кибернетики и прикладной экономики экономическогофакультета Харьковского национального университета им. В.Н. Каразина длястудентов экономических специальностей всех форм обучения.


Понятие информатики. Источникии предпосылки информатики

 

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

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

В нашейстране для обозначения новой научной дисциплины применялись термины«вычислительные науки» или «вычислительное дело», использование же термина«информатика» сдерживалось употреблением его в области, связанной сдокументалистикой. Начиная с 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<sub/>

/>Получатель Р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б) над основаниями вдокументе выполняются арифметические операции. Так, по каждой строке документапроизводится операция таксировка:

/>

/> <td/> />
В целом по документу«Накладная» определяется также итог по графе

«Сумма» путемсуммирования данных по указанной графе:

где: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<sup/>+ а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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

10

11

100

101

110

111

1000

1001

1010

1011

1100

1101

1110

1111

1

2

3

4

5

6

7

10

11

12

13

14

15

16

17

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)=11010 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. Исторически на IBM PC-совместимых компьютерахприменялись и применяются следующие микропроцессоры: Intel-8088,80286, 80386 (модификации SX и DX),80486 (модификации SX, SX2, DX, DX2, DX4),Pentium, Pentium Pro, Pentium II (и его модификации Celeron ит.д.). Основная память. Основная память – важнейший компонентперсонального компьютера. Название «основная» отличает эту память от внешнейпамяти, которая организуется на некотором внешнем устройстве (например, наНГМД). Это название говорит о том, что микропроцессор может обрабатывать толькоте данные, которые хранятся в основной памяти. Основная память обычно состоитиз двух частей – ОЗУ и ПЗУ.

Оперативное запоминающее устройство(ОЗУ) обеспечивает чтение находящихся в нем данных и запись в него новыхданных. В компьютерах ОЗУ обычно реализуется как энергозависимая память,т.е. такая память, содержимое которой разрушается («стирается») при выключениипитания компьютера. Часто для обозначения оперативной памяти используют аббревиатуруRAM (random access memory),т.е. память с произвольным доступом. Микросхемы ОЗУ собираются в блокиразличной емкости. Наиболее распространены емкости 16, 32, 64 и 128 мегабайт. Взависимости от способа работы микросхем памяти они бывают SIMMили DIM, последние наиболее распространены. Дляубыстрения доступа к оперативной памяти на быстродействующих компьютерахиспользуется еще и дополнительная специальная сверхбыстродействующая память,так называемая кэш-память. Она хранит копии наиболее часто используемыхучастков оперативной памяти и как бы занимает промежуточное положение междумикропроцессором и оперативной памятью. Кэш-память может располагаться иливнутри микропроцессора, или в виде отдельной платы. Так микропроцессоры серий486 и Pentium содержат небольшую внутреннюю кэш-память.Часто кэш-память, располагаемую отдельно от микропроцессора называюткэш-памятью второго уровня (level two cache, L2 cache). В микропроцессоре Pentium Pro, например,кэш-память второго уровня содержится в едином с ним корпусе. Микропроцессоры486 серии и Pentium обычно оснащаются кэш-памятьюемкостью 256 Кбайт.

Постоянное запоминающее устройство(ПЗУ) обеспечивает только чтение данных, которые однажды были записаны в ПЗУ.Таким образом, содержимое ПЗУ не может быть изменено компьютером, оно постоянно(отсюда и название вида памяти). Это устройство создается как энергозависимаяпамять: ее содержимое не «стирается» при выключении питания компьютера. Записьнужных данных в ПЗУ осуществляется на специальных устройствах, вне компьютера.В ПЗУ обычно помещаются некоторые особо важные или не подлежащие изменениюпрограммы и разнообразные константы. Такой вид памяти часто называют ROM (read only memory),или память только для чтения. Поскольку большая часть этих данных, программсвязана с обслуживанием ввода-вывода, то часто содержимое ПЗУ называют BIOS (Basic Input-Output System), базовая система ввода-вывода. В компьютере имеетсятакже небольшой участок полупостоянной памяти для хранения параметровконфигурации компьютера. Ее называют CMOS-памятью. Содержимоеэтой памяти не изменяется при выключении компьютера, так как ее питаниеосуществляется от небольшого специального аккумулятора. Для изменения значенияпараметров конфигурации компьютера в BIOS имеетсяспециальная программа SETUP.

Интерфейсы для устройств ввода ивывода. Они представляют собой блоки сопряжения с устройствамисоответственно ввода и вывода. Не останавливаясь пока на описании устройствввода и вывода, отметим лишь, что термин «интерфейс» означает приблизительно«сопряжение двух устройств друг с другом с помощью аппаратных и программныхсредств». Необходимость интерфейсов, или, как их еще называют, интерфейсныхблоков (контроллеров), вызывается тем, что устройства ввода и вывода(например, дисплей, печатающее устройство, НГМД и т.д.) нельзя непосредственноподключать к компьютеру. Одной из причин этого является то, что количество ихарактер сигналов, передаваемых и принимаемых по системной магистрали, скоторой связаны все компоненты компьютера, как правило, отличаются отколичества и типа сигналов, формируемых или воспринимаемых устройствомввода-вывода. Соответствующий интерфейсный блок обеспечивает должноесогласование сигналов системной магистрали и устройства ввода-вывода.

На любом персональном компьютере имеютсяконтроллеры для управления клавиатурой, монитором, дисководами для дискет,жестким диском и т.д. Некоторые из контроллеров размещаются на основнойсистемной или материнской плате компьютера, тогда они называются встроеннымиили интегрированными; а другие на отдельных электронных платах – платахконтроллеров. Эти платы соединяются (вставляются) с материнской с помощьюспециальных разъемов – слотов.

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

Основным средством ввода данных наперсональном компьютере всегда служит клавиатура. Из других средствввода-вывода отметим следующие:

1.        Накопители (или дисководы) для гибких магнитных дисков, используемые длячтения и записи на гибкие магнитные дискеты. В настоящее время используютсядискеты емкостью 1,4 Mb и 2 Mb.

2.        Накопитель на жестком магнитном диске, предназначенный для записи ичтения на несъемный жесткий магнитный диск (винчестер). Сейчас применяются восновном винчестеры емкостью в 5-10 GB.

3.        Устройства для чтения с компакт дисков, так называемые CD ROMы. Емкость таких дисков обычносоставляет 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 ит.д.

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

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

Программы-оболочкиобычно представляют собой более удобные средства для общения с ЭВМ, чемстандартные средства ОС. Так для MS DOS это – Norton Commander, для Windows – Norton Navigatorи т.д. Причем, чаще всего программы-оболочки не стараются заменить операционнуюсистему, а наоборот пополняют ее новыми, более удобными функциями.

Утилиты илипрограммы обслуживания объединяют большое количество системных программвспомогательного назначения:

1.   Антивирусныепрограммы – основные функции которых — предотвращение заражения компьютеравирусами и ликвидация последствий таких заражений. Различают антивирусныепрограммы детекторы, вакцины, полифаги — в зависимости от их способов борьбы скомпьютерными вирусами. В нашей стране наибольшее распространение получилипрограммы AidsTest и Dr.Web.

2.   Программыархиваторы или упаковщики позволяют создавать резервные копии файлов, путемуменьшения их размеров за счет выполнения сжатия, уплотнения информации.Наиболее распространены Arj, Zip,Rar для операционных систем MS DOS и Windows.

3.   Программыдля диагностики технического состояния компьютера, которые позволяютпроверять исправность всех устройств компьютера;

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

5.   Программыограничения доступа позволяют защитить хранящиеся на компьютере данные отнесанкционированного доступа.

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

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

Дляперсонального компьютера имеются системы программирования для всех популярныхязыков программирования, таких как Си, С++, Паскаль, Фортран, Бейсик и т.д. Внастоящее время стали распространяться системы программирования с языка Java, позволяющие создавать программы-сценарии для Web-страниц в Интернет.

Особымклассом систем программирования являются системы разработки приложений типа клиент-сервер.Они позволяют быстро создавать информационные системы для подразделений ипредприятий, с использованием средств визуального программирования. Какправило, эти системы позволяют работать с самыми разными базами данных.Наиболее популярными являются системы Delphi, Visual Basic,C-Builder, Sybase,PowerBuilder, SQLWindows.

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

1.   Редакторыдокументов, позволяющие подготавливать различные документы высокогокачества. Они полностью заменили пишущую машинку, да еще позволилидополнительно выполнять целый ряд функций по подготовке высококачественныхдокументов: управление шрифтами, абзацами, перенос слов, проверка орфографии,вставка рисунков, диаграмм и т.д. Наиболее популярны для ОС MS DOS ЛЕКСИКОН, Microsoft Word, WordPerfect,а для Windows – Microsoft Word, Corel WordPerfect, Word Pro фирмы Lotus,Just Writeфирмы Symantec.

2.   Табличныепроцессоры, представляющие документ в виде таблицы из прямоугольных клеток,в которых могут храниться числа, формулы, пояснительные тексты. Всераспространенные табличные процессоры позволяют производить перевычислениезначений, строить различные графики, включать в таблицы рисунки, использоватьмакрокоманды, работать с базами данных. Наибольшей популярностью пользуются Microsoft Excel, Lotus 1-2-3, Quattro Pro.

3.   Издательскиесистемы предназначены для подготовки рекламных буклетов, оформления газет,журналов, книг. Их основная функция – верстка, т.е. размещение текста, рисункови пр. на страницах документа. Наибольшую популярность получили издательскиесистемы – PageMaker фирмы Adobeи QuarkXpress фирмы Quark.

4.   Программыподготовки презентаций могут оформлять слайды для презентаций, помещая тудакрасивые диаграммы, рисунки, надписи, включать звуковое сопровождение ипоказывать презентации на компьютере. Наиболее известны программ – PowerPoint фирмы Microsoft, Harvard Graphicsфирмы Software Publishing.

5.   Графическиередакторы, позволяющие работать с графическими объектами – рисунками,фотографиями. Наиболее известны — Adobe PhotoShop, Corel Draw.

6.   Анимационныепрограммы позволяют создавать трехмерные движущиеся модели объектов,создавать анимационные фильмы. Примером может служить программа 3D Studio фирмы Autodesk.

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

8.   Бухгалтерскиепрограммы позволяют вести бухгалтерский учет, подготавливать финансовуюотчетность. Наибольшее распространение получили – 1С-бухгалтерия, Инфо-Бухгалтер.Для предприятий с большим объемом хозяйственных операций, многие из которых ужене относятся к бухгалтерскому учету – складской учет, учет торговых операций,контроль за выполнением договоров, управленческий учет, финансовый анализдеятельности предприятия, целесообразно применение программных комплексов: Парус,Инфософт, Инфин и т.д.

9.   Правовыебазы данных содержат тексты нормативных документов и предоставляютвозможности поиска и распечатки, например, Гарант, Кодекс, Юрисконсульт.

10.Персональные информационные менеджеры позволяюназначать разовые и повторяющиеся мероприятия, напоминать о делах, встречах,облегчают звонки по телефону. Пример таких программ: LotusOrganizer, Sidekick фирмы Starfish Software.

11.Программы планирования позволяют составлятьплан-графики работ, например, Microsoft Project, TimeLineфирмы Semantic.

12.Программы распознавания символов позволят вводить спомощью сканера напечатанные тексты, рисунки, графики, фотографии. У насполучила наибольшее распространение программа FineReader фирмыБит.

13.Программы переводчики позволяют переводить с одногоязыка на другой с более менее пристойным качеством, например, Stylus фирмыПроМТ, Сократ фирмы АрсеналЪ.

14.Программы словари (Мультилекс фирмы МедиаЛингва, Контекстфирмы Информатик, Лингво фирмы Бит) – это электронные версии обычных словарей снекоторыми дополнительными возможностями.

15.Системы управления базами данных позволяют управлятьбольшими информационными массивами. Так, весьма мощны и удобны в использовании Lotus Approach,DataEase, Paradox, FoxPro, Access. Для создания большихи многопользовательских информационных систем типа клиент-сервер широкоиспользуются Oracle, Microsoft SQL Server, Sybase SQL Server, Iformix.

16.Системы автоматического проектирования (САПР) позволяютосуществлять черчение и конструирование различных предметов и механизмов спомощью компьютера. Среди систем малого и среднего класса наиболее популярнасистема AutoCad фирмы AutoDesk.Системы более высокого класса включают средства трехмерного моделирования,процессов механобработки, программирования оборудования с числовым программнымуправлением. Здесь можно отметить системы «Компас» фирмы Аскон и T-Flex CAD фирмы Топсистемы.

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. Обозначим оператор ввода исходных данных через B1. Оператор вывода результата (значений y, z) через B2. Оператор вычисления значения y по формуле (I) — через A1. Оператор вычисляющий z- по формуле (2), через – A2. Оператор остановки процесса решения через O1. Переход между операторамиобозначим стрелками. Тогда операторную схему алгоритма решения данной задачиможно представить следующим образом:

/>

т.е. вначале следуетввести значения исходных данных –x, a (оператор B1); затем вычислить значение y (оператор A1); вычислив значение y,требуется вычислить значение z(оператор A2); напечатать результат — значения y, z (оператор B2) и остановить процесс – оператор О1.

Если операторывыполняются в том порядке, в котором они записаны, то стрелки можно опустить,т.е. операторную схему можно записать в следующем сокращенном виде: />.

Этопример линейного алгоритма. Приведем пример разветвляющегося алгоритма.

Пример 4. Написать операторную схему алгоритма по определениюкорней квадратного уравнения /> при />. Опишем процесс (план) решениязадачи:

1)        вычисляемзначение дискриминанта, />;

2)        сравниваемзначения дискриминанта с нулем;

3)   если  />,то вычисляем x1, x2<sub/>по формулам


/>;   />,

 печатаемполученные значения,и останавливаем процесс решения;

4) если/>, то выводим фразу«Действительных корней нет»иостанавливаем процесс решения.

Запишем теперь операторную схему,

Обозначим:

B1 — оператор ввода значений a, b, c;

A1 — оператор вычисляющий дискриминант D;

P1 — оператор проверяющий условие D<0;

   A2 — оператор вычисляющий значениеx1;

   A3 — оператор вычисляющий значение x2;

      B2 — оператор вывода значений x1, x2;

      B3 — оператор вывода фразы «Действительныхкорней нет»;

  O1, O2 — операторы остановки.

нет

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

да

  />        A2A3B2O1

/>B1A1P1

         B3O2

Циклические алгоритмы

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

Различают два видациклических операторов:

1) Циклический оператор сзаданным количеством повторений;

2) Итерационныйциклический оператор.

нет

  Схематически оба эти операторы имеют одинаковую структуру, которую можноизобразить следующим образом:

/>/>/>/>/> A0    A1    P1    (продолжение)

/> /> /> /> /> /> /> /> <td/>

да

 

A- оператор или операторы подготовки цикла.

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= xy. Если описанный процесс обозначить математическимиформулами, то будем иметь следующую запись:

/>,

/>.

Исходными данными длярассматриваемой задачи являются значения x, a, b, c. Результатом будет значение z. Заметим, что взависимости от требуемого, результатом может быть величина подоходного налога уи заработная плата z. Выводитьна печать можно также вместе с результатами и значение х.

Блок схема алгоритма решенияданной задачи представлена на рис. 4.

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

/>

Рис. 4. Блок-схема задачиначисления подоходного налога.

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

Пример 6. Проиллюстрируем метод декомпозициина составлении блок-схемы алгоритма решения квадратного уравнения:

/>

Укрупненная схемаалгоритма следующая:

/>


1.        Исходными даннымидля задачи являются значения коэффициентов уравнения a, b, c. Разукрупнять блок «Ввод исходных данных» ненадо, т.к. этот ввод можно осуществить одним оператором.

2.        Блок «Нахождениерешения уравнения». Для определения решения уравнения надо вначалевычислить дискриминант />. Затем проверитьзнак дискриминанта. Если дискриминант больше нуля, то уравнение имеет двакорня, которые вычисляются по формулам:

/>;   />.

В этом случае результатомбудет значения этих корней.

Еслидискриминант равен нулю, то уравнение имеет один корень, который вычисляется поформуле: />. Это значение и будетрезультатом в этом случае.

Еслидискриминант меньше нуля, то уравнение не имеет действительных корней. В этомслучае результатом будет фраза «Уравнение не имеет действительных корней».

Декомпозиция этого блокаследующая:

/>


3.        Блок «Выводрезультатов». В зависимости от значения дискриминанта, мы можем получитьтри результата. Поэтому этот блок по сути состоит из трех разных оператороввывода:

/>


Приведем примеры циклических алгоритмов

Пример 7.Составим блок-схему алгоритма начисления процентов повкладам.


/>

Рис. 5. Блок-схемаалгоритма начисления процентов по вкладам.

Описаниепостановки задачи:

Имеется n записей z1,z2,…zn, характеризующих вклады. Средихарактеристик имеются следующие: si – величина вклада; di – дата последнего начисленияпроцентов. Если по вкладу не было начислений процентов, то эта дата совпадает сдатой вложения. Требуется произвести начисление процентов из условия p процентов годовых. Начислениепроводится в конце некоторого периода (года, квартала) на дату, которуюобозначим D. Кроме начислений по каждому вкладу,требуется определить общую сумму начисленных процентов. Суть алгоритмазаключается в следующем: просматриваем записи, поочередно, начиная с первой.Для каждой записи находим количество дней, прошедших после последнегоначисления процентов. Пусть это количество равно ki для i-ой записи. Тогда соответствующая сумма процентов будетопределяться по формуле:

/>


Эту сумму добавляем к si и в общую сумму начисленныхпроцентов, которую обозначим Sp.Блок-схема алгоритма представлена на рис.3.

Пример 8. Блок–схема алгоритма сортировки.(Метод «Пузырек»).

Пусть а1, а2,…, аn<sub/>есть массив записей, описывающихнекоторое множество объектов. Например, а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 – количество элементов в множестве.(входной параметр).

a1,…,an – элементы (записи) множества(входной массив и он же результат).

p1,…,pn – значения признака, по которомупроизводится сортировка.

kграница просмотра на каждом шаге (k=2,…,n).

i — текущий номер просматриваемой пары(i=2,…,k).

Блок-схема алгоритмапредставлена на рис.6.


/>/>

Рис. 6. Блок-схемаалгоритма сортировки, метод «Пузырек».

Пример 9. Написать блок-схему алгоритма произведения двух матриц(пример алгоритма с тройным циклом).

/>

Рис. 7. Блок-схемаалгоритма перемножения двух матриц


Напомним, что перемножать можноматрицы, у которых количество столбцов первой матрицы равно количеству строквторой матрицы. Пусть имеется матрица А, размера nxm и матрица В, размера m x p. Тогда произведением этих матриц будет матрица С=АВ,элементы которой определяются по формуле:

/>             (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,I1,…,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грн.).

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

еще рефераты
Еще работы по информатике, программированию