1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 1

Компьютер как инструмент исследователя

oавтоматизация эксперимента;

oмоделирование;

oсимвольные вычисления;

oобработка результатов;

oпоиск информации;

oоформление публикации/презентации.

Краткая история компьютерных технологий

Докомпьютерная эра

Механические и электромеханические вычислительные устройства. Технологии хранения информации на перфокартах.

Б. Паскаль, Ч. Бэббидж, А. Лавлейс, Г. Холлерит. Разработка важнейших концепций программирования.

Первое поколение ЭВМ

1940-е – середина 1950-х.

Универсальные программируемые вычислительные машины.

Элементная база: электронные лампы, электронно-лучевые трубки, память на ртутных линиях задержки.

Программирование в машинных кодах, отсутствие операционных систем. Язык программирования ShortCode, проект языка Plankalkul (Конрад Цузе).

Первые действующие электронно-вычислительные машины (ЭВМ): Colossus, ENIAC и др.

Второе поколение ЭВМ

Середина 1950-х – первая половина 1960-х.

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

Первые языки программирования высокого уровня (Fortran, ALGOL, COBOL), системное программное обеспечение.

Третье и четвертое поколения ЭВМ

Первая половина 1960-х – 1970-е.

Элементная база: интегральные схемы, большие интегральные схемы, сверхбольшие интегральные схемы.

Языки программирования высокого уровня, операционные системы (в т. ч. UNIX). Первые суперкомпьютеры.

2

Современное состояние компьютерных технологий

Сети, Интернет Параллельные и высокопроизводительные вычисления Грид-технологии

Закон Мура

Первый закон Мура

Число транзисторов на кристалле микропроцессора увеличивается в 2 раза каждые 1824 месяца.

o1970-1985 гг – рост производительности процессора происходил главным образом за счет совершенствования элементной базы и увеличения тактовой частоты;

o1985-2000 гг – использование для увеличения быстродействия усовершенствований архитектуры микропроцессора (конвейеры, суперскалярные процессоры, процессоры с сокращенным набором команд – RISC, кэширование, увеличение разрядности и т. д.);

o2001 г – ресурс повышения тактовой частоты практически исчерпан;

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

3

Компьютерные сети и Интернет

Появление и эволюция компьютерных сетей

Системы пакетной обработки

oцентрализованные системы на базе мощных компьютеров универсального назначения (mainframe);

oприоритет эффективности использования центрального процессора.

Многотерминальные системы

oодновременный доступ к одному компьютеру нескольких пользователей;

oраспределенный ввод-вывод;

oодин (общий) вычислительный ресурс.

Первые глобальные вычислительные сети

oудаленный доступ к компьютеру или нескольким компьютерам (протяженность линии 100-1000 км);

oсвязь посредством телефонной линии;

oудаленные связи «терминал-компьютер» и «компьютер-компьютер»;

oобмен данными между компьютерами в автоматическом режиме;

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

4

Первые локальные вычислительные сети (ЛКС/LAN - Local Area Networks)

oобъединение вычислительных ресурсов в рамках одной организации;

oнестандартные устройства соединения компьютеров, потребность в устройствах сопряжения;

oотработка стандартных технологий создания локальных компьютерных сетей.

Распределенные системы

oмногопроцессорные вычислительные системы;

oмногомашинные вычислительные системы;

oсети.

Вычислительные сети

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

oслабые программно-аппаратные связи между компьютерами, автономность узлов;

oсвязь между компьютерами с помощью специальных устройств – сетевых адаптеров, соединенных относительно протяженными линиями связи;

oкаждый компьютер работает под управлением своей собственной операционной системы;

oвзаимодействие с помощью обмена сообщениями.

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

Программные модули, ожидающие запросы, которые могут поступить от других компьютеров – программные серверы.

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

Пара «клиент-сервер», обеспечивающая доступ к определенному типу ресурсов – служба.

1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 2

Компьютерные сети и Интернет

Вычислительные сети

Основные компоненты сети:

oкомпьютеры (первый, внутренний слой);

oкоммуникационное оборудование (второй слой);

oоперационные системы (третий слой);

oсетевые приложения (четвертый, внешний слой) – почтовые системы, сетевые базы данных и др.

Передача данных по линиям связи

Проблемы, связанные с физической передачей сигналов по линиям связи:

oдвоичное представление информации. Различные способы кодирования (потенциальное, импульсное, модуляция);

oвнутренние и внешние линии связи. Внешние линии связи – большая протяженность, слабая помехозащищенность.

Способы кодирования информации при передаче по сетям:

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

Адресация компьютеров

oадрес должен однозначно идентифицировать компьютер в сети любого масштаба;

oсхема назначения адресов должна сводить к минимуму вероятность дублирования адресов и ручной труд администраторов;

2

oадрес должен иметь иерархическую структуру, удобную для построения больших сетей;

oадрес должен быть удобен для пользователей сети;

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

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

oаппаратные адреса;

oсимвольные адреса (имена);

oчисловые составные адреса.

Аппаратные адреса:

oпредназначены для сетей небольшого размера;

oне имеют иерархической структуры;

oиспользуются только аппаратурой;

oжестко связаны с аппаратурой или автоматически генерируются;

oзаписываются в виде двоичного/шестнадцатеричного значения.

Символьные адреса:

oпредназначены для запоминания пользователем;

oпредназначены для небольших и крупных сетей;

oимеют иерархическую структуру;

oжестко связаны с аппаратурой или автоматически генерируются;

oзаписываются в виде двоичного/шестнадцатеричного значения.

Числовые составные адреса:

oпредназначены для коммуникационной аппаратуры;

oпредназначены для больших сетей;

oимеют иерархическую структуру. IP-адрес - двухуровневая иерархия: старшая часть – номер сети, младшая часть – номер узла.

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

Централизованный подход - сервер имен (DNS – Domain Name Server) хранит таблицу соответствия имен различных типов

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

Сетевая технология

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

Сетевая технология Ethernet

Основные принципы:

oслучайный метод доступа к разделяемой среде передачи данных;

oкомпьютеры подключаются к разделяемой сети с помощью общей шины. Управление доступом к сети – сетевые адаптеры Ethernet.

Определение доступности среды.

3

Захват и монопольное использование среды передачи.

Кадр – единица данных, которыми обмениваются компьютеры в сети Ethernet.

Все сетевые адаптеры принимают кадр.

Разрешение коллизий.

Надежность, масштабируемость.

Протоколы, интерфейсы и стеки протоколов

4

Физический уровень

Передача информации по физическим каналам связи (витая пара, оптоволокно и т. д.)

Канальный уровень

Проверка доступности среды передачи. Обнаружение и коррекция ошибок

Сетевой уровень

Создание единой транспортной системы для разнородных сетей.

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

Транспортный уровень

Обеспечивает прикладному и сеансовому уровням тот уровень надежности, который требуется

Сеансовый уровень

Обеспечивает управление диалогом – определяет, какая из сторон активна, предоставляет средства синхронизации

Представительный уровень

Имеет дело с формой представления передаваемой информации

5

Прикладной уровень

Набор протоколов, с помощью которых пользователь получает доступ к разделяемым ресурсам

1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 3

Компьютерные сети и Интернет

Вычислительные сети

Стек протоколов TCP/IP

Стек протоколов TCP/IP - самое популярное средство организации составных сетей.

Встеке TCP/IP определены 4 уровня (а не 7!):

1.Уровень 1. Прикладной – объединяет службы, предоставляемые системой пользовательским приложениям. Протоколы FTP, Telnet, DNS, SMTP, HTTP и другие;

2.Уровень 2. Основной (транспортный) – обеспечивает надежную информационную связь между конечными пунктами. Основные протоколы - TCP (Transmission Control Protocol)

и UDP (User Datagram Protocol);

3.Уровень 3. Уровень межсетевого взаимодействия – обеспечивает возможность перемещения пакетов по сети, используя наиболее рациональный в данный момент времени маршрут. Основной протокол IP (Internet Protocol);

4.Уровень 4. Уровень сетевых интерфейсов – интеграция в составную сеть других сетей.

Адресация в IP-сетях

Встеке TCP/IP используются 3 типа адресов:

1.локальные (аппаратные). MAC–адрес (например, 22-B1-71-4D-CB-02);

2.IP-адреса. 4-байтовые – 195.168.0.34. Назначаются сетевым администратором;

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

IP-адреса

Классы IP-адресов:

2

Особые IP-адреса:

127.0.0.0 (loopback) - тестирование программ и взаимодействия процессов в пределах одной машины.

Другая схема адресации – с использованием масок.

Маска – это число, которое используется в паре с IP-адресом. Двоичная запись маски содержит единицы в тех разрядах, которые должны интерпретироваться как номер сети.

Маски для сетей различных классов:

oкласс A – 255.0.0.0

oкласс B – 255.255.0.0

oкласс C – 255.255.255.0

Необходимо обеспечить уникальность IP-номеров для всех сетевых интерфейсов Интернета. Для этого требуется центральный орган регистрации для всего Интернета. Такой орган существует: The Internet Corporation for Assigned Names and Numbers – «Корпорация Интернет по распределению имен и номеров» ([http://www.icann.org]). Эта некоммерческая организация выделяет большие блоки IP-номеров региональным организациям, управляющим распределением IP-номеров.

ВЕвропе такой организацией является RIPE NCC – Reseaux IP Europeens Network Coordination Center ([http://www.ripe.net]), расположенный в Париже.

Региональные организации выделяют меньшие блоки IP-номеров для национальных организаций. В России это Российский научно-исследовательский институт развития общественных сетей – РОСНИИРОС (http://www.ripn.net).

Любой желающий получить IP-номер для своего сетевого интерфейса может обратиться в РОСНИИРОС, заполнить анкету и получить один или несколько IP-номеров. Через два года придется отчитаться – использовался ли номер – а если не использовался, то РОСНИИРОС его отберет и два года не даст нового.

Внастоящее время спецификация IPv6 приходит на смену спецификации IPv4.

Доменные имена

Собственно имя компьютера или домена состоит из:

oлатинских букв;

oцифр;

oзнака тире (–).

Вимени должна быть хотя бы одна буква. Регистр букв значения не имеет (строчные и заглавные буквы можно употреблять на равных). Имена вида "195.19" недопустимы, их можно спутать с IP-адресами.

Полное доменное имя начинается с имени компьютера, за которым следует имя домена, к которому принадлежит компьютер,

за которым следует имя домена, к которому принадлежит тот домен, к которому принадлежит компьютер

и так далее, пока не будут перечислены все домены.

Примеры:

сomphys.phys.spbu.ru ftp.microsoft.com

3

(Рисунок из методического пособия В.А. Капустина «Основы профессиональной работы с информационными ресурсами Интернета», СПб, 2003)

Доменные имена верхнего уровня

Такие домены, которые не вложены ни в какие другие домены, называются доменами верхнего уровня.

Географические домены верхнего уровня соответствуют странам. Имена географических доменов верхнего уровня состоят из двух букв.

Примеры:

oru – Россия;

oua – Украина;

oau – Австралия;

oat – Австрия.

Тематические домены верхнего уровня

Имена тематических доменов верхнего уровня состоят из трех или более букв.

Примеры:

omil – организации Министерства обороны США;

ogov – правительственные учреждения США;

oedu – учреждения образования (в основном, США, но встречаются и домены в других странах);

ocom – коммерческие организации;

oorg – некоммерческие организации;

oint – международные организации;

onet – все остальные организации и даже частные лица, имеющие отношение к сетевой деятельности.

ounesco.org – международная организация ЮНЕСКО;

omicrosoft.com – коммерческая фирма Microsoft;

ohp.com – коммерческая фирма Hewlett-Packard.

Служба доменных имен

Служба доменных имен – отвечает за преобразование доменных имен в IP-адреса и обратно (DNS – Domain Name Server). Cостоит из компьютеров, программ, баз данных и людей, которые сопровождают базы данных, программы и компьютеры, на которых эти программы работают. Эти люди – администраторы DNS – вручную заносят в базы данных DNS информацию о соответствии между доменными адресами и IP-номерами.

4

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

DNS жизненно необходима для работы в Интернете. В сетевых настройках компьютера должен быть указан IP-номер того компьютера, на котором работает программа DNS.

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

Если вы обратились к какому-то компьютеру, то велика вероятность, что вы обратитесь к нему еще раз:

oпрочитав каталог ftp-сервера, вы либо смените каталог, либо захотите скачать файл;

oполучив HTML-страницу, вы, щелкнув по ссылке, можете перейти на другую страницу того же сайта;

oполучив электронную почту, вы захотите отправить ответ и т. д.

поэтому серверы имен, получив однажды с другого сервера имен информацию о соответствии доменного имени и IP-номера, хранят такую информацию неделю.

(Рисунок из методического пособия В.А. Капустина «Основы профессиональной работы с информационными ресурсами Интернета», СПб, 2003)

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

URL (Universal Resource Locator) – используется для обращения к компьютеру с целью получения с него определенного информационного ресурса.

Структура URL:

<схема><доменное имя><уточнитель ресурса>

Схема определяет способ связи:

ofile – файл расположен локально;

ohttp – доступ по протоколу HTTP;

oftp – доступ по протоколу FTP;

ohttps – доступ по безопасному протоколу HTTPS.

5

Уточнитель ресурса содержит до четырех составляющих (если они есть, то они пишутся вплотную друг к другу):

1.:необязательный номер порта;

2.путь по серверу;

3.собственно имя файла ресурса;

4.необязательное имя части ресурса или запрос.

Пример

http://www.nic.nw.ru:80/VAK/JS/js.html#5.10

:80

номер порта

/VAK/JS/

путь по серверу js.html

файл ресурса

#5.10

имя части файла

(Рисунок из методического пособия В.А. Капустина «Основы профессиональной работы с информационными ресурсами Интернета», СПб, 2003)

1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 4

Компьютерные сети и Интернет

Введение в HTML

HTML (HyperText Markup Language) – язык гипертекстовой разметки.

Всемирная паутина (WWW – WorldWide Web) состоит из HTML-документов – текстовых

документов, размеченных с помощью языка HTML.

HTML-документ – это обычный текстовый документ, в который внесена разметка. HTML-

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

Элементы HTML бывают двух типов:

1.простые элементы, которые существуют сами по себе;

2.элементы-контейнеры, которые могут включать размечаемый текст или другие элементы (как простые, так и контейнеры).

Разметка осуществляется с помощью ярлыков. Ярлык заключен в угловые скобки (<, >), и не виден при просмотре HTML-документа. Непосредственно за открывающей угловой скобкой (без пробелов!) следует имя ярлыка, а за именем через пробел – атрибуты.

Пример определения ярлыка с именем BODY и 8-ю атрибутами (onLoad, onUnload, BACKGROUND, BGCOLOR, TEXT, LINK, VLINK и ALINK):

<BODY onLoad="parent.moveDot(UNIT)"

onUnload="parent.lessonLog(LESSON,UNIT,'STOP');"

BACKGROUND=""

BGCOLOR="#d2bc93"

TEXT="#000000"

LINK="#006464"

VLINK="#800080"

ALINK="#ff0000"

>

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

Пример:

Изображение в HTML-документе определяется элементом IMG и размечается с помощью ярлыка <IMG …>

Элемент-контейнер размечается двумя ярлыками – открывающим и закрывающим. Между этими ярлыками помещается содержимое контейнера (например, текст абзаца).

Имя открывающего ярлыка элемента-контейнера совпадает с именем этого элемента, а имя закрывающего ярлыка начинается с косой черты (/), за которой следует имя элемента.

2

Пример:

Фрагмент текста, набранный моноширинным шрифтом – это элемент-контейнер с именем TT:

<TT>Чтоб вам столько работать, сколько хотите получать! </TT>

Структура HTML-документа

HTML-документ – это контейнер с именем HTML. Он начинается с ярлыка <HTML> и заканчивается ярлыком </HTML>:

<HTML>

……………

</HTML>

В этом контейнере лежат два других элемента-контейнера HEAD и BODY:

<HTML>

<HEAD>

Заголовок – предназначен для размещения служебной информации о документе

</HEAD>

<BODY>

Говорите, говорите, я всегда зеваю, когда мне интересно.

</BODY>

</HTML>

Минимальный документ:

<HTML>

<HEAD>

<TITLE>Простейший HTML-документ </TITLE>

</HEAD>

<BODY>

Говорите, говорите, я всегда зеваю, когда мне интересно.

</BODY>

</HTML>

Заглавие HTML-документа

Заглавие HTML-документа используется поисковыми системами. Оно появляется на верхней рамке окна браузера, в истории путешествий по Интернету, в закладках и др. Многие из этих мест имеют ограниченную длину (как правило, не более 60 символов), поэтому заглавие (элемент TITLE) должно быть коротким и информационно емким. Заглавие должно содержать как русский, так и английский текст.

Кодировка в HTML-документе

Указание кодировки требуется для корректного отображения кириллических (русских) текстов. С помощью служебного, невидимого элемента <META>, помещенного в контейнер HEAD, указать браузеру, какую кодировку следует использовать:

3

<HTML>

<HEAD>

<TITLE>This is my first document - Это мой первый документ</TITLE>

<META HTTP-EQUIV="Content-Type" CONTENT="text/html, charset=windows1251">

</HEAD>

<BODY>

Говорите, говорите, я всегда зеваю, когда мне интересно!

</BODY>

</HTML>

Абзац в HTML-документе

Абзац – это элемент логической структуры текста. Для него есть соответствующий элемент HTML. Этот элемент – контейнер, поскольку он содержит текст абзаца; следовательно, этот элемент должен иметь открывающий и закрывающий ярлыки.

<HTML>

<HEAD>

<TITLE>This is my first document – Это мой первый документ</TITLE>

<META HTTP-EQUIV="Content-Type" CONTENT="text/html, charset=windows-

1251">

</HEAD>

<BODY>

Первый абзац!

<P>

Второй абзац!

</P>

</BODY>

</HTML>

Логическая структура HTML-документа

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

<H1> Заголовок части </H1> <H2> Заголовок раздела </H2> <H3> Заголовок главы </H3> <H4> Заголовок пункта </H4> <H5> Заголовок подпункта </H5>

<H6> Заголовок подподпункта </H6>

Логическая структура документа может также содержать выделенный текст (текст, значение которого более важно для автора):

<EM>выделенный текст</EM>

и "сильно выделенный текст":

<STRONG>сильно выделенный текст</STRONG>

а также и другие структурные элементы: списки, цитаты, определения и др.

charset=windows-1251"> </HEAD>

<BODY>

<EM>За обыском начинается допрос,</EM><STRONG> который тоже является не самой</STRONG>

</BODY>

</HTML>

Простейшая оформительская разметка HTML-документа

Выделение фрагментов текста

Простейшая оформительская разметка позволяет задать полужирный или наклонный шрифт (но браузер может проигнорировать одновременное задание полужирности и наклонности

шрифта):

<B>полужирный</B> <I>наклонный</I>

<B><I>полужирный и наклонный</I></B> <I><B>наклонный и полужирный</B></I>

Кроме наклонного и полужирного начертания символов можно определить индексы:

<SUP>верхний</SUP>индекс <SUB>нижний</SUB>индекс

Шрифтовое оформление

Элемент-контейнер, позволяющий задать размер цвет шрифта независимо от логической или оформительской разметки:

<FONT>...</FONT>

Элемент <FONT> имеет несколько атрибутов. Важнейшие из них: SIZE и COLOR, задающие, соответственно, размер и цвет шрифта.

Размер шрифта

Атрибут SIZE может иметь значения двух типов – абсолютного и относительного. Абсолютное значение атрибута – это число от 1 до 7:

Относительное значение атрибута – это также число от 1 до 7 , но со знаком + или –.

5

Цвет шрифта

Цвет шрифта задается значением атрибута COLOR элемента FONT:

Разметка связей

Разметка связей выполняется с помощью ярлыка (элемента-контейнера) с именем "A", который следует внести в первый документ:

<HTML>

<HEAD>

<TITLE>The first document</TITLE>

</HEAD>

<BODY>

<H1>Это документ #1</H1>

Далее идет

<A HREF="2.html">связь со вторым документом</A>. </BODY>

При щелчке левой кнопкой мыши в момент, когда курсор имеет форму руки, связь активизируется и текущий документ («первый») заменяется тем, на который указывает связь («второй»).

Для внешних связей следует указывать полный URL, включающий и протокол:

<HTML>

<HEAD>

<TITLE>The second document</TITLE>

</HEAD>

<BODY TEXT="#008080">

<H1>Это документ #2</H1>

Далее идет

<A HREF="1.html">связь с первым документом</A>.

<P>

А второй абзац указывает на

<A HREF="http://www. microsoft.com">Microsoft</A> ;-)

</BODY>

</HTML>

6

Как создать HTML-документ

Три способа создания HTML-документа:

1.набрать текст в Microsoft Word и сохранить его как HTML;

2.с помощью специализированных редакторов HTML;

3.с помощью обычных текстовых редакторов (например, "Блокнот" или <F4> в FAR Manager).

Поиск информации в Интернете

Информационная потребность. Понятие пертинентного документа

АВТОР создает ДОКУМЕНТ. У нас возникает ИНФОРМАЦИОННАЯ ПОТРЕБНОСТЬ.

В теории информационного поиска вместо слова "подходит" используют термин ПЕРТИНЕНТНЫЙ ДОКУМЕНТ, а вместо "не подходит" – НЕ ПЕРТИНЕНТНЫЙ. Слово пертинентный происходит от английского pertinent, что значит относящийся к делу,

подходящий по сути.

Субъективно понимаемая цель информационного поиска – найти все пертинентные и только пертинентные документы (мы хотим найти "только то, что хотим, и ничего больше"). Эта цель недостижима.

Информационный шум

Оценить пертинентность документа часто можно только в сравнении с другими документами. Для того, чтобы было с чем сравнивать, необходимо некоторое количество непертинентных документов. Эти документы называются – "ШУМ".

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

Практика показывает, что когда количество непертинентных документов лежит в интервале от 10% до 30%, ищущий чувствует себя комфортно, не теряясь в море шума и считая, что количество найденных документов – удовлетворительно.

Информационно-поисковые системы

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

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

Запрос редко может точно выразить информационную потребность. Многие ИПС по разным

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

оказаться непертинентным и наоборот.

Словарные ИПС

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

7

Логические операторы

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

стол ИЛИ стул

Как правило, словарные ИПС Интернета предоставляют пользователям два интерфейса – режим сложного запроса (advanced search), в котором доступны все логические операторы, и

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

Правое усечение

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

стол ИЛИ стола ИЛИ столу ИЛИ столе ИЛИ столом

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

стол*

Формально говоря, звездочка заменяет любое количество символов, поэтому говорят, что она обозначает правое усечение.

Стратегия поиска

Дать общий рецепт эффективной стратегии поиска информации в Интернете невозможно. Есть лишь некоторые принципы, позволяющие тратить меньше времени.

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

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

Используйте несколько ИПС. Если вы регулярно занимаетесь поиском информации по какой-то тематике, отметьте те ИПС. которые для вас наиболее эффективны.

1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 5

Компьютерные сети и Интернет

Поиск информации в Интернете

Языки запросов поисковых систем

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

Яндекс

Google Rambler

Язык запросов ИПС Яндекс

Запрос содержит ключевые слова и операторы.

Для запросов из нескольких слов, Яндекс умеет определять, на каком максимальном расстоянии должны быть слова запроса. Требования к расстоянию могут быть указаны в явном виде.

Если запрос содержит несколько слов, Яндекс пытается определить, насколько тесно они между собой связаны:

oслова, которые сильно связаны между собой, ищутся в пределах одного предложения;

oменее тесно связанные слова ищутся на расстоянии в несколько предложений;

oнесвязанные слова ищутся в одном документе.

Близость слов определяется по факту их синтаксической согласованности:

ловля рыбы спиннингом

Пример синтаксической несогласованности:

ловля рыбий спиннинговый

Требования к расстоянию могут быть заданы в явном виде:

Слова идут подряд

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

“параллельные вычисления”

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

вычисления

Слова в одном предложении

Ограничить поиск страницами, где слова запроса находятся в пределах предложения, можно, соединив слова оператором &:

лето & зима

2

Слова в одном документе

При поиске документов, где присутствуют заданные слова — неважно, на каком расстоянии и в каком порядке, используется оператор &&:

свет && тьма

Слова на расстоянии в несколько слов

Максимально допустимое расстояние между двумя любыми словами запроса можно указать, поставив после первого слова символ /, сразу за которым идет число, задающее расстояние

свет /2 тьма

Слова на расстоянии в несколько предложений

Расстояние между словами можно задавать в предложениях. Для этого перед оператором расстояния / указывается оператор &&:

свет &&/2 тьма

Порядок слов

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

Слова следуют в определенном порядке на нужном расстоянии

Если точно известно не только расстояние, но и порядок слов запроса, в котором они должны идти в тексте страниц, можно указать между символом / и числом-расстоянием символ + для прямого порядка слов или - для обратного

свет /+2 тьма

Слова расположены в заданной окрестности

В некоторых поисковых задачах слова могут идти в разном порядке, между ними может быть от n слов (минимум) до m (максимум). В таком запросе используется оператор /(n m):

свет /(-10,+15) тьма

Поиск любого из слов

При поиске любого из слов используется оператор |:

добро | зло

Исключение слов из поиска

Яндекс позволяет исключать страницы, где есть определенные слова. Для этого используется оператор ~~, слева от которого указывают, что искать, а справа - какие страницы исключать из поиска:

Чирцов ~~ декан

Исключение слов из поиска

Иногда допустимо, чтобы слово встречалось на странице, но нельзя, чтобы оно встретилось в том же предложении. С этой целью используется оператор ~ :

Кузькина ~~ мать

Сложные запросы

В сложных запросах можно использовать скобки:

чирцов && (лыжи | парашют | дайвинг) ~~ (декан | ректор)

Морфология

Слова, указанные в запросе, по умолчанию ищутся с учетом морфологии. Для отключения этого учета перед словом используется оператор !:

!чирцов && (лыжи | парашют | дайвинг) ~~ (декан | ректор)

3

Другие возможности языка запросов

Поиск текста в заголовке страниц: $title(запрос)

Ограничение поиска группой страниц с заданным URL:

url=“www.gde-to.ru/chto-to/*”

Ограничение поиска заданным типом файла:

mime=“HTML|PDF|DOC|PPT|…”

Ограничение поиска заданным языком:

lang=“ru|en|de|fr|…”

Поиск только по страницам, дата которых удовлетворяет заданному условию: date=“ГГГГ{*|ММ{*|ДД}}”

4

Архитектура ЭВМ

Мейнфрейм Персональный компьютер Бортовой компьютер Наладонный компьютер

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

Идеи фон Неймана, высказанные им в статье, опубликованной в 1946 году совместно с Артуром Берксом и Германом Голдстайном «Предварительное обсуждение логического устройства электронного вычислителя» («Preliminary Discussion of the Logical Design of an Electronic Computing Instrument»), до сих пор лежат в основе устройства современных компьютеров

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

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

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

1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 6

Архитектура ЭВМ

Устройства ввода-вывода

Ввод

Клавиатура, мышь, дигитайзер и др. – текстовая, визуальная информация. Микрофон – аудиоинформация.

Вывод

Визуальная информация. Аудиоинформация.

Визуальная информация

Дисплей, принтер, плоттер

Аудиоинформация

Акустические колонки, наушники

Дисплей

Электронно-лучевой Жидкокристаллический

Принтер

Матричный

Струйный

Лазерный

Сублимационный

Память

Проблема – процессор работает быстро, а память работает медленно. Решение – многоуровневая организация памяти

2

Процессор

Конвейер

Процессор со сверхбольшим командным словом

3

1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 7

Архитектура ЭВМ

Устройства ввода-вывода

Дисплей

Электронно-лучевой Жидкокристаллический

2

Электронно-лучевая трубка (ЭЛТ, CRT – Cathode Ray Tube)

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

Развертка:

Жидкокристаллический дисплей (ЖК, LCD – Liquid Crystal Display)

3

Принтеры: струйные, лазерные и сублимационные

Самостоятельно

Многоядерные процессоры

1980’е - векторные SMP компьютеры

1990’е - массивно параллельные компьютеры До второй половины 1990’х - кластеры

Закон Мура

4

Многоядерная технология

Один процессор содержит 2 или больше вычислительных ядер:

Многоядерный процессор

Вычислительная работа, выполняемая одной программой, может быть распределена между вычислительными ядрами:

Вычислительная работа

Распределение вычислительной работы между ядрами

За один и тот же интервал времени может быть выполнено большее количество задач.

Как появились многоядерные процессоры

Регистры

*+

Обычный фон-неймановский процессор конвейер

1 команда / такт

5

Регистры

* + +

Суперскалярная архитектура

Регистры

*+

Регистры

*+

Двухъядерный (Dual Core)

Количество транзисторов увеличилось вдвое

7

Гипертрединг (Hyperthreading)

8

Многоядерная архитектура (Multicore)

Multicore+Hyperthreading

Процессор Cell

IBM+Sony+Toshiba

oТактовая частота 4,6 ГГц;

oНапряжение питания ядра 1,3 В;

oРабочее энергопотребление около 85 Вт;

oДесять термосенсоров;

oПропускная способность «вне процессора» 6,4 Гбит/с;

9

oТехпроцесс 90 нм («кремний-на-диэлектрике», low-k, восемь слоев, меднометаллические внутренние соединения);

oКоличество транзисторов — 234 млн, площадь чипа 221 мм².

Cell состоит из:

oпроцессорного элемента на основе POWER-архитектуры (PPE - POWER Processor Element);

oвосьми «синергических процессорных элементов» (SPE - Synergistic Processor Element);

oшины взаимосвязываемых элементов (EIB - Element Interconnect Bus);

oконтроллера интерфейса памяти (MIC - Memory Interface Controller);

oконтроллера интерфейса шины ввода/вывода (BIC - Bus Interface Controller).

PPE представляет собой два 64-разрядных процессорных ядра (на основе POWER-архитектуры) с поочерёдным выполнением команд (in-order execution), в отличие от внеочередного выполнения (out-of-order execution), присущего всем современным процессорам. PPE поддерживает технологию одновременной обработки двух потоков (SMT - Simultaneous MultiThreading), примерным аналогом которой является Hyper-Threading в Pentium 4. В PPE присутствует блок VMX (VMX - Vector Multimedia eXtensions). Объём кэш-памяти L1

составляет 64 Кб (по 32 Кб на кэш инструкций и данных), L2-кэш-памяти - 512 Кб.

10

Процессор Sun UltraSPARC T1

До 8 ядер; 4 потока на ядро (CoolThreads).

Четыре 144-разрядных интерфейса памяти DDR2-533 SDRAM. Исправление четырехбитных ошибок, обнаружение восьмибитных ошибок; поддержка технологии Chipkill ECC. 4 модуля DIMM на контроллер: всего 16 модулей. Поддержка двухканального режима работы.

Интерфейс JBUS - Пропускная способность до 3,1 ГБ/с. 128-разрядная шина адреса/данных - частота 150 - 200 МГц.

1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 8

Архитектура ЭВМ

Классификация компьютерных архитектур

Классификация Флинна

SISD – Single Instruction Single Data Flows

2

MISD – Multiple Instruction Single Data Flows

SIMD – Single Instruction Multiple Data Flows

MIMD – Multiple Instruction Multiple Data Flows

3

Форматы хранения данных. Машинная арифметика

Системы счисления

Система счисления – это совокупность правил записи чисел.

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

Примеры:

унарная (единичная)

Вавилонская шестидесятеричная система: 92=60 + 32:

Славянская алфавитная система:

4

греческая (ионийская) система

римская система:

oI – 1 (один палец)

oV – 5 (раскрытая ладонь)

oX – 10 (две сложенные ладони)

oL – 50

oС – 100 (Centum)

oD – 500 (Demimille)

oM – 1000 (Mille)

IX – 9 VIII – 8 XXVIII – 28 XCIX – 99

CXXVI

умножить на

XXXVII

5

Недостатки непозиционных систем счисления:

1.существует постоянная потребность введения новых знаков для записи больших чисел;

2.невозможно представлять дробные и отрицательные числа;

3.сложно выполнять арифметические операции.

Позиционные системы счисления

В позиционных системах счисления количественный эквивалент (значимость) цифры зависит от ее места (позиции) в записи числа:

2376

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

За основание системы счисления можно принять любое число не меньшее 2.

Существует бесконечно большое число позиционных систем счисления.

Наименование системы счисления соответствует ее основанию (десятичная, двоичная, восьмеричная и т. д.)

Достоинства позиционных систем счисления:

1.простота выполнения арифметических операций;

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

Впозиционной системе счисления любое вещественное число в развернутой форме может быть представлено в следующем виде:

N = ± (an −1 pn −1 + an −2 p n −2 + …+ a0 p0 + …+ a− m p − m )

Здесь:

N — число;

p — основание системы счисления,

ai —цифры, принадлежащие алфавиту данной системы счисления, n — число целых разрядов числа,

m — число дробных разрядов числа.

6

В свернутой форме:

N = ± (an −1an −2 …a0 .…a− m p − m )

Десятичная:

0 1 2 3 4 5 6 7 8 9

Двоичная: 0 1

Восьмеричная: 0 1 2 3 4 5 6 7

Шестнадцатеричная:

0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14 15

Преобразование целых значений из p-чной системы счисления в десятичную

Алгоритм умножения:

1.перенумеровать разряды p-чного числа справа налево от 0 до n – 1;

2.найти десятичное число, используя развернутую форму:

N = an −1 pn −1 + an −2 pn −2 + …+ a0 p0

Преобразование целых значений из двоичной системы счисления в восьмеричную

Алгоритм преобразования:

1. двигаясь справа налево, разбить двоичное число на триады:

001011101111

2. каждую триаду заменить восьмеричной цифрой.

Преобразование целых значений из двоичной системы счисления в шестнадцатеричную

Алгоритм преобразования:

1. двигаясь справа налево, разбить двоичное число на тетрады;

001011101111

2. каждую тетраду заменить шестнадцатеричной цифрой.

Преобразование целых значений из десятичной системы счисления в p- чную

Алгоритм деления:

1.разделить десятичное число на основание и записать остаток цифрой p-чной системы счисления;

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

7

Двоичная система счисления

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

oОтносительная простота технической реализации с помощью устройств, имеющих два устойчивых состояния;

oОтносительная простота реализации двоичной арифметики.

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

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

Недостатки:

oгромоздкость;

oнизкая точность операций с плавающей точкой (с нецелыми числами).

Единицы информации

Бит (bit – binary digit)

1.По Шеннону бит - двоичный логарифм вероятности равновероятных событий или сумма произведений вероятности на двоичный логарифм вероятности при разновероятных событиях. (Замена основания логарифма 2 на е или 10 приводит соответственно к редко употребляемым единицам нат и хартли.)

2.Один разряд двоичного кода (двоичная цифра). Может принимать только два взаимоисключающих значения: да/нет, 1/0.

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

8

8 бит = 1 байт

1024 байта = 1 килобайт

1024 килобайта = 1 мегабайт

1024 мегабайта = 1 гигабайт

1024 гигабайта = 1 терабайт

1024 терабайта = 1 петабайт

1024 петабайта = 1 экзабайт

Основные форматы хранения целых чисел без знака

Однобайтовый

0000 0000 - 1111 11112

0 - 25510

Двухбайтовый

00000000 00000000 – 11111111 111111112

0 - 6553510

Четырехбайтовый

00000000 00000000 00000000 00000000 –

11111111 11111111 11111111 111111112

0 – 2 x 2 147 483 64710

1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 9

Архитектура ЭВМ

Форматы хранения данных. Машинная арифметика

Арифметические операции в двоичной системе счисления

Сложение

Переполнение разрядной сетки

Умножение

11011

00101

11011

11011 .

10000111

Умножение в двоичной системе счисления = поразрядные сдвиги + суммирование

Основные форматы хранения целых чисел со знаком. Прямой код

Знак = (-1)s

Однобайтовый (абс. величина)

000 0000 - 111 11112

0 - 12710

Двухбайтовый (абс. величина)

0000000 00000000 – 1111111 111111112

0 – 32 76710

Четырехбайтовый (абс. величина)

0000000 00000000 00000000 00000000 –

1111111 11111111 11111111 111111112

0 – 2 147 483 64710

2

Обратный код

-13

Прямой код: 1000 11012

Обратный код: 1111 00102

Дополнительный код

-13

Обратный код: 1111 00102

Дополнительный код: 1111 00112

Арифметические операции в прямом, обратном и дополнительном коде

3

Преобразование дробных значений между системами счисления

Перевод дробного числа из десятичной системы счисления в произвольную p-ичную:

1.умножить D10 на p;

2.целую часть произведения представить соответствующей цифрой p-ичного представления;

3.умножать D10 на p до тех пор, пока будет достигнута требуемая точность (получится p- ичное число с k дробными разрядами) или дробная часть обратится в ноль.

Числа с плавающей точкой

Число с фиксированной точкой:

3.14159

Число с плавающей точкой: (-1)s0.m pn

Здесь:

m – мантисса; n – порядок.

0.314 101 0.0314 102

Машинные числа

Машинными называются числа, допускающие точное представление во внутреннем формате хранения числовых значений.

4

Форматы хранения чисел с плавающей точкой

Институт инженеров по электротехнике и электронике (Institute of Electrical and Electronics Engineers, IEEE) разработал международные стандарты, которые описывают представление чисел с плавающей запятой:

oстандарт ANSI/IEEE 754:1985 определяет требования к реализации двоичной плавающей арифметики;

oANSI/IEEE 854:1987 обобщает прежний стандарт, допуская дополнительно, кроме двоичного, десятичное основание представлений мантиссы и экспоненты и произвольную длину машинного слова.

Позднее требования этих стандартов были отражены в стандарте IEC 60559:1989.

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

В большинстве современных платформ, таких как Intel и большинстве RISC-систем аппаратно реализована плавающая арифметика, соответствующая стандарту IEC 60559.

Стандарты IEEE определяют следующие форматы хранения вещественных чисел:

oс простой точностью (соответствует типам REAL*4 в языке Фортран и float в C);

oс двойной точностью (соответствует типам REAL*8 в языке Фортран и double в C);

oс расширенной точностью (условно говоря, соответствует типам REAL*10 и более в языке Фортран и long double в C).

Число в представлении с простой точностью занимает 32 двоичных разряда: 23 разряда занимает мантисса и 8 разрядов отведено для порядка. Старший разряд является знаковым.

Нормализованная форма чисел с плавающей точкой

Числа с плавающей точкой хранятся в нормализованном виде:

oв нормализованной форме точка расположена перед первой значащей, то есть, отличной от нуля, цифрой мантиссы;

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

обеспечить наибольшую точность представления вещественного числа.

Мантисса нормализованного числа, если она не равна нулю, принадлежит диапазону [0.5, 1), в общем случае:

Порядок задается в формате с избытком (смещением) истинное значение порядка увеличивается на 127, сумма всегда положительна. Фактическое значение порядка находится в промежутке от –126 до +127. Основанием является 2.

Младший бит мантиссы в формате с простой точностью представляет значение 2-24 (примерно 10-7), что соответствует 7 значащим цифрам десятичного представления.

Значащие цифры числа допускают точное представление. Следующие значения имеют одинаковое (равное четырем) число значащих цифр: 3.142, 0.003142, 3.142e3.

5

В формате с простой точностью не имеет смысла хранить значения, содержащие более 8 десятичных разрядов мантиссы. Минимальное значение порядка -126 определяет минимальное по модулю, отличное от нуля, машинное число (около 1.17x10-38). Максимальное значение порядка составляет 127, что приблизительно соответствует значению 1.70x1038.

Число в представлении с двойной точностью занимает 64 двоичных разряда, из которых 52 разряда отводятся мантиссе и 11 разрядов порядку.

Для чисел с двойной точностью в десятичной системе диапазон значений составляет:

от 2.22x10-308 до 1.79x10308.

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

Расширенный формат используется для повышения точности промежуточных результатов вычислений.

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

Расширенный формат используется и для вычисления значений математических функций. Диапазон значений от 3.4x10-4932 до 1.2x104932.

Особые значения

Порядок 255 при нулевой мантиссе представляет значение «бесконечность». Порядок 255 при ненулевой мантиссе представляет значение, которое обозначается символьной строкой NaN (Not-a-Number, не число). Оно возникает при выполнении недопустимой операции вроде деления нулевого значения на нулевое или извлечения квадратного корня из отрицательного числа.

Если порядок равен нулю, а мантисса отлична от нуля, число называется анормальным (субнормальным, денормализованным). Оно может быть использовано для представления положительного и отрицательного нулей, а также значений, меньших минимального нормализованного числа. Субнормальные числа заполняют щель между нулем и наименьшим ненулевым нормализованным значением. Для чисел с простой точностью минимальное субнормальное значение равно 1.4x10-45, для чисел с двойной точностью 4.9x10-324, а для чисел с расширенной точностью не более 3.6x10-4951.

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

Существуют также форматы IBM, CRAY и некоторые другие. Они не получили широкого распространения.

Свойства множества машинных чисел

oдискретность любые два машинных числа разделены на числовой оси конечным промежутком. В диапазоне [0, 1] из всех чисел с одинаковым количеством знаков после десятичной точки только пятая часть может быть точно представлена в двоичной форме;

6

oконечность имеются наименьшее и наибольшее машинные числа;

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

Распределение машинных чисел на числовой оси:

Количественные характеристики множества машинных чисел:

oмаксимальное машинное число;

oминимальное машинное число;

oминимальное машинное число, отличное от нуля;

oмашинное эпсилон.

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

Справедливы следующие оценки для абсолютной величины машинного числа:

2L−1 ≤ x fl ≤ 2U (1 − 2− t )

где L и U — минимальное и максимальное значения порядка, а t — разрядность мантиссы.

Количество машинных чисел:

N fl = 2t (U − L + 1) + 1

Наименьшее субнормальное число:

2L−t

Машинное эпсилон представляет собой расстояние между единицей и ближайшим справа машинным числом:

ε m = 21−t

Это — наименьшее из машинных чисел, для которого (в смысле машинной арифметики):

1 + ε m > 1

Машинное эпсилон определяется размером мантиссы. Для простой точности его величина составляет приблизительно

1.19x10-7

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

7

Машинные числа равномерно распределены на каждом из интервалов

2e , 2e+1

где e — порядок.

Расстояние между соседними машинными числами:

2e−t

Увеличение порядка на единицу увеличивает длину интервала и, следовательно, удваивает это расстояние (в двоичном представлении).

Абсолютная погрешность машинного представления:

E( x) ≤ 2e−t −1

Относительное расстояние между двумя последовательными машинными числами:

1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 10

Архитектура ЭВМ

Форматы хранения данных. Машинная арифметика

Отображение произвольных численных значений на множество машинных чисел

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

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

oпереполнение (overflow) - результат больше максимального или меньше минимального машинного числа. Переполнение приводит к завершению выполнения программы;

oпотеря точности (потеря значимости, исчезновение порядка — underflow) - результат меньше наименьшего, отличного от нуля, машинного числа. Чистый выход за пределы точности (graceful underflow), при использовании субнормальных чисел;

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

Применение расширенного формата

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

Любые значения, пересылаемые из памяти в любом формате, «на лету» преобразуются в расширенный формат. Значение при этом не изменяется.

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

Искажение значений при вводе

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

Пример

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

Разряды защиты

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

2

Пример

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

1 - 0.99

Операнды хранятся в следующем виде: 0.1x101 и 0.99x100. При вычитании сначала выполняется выравнивание порядков, в результате получаем для уменьшаемого и вычитаемого: 0.1x101 и

0.09x101.

При выравнивании порядков в вычитаемом «потерялась» одна значащая цифра!!!

Разность 0.01x101 = 0.1, что на порядок отличается от правильного результата! Наличие дополнительного разряда для хранения промежуточного результата позволяет избежать большой погрешности.

Простое усечение

Существуют разные способы преобразования дробного значения к числу с заданной разрядностью. Один из способов заключается в отбрасывании «лишних» разрядов. Если исходное значение (в формате с простой точностью):

x = (.a1a2 …a24a25 …) × 2m

то машинное число, получаемое в результате усечения:

x′ = (.a1a2 …a24 ) × 2m

где aɶ24 = a24

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

Это смещенное приближение. Если

Фоннеймановское усечение

Фоннеймановское усечение является симметричным. Оно формируется заменой младшего двоичного разряда результата единицей, если хотя бы один из отбрасываемых разрядов отличен от нуля. «Лишние» нулевые разряды просто отбрасываются.

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

Округление

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

разрядов равен 1, к младшему из остающихся двоичных разрядов прибавляется 1: aɶt = at для at 1 = 0

+

3

округления будет выполняться xɶ<yɶ (символом «волна» здесь обозначены результаты округления).

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

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

| x − x′ |≤ 1 | x′′ − x′ |= 1 × 2−24 × 2m = 2m−25

Здесь x - точное значение, x’ - результат простого усечения, x” - результат фоннеймановского усечения

Относительная погрешность при усечении:

Единичная ошибка округления

| δ |≤ 2−24

единичная ошибка округления. Ее значение зависит от реализации машинной арифметики.

Результатом округления является замена исходного вещественного числа машинным:

где

ε= 1 p1−n

2

вслучае округления и

ε= p1−n

вслучае усечения.

Погрешность арифметических операций

Арифметические операции с целыми числами выполняются абсолютно точно. Действия с дробными числами выполняются с погрешностью.

4

Причины:

1.Результат операции может оказаться не машинным числом.

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

При умножении или делении чисел выравнивание порядков не выполняется.

Может оказаться так, что в процессе вычислений возникает:

1.слишком маленькое (порядок меньше –126 или –1022);

2.слишком большое (порядок превышает +127 или +1023) значение.

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

Это особые ситуации, называемые арифметическими исключениями.

Пусть — произвольная арифметическая операция, применяемая к истинным

вещественным числам, а

.

Этому условию удовлетворяют только операции, в реализации которых используются разряды защиты

Можно показать, что для операции суммирования относительная погрешность:

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

Пример

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

x + y

m =

2

и

y − x

m = x +

2

5

Первый вариант оказывается более точным, если оба значения имеют одинаковые знаки и второй — если противоположные.

Величина погрешности вычисления разности дается следующей теоремой.

ТЕОРЕМА

x

Тогда при вычислении разности x−y теряется от p до q значащих цифр.

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

При переходе к машинной арифметике сохраняются коммутативность (перестановочное свойство) сложения и умножения.

Ассоциативность (сочетательное свойство) этих операций нарушается.

Форматы хранения символьной информации

Код ASCII (American Standard Code for Information Interchange.

Каждому символу сопоставляется 7- или 8-битный (1-байтовый) числовой код.

Расширенная таблица ASCII использует 8 двоичных разрядов и состоит из двух частей. Первая, в которую входят символы с кодами 0–127, является универсальной, а вторая (коды 128–255) предназначена для специальных символов и букв национальных алфавитов (в том числе и русского). Символы в первых позициях этой таблицы являются управляющими.