первый помощник

второй помощник
Добро пожаловать на сайт учащихся СОШ №11 г.Свободного! Подготовимся к экзамену вместе!

Главная Устный экзамен Тестирование Готовимся к ЕГЭ Карта сайта

Полезные ссылки

Билет №1. Понятие информации. Виды информации, ее свойства, классификация. Информационные процессы. Передача информации. Информационная система, управление, обратная связь.

Билет №2. Понятие о кодировании информации. Позиционные и непозиционные системы счисления. Двоичная арифметика.

Билет №3. Подходы к изменению информации. Преимущества и недостатки вероятного и алфавитного подходов к измерению информации. Единицы измерения информации. Скорость передачи информации.  Пропуская способность канала связи.

Билет №4. Понятие алгоритма: свойство алгоритмов, исполнителя алгоритмов. Автоматическое исполнение алгоритма. Способы описания алгоритмов. Основные алгоритмические структуры и их реализация на языке программирования. Оценка эффективности алгоритмов.

Билет №5. Язык программирования. Типы данных. Реализация основных алгоритмических структур на языке программирования. Основные этапы разработки программ.

Билет №6. Технология программирования. Структурное и объектно-ориентированное программирование. Процедуры и функции. Локальные и глобальные переменные.

Билет №7. Типы данных. Структуры данных. Обработка массивов. Итеративные и рекурсивные алгоритмы обработки массивов. Многомерные массивы.

Билет №8. Основные понятия и операции формальной логики. Законы логики. Логические переменные. Логические выражения и их преобразования. Построение таблиц истинности логических выражений.

Билет №9. Логические элементы и схемы. Типовые логические устройства компьютера: полусумматор, сумматор, триггеры, регистры. Описание архитектуры компьютера с опорой на составляющие ее логические устройства.

Билет №10. Моделирование как метод познания. Информационные модели. Основные этапы компьютерного моделирования.

Билет №11. Информационные основы управления. Общие принципы управления. Роль обратной связи в управлении. Замкнутые и разомкнутые системы управления. Самоуправляемые системы, их особенности. Понятие о сложных системах управления, принцип иерархичности систем. Самоорганизующиеся системы.

Билет №12. Архитектура современных компьютеров. Основные устройства компьютера, их функции и взаимосвязь. Магистрально-модульный принцип построения компьютера. Безопасность, гигиена, эргономика, ресурсосбережение, технологические требования при эксплуатации компьютерного рабочего места. Комплектация компьютерного рабочего места в соответствии с целями его использования.

Билет №13. Компьютерные сети. Аппаратные средства компьютерных сетей. Топология локальных сетей. Характеристики каналов (линий) связи. Профессии, связанные с обеспечением эксплуатации сетей.

Билет №14. Основные этапы становления информационного общества. Информационные ресурсы государства, их структура. Образовательные информационные ресурсы. Информационная этика и право, информационная безопасность. Правовые нормы, относящиеся к информации, правонарушения в информационной сфере, меры их предотвращения.

Билет №15. Классификация и характеристика программного обеспечения компьютера. Взаимосвязь аппаратного и программного обеспечения компьютера. Многообразие операционных систем. Понятие о системном администрировании. Программные и аппаратные средства для решения различных профессиональных задач.

Билет №16. Компьютерные вирусы и антивирусные программы. Специализированное программное обеспечение для защиты программ и данных. Технологии и средства защиты информации в глобальной локальной компьютерных сетях от разрушения, несанкционированного доступа.

Билет №17. Понятие файла. Файлы прямого и последовательного доступа. Файловый принцип организации данных. Операции с файлами. Типы файлов. Аппаратное обеспечение хранения данных и функционирования файловой системы.

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

Билет №19. Кодирование графической информации. Растровая и векторная графика. Средства и технологии работы с графикой. Создание и редактирование графических информационных объектов средствами графических редакторов, систем презентационной и анимационной графики. Форматы графических файлов. Способы сжатия.

Билет №20. Кодирование звуковой информации. Форматы звуковых файлов. Ввод и обработка звуковых файлов. Использование инструментов специального программного обеспечения и цифрового оборудования для создания и преобразования звуковых файлов.

 

    Билет №7

Типы данных. Структуры данных. Обработка массивов. Итеративные и рекурсивные алгоритмы обработки массивов. Многомерные массивы

Обсуждая билет №5, мы уже говорили о типах данных, их роли в алгоритме, а также о том, что дает компьютеру «знание» типа конкретной величины. Мы также говорили, что существуют простые и сложные типы данных. Простые типы чаще всего используются для хранения рабочих величин, но могут быть также аргументами или результатами в несложных алгоритмах. Тем не менее для представления данных в реальных задачах возможностей простых данных обычно недостаточно. В самом деле, в типичном случае о человеке необходимо хранить фамилию, имя и отчество (текстовые данные), год рождения (число), пол и семейное положение (одно из значений, выбираемых из фиксированного набора), факты наличия или отсутствия определенных признаков, например, обладая недвижимостью (логические данные) и т.д. В результате для объединения совокупности всех относящихся к одному реальному объекту данных (компонентов) требуется возможность создания из них единой сложной структуры.

      Примечание. Стоит отметить, что если к сложному набору данных, состоящему из отдельных компонентов (полей), добавить методы их обработки, то получится автономная конструкция еще более высокого уровня – объект (см. билет №6).

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

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

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

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

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

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

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

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

m1 : array [1 . .10] of real ; - Паскаль

float m2[10] ; - Си, Java  и ряд других языков программирования

dim m3 (9) as variant ; - VBA (Visual Basic for Applications)

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

    Подчеркнем, что хотя в одних языках (Basic, Си) индексы, определяющие положения элемента массива, всегда числовые, а других (Паскаль, Ада) допускаются и другие «счетные» типы (более точно их называть порядковыми). Хорошим примером порядковых данных может служить символьный тип CHAR, Упорядоченный в соответствии с принятым в компьютере алфавитом (см. билет № 20).

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

    При решении задач на обработку массивов очень важно постоянно контролировать корректность значений индексов. Особенно актуальной эта проблема становится в том случае, если значение индекса задаются не в явном виде, а вычисляются тем или иным способом. Рассмотрим в качестве примера следующий фрагмент программы. Пусть в описании сказано, что массив Q состоит из элементов с номерами от 1 до 5. Пусть далее в некотором месте программы находится оператор присваивания Q[t+2] : = 0. Тогда в случае t>3 нулевое значение будет сохранено вне массива, точнее говоря, в то место памяти, где находился бы элемент под номером t+2, если бы он существовал. Так что в результате выполнения данного некорректного присвоения в лучшем случае будет «испорчено» значение какой-либо другой переменной, а в худшем – сама исполняемая программа. В любом случае найти такую ошибку крайне сложно: для этого потребуется большое внимание и глубокое понимание логики работы программы.

        Введение сложного типа «массив» позволяет компактно описывать решение широкого круга важных для практики задач. К типовым задачам обработки массива относится:

·       заполнения его элементов по определенному закону;

·       нахождение некоторого характерного элемента (например, максимального или первого нулевого) и, может быть, его положения;

·       поиск элементов, удовлетворяющих определенному условию (или подсчет их количества);

·       определение некоторых характеристик массива (сумма, среднее значение, наличие упорядоченности или симметрии);

·       сортировка массива;

·       перенос данных из одного массива в другой, разделение массива на части, объединение массивов – и некоторые другие. Подчеркнем, что к этим, казалась бы, весьма абстрактным упражнениям сводится огромное множество практических задач: от обслуживания каталогов дисков до обработки результатов соревнований.

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

PROGRAM ind_max (INPUT, OUTPUT);

CONST n = 10;

m: ARRAY [1..n] OF INTEGER = (8,10,9,4,7,2,5,6,3,1) ;

VAR k, im: INTEGER;

BEGIN im : = 1;

  FOR k : =2 TO n DO

     IF m [k] . m[im] THEN im : = k;

WRITELN (`max=`, im)

END.

       Программа настолько проста и традиционна, что не требует особых комментариев. Отметим только, что простоты отладки элементы массива не вводятся с клавиатуры, а инициализируются входящими в текст программы значениями с помощью механизма так называемых типизированных констант. Разумеется, вместо этого для ввода может быть написан и стандартный цикл FOR k : 1 TO n DO READLN (m[k]).

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

Пример итеративной обработки массива

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

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

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

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

   PROGRAM sort_iter(INPUT, OUYPUT);

   CONST n = 10:

   m:ARRAY [ 1..n] OF INTEGER = (10,9,8,7,6,5,4,3,2,1,);

   VAR i,p: INTEGER; c; BOOLEAN;

   BEGIN REPEAT c : = FALSE;

         FOR i:  = 1 TO n – 1 DO

           IF m[i] > m[i+1] THEN

BEGIN p : m[i] ; m[i] : = m[i+1] ;

m[i+1] : = p;

c := TRUE

END;

For i  : = 1 TO n DO

   WRITE (m [i], ` ` ) ; WRITELN;

UNTIL NOT c;

END.

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

Примеры рекурсивной обработки массива.

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

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

     Рассмотрим возможную реализацию программы.

PROGRAM sort_rekurs (INRUT, OUTPUT) ;

CONST n = 10;

M: ARRAY [1 ..n] OF INTEGER = (10,9,8,7,6,5,4,3,2,1);

FUNCTION ind_max (k: INTEGER) : INTEGER;

VAR w: INTEGER;

BEGIN IF k > 1 THEN BEGIN w : = ind_max (k – 1);

     IF m[k] < m [w] THEN ind_max : = w

                                ELSE  ind_max : = k

END

ELSE ind_max : = 1

END;

PROCEDURE sort 2 (p: INTEGER);

VAR im, c: INTEGER;

BEGIN im : = ind_max(p);

c : = m[im]; m [im] : = m[p]; m[p] : = c;

FOR c : = 1 TO n DO WRITE (m[c], ` `); WRITELN;

IF p > 2 THEN sort2(p – 10

END;

BEGIN sort2(n)

END.

    Описание начнем рассмотрения рекурсивной функции ind_max для нахождения индекса максимального элемента. Ее рекурсивная логика может быть сформулирована следующим образом. Решение задачи для массива из n элементов весьма трудоемко, поэтому его постепенно сводим к более простому: для n – 1, n – 2 и т.д. элементов (см. вызов  ind_max (k-1), который и является рекурсивным вызовом функцией самой себя). Так поступаем до тех пор, пока ответ не станет тривиальным: в массиве из одного элемента индекс максимально равен индексу этого единственного элемента ( в нашем случае1). Далее производится «обратный ход» - зная текущее значение  ind_max, соответствующее ему значение максимума сравниваем с текущим элементом массива, после чего индекс наибольшего из сравниваемых элементов запоминаем. Таким образом, отрабатывается последовательная цепочка рекурсивных вызовов и без всякого цикла организует полный перебор всех элементов массива.

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

     Теперь, рассматривая функцию id_max как единое целое и не обращая внимание на ее внутреннюю логику, обсудим второй рекурсивный алгоритм – сортировку массива, описанную в рекурсивной процедуре sort2. Ее логика работы такова. В массиве размерности  n находится максимальный элемент, и он меняется местами с последним. В результате самый последний элемент, и он меняется местами с последним. В результате самый последний элемент массива займет свое окончательное место и останется рассортировать массив уже меньшего размера, т.е. n - 1. Аналогичным образом задача последовательно решается для все меньшего и меньшего массива, пока не останется массив из одного элемента, в котором, естественно, сортировка уже не требуется: условие p > 2 предотвращает вызов sort2 (1)  и процесс рекурсии благополучно завершается.

    Примечание. Имеющийся в sort2 цикл вывода массива на экран играет вспомогательную роль. Читатели при желании могут без труда самостоятельно оформить в его в виде рекурсивной процедуры (печатаем первый элемент, а затем вызываем процедуру вывода оставшегося массива!), реализовав тем самым число рекурсивную программу без единого цикла.

     Основная программа состоит из единственной строки sort2 (n) , которая запускает процесс сортировки, начиная с полного массива.

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

     В математике, физике и некоторых других науках тем не менее широко используются и многомерные массивы. Поэтому такие структуры не смогли не появиться в языках программирования. Фактически есть два способа определения многомерных массивов6 непосредственный  и создание сложной структуры. Мы ограничимся обсуждением двумерных массивов; обобщения для большей размерности делается аналогично. На языке Паскаль, например, эти два способа описания массивов выглядят так:

m1: ARRAY [1..3, 1..5] OF REAL;

m2: ARRAY [1..3] OF ARRAY [1..5] OF REAL;

Примечание. Обращение к элементам массивов m1 и  m2 отличаются6 они записываются как  m1[ i, j ] m2[ i ]  [j ] соответственно.

    В некоторых простых языках программирования типа Basic используется только традиционная математическая («матричная») форма представления массивов, а в языках с более развитыми средствами создания данных, в частности Паскале, допустимы обе формы.

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

   С математической точки зрения для увеличения размерности массива достаточно формально приписать еще один индекс. Однако для реализации такой структуры в памяти компьютера потребуется как-то приспособить многомерную структуру данных к хранению в одномерной памяти. «За исключением языка Fortran, все языки хранят двумерные массивы как последовательности строк…Такое размещение вполне естествен, поскольку сохраняет идентичность двумерного массива данных в «линейном» ОЗУ компьютера.

    Учитывая, что все элементы массива однородны ( имеют один и тот же тип и, следовательно, занимают одинаковое место в памяти), получить формулу пересчета индексов в требуемый адрес ОЗУ является несложной задачей. И хотя школьных знаний для этого вполне достаточно, мы не будем сейчас этим заниматься. Заметим лишь, что в 32-разрядных процессорах Intel специально предусмотрены аппаратные методы адресации, в которые заложены такие формулы для данных стандартной длинны (1,2,3 и даже 8 байт), что существенно облегчает для программиста (или для компилятора) доступ к элементам массивов.

 

Главная Устный экзамен Тестирование Готовимся к ЕГЭ Карта сайта Полезные ссылки
: msosh11@mail.ru