Экзаменационные билеты по информатике 2000/2001 учебный год
В процессе работы программы и данные загружаются в специальное устройство — оперативную память. Объем оперативной памяти на современных компьютерах составляет от 8 до 32 Мб, а аппаратно оперативная память реализуется на БИС различных типов (SIMM, DIMM и т. д.).
Однако при выключении компьютера вся информация из оперативной памяти стирается. Как повторно загрузить программу или оперативно загружать различные программы? Для пользователя необходимо иметь возможность долговременного хранения большого количества различных программ и данных. Предназначенные для этого устройства называются устройствами внешней памяти.
Аппаратно внешняя память реализуется на накопителях на гибких магнитных дисках (НГМД) емкостью 1,2 Мб или 1,44 Мб, жестких дисках (НЖМД) емкостью от 1 до 6 Гб и CD-ROM-дисководах емкостью 640 Мб. Дисководы для гибких дисков и жесткие диски используют магнитный принцип записи, когда информация записывается путем намагничивания отдельных небольших участков (нет намагниченности — 0, есть намагниченность — 1). CD-ROM-дисководы используют лазер для считывания информации с CD-ROM-диска, на котором чередуются участки с различной отражающей способностью.
Пользователи для работы на компьютере используют программы-приложения. С помощью этих программ они могут создавать различные файлы-документы (текстовые, графические, звуковые и др.). Программы-приложения имеют объем в десятки и сотни мегабайт, хранятся во внешней памяти и по мере необходимости загружаются в оперативную память. Это могут офисные приложения (Word, Excel и т. д.), сетевые приложения (браузе-ры, почтовые программы и т. д.), программы обработки графики (CorelDraw) и другие.
Программисты для работы используют трансляторы языков (Turbo Pascal, С) и современные системы программирования с графическим интерфейсом (VisualBasic, Delphi). С помощью этих программ создаются исполняемые программы. Системы программирования имеют объем в десятки мегабайт, хранятся во внешней памяти и при необходимости загружаются в оперативную память.
Для того чтобы все устройства компьютера работали согласованно и пользователю были доступны аппаратные ресурсы, необходима операционная система. Операционная система хранится во внешней памяти и при включении компьютера загружается в оперативную память. На IBM-совместимых компьютерах долгое время использовалась операционная система MS-DOS, в настоящее время используется операционная система с графическим интерфейсом Windows.
Билет №16
Разработка алгоритмов методом последовательной детализации. Вспомогательные алгоритмы.
Процесс решения сложной задачи довольно часто сводится к решению нескольких более простых подзадач. Соответственно при разработке сложного алгоритма он может разбиваться на отдельные алгоритмы, которые называются вспомогательными. Каждый такой вспомогательный алгоритм описывает решение какой-либо подзадачи.
Процесс построения алгоритма методом последовательной детализации состоит в следующем. Сначала алгоритм формулируется в «крупных» блоках (командах), которые могут быть непонятны исполнителю (не входят в его систему команд) и записываются как вызовы вспомогательных алгоритмов. Затем происходит детализация, и все вспомогательные алгоритмы подробно расписываются с использованием команд, понятных исполнителю.
Рассмотрим процесс создания алгоритма Домик для исполнителя Чертежник методом последовательной детализации. Пусть необходимо нарисовать домик с крышей.
Сначала запишем алгоритм, состоящий из крупных блоков. Такими блоками, содержащими «непонятные» для исполнителя Чертежник команды, являются блоки стена, крыша. Теперь детализируем эти блоки и запишем их в виде вспомогательных алгоритмов, содержащих понятные Чертежнику команды.
Ширина домика: 4
Высота стены: 2
Высота крыши: 1

алг домик нач 1 стена 1 крыша
алг стена нач сместиться в точку опустить перо сместиться в точку сместиться в точку сместиться в точку сместиться в точку поднять перо кон
(0,0)
(0,2) (4,2) (4,0) (0,0)
алг крыша нач
сместиться в точку (0, 2) опустить перо сместиться в точку (2, 3) сместиться в точку (4, 2) сместиться в точку (0, 2) поднять перо кон
В результате мы имеем основной алгоритм (домик), созданный методом последовательной детализации, в который входят как составные части два вспомогательных алгоритма (стена, крыша).
Функциональные узлы процессорах регистры, сумматоры и др.
Процессор должен выполнять команды программы, которые хранятся в оперативной памяти по определенным адресам. В команде указано, какие действия необходимо выполнить над данными, а также адреса данных. Для того чтобы считывать команды и данные из оперативной памяти, а также записывать результаты выполнения команд в оперативную память, внутренняя магистраль процессора должна быть подключена к внешней магистрали системной платы. Подключение внутренней магистрали процессора ко внешней магистрали осуществляется через буферы адреса и данных.
Основным устройством процессора является арифметико-логическое устройство (АЛУ). Именно это устройство выполняет все операции над данными. Таким образом, это устройство должно иметь специальные регистры (команд и данных) для временного хранения поступивших из оперативной памяти команд и данных.
Для того чтобы выполнить команду, процессор должен ее расшифровать (декодировать), т. е. по двоичному коду определить характер и последовательность действий с данными. Значит, в составе АЛУ должно быть декодирующее устройство.
Операции над данными производятся в сумматоре, а результат помещается в специальный регистр, называемый аккумулятором.
В состав процессора входит устройство управления, которое помимо других функций отслеживает последовательность выполнения команд, т. е. в нем имеется счетчик команд (программный счетчик).
Кроме этого, в состав процессора входят регистры общего назначения, представляющие собой совокупность ячеек памяти, предназначенных для временного хранения необходимой процессору информации. Так как регистры общего назначения выполнены непосредственно в БИС процессора, они обладают очень большим быстродействием. В современных процессорах типа Pentium такие регистры образуют кэш-память.

Рассмотрим цикл работы процессора, например, при сложении двух чисел:
1. В результате начального включения или завершения предыдущей команды в программном счетчике устанавливается адрес команды и через буфер передается в шину адреса компьютера.
2. В оперативную память компьютера из устройства управления процессора посылается сигнал «чтение», происходит считывание команды из ячейки с указанным адресом, содержимое ячейки выдается в шину данных компьютера и через буфер данных попадает в регистр команд.
3. Декодирующее устройство расшифровывает код операции, содержащийся в команде, и передает управление сумматору.
4. Сумматор начинает выполнение соответствующих действий и запрашивает из оперативной памяти (или с устройства ввода) находящиеся по указанным адресам данные.
5. Результат выполнения команды помещается в аккумулятор и при необходимости пересылается в определенные ячейки оперативной памяти компьютера.
Билет № 17
Компьютер как формальный исполнитель алгоритмов (программ).
Алгоритм может быть записан на естественном языке, изображен в виде блок-схемы, записан с соблюдением строгих правил синтаксиса на алгоритмическом языке или закодирован на языке программирования. Для того чтобы компьютер мог его выполнить, алгоритм должен быть записан на понятном для компьютера языке.
Устройством, которое обрабатывает информацию в компьютере, является процессор, следовательно, алгоритм должен быть записан на языке, «понятном» для процессора, т. е. должен использовать систему команд процессора. Таким образом, алгоритм должен быть записан на машинном языке, представляющем собой логические последовательности нулей и единиц.
Действительно, вначале, в 50—60 годы, программы писались на машинном языке, т. е. представляли собой очень длинные последовательности нулей и единиц. Однако составление программ на машинном языке было чрезвычайно трудоемким делом.
Для облегчения труда программистов начали создаваться языки программирования, т. е. искусственно созданные языки с несколькими десятками слов (операторов) и строгими правилами синтаксиса, т. е. правилами соединения этих слов в предложения.
Известный всем Бейсик был создан в 1964 году сотрудниками Дартмутского колледжа Дж. Кемени и Т. Курцом. (Название BASIC является аббревиатурой английского названия Beginner's All-purpose Symbolic Instruction Code.) Интересно, что языки программирования развиваются так же, как и естественные, т. е. они обогащаются новыми операторами и новыми возможностями, возникают различные версии языка (QBasic, VisualBasic и др.).
Для того чтобы процессор мог выполнить программу, эта программа и данные, с которыми она работает, должны быть загружены в оперативную память.
Итак, мы создали программу на Бейсике (некоторый текст) и загрузили ее в оперативную память из внешней памяти или с клавиатуры. Теперь мы хотим, чтобы процессор ее выполнил, однако процессор «понимает» команды на машинном языке, а наша программа написана на Бейсике. Как быть? Необходимо, чтобы в оперативной памяти находилась программа переводчик (транслятор), автоматически переводящая с Бейсика на машинный язык.
Ясно, что один и тот же компьютер может «понимать» и QBasic, и Turbo Pascal, и какой-либо другой язык, все зависит от того, транслятор какого языка программирования размещен в оперативной памяти компьютера.
Рассмотрим на простейшем примере (умножение двух чисел) процесс построения алгоритма, его кодирование на языке программирования и выполнение программы. В качестве языка программирования выбран Бейсик, однако это может быть практически любой язык программирования.
Сначала запишем алгоритм на естественном языке. Он является линейным и состоит из трех действий. Затем построим блок-схему данного алгоритма, что позволяет в наглядной форме представить логическую структуру алгоритма и проследить динамику его выполнения. В процессе построения алгоритма особое внимание обратим на то, какие данные вводятся в компьютер и какие выводятся (фиксируются аргументы и результаты алгоритма).
| Естественный язык | Блок-схема | Бейсик |
|
Следующим этапом является кодирование алгоритма на языке программирования (в данном случае Бейсике) и загрузка полученной программы в оперативную память. Оперативная память состоит из отдельных адресуемых ячеек, в которых информация может храниться, записываться и стираться. Каждая ячейка имеет уникальный адрес, и в ней может храниться 1 байт информации. Количество таких ячеек в современных компьютерах велико и соответствует объему памяти, выраженному в байтах. Для памяти 16 Мб оно составляет 16 777216 ячеек.
Программа займет в оперативной памяти определенное количество ячеек в области, отведенной для программ пользователя. Программа будет записана в памяти во внутреннем представлении языка программирования (в данном случае Бейсика), который процессор «не понимает». Для перевода программы на машинный язык, понятный процессору, в памяти должна находиться программа-транслятор с данного языка программирования.
Переход в режим выполнения программы задается соответствующей командой (RUN), процессор последовательно будет считывать из памяти операторы и их выполнять. Выполнение программы «проиграем» на структурной схеме компьютера на конкретном примере (например, умножение чисел 5 и 8).

REM — оператор комментариев; неисполняемый оператор, все, что стоит в строке программы после этого оператора, компьютером игнорируется.
INPUT — оператор ввода значений переменных; процессор отводит в оперативной памяти области (некоторое количество ячеек) и «называет» их именами переменных (А, В) из списка вво'да; запрашивает у пользователя их значения (на экране дисплея появляется знак вопроса ?); пользователь вводит значения переменных с клавиатуры (5,8); процессор записывает эти значения в отведенные области памяти.
LET — оператор присваивания; процессор считывает из памяти значения переменных (А, В), составляющих арифметическое выражение в правой части присваивания; вычисляет значение арифметического выражения (40); отводит в памяти область под переменную, стоящую в левой части присваивания (X); записывает вычисленное значение (40) арифметического выражения в эту область.
PRINT — оператор вывода значений переменных на экран; процессор считывает значение переменной (X) из памяти и высвечивает это значение (40) на экране дисплея.
END — оператор окончания программы; на экране дисплея появляется соответствующее сообщение (Ok) и курсор.
Системы счисления. Двоичная система счисления и ее применение в вычислительной технике.
Под системой счисления понимают совокупность приемов для представления и записи чисел с помощью определенного количества знаков (цифр).
Мы привыкли считать предметы десятками: десять единиц образуют десяток, десять десятков — сотню, десять сотен — тысячу и т. д. Наша система счисления десятичная. Но десятичная система не единственно возможная. Существуют, например, двенадцатеричная система счисления (там счет идет на дюжины) или римская система счисления.
Различают позиционные и непозиционные системы счисления. В позиционных системах значение (вес) каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Примером позиционной системы является десятичная система счисления. Проанализируем, как представляются числа в этой системе.
Для представления чисел в десятичной системе используются десять цифр: от 0 до 9. Число 2359,407, записанное в десятичной системе, читается как «две тысячи триста пятьдесят девять и четыреста семь тысячных » и может быть представлено следующим образом:
2-1000+3-100+5-10+9-1+4-0,1+7-0,001. Множители каждого слагаемого представляют собой одну из степеней числа 10, т.е. можно записать:
10^+9-10°+4- 10^ +
10^ + 10^ + 7
10^ +
+ 0 - 10" + 7 - 10"
Подчеркнем, что положение (позиция) цифры определяют ее значение. Двойка, стоящая на первом месте, означает количество тысяч в этом числе, а четверка, стоящая после запятой, — количество десятых долей.
В непозиционных системах значение цифры не зависит от ее позиции. Общеизвестным примером непозиционной системы является римская система счисления. Так, в числе МСХХХ11 (1132) значение цифры Х не изменяется и всегда равно десяти.
В ЭВМ применяются позиционные системы счисления, в основном двоичная система. Применение двоичной системы обусловлено, прежде всего, простотой представления в ЭВМ только двух цифр (0 и 1), которые она использует. Чтобы представить две цифры в ЭВМ, надо иметь элементы с двумя устойчивыми состояниями, одно из которых можно принять за 1, другое — за 0. Таких элементов достаточно много: намагниченный или ненамагниченный сердечник, открытый или закрытый транзистор и др.
Число в двоичной системе, так же как в десятичной, изображается последовательностью цифр. Например, десятичное число 13 изображается как последовательность двух цифр 1 и 3, это же число в двоичной системе — последовательность четырех цифр—1101: 1310^11012.
Так же как в десятичной, в двоичной системе есть понятие разряда числа. Если в десятичной — это разряд единиц, десятков, сотен и т. д. (т. е. разряд 10* 10^ 10^ и т. д.), то в двоичной — это разряд 2°, 2^, 2^, 2^ и т. д. Двоичный разряд принято называть битом.
Например, число 1101 в двоичной системе можно представить как 1-2^+1-2^+0-2^+1-2^.
Алгоритм перевода числа из двоичной системы счисления в десятичную достаточно простой. Напомним, что для такого перевода необходимо вычислить сумму вкладов битов по правилам десятичной системы счисления. Примеры: 101 = 2+0+1==
= 5; 110 010 = 2^+2^+0+0+2+0= 50.
Для перевода десятичной записи числа в двоичную существует несколько различных способов. Рассмотрим, например, следующий