Как проходит экзамен по информатике в вузе

6.1. Экзамены и зачеты по информатике

Изучение информатики должно заканчиваться экзаменами, на которых проверяется знание основ информатики и
умения решать задачи на персональных ЭВМ. Зачеты по информатике могут прово­диться
по завершении каждого из разделов курса информатики либо в конце курса по совокупности
практических заданий.

Зачеты и экзамены по
информатике могут и должны проводиться с помощью и использованием персональных
ЭВМ. При дистанци­онном образовании персональные компьютеры являются основным
средством обучения и поэтому экзамены по информатике должны проводиться только
с помощью ЭВМ.

На зачетах должны проверяться уровень изучения курса инфор­матики и
выполнение компьютерных заданий.
Проверка знаний и анализ выполнения заданий по информатике могут и должны
проверяться на ЭВМ. В качестве средств контроля могут и должны использоваться бумажные
копии результатов тестирования и выпол­нения заданий на ЭВМ.

Экзамены в вузах и колледжах, обучающих по программе бакалавриата,
служат для проверки знаний студентов в соответствии с госу­дарственными стандартами высшего профессионального
образования [I], утвержденными правительством Российской Федерации в 1994 г.

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

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

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

1) оформление на ЭВМ стихотворения
или юмористического рас­сказа, подготовленных с помощью редактора текстов;

2) оформление на ЭВМ рекламы
или забавного рисунка, создан­ных с помощью графического редактора;

3) проведение поиска
информации в сети Интернет по своим лич­ным и профессиональным вопросам и
проблемам.

Базовый уровень знаний
основ информатики и владения средст­вами ЭВМ проверяется на зачетах или
экзаменах по результатам самостоятельного выполнения на ЭВМ следующих учебных
заданий:

1) организация на ЭВМ базы
данных о товарах, услугах или фир­мах со своими сведениями в некоторой
системе управления базами данных;

2) организация на ЭВМ базы
знаний о своих знакомых, друзьях или круге предметов с самостоятельно
подобранными правилами вывода.

3) организация на ЭВМ калькуляций
и расчетов закупок товаров или сметы затрат с помощью электронных таблиц.

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

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

1) организация на ЭВМ диалоговой процедуры или программы с
использованием диалоговой системы программирования;

2) организация на ЭВМ обработки данных на основе самосто­ятельно
составленных алгоритмов и программ;

3) самостоятельное составление алгоритмов и программ решения задач
вплоть до отладки и получения результатов на ЭВМ.

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

1) самостоятельная постановка
задач и разработка соответству­ющих алгоритмов и программ их решения на
ЭВМ:

2) подбор методов решения
некоторого класса профессиональных задач и его реализации в виде диалоговых программ
на ЭВМ;

3) обоснование правильности результатов решения задач, полу­ченных
на ЭВМ с помощью самостоятельно созданных алгоритмов и программ.

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

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

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

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

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

При компьютерном
тестировании предварительная оценка отве­тов проводится сразу после ввода их в
ЭВМ, а преподаватели выставляют окончательную оценку по протоколам тестирования.
Данная форма наиболее удобна для учащихся и существенно упро­щает работу
преподавателям.

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

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

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

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

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

Для записи программ,
могут применяться любые языки програм­мирования — Бейсик, Паскаль, Си, Фортран
и т.д. Однако необ­ходимо помнить, что в вузах для обучения и принятия экзаменов
используются обычно персональные компьютеры IBM PC с опера­ционной системой MS DOS или Windows.

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

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

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

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

Во многих вузах экзамены
по информатике проводятся и для поступающих.
В 1999 г. приказом № 640 министра образования Рос­сийской Федерации всем вузам
разрешено вводить вступительные экзамены по информатике в качестве
альтернативных вступительных испытаний на профильные специальности и
факультеты.

Для вступительных экзаменов по информатике по заказу Гос­комвуза
России в 1994 г. была создана типовая программа [З]. Она основана на учебных
программах, утвержденных Министерством образования, и школьных учебниках
информатики, имеющихся в средних учебных заведениях.

В 1999 г. более 40 вузов Российской Федерации принимали всту­пительные экзамены по информатике:
вузы — Москвы, Петербурга, Владивостока, Владимира, Воронежа,
Комсомольска-на-Амуре, Перми, Самары, Саратова, Томска, Тулы, Череповца. Полный
список вузов, принимающих вступительные экзамены по информатике, можно найти в
сети Интернет с помощью запроса «экзамен инфор­матика» в поисковой системе
Апорт.

В средних школах выпускные
экзамены по информатике, как пра­вило, проводятся по выбору учащихся в
зависимости от их дальнейших планов. Программы курса информатики с выпускными
экзаменами были созданы и рекомендованы Министерством образования для средних
школ в 1988, 1992 и 1998 гг. [4, 5].

6.2. Решение экзаменационных задач

 

Решение задач по информатике
представляют интерес не только для всех студентов, но и для абитуриентов и
учащихся средних школ, собирающихся поступать на профильные специальности и
факуль­теты. Здесь рассматриваются задачи, предлагавшиеся на вузовских
экзаменах по информатике, а также задачи выпускных и вступитель­ных экзаменов в
1994-1997 годах.           

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

Основной сложностью
организации экзаменов по информатике является необходимость отладки
программ и получения результатов на ЭВМ при разнообразии языков программирования
— Бейсик, Паскаль, Си, Фортран,
изучаемых в вузах и школах. В силу этих причин приводимые здесь формулировки задач
носят содержательный характер, независимый от языков программирования и
используемых ЭВМ.

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

Существуют три основных общих
способа организации ввода исходных данных в персональных ЭВМ, имеющихся в
таких языках программирования как Бейсик, Паскаль, Си и Фортран. Рассмотрим их
особенности и недостатки.

П е р в ы й   с п о с о б —
ввод исходных данных с клавиатуры ЭВМ. Этот способ может быть реализован на
любых персональных ЭВМ с помощью любого языка программирования. Однако здесь
весьма существенен порядок ввода данных, который должен явно указы­ваться в условиях
задач.

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

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

Т р е т и й   с п о с о б —
наиболее удобный для отладки программ на персональных ЭВМ — описание исходных
данных внутри текста программ в виде присваивании или операторов data на языке Бейсик. Этот способ описания данных приведен в
настоящем учебном по­собии, изложен во всех школьных учебниках по информатике и
известен всем школьникам, изучавшим информатику в школах.

Однако этот способ, характерный и удобный для диалоговых программ,
отсутствует в профессиональных языках программирова­ния таких как Паскаль, Си,
Фортран, изучение которых выходит за рамки школьных учебников. По этой причине
в формулировках задач по программированию, ориентированных на учащихся с
углубленным изучением информатики, используется форматный способ ввода,
принятый для професссиональных языков программирования.

Здесь в примерах программ
решения экзаменационных задач ис­пользуется самый простой и наиболее удобный
для отладки программ способ организации ввода тестовых данных в виде операторов data на языке Бейсик. Однако
формулировки задач приводятся так, чтобы исходные данные могли вводиться всеми
тремя указанными выше способами.

Рассмотрим образцы решения
экзаменационных задач с приме­рами составления как алгоритмов, так и сценариев
диалога. Использо­вание сценариев диалога и является тем средством, которое
уравнивает все используемые на персональных ЭВМ языки программирования и
позволяет экзаменующимся избегать ошибок ввода-вывода данных, характерных для
профессиональных языков программирования.

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

В качестве основного языка
иллюстраций и примеров программ здесь и далее используется язык Basic для компьютеров IВМ PC как из-за удобств
описания входных данных, так и из удобств отладки программ на Бейсике на персональных
ЭВМ.

Многолетняя практика
проведения экзаменов по информатике на ЭВМ показала, что отладка программ
на Бейсике стабильно завер­шается на ЭВМ в два раза быстрее, чем на более
«мощных» языках, таких как Паскаль, Си или Фортран, что весьма существенно при
жестких ограничениях времени на экзаменах.

Задача 1.
«Информационно-логическая».

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

фамилия	имя	рост	вес	пол
Иванов	Вова	160	85	муж
Петрова	Катя	167	67	жен
Сидоров	Миша	180	80	муж

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

Сценарий

ученики:

 <фам> <имя> <вес>
<рост> <пол>        *

                        …
… …

самый
легкий ученик:

<фам> <имя> <вес>

отсутствует

Программа                                                   Алгоритм

‘ выбор самого легкого
ученика               алг «выбор самого легкого ученика»

сls      
                                                             ‘ нач

? «ученики:»                                                 ‘
вывод («ученики:»)

vs = 0                                                              ‘ vs = 0

do                                                                    ‘ цикл

read fm$, nm$, r, v, pl$                            ‘
    ввод fmS, nm$, r, v, pl$

if fm$ = «» then exit do                            ‘     если fm$ = «» то выход

fm$, nm$, r, v, pl$                                                ‘
    вывод fm$, nm$, r, v, pl$

if р1$=»муж» then                                   ‘
    если
pl$ = «мyж» то

if vs = 0 then                                           ‘
       если vs = 0 то

vs = v                                                     ‘          
vs = v

fs$ = finS: ns$ = nm$                           ‘           fs$ = fin$: ns$ = nm$

elseif v < vs then                                     ‘
       инес v < vs то

vs = v                                                     ‘          
vs = v

fs$ = fm$: ns$ = nm$                           ‘          
fs$ =fm$: ns$ = nm$

end if                                                       ‘
      кесли

end if                                                          ‘
    кесли

loop                                                                 ‘ кцикл

? «самый легкий ученик:»                         ‘ вывод («самый легкий ученик:»)

if vs = 0 then                                                  ‘ если vs = 0 то

?
«отсутствует»                                     ‘ 
   вывод («отсутствует»)

elseif vs > 0 then                                            ‘ инес vs > 0 то

? fs$, ns, vs                                              ‘
    вывод (fs$, ns, vs)

end if                                                          ‘ кесли

end                                                                  ‘ кон

data «Иванов», «Вова», 160, 85, «муж»

data «Петрова», «Катя», 167, 67, «жен»

data «Сидоров», «Миша», 180, 80, «муж»

data «», «», 0, 0, «»

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

Задача 2.
«Экономическая».

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

товар	тип	цена	кол-во
ананасы	прод	8000	40
утюги	пром	60000	3
сахар	прод	6000	20

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

Сценарий

промышленные товары

отсутствуют

<товар>
<цена> <кол> <стоим>               *

                        … … …

общая стоимость = <sum>

Программа                                                   Алгоритм

‘ стоимость промтоваров                          ‘ алг
«стоимость промтоваров»

сls                                                                    ‘ нач

?
«промтовары:»                                    ‘ вывод («промтовары:»)

n
= 0: sum = 0                                            ‘
п = 0: sum = 0

do                                                               ‘ цикл

read tv$, tp$, сn, kl                              ‘
    ввод tv$, tp$, сn, kl

if tv$ = «» then exit do          
                       ‘ если tv$ = «» то выход

if tp$ = «пром» then 
                               ‘     если tp$ = «пром»
то

n = n + 1                  
                             ‘        n =n + 1

st = cn*kl                                               ‘        st = cn *kl

? tv$, en; kl; st             
                        ‘
       вывод (tv$, en, kl, st)

sum = sum + st                                      ‘        sum = sum + st

end if                                                          ‘
    кесли

loop                                                                 ‘ кцикл

if n = 0 then                                               ‘ если n = 0 то

?
«отсутствуют»                                 ‘     вывод («отсутствуют»)

else                                                                  ‘ иначе

?
«общая cтoимocть=»,sum              ‘
    вывод(«общая
стоимость=», sum)

end if                                                          ‘ кесли

end                                                                  ‘ кон

data «сахар», «прод», 6000, 20

data «утюги», «пром», 60000, 3

data «книги», «пром», 4000, 30

data «», «», 0, 0

Рассмотрим в качестве иллюстрации примеры решения экзаменаци­онных задач в МЭСИ — Московском
государственном университете экономики, статистики и информатики. Этот университет
одним из первых в 1991 году ввел вступительные экзамены по информатике и стал
лидером в дистанционном образовании среди государственных вузов Российской
Федерации.

Задание на экзаменах в МЭСИ
состоит из пяти задач. Первая задача по системам счисления. Вторая задача — на
алгебру логики. Третья задача — тест или анализ блок-схемы. Четвертая и пятая
задача — задача на составление алгоритмов и программ.

Первые три задачи в экзаменационных билетах МЭСИ по слож­ности
оцениваются на два балла, а четвертая и пятая задача — на четыре и пять баллов.
Положительную оценку на экзамене получает та работа, в которой набрано не менее
8 баллов.

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

В виду указанной особенности вступительных экзаменов по ин­форматике
в МЭСИ разберем примеры решения задач на составле­ние программ, используя для
описания алгоритмов псевдокод, а не блок-схемы, как это делается в учебниках
МЭСИ.

Задача 1. Написать
программу на любом языке программирова­ния согласно следующему условию.

Дана целочисленная матрица А размера M´N, где M,N — задан­ные натуральные числа. Найти
количество столбцов матрицы, со­держащих одни нулевые элементы.

Пример матрицы:

Для представления матрицы в программе на языке Бейсик можно
использовать операторы data,
в первой строке которых указывается размерность матрицы:

data 5

data 1, 0, 1, 0, 0

data 0,
1, 0, 0, 0

data 0, 0, 1, 0, 0

data 0, 1, 0, 0, 0

data 0, 0, 0, 0, 0

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

     Матрица А<n><n>:

<а₁₁>
… <a_1n>

   … … …

<a_nl>
… <a_nn>

Число
нулей в столбцах:

<d₁> … <d_n>

Решением поставленной задачи на ЭВМ можно получить с помо­щью
следующего алгоритма и программа на языке Бейсик. Обратите внимание в программе
используются массивы переменной длины, которая определяется при вводе размеров
матрицы А:

‘ подсчет нулевых
столбцов                      ‘  алг
«подсчет нулевых столбцов»

‘ в квадратной матрице Ann                     ‘ нач

read n                         
                                   ‘
чтение(п)

dim A(n,n), D(n)                                            ‘ массивы А(1:п,1:п), D(1:n)

print «Матрица A»;n;n;«:»       
                 ‘ вывод («Матрица А»;п;п; «:»)

for k = 1 to n                  
                               ‘ от k = 1 до п цикл

for 1 =1 to n                  
                            ‘
   от
l =1 до п цикл

read A(k,l)                                            ‘
      чтение A(k,l)

print A(k,l)
                                           ‘       вывод A(k,l)

next 1                                                         ‘
   кцикл

 next k                                                
            ‘ кцикл

for k = 1 to n                  
                               ‘ om k= 1 до п цикл

D(k) = 0                     
                                ‘    D(k) = 0

for 1 = 1 to n                                              ‘
   от
l=1 до п цикл

if A(k, l) = 0 then                                  ‘
      если A(k, l) = 0 то

D(k) = D(k) + 1           
                      ‘         
D(k) = D(k) + 1

end if                                                     ‘
      кесли

next 1                                                         ‘
   кцикл

print D(k);                                                 ‘
   вывод D(k);

next k                                                              ‘ кцикл

end    
                                                             ‘ кон

Задача 2. Дана строка
символов. Распечатать все слова нечетной длины, отличные от второго слова.

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

Пример строки

Я волком бы выгрыз бюрократизм.

К мандатам почтения нет.

Результат обработки

бы

выгрыз

бюрократизм.

почтения

нет.

Для представления строк в программе на Бейсик можно восполь­зоваться
операторами data:

data «Я волком бы выгрыз
бюрократизм.»

data «К мандатам почтения нет.»

data «»

Здесь пустое слово «» означает конец исходного текста.

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

исходный
текст:

      <строка₁>

            … …

    
<строка_n>

        слова нечетной длины:

     <слово₁>

            … …

    
<слово_m>

Решение поставленной задачи на ЭВМ можно получить с помо­щью
следующих алгоритма и программы на Бейсике, в которых в виде вспомогательного
алгоритма и подпрограммы выделена обра­ботка каждой отдельной строки текста:

‘ выделение слов нечетной длины                       ‘ алг «слова нечетной
длины»

print «исходный текст:»                                         ‘ вывод «исходный
текст;»

n = 0: s2$ = «»                                                            ‘ n = 0: s2$ = «»

print «исходный текст:»                                         ‘ вывод «исходный текст:»

do                                                                                ‘цикл

read str$                                                                ‘
   чтение_строки

if str$ = «» then exit do                                             ‘ при str$ = «» выход

print str$                                                                ‘
   вывод_строки

gosub stroka                                                          ‘
   обработка_строки

loop                                                                             ‘ кцикл

end                                                                              ‘ кон

stroka: ‘ обработка строки                                     ‘ алг «обработка строки»

dl = len(sfr$)                                                          ‘    dl =
длuнa(str$)

 print «слова
нечетной длины:»                            ‘ вывод «слова нечетной
длины:»

sl = 0                                                                           ‘ sl=0

for k=l to dl                                                                ‘ от k = 1 до dl цикл

if str$(k) 0 «» then                                                ‘
   если str$(k)
¹ «» то

sl = sl + 1                                                              ‘       sl
= sl + 1

elseif sl > 0 then                                                     ‘
   инеc sl > 0 то

p = k — sl + 1                                                        ‘       p
= k — sl + 1

slv$ = mid$(str$,p,sl)                                          ‘      slv$
= cpeдн.(str$,p,sl)

n = n + 1                                                              ‘      n =
n + 1

if n = 2 then                                                         ‘
     если n = 2 то

sl2$ = slv$                                                          ‘        
sl2$ = slv$

elseif slv$ 0 sl2$ then                                          ‘
   инеc slv$ ^ sl2$ то

if (sl/2)*2= si then                                             ‘
      если (sl/2) *2 = sl то

print slv$                                                      ‘
        вывод slv$

end if                                                                 ‘
      кесли

end if                                                                   ‘   
кесли

sl = 0                                                                    ‘   
sl = 0

end if                                                                      ‘ 
кесли

next k                                                                          ‘ кцикл

return                                                                         ‘ кон

Экзаменационные задачи МЭСИ (Московский государственный

университет экономики, статистики и информатики)

1. Дана действительная квадратная матрица А порядка N, где N — заданное натуральное число,
все элементы которой различны. Сколько элементов матрицы равны (МАХ + MIN)/2, где МАХ, MIN — соответственно,
максимальное и минимальное значения среди элементов матрицы.

2. Дана целочисленная матрица А размера M´N, где М, N — заданные
натуральные числа. Сформировать одномерный массив В, где B(i) равно сумме элементов, кратных
пяти и расположенных в i
строке матрицы i = 1,2, …. М.

3. Дана целочисленная матрица А размера MxN, где М, N — заданные
натуральные числа. Найти количество столбцов матрицы, содержащих одни нулевые
элементы

4. Дана квадратная целочисленная матрица А порядка N, где N —
заданное натуральное число, все элементы которой различны. По­менять местами
строку, в которой находится наименьший элемент матрицы, со строкой, где
находится наибольший элемент матрицы.

5. Дана целочисленная матрица А размера М х N, где М, N — заданные
натуральные числа, причем М > 5. Найти количество столб­цов матрицы, в
каждом из которых содержится не менее 5 нулевых столбцов.

6. Дана квадратная целочисленная матрица А порядка N, где N —
заданное натуральное число. Является ли заданная матрица маги­ческим квадратом,
т. е. такой матрицей, в которой суммы элементов во всех строках и столбцах одинаковы

7. Дана действительная матрица А размера M´N,
где М, N — заданные натуральные числа, все элементы которой различны.
Сформировать одномерный целочисленный массив В, где B(j) равно среднему арифметическому
значению индексов наибольшего и наи­меньшего элементов в j -ом столбце j
=1,2, …. N.

8. Дана строка символов. Распечатать все слова с количеством
символов больше 4 и меньше 10.

9. Дана строка символов. Распечатать самое длинное слово, начинающееся
на букву «К».

10. Дана строка символов. Распечатать самое длинное слово, первые
две буквы которого «КО».

11. Дана строка символов. Составить одномерный массив из слов,
которые отличны от слова
INFORMATION.

12. Дана строка символов. Распечатать самое длинное симмет­ричное
слово, первые две буквы которого «КО».

13. Дана строка символов. Выяснить, какое слово встречается раньше в
строке с наименьшим или наибольшим количеством симво­лов.

14. Дана строка символов. Определить среднее количество сим­волов в
словах четной длины.

15. Дана строка символов. Распечатать все слова нечетной длины,
начинающиеся и оканчивающиеся на букву «Т».

6.3. Проверка программ на ЭВМ

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

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

1) программа объявляется
содержащей ошибки, если можно ука­зать тесты, при которых выполнение
программы на ЭВМ приводит к отказу, сбою или получению неправильных результатов;

2) программа является
правильной, если при любых допустимых исходных данных она дает правильные
результаты.

Напомним два дополнительных, но весьма существенных опре­деления
допустимости исходных данных:

1) исходные данные считаются
допустимыми, если для этих данных существует решение поставленных задач;

2) исходные данные
недопустимы, если для этих данных постав­ленная задача не имеет решений.

Наконец правильность результатов решения регламентируется следующими
двумя определениями:

1) результаты решения
правильные, если они соответствуют требованиям поставленной задачи;

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

Подбор тестов для проверки программ опирается на некоторые общие
принципы, среди которых можно выделить следующие:

1) проверка частных случаев
задачи;

2) проверка основных случаев
задачи;

3) проверка граничных
случаев.

Частные случаи — те,
которые допускают простейшие способы решения и проверки правильности
результатов. Граничными случаями объявляются данные, которые лежат на границе
между допустимыми и недопустимыми данными.

Разбор этих понятий проведем на примере типичной экзамена­ционной
задачи по информатике.

Задача. «Средняя
зарплата».

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

Иванов	начальник	2500
Петров	сотрудник	1800
Сидоров	секретарь	900

Типичность этой задачи заключается в том, что она является одной из задач обработки данных, представленных в нашем случае таблицей. Частным случаем в
этой задаче является таблица, состо­ящая из одной строки (случай N = 1).
Граничным случаем — ситу­ация, когда все сотрудники получают одинаковую
зарплату и никто из них не получает зарплату выше средней.

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

Приведем примеры тестов, применявшихся при проверке на ЭВМ
правильности программ решения этой задачи:

1) тест₁ (проверка
основного случая):

Иванов	начальник	2500
Сидоров	секретарь	900

2) тест₂
(проверка частного случая):

3) тест₃
(проверка граничных ситуаций):

Иванов	начальник	2000
Петров	сотрудник	2000

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

Правильными ответами с точностью до формулировок в этой задаче
являются:

ответ₁
(основной случай):

ответ₂
(частный случай):

«никто не получает зарплату выше средней»

ответ₃ (граничный
случай):

«никто не получает зарплату выше средней»

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

Сценарий

список сотрудников:

<фамилия> <долж>
<з/плата>       *

                        …
… …

средняя з/плата = <среднее>

з/плата выше средней:

                                    <фамилия> <з/плата>                      *

                                                …
… …

не получает никто

Программа                                       Алгоритм

‘ выше средней з/платы                 алг «выше средней з/платы

сls                                                        нач

?
«сотрудники:»                             вывод
«сотрудники:»

do                                                      цикл

read Hn$, dl$, zp                             чтение fm$, dl$, zp

if fm$=«» then exit do                     если fm$=«» то выход

? fm$, dl$, zp                                   вывод fm$, dl$, zp

sum = sum + zp                               sum = sum + zp

n = n + 1                                           n = n + 1

loop    
                                                кцикл

sr = sum/n                                          sr = sum/n

?  «средняя з/плата=»; sr   
            вывод («средняя 3/nлama=»;sr)

? «з/плата выше средней:»            вывод(«з/плата
выше средней:»)

restore zplts                                        перезагрузка данных

ns = 0                                                  ns = 0

for k = 1 to n                                      от k = 1 до п

read fm$, dl$, zp                               чтение fm$, dl$, zp

if zp > sr then                                    если zp > sr то

? fni$, zp                                          вывод (fm$, zp)

ns = ns + 1                                        ns = ns + 1

end if                                                кесли

next k                                                  кцикл

if ns = 0 then                                      если ns = 0 то

? «нe получает никто»                  вывод
(«не получает никто»)

end if                                                  кесли

end                                                      кон

zplts:
‘данные о зарплате:

data «Иванов», «начальник»,
250000

data «Сидоров», «секретарь»,
90000

data «», «», 0

Проверку правильности этой программы следует провести на указанных
выше трех тестах. Достоинства приведенной программы:

1) хорошо организованный вывод результатов, совмещенный с выводом
исходных данных            (свойства, заложенные
в сценарий);

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

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

Экзаменационные задачи ГУУ

(Государственный университет управления)

Задача 1

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

Задача 2

N сотрудников (известны фамилии) работают в 2 смены по инди­видуальному
графику (1-й день — «утро», 2-й день — «вечер», 
3-й день — «выходной»). Все они в свое нерабочее время должны пройти диспансеризацию
в медпункте, который работает ежедневно в 2 смены. В день начала диспансеризации
о каждом сотруднике известно в какую смену он работает или то, что он выходной.
Со­ставить ежедневные списки посещения сотрудниками медпункта с указанием
времени посещения («утро» и «вечер»), учитывая, что в каждой смене медпункта
могут быть приняты не более М человек должен посетить медпункт один раз. Числа
N и М заданы.

Задача 3

На кинофестивале 35 стран представили свои фильмы. Общее число
фильмов не превышает 100. Известны названия стран — участ­ниц и фильмов, а
также баллы, полученные каждым из фильмов. Определить фильм, завоевавший первый
приз (максимальный балл) и страну, получившую наибольший средний балл за
представленные фильмы. Считать, что фильмы в общем списке по странам не упоря­дочены,
а фильм и страна, его представляющая, является единствен­ными победителями.

Задача 4

Известны очки, полученные каждым из М спортсменов-много­борцев в
каждом из N видов соревнований (N и М заданы). Для каждого из спортсменов
определить, в каких видах соревнований он получил результат не хуже других
спортсменов и какой конкретно. Фамилия спортсменов и названия видов соревнований
известны.

Задача 5

Даны сведения о соревновании N фигуристов ( N — заданное число):
фамилия, наименование спортивного общества, 10 оценок за выступление. Требуется
по каждому спортивному обществу опре­делить фигуриста, показавшего наивысший
результат, считая его единственным. Баллы, полученные фигуристом, подсчитываются
следующим образом: максимальная и минимальная оценки отбра­сываются, а из
остальных формируется средняя.

6.4. Олимпиадные задачи по информатике

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

Согласно приказу министра образования Российской Федерации № 500
победители и призеры международных олимпиад могут руко­водством российских
вузов зачисляться без экзаменов на
профиль­ные специальности и факультеты.

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

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

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

Победителям и призерам этой олимпиады, решившим наиболь­шее число задач
с наименьшим числом ошибок, было предложено поступление без экзаменов в
Московский институт электроники и математики (МИЭИ) для обучения по
специальностям в области информатики и вычислительной техники.

Примеры олимпиадных задач по информатике в других уни­верситетах и
вузах Российской Федерации, которые засчитывают результаты побед в
региональных, российских и международных олимпиадах по информатике, можно найти
в Интернете по запросу «олимпиада информатики» с помощью поисковых систем
Апорт, Ремблер или Яндекс. В 1999 году таких вузов было более сорока.

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

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

1) при правильных результатах на всех тестах 100% баллов; 2) при
получении правильного решения хотя бы на одном тесте 40% баллов, а за
результаты на остальных (n
— 1 )-м тестах добавляется
60%/(n — 1) баллов; 3) при неправильных результатах на всех тестах или
отсутст­вии программы оценка не ставилась.

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

задача 1 («Экзамены») —
50 баллов;

задача 2 («Слова») — 100
баллов;

задача 3 («4 точки») -150
баллов;

задача 4 («Ломаная») —
250 баллов.

Более 120 участников из 200 представили решения задач. Из них более
20 представили решения трех задач, девять участников пред­ложили решения
четырех задач. Правильное решение четырех задач представил только один
участник, но даже и у него в последней четвертой задаче программа не прошла все
тесты.

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

Рассмотрим формулировки задач, проверочные тесты и правильные
решения в форме программ на языке Basic. Первая задача относится к классу
информационно-логических.

Задача 1. «Экзамены».

Среди N абитуриентов, сдававших экзамены по информатике, математике
и языку, выбрать всех отличников и всех учащихся, на­бравших в сумме не меньше
проходного балла. Данные о проходном балле вводятся с клавиатуры, а данные о
результатах сдачи экзаме­нов представлены таблицей:

фамилия	имя	информатика	математика	язык
Иванов	Саша	4	4	3
Петрова	Катя	5	5	5
Сидоров	Алеша	5	3	3

Приведем проверочные тесты и правильные результаты:

Тест 1:

Иванов	Саша	4	4	3
Петрова	Катя	5	5	5
Сидоров	Алеша	5	3	3

проходной балл =? 12

Правильные результаты:

отличники:

Петрова Катя

не меньше проходного:

Иванов Саша

Петрова Катя

Тест 2:

Иванов	Саша	4	4	3
Сидоров	Алеша	5	3	3

проходной балл =? 12

Правильные результаты:

отличники:

отсутствуют

не меньше проходного:

Иванов Саша 4  4  4

Тест 3:

Сидоров

Алеша

5

3

3

проходной балл =? 14

Правильные результаты:

отличники:

отсутствуют                            

 не меньше проходного:

отсутствуют.

В приведенных тестах анализируются различные логические ситуации с
отсутствием «отличников» или «успешно» сдавших экза­мены. При составлении
программы эти ситуации можно явно преду­смотреть в сценарии диалога с ЭВМ:

Сценарий

  
оценки учащихся:

<фам> <имя> <мат>
<инф> <язык>
     *

 
………………………………….

проходной балл=? <b1>

отличники:

                                                         <фам> <имя>                      *

                                                            ……………

отсутствуют

не
меньше проходного:

                                                  <фам> <имя> <sum>       
         *

                                                            ……………..

отсутствуют

Программа                                                   Алгоритм

‘ результаты экзаменов                             алг «результаты экзаменов»

    cls                                                                      нач

  ? «оценки учащихся:»                                  вывод
(«оценки учащихся:»)

     do                                                                       цикл

 read fm$, nm$, mt, in, zk                                 ввод fm$, nm$, mt, in, zk

if fm$ = «» then exit do                                      если fm$ = «» то
выход

? fm$, nm$, mt, in, zk      
                        вывод (fm$, nm$, mt, in, zk)

loop    
                                                            кцикл

input «проходной балл=»,b1                      запрос («проходной балл=»,b1)

restore ocenki           
                                    перезагрузка_ oценки

? «отличники:»       
                                    вывод («отличники:»)

n = 0   
                                                            п = 0

do                                                                    цикл

read fm$, nm$, mt, in, zk                             ввод fm$, nm$, mt, in, zk

if fm$ = «» then exit do                               если fm$ = «» то выход

if mt=5 and in=5 and zk=5 then                 если mt=5 и in = 5 и zk=5 то

? fin$, nm$                                                   вывод (fm$, nm$)

n = n + 1                                                        n
= n + 1

end if                                                             кесли

loop                                                                 кцикл

 if n=0
then ? «отсутствуют»         
            если п=0 то вывод(«отсутствуют»)

restore ocenki           
                                    перезагрузка-оценок

? «не меньше проходного:»                      вывод
(«не меньше проходного:»)

n = 0   
                                                            п = 0

do                                                                     цикл

   read
fm$, nm$, mt, in, zk                             ввод fm$, nm$, mt, in, zk

       if
fm$ = «» then exit do                                если fm$ = «» то
выход

sum = mt + in + zk                                        sum
= mt + in + zk

if sum >= hi then                                           если sum >= bl то

? fm$, nm$, sum                                           вывод (fm$, nm$, sum)

n = n + 1                                                         n
= n + 1

end if                                                                          кесли

loop                                                                 кцикл

if n = 0 then ? «отсутствуют»                     если
п = 0 то вывод
(«отсутствуют»)

end     
                                                            кон

ocenki: ‘оценки учащихся

data «Иванов», «Саша», 4, 4, 3

data «Петрова», «Катя», 5, 5, 5

data «Сидоров», «Алеша», 5, 3, 3

data «», «», 0, 0, 0

Рассмотренная задача имеет чисто квалификационный характер проверки знаний информатики   по школьной программе и умения самостоятельно
составлять алгоритмы и программы решения на ЭВМ простейших информационных задач.
С этой задачей справилось большинство участников олимпиады. Однако далеко не
все преду­смотрели исключительные ситуации и в результате многие из них
потеряли определенную часть баллов на указанных тестах.

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

Задача 2. «Слова».

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

Исходная фраза:

ВЕЧЕРАМИ МЫ
СМОТРИМ ТЕЛЕВИЗОР

Циклическая перестановка слов:

МЫ СМОТРИМ
ТЕЛЕВИЗОР ВЕЧЕРАМИ

СМОТРИМ
ТЕЛЕВИЗОР ВЕЧЕРАМИ МЫ

ТЕЛЕВИЗОР
ВЕЧЕРАМИ МЫ СМОТРИМ

ВЕЧЕРАМИ МЫ
СМОТРИМ ТЕЛЕВИЗОР

Сценарий

     Исходная фраза:

<строка>

Перестановка
слов:

     
                                                      <строка’>      
   *

Проверочные .тесты:

Тест 1: Исходная фраза:

утром был дождь

Правильные результаты:

Перестановка слов:

был дождь утром

дождь утром был

утром был дождь

Тест 2: Исходная фраза:

правильно

Правильные результаты:

Перестановка слов:

правильно

Программа  
                                    Алгоритм

¢ перестановка слов                                    алг «перестановка слов»

cls       
                                                нач

?
«Исходная фраза:»                       вывод
(«Исходная фраза:»)

line input st$                                      ввод-строки (st$)

? st$                                                     вывод st$

In = len(st$)   
                                    in = len(st$)

? «Перестановка слов:»    
            вывод («Перестановка слов:»)

s$ = st$                                                s$ = st$

do       
                                                цикл

k = instr(s$,«»)                                 k
= instr(s$,«»)

if k = 0 then                                      если k = 0 то

? s$                                                    вывод (s$)

exit do                                               выход

end if                                                   кесли

lf$ = left$(s$,k-l)                              lf$
= left$(s$,k-l)

rt$ = right(s$,ln-k)                          rt$  = right(s$,ln-k)

ns$ = rt$ + «» + lf$                          ns$
= rt$  + «» + lf$

? ns$ вывод                                    (ns$ )

if ns$ = st$ then exit do                   при ns$ = st$  выход

s$ = ns$                                            s$  = ns$

loop                                                 кцикл

end                                                      кон

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

Задача 3. «4 точки».

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

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

Сценарий

      
координаты точек:

<х1> <у1>

… … …

<х4> <у4>

максимальный маршрут:

<ml> <m2> <m3> <m4>

длина = <mх>

минимальный маршрут:

<n1> <n2> <n3>
<n4>

длина = <mn>

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

Программа                                                   Алгоритм

¢мин. и макс.
маршруты         
                  алг «мин. и макс. маршруты»

cls                            
                                       нач

n =
4                                                              п = 4

dim x(n),y(n),r(n,n)                                      dim x(n),y(n),r(n,n)

?
«координаты точек»                                вывод («координаты точек»)

gosub vvdan ‘ввод данных                         ввод-координат-точек

 restore mrshrt
‘маршруты                         загрузка-маршрутов

? «маршруты:»                                               вывод
(«маршруты:»)

mr = 1*2*3                                                     mr =1*2*3

mx = 0                                                             тх = 0

for l = 1 to mr                                                от l = 1 до mr

read k1, k2, k3, k4                                        ввод k1, k2, k3, k4

dl = r(kl,k2) + r(k2,k3)                                 dl
= r(kl,k2)
+ r(k2,k3)

d3 = r(k3,k4) + r(k4,kl)                                d3 = r(k3,k4) + r(k4,k1)

d = dl + d3                                                     d
= d1 + d3

? kl; k2; k3; k4, d                                                     вывод (k1; k2; k3; k4, d)

if mx = 0 then                                                  если тх = 0 то

mx = d: mn = d                                               mx
= d: mn = d

ml = kl: m2 = k2                                             ml = k1: m2 = k2

m3 = k3: m4 = k4                                           m3
= k3: m4 = k4

nl = kl: n2 = k2                                               n1
= k1: n2 = k2

n3 = k3: n4 = k4                                             n3
= k3: n4 = k4

elseif d > mx then     
                                    инеc d > mx то

mx = d                                                             mx
= d

ml = kl: m2 = k2                                             m1
= k1: m2 = k2

m3 = k3: m4 = k4                                           m3=
k3: m4 = k4

elseif d < mn then     
                                    инеc d < mn то

mn = d                                                            mn
= d

nl = kl: n2 = k2                                              n1
= k1: n2 = k2

n3 = k3: n4 = k4                                             n3 = k3:
n4 = k4

end if                                                              кесли

next 1                                                             кцикл

? «максимальный маршрут:»                 вывод
(«максимальный маршрут:»)

? ml; m2; m3; m4                                         вывод (m1; m2; m3; m4)

? «длина =»; mx                                          вывод
(«длина =»; mx)

? «минимальный маршрут:»                  вывод
(«минимальный маршрут:»)

? nl; n2; n3; n4                                             вывод (n1; n2; n3; n4)

? «длина =»; mn                                         вывод
(«длина =»; mn)

end                                                                  кон

vvdan: ‘ввод данных                                   алг «ввод данных»

restore tchks                                                  загрузка-точек

for k = 1 to n                                                от k = 1 до п

read x(k),y(k)                                               ввод x(k),y(k)

? x(k),y(k)                                                     вывод x(k),y(k)

next k                                                              кцикл

for k = 1 to n                                                  от k = 1 до п

for l = 1 to n                                                    от l = 1 до п

dx = x(k) — x(l)                                               dx
= x(k) — x(l)

dy = y(k) — y(l)                                                dy
= y(k) — y(l)

rs = dx*dx + dy*dy                                       rs =
dx*dx + dy*dy

r(k,l) = sqr(rs)                                              r(k,l)
= sqr(rs)

next 1                                                                 кцикл

next k                                                                кцикл

return
                                                            кон

mrshrt: ‘маршруты:

data 1, 2, 3, 4

data 1, 2, 4, 3

data 1, 3, 2, 4

data 1, 2, 4, 3

data 1, 4, 2, 3

data 1, 4, 3, 2

tchks: ‘координаты точек 

data 0, 0

data 0, 3

data 4, 0

data 4, 3

Результаты выполнения на  ЭВМ
приведенной программы:

координаты точек:

0 0

03

4 0

4 3

маршруты:
                          длина:

1  2  3  4
                                 16

1  2  4  3
                                 14

1  3  2  4
                                 18

1  2  4  3
                                 14

1  4  2  3
                                 18

1   4 
3  2                                 16

максимальный маршрут:

1  3  2  4

длина =18

минимальный маршрут:

1  2  4
  3

длина = 14

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

Задача 4. «Ломаная».

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

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

Приведем проверочные тесты:

Tecт₁. (Основной случай)

Правильные результаты:

точки пересечения

0.5             
0.5

Тест ₂. (Основной случай)

Правильные результаты:

точки пересечения:

отсутствуют

Тест₃.
(Наложение вершины)

Правильные результаты:

точки пересечения

0.5             
0

Тест₄.
(Наложение ребра)

0	0
0	1
0.2	0
0.8	0
1	1
1	0

Правильные результаты:

отрезок пересечения:

[0.2, 0] — [0.8, 0]

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

Сценарий

           точек: <n>

координаты
точек:      

                                                    <k>: <x> <у> 

                                                            …….. 

           точки
пересечения:

отрезок: <k> — <k+l>
     *

                                                отрезок:
<1> — <1+1>

    точка: <х>
<у>

            ………

    
отсутствуют

Метод решения данной задачи может быть основан на вычислении точек
пересечения отрезков (х₁, у₁) — (x₂, у₂)
и (х₃, y₃) — (х₄, y₄) как точек
пересечения линий, проходящих через заданные отрезки, с помощью системы
уравнений:

 (y₂ – y₁
)×( x
– x₁) — (x₂ – x₁)×(y – у₁) = 0;

 (у₄ – у₃)×(x – x₃) — (x₄ – x₃)×(у – y₃) = 0.

Решение этих уравнений может быть проведено вычислением
определителей D, D_x,
D_y приведенной системы уравнений:

 (у₂ – у₁)×х — (х₂ – х₁)×у = (у₂ – y₁)×х₁ — (x₂
– x₁)×y₁;

 (у₄ – y₃)×х
— (х₄ – х₃)
×у = (у₄ – у₃)×х₃— (x₄
– x₃)×y₃,

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

х = D_x/D;

у = D_y/D;

D = (у₂ — у₁)×(х₄
— x₃) — (x₂ — x₁)×(y₄ —  y₃);

 D_x =
[(y₂
— y_l)×x_l — (х₂ – x₁)×y₁] — (x₄ – х₃)
— (x₂ – x₁)×[(y₄ – y₃)×x₃
— (х₄ – х₃)×y₃];

D_y
= (у₂ — у₁)×[(у₄ – у₃)×х₃ — (x₄
— x₃)×у₃] —
[(у₂ – y₁)×x₁ — (х₂ – x₁)×y₁]×(y₄ – y₃).

Факт пересечения пар отрезков может быть установлен из этих же
уравнений подстановкой в правые части координат точек альтерна­тивного отрезка
и сравнением значений этих выражений. А именно отрезок [(х₃, у₃)
— (х₄, у₄)] пересекает линию, проходящую через отрезок [(x₁, y₁) — (х₂, у₂)],
если эти выражения имеют разные знаки:

(у₂ — у₁)×(х₃
– x₁) — (х₂
– х₁)×(y₃ – у₁)
´
(у₂ — у₁)×(х₄
– x₁) — (х₂ – x₁)×(y₄ – y₁)
£
0.

Соответственно, отрезок [(х₁, у₁) — (х₂,
у₂)] пересекает линию, проходящую через отрезок [(х₃, у₃)
— (х₄, у₄)], если аналогичные выражения имеют разные
знаки:

(у₄ – у₃)×(х₁ – х₃)
— (х₄ – х₃)×(у₁
– у₃)´(у₄
– у₃)×(х₂
– х₃) — (х₄ – х₃)×(у₂
– у₃)
£
0.

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

В последнем случае общая часть отрезков находится из взаимо­расположения
отрезков [(х₁, у₁)
— (х₂, у₂)] и [(х₃, у₃) — (х₄,
у₄)] на прямой. В данной ситуации взаиморасположение вершин отрезков
можно выяснить, вычислив взаиморасположение между ними на прямой относительно отрезка
[(х₁, у₁) — (х₂, у₂)] по следующим
фор­мулам:

d₁ = 0;                                            

d₂ = (х₂ – х₁)×(х₂ – х₁) + (у₂
– у₁)×(у₂
— 1);

d₃
= (х₃ – х₁)×(x₂ – х₁) + (у₃
— у₁)×(у₂
— 1);

d₄ =
(х₄ – х₁)×(х₂ – х₁) + (у₄ – y₁)×(y₂ — 1).

Если d₂
< min (d₃, d₄) или max (d₃, d₄) <
0, то отрезки не пересе­каются. В противном случае необходимо выделить и
отбросить две крайние точки, и тогда оставшиеся две точки зададут общую часть
этих отрезков.

Опираясь на эти
математические факты можно приступить к составлению алгоритмов и программы.
Приведем программу, в которой установлено максимальное число точек nt = 200. Реальное число
точек устанавливается при вводе исходных данных из перечня операторов data, записанных в конце
текста программы.

¢ самопересечение
ломаной

nt = 200

dim x(nt), y(nt)

gosub wod ‘ввод данных

? «точки пересечения:»

np = 0 ‘число пересечении

for k = 1 to nt — 1

xl = x(k): yl = y(k)

x2 = x(k + I): y2 = y(k + 1)

for 1 = k + 1 to nt — 1

x3 = x(I): y3 = y(I)

х4
= x(I + 1): y4 = y(I + 1)

gosub pint ‘пересечение

next 1

next k

if np = 0 then ? «отсутствуют»

end

pint:
¢ точка пересечения:

d213 = (у2 — yl)*(x3 — х1) — (х2 — х1)*(у3 — у1)

d214 = (у2 — у1)*(х4 — х1) —
(х2 — х1)*(у4 — у1)

d431 = (у4 — у3)*(х1 — хЗ) — (х4 — х3)*(у1 —
уЗ)

d432 = (у4 — у3)*(х2 — хЗ) —
(х4 — х3)*(у2 — уЗ)

if d213*d2l4 > 0 or d431*d432 > 0 then

‘
нет пересечения

elseifd213*d214 < 0 or d431*d432 < 0 then

gosub tchki ‘ расчет точки

else ‘ отрезки на одной
прямой

gosub lin 1

end if

return

tchki: ‘ расчет точки пересечения

np = np+1

?
«отрезок:»; k; k + 1

?
«отрезок:»; I; I + 1

D = (у2 — yl)*(x4 — хЗ) — (х2 — х1)*(у4 — уЗ)

Dx = [(у2 — у1)*х1 — (х2 —
х1)*у1]*(х4 — хЗ)

Dx = Dx — (х2 — х1)*[(у4 —
у3)*х3 — (х4 — х3)*у3]

Dy = (у2 — у1)*[(у4 — у3)*х3 — (х4 —
х3)*у3]

Dy = Dy — [(у2 — yl)*xl — (х2 — х1)*у1]*(у4 — уЗ)

х
= Dx/D

у
= Dy/D

?
х; у

return

lin 1: ‘отрезки на одной
прямой

d2 = (х2 — х1)*(х2 — х1) + (у2 — у1)*(у2 —
1)

d3 = (хЗ — х1)*(х2 — х1) + (уЗ — у1)*(у2 —
1)

d4 = (х4 — xl)*(x2 — х1) + (у4 — у1)*(у2 — 1)

if d3 > d2 and d4 > d2 then

‘
нет пересечения

Iseif d3 < 0 and d4 < 0 then

‘
нет пересечения

else ‘ отрезки пересекаются:

gosub otrеz ‘ общий отрезок

end if

return

otrez: ‘расчет общего отрезка

np = np + 1

? «отрезок пересечения:»

if d3 < 0 or d4 < 0 then

? х1; у1; «-»

elseif d3 < d4 then

? х3; у3; «-»

else                                    

? х4; у4; «-»

end if

if d2 < d3 or d2 < d4 then

? х2; у2

elseif d3 < d4 then

? x3; y3

else

? х4; у4

end if

return

vvod: ‘ ввод данных

restore test1

read n

?
«точек:»;nt

for k = 1 to nt

read x(k), y(k)

? x(k); y(k)

next kn

t = nt + 1

x(nt) = x(l)

y(nt) = y(l)

return

test1: ‘точки ломаной:

data 4

data 0, 0

data 1, 0

data 0, 1

data 1, 1

test2: ‘точки ломаной:

data 4

data 0, 0

data 1, 0

data 0, 1

data 1, 1

В тексте данной программы записаны два варианта тестовых данных,
смена которых может быть проведена изменением имени метки test1 или test2 в операторе
перезагрузки restore в
подпрограмме ввода данных.

6.5. Технология дистанционного обучения

Дистанционное образование — это новая технология обучения,
основанная на использовании персональных компьютеров, электрон­ных учебников и
сетей телекоммуникации. Эта новая технология и форма обучения самым тесным
образом связана с развитием сети Интернет [7, 8, 9].

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

В Республике Казахстан дистанционные формы обучения полу­чили
официальное признание после принятия нового закона об об­разовании летом 1999
года. В Законе об образовании Казахстана дистанционное обучение определено как
«одна из форм обучения лиц, находящихся в отдалении от организаций образования,
с помощью электронных и телекоммуникационных средств».

Началом распространения новых компьютерных технологий обу­чения
послужило введение в середине 80-х годов курса информатики во всех средних
школах нашей страны [16]. Основной целью школь­ного курса информатики с конца
80-х годов было обучение всех учащихся компьютерной грамотности — умениям
читать, писать и получать информацию с помощью персональных ЭВМ [17].

Эксперименты с дистанционным образованием в вузах России начались с
середины 90-х годов. Технологической
базой для дистан­ционного обучения являются персональные компьютеры,
электронные учебники и вычислительные сети. Развитие сети телекоммуникаций и
появление образовательных серверов в сети Интернет сделало реальностью
распространение новых технологий дистанционного обучения [7, 8. 9].

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

В США, Великобритании, Австралии, Канаде, Германии развитие сети
Интернет создало условия для организации сетей дистанцион­ного обучения,
переживающих настоящий бум. При этом наиболее продвинутые проекты
дистанционного образования развиваются на базе или при поддержке крупнейших компьютерных
фирм — IBM, Apple, DEC, Sun,
Novel, Microsoft и т. д.

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

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

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

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

Вторым по развитию у нас в стране является проект Института дистанционного образования
Московского государственного уни­верситета экономики, статистики и информатики
(МЭСИ). В рос­сийском проекте дистанционного образования в настоящее время
обучается более 25 тысяч студентов по различным экономическим специальностям,
для которых созданы соответствующие комплекты бумажных и электронных учебников
[6, 7].

Еще один проект дистанционного образования был развернут в середине
90-х годов Российским Государственным
технологическим университетом
(МАТИ) на базе более 120 школ Москвы, Подмос­ковья, Челябинска и Приднестровья.
Целью этого проекта была дистанционной подготовка учащихся средних школ к
вступитель­ным экзаменам в вузы Российской Федерации.

Для данного проекта были созданы учебные пособия для посту­пающих в
вузы по информатике, математике и английскому языку с использованием
тестов, электронных учебников и электронных за­дачников. В рамках данного
проекта был разработан и апробирован электронный учебник по информатике,
используемый в настоящем учебном пособии [20].

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

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

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

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

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

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

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

Данные тесты по информатике с 1997 года используются в систе­ме дистанционного контроля знаний
учащихся средних школ, создан­ных на психологическом факультете Московского
Государственного Университета и получившей название Телетестинг. Использование
психологами этих тестов в течение последних трех лет показало уди­вительные
результаты.

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

Объяснением этим фактам может служить следующее. Участ­вовать в
телетестинге могут только те школьники, которые умеют работать на ЭВМ, а для этого необходимо получить соответствую­щие
знания. Самые первые учебники ориентировались на изучение основ алгоритмизации
без работы и отладки программ на ЭВМ [16].

В новейших учебниках по
информатике изучение элементов про­граммирования либо вовсе отсутствует, либо
проходит в отрыве от изучения основ алгоритмизации [18, 19, 21]. По этой причине знания
учащихся либо фрагментарны, либо неверны.

Освоению компьютерной грамотности с последующим изучением
алгоритмизации и отладки программ на ЭВМ был посвящен базовый школьный учебник [17], признанный лучшим в 1997 году. Однако
он не переиздавался и стал недоступен.

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

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

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

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

Подробную информацию о всех
Российских вузах и новостях дис­танционного образования можно найти в сети
Интернет на сервере Информатика Министерства образования Российской Федерации.