Информатика

         

Анализ правильности алгоритмов


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

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

Проявления ошибок:

Программа

¯

данные  ® ЭВМ  ® { отказ | сбой | ошибка }

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

Сбой - это потеря части данных либо получение непредусмот­ренных данных. Такого рода ошибки говорят о их частичной нера­ботоспособности программ либо об их недостаточной надежности.

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

 

Оценка программ:

 

Задача



 

исходное   требуемое

 

данные  ® программа  ® результаты

О правильности программ нельзя утверждать

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

В качестве примера рассмотрим решение квадратного уравнения:

х2 + 3×х + 2 = 0.

Исходные данные - коэффициенты – а = 1, b = 3, с = 2. Требу­емые результаты - пара чисел х1

и x2, являющихся корнями уравне­ния. Посмотрим, будут ли корнями уравнения пары чисел:

а) х1 = 2, x2

= 3;       б) x1 = -2, x2 = -3.

Решением уравнений являются числа, подстановка которых пре­вращает уравнение в тождество. В первом случае подстановка чисел х1 = 2, х2 = 3 в уравнение дает:

22

+ 3×2 + 2 = 12 ¹


0  - неправильно,

32

+3×3+2 = 20  ¹

0  - неправильно.

Следовательно, числа х1 = 2, х2 = 3 не являются правильными результатами.

Подстановка в уравнение чисел х1 = -2, х2 = -3:

(-2)2

+ 3×(-2) +2 = 0- правильно;

(-3)2

+ 3×(-3) +2 = 0- правильно.

Следовательно, числа х1 = -2, х2=

-3 являются правильными результатами.

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

Постановка задачи

Решение квадратного уравнения

а×х2

+ b×x + с = 0.

Дано:  a, b, с - коэффициенты.

Треб.:  х1, х2 - корни.

Где:     а×х12

+ b×х1

+ с = 0.

            а×х22 + b×х2 + с = 0.

При:    а ¹ 0.

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

Способ правильный, если он дает правильные результаты. Способ неправильный, если он дает неправильные результаты или не дает результатов вообще.

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

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

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

Метод решения

    x1 = (-b +
)/(2×а),

    x2 = (-b -
)/(2×a),

где

{ D = b2 - 4×а×с.

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

Для первого корня х1 = (-b +
 )/(2×a) подстановка и тождест­венные преобразования формул дадут:

а×х12 + b×х1 + с = а×[(-b +
)/(2×а)]2 + b× (-b +
)/(2×a) + с =

= (-b +
)2/(4×а) + b× (-b +
)/(2×a) + с = (b +
) × (-b +
)/(4×а) + с =



= (-b2 + D)/(4×a) + с = (-b2 + b2 - 4×а×с)/(4×а) + с = -4×а×с/(4×а) + с = 0.

Аналогичные результаты получаются и при подстановке формулы второго корня

х2

= (-b -
)/(2×a). После выполнения анало­гичных преобразований будет получено такое же тождество. И на основании этих проверок можно сделать заключение, что рассмот­ренный метод дает правильные результаты для любык допустимых данных.

Однако саму постановку задачи необходимо дополнить условием: b2

- 4×а×с ³ 0. При нарушении этого условия не только уравнение не имеет решений, но и метод решения также не дает результатов из-за необходимости вычисления корней от отрицательного дискриминан­та: D < 0.

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

алг «квадратное уравнение»                       Результаты вычислений

нач

если а ¹ О то                                                при а ¹ 0

D: = b*b - 4*а*с                                        D = b2 - 4×а×с

если D > = 0 то                                             при D >= 0

х1:

= (-b +
)/(2*a)                                   х1 = (-b +
)/(2×a)

х2:

= (-b -
)/(2*a)                                   х2 = (-b -
)/(2×a)

 все

инеc а = 0 то                                                 при а = 0

если b ¹ 0                                                       при b ¹ 0

х 1: = -c/b                                                     xl = -c/b

все

кон

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

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


Использование алгоритмов, содержащих ошибки, приводит к созданию программ, также содержащих ошибки.

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

Первый способ - проверка основных этапов построения алго­ритма:

задача ® постановка ® метод ® алгоритм

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

задача ¬ постановка ¬ метод ¬ алгоритм

Приведем пример построения алгоритма с одновременным ана­лизом его правильности.

Задача: Определить периметр треугольника, заданного на плос­кости координатами вершин.

XС,УС

XА,УА                         Xв,Ув

Постановка задачи

Определение периметра треугольника, заданного на плоскости.

Дано:  А = (ХА, УА)

В = (ХВ, УВ)     - координаты вершин треугольника

С = (XС,УС) 

Треб.: Р - периметр

Метод решения

    Р = LАВ +LВС+LСА

    LАВ =


    LВС =



    LСА = 


Где: Р = L(A,B) + L(B,C) + L(C,A);

здесь L[(x,y),(u,v)] =
 .

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

алг «периметр треугольника»

нач

LAB: =
               

LBC : =


LCA

: =


Р := LAB + LBC + LCA

кон

Результаты

  


  


  


     Р = LAB + LBC + LCA

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

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

Анализ правильности:

задача            ¬    способ

¯                              ¯



постановка   ¬  методы

¯                              ¯

сценарий    ¬   алгоритмы

¯                              ¯

ЭВМ      ®       программа

 

Основные типы алгоритмических ошибок в программах:

·         ошибки в выбранных методах решения;

·         ошибки в постановке решаемых задач;

·          дефекты в сценариях диалога с ЭВМ;

·          ошибки организации ввода данных;

·          неправильная реализация методов решения.

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

Будем считать, что программа правильная,

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

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

В качестве иллюстрации приведем пример систематического со­ставления алгоритма и программы задачи определения суммарного веса учеников по данным из таблицы:

фамилия                    рост                            вес

Иванов

185

85

Петрова

165

65

Сидоров

170

80

 

Рассмотрим постановку задачи и метод вычисления суммарного веса.

Постановка задачи

Определение суммарного веса.

Дано:                                                                          Метод вычисления

(D1,.., DN) - данные об учениках,                             S0 = 0

где D = [Fam,R,V] - состав данных,                          Sk

= Sk-1 + vk

Fam - фамилия, R - рост, V - вес.                               [k = (1 ...


N)]

Треб.: Vsum - суммарный вес.                                   Vsum = SN

Vsum = v1

+ v2 + ... + vN

При:

N > 0.

Правильность метода вычислений можно доказать по индукции. Рассмотрим результаты вычислений на 1-м, 2-м и k-м шагах. Отме­тим, что начальное значение S0 = 0.

На первом шаге при k = 1 результат вычисления

S1

= S0 +v1 = v1

На следующем втором шаге при k = 2 результат

S2 = S1 + v2  = v1 + v2.

На третьем шаге при k = 3 результат

S3= S2 + v3 = v1

+ v2 + v3.

В общем случае можно предположить, что к k-му шагу результат вычисления

Sk-1=v1+...+vk-1.

Тогда результат вычислений после k-го шага (исходя из описания метода)

Sk =

Sk-1 +vk = v1

+ … + vk-1

+ vk.

В силу принципа математической индукции утверждение верно для всех k = 1, 2,.... N. Следовательно, на последнем шаге при k = N конечный результат:

SN

= v1 + ... + vN.

Что и требовалось. Следовательно, метод правильный.

Приведем сценарий диалога решения поставленной задачи на ЭВМ. Для представления данных в программе примем последова­тельность операторов

data.

Сценарий                                                       Представление данных



Данные об учениках

фамилия   вес    рост

dano:'данные учеников

<Fam1> <V1> <R1>                                            data «Иванов», 185, 85

…  …  …                                                        data «Петрова», 165, 65

<FamN>

<VN> <RN>                                       data «Сидоров», 170, 80

                                                                                                data «», 0, 0

суммарный вес = <Vsum>

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

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

алг «суммарный вес»                                               '

суммарный вес

нач                                                                              cls



вывод («Данные об учениках»)                             ? «Данные об учениках»

вывод («фамилия вес рост»)                                 ? «фамилия вес рост»

s := 0                                                                          s = 0

цикл                                                                          do

чтение famS, r, v                                                   read fam$, r, v

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

вывод (fam$, v, r)                                                  ? fam$; v; r

s := s + v                                                                  s = s + v

кцикл                                                                        loop

vsum

= s                                                                    vsum = s

вывод («суммарный вec=»,vsum)                          ? «суммарный вес=»; vsum

кон                                                                              end

 

Правильность приведенного алгоритма можно увидеть из описа­ния результатов его выполнения.

Алгоритм                                                                  Результаты выполнения

алг «суммарный вес»                                               на экране и в памяти ЭВМ

нач

вывод («Данные об учениках»)                          Данные об учениках

вывод («фамилия вес рост»)                              фамилия вес рост

s: = 0                                                                         s0 = 0

цикл

чтение fam$, r, v

при fam$=«» выход

вывод (fam$, v, r)                                              <famk> <vk> <rk>

 s:

= s + v                                                             sk = sk-1

+ vk

кцикл                                                                       [k = (1...n)]

vsum

= s                                                                   vsum = sn

  вывод («суммарный вec=»,vsum)                          суммарный вес= <vsum>



кон

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

В о п р о с ы

 

1. Когда программы содержат ошибки?         

2. Что такое правильный способ решения?

3. Когда способ решения неправильный?

4. Что такое правильный метод решения?

5. Когда метод решения неправильный?

6. Что такое правильный алгоритм?

7. Когда алгоритм содержит ошибки?

8. Каковы основные типы ошибок в программах?

З а д а ч и

 

1. Приведите постановку задачи, сценарий, алгоритм и программу ре­шения линейного уравнения а×х + b = 0, с помощью формулы х = -b/а (при а ¹ 0).

2. Приведите постановку задачи, сценарий, алгоритм и программу решения квадратного уравнения а×х2 + b×x + с = 0 с помощью формулы дискриминанта.

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

 а×х + Ь×у = е,

 с×х + d×y = f.

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

 х = Dx/D,

 y = Dy/D.

Определители D, Dx и Dy вычисляются по формулам:

 D = a×d - b×c,

 Dx = e×d - f×b,

 Dy = a×f - c×e.

4. Приведите постановку, сценарии, алгоритм и программу решения следующих задач:

а) определение площади треугольника по длине сторон а, Ь, с по формуле Герона:

 

S =
,

р = (а + b + с)/2.

б) определение площади треугольника, заданного на плоскости ко­ординатами своих вершин: (х1, у1), (х2, у2), (х3, у3); для вычисления длин сторон треугольника воспользуйтесь формулой определения длин от­резков на плоскости, задаваемых координатами концов:

l =


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

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

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



в) определение времени движения парохода по течению и против течения реки;

г) определение времени движения пешеходов навстречу друг другу, если один из них движется с замедлением;

д) определение времени падения тела с заданной высоты;

е) определение времени полета тела, брошенного вверх;

ж) определение расстояния, на которое улетит мяч, брошенный под углом к горизонту.

6. Дана прямоугольная матрица АNM - прямоугольная числовая таб­лица размера N ´ М. Приведите постановку, метод решения, сценарий, алгоритм и программу для решения следующих задач:

а) подсчет сумм элементов матрицы по столбцам,

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

в) нахождение минимального значения в каждом столбце,

г) нахождение минимального значения в каждой строке,

д) нахождение максимального значения в каждом столбце,

е) нахождение максимального значения в каждой строке,

ж) нахождение наибольшего из минимальных значений в столбцах,

з) нахождение наименьшего из максимальных значений в строках.


Базовые понятия языка Пролог


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

Факты в Прологе служат для описания конкретных данных и простейших сведений. Примеры фактов:

мама (зина, вова);    - Зина - мама Вовы

папа (миша, вова);   - Миша - папа Вовы

Группы фактов могут образовывать данные. Совокупность дан­ных, размещаемых на дисках, образуют базы данных. Общее опреде­ление данных в Прологе:

данные:

<факт>; [<факт>;...]

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

родитель (х,у) ¬ папа (х,у);    - Родитель — это папа или мама

родитель (х,у) ¬ мама (х,у);

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

процедура:

[<факты>] <правило>; [<правило>; ...]

Пример описания рекурсивной процедуры, в которой определя­емое понятие задается через самое себя:

предок (х,у) ¬ родитель (х,у);

предок (x,z) ¬ родитель (х,у), предок (y,z);

Программа на Прологе — это совокупность процедур над опреде­ленными данными:

программа:

<процедуры>; [<данные>;]

Описания баз данных на Прологе образуют совокупность описа­ний данных:

база данных:

<данные>; [<данные>; ... ]

Базы знаний на Прологе описываются наборами фактов и правил определения обобщенных понятий над ними:

база знаний:

<данные>; <правила>;

Вопросы в языке Пролог служат запросами к базам данных и знаний, а также обращениями к процедурам и программам. Приме­ры вопросов:

? мама (х,вова) ?

предок (х,вова)



Базовые средства программирования


Базовыми средствами программирования для персональных компьютеров считаются языки семейства Basic (Бейсик). Эти языки программирования имеются на всех персональных компьютерах и широко используются для обучения началам программирования в школах и вузах.

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

На персональных компьютерах IBM PC язык Бейсик имеет три версии, связанные с операционными системами для этих компьюте­ров, созданных и развиваемых фирмой Microsoft:

1) традиционный Бейсик (без ОС),

2) структурный Бейсик(МS DOS),

3) графический Бейсик (Windows).

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

Структурный Бейсик под именем Quick Basic был создан вместе с первыми моделями персональных компьютеров IBM PC как базовое средство программирования в операционной системе MS DOS. Интерпретатор этой версии Бейсика имеется на всех персональных компьютерах IBM PC в качестве стандартной компоненты операци­онной системы MS DOS.

Графический Бейсик под именем язык Visual Basic был создан фирмой Microsoft в качестве базового средства программирования для новейших моделей компьютеров IBM PC с операционной систе­мой Windows. Этот язык может использоваться только в среде Windows и только на старших моделях IBM PC.

Пример программы на традиционном языке Бейсик с коммента­риями, в которых записан реализованный в ней алгоритм.

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

10 ' поздравление                             ' алг «поздравление»

20 сls                                                   ' нач


30 nm$ = «Оля»                                ' пт$ = «Оля»

40 dn$ = «с днем рождения»          ' dn$ = «с днем рождения»

50 print «Дорогая» + nm$               ' вывод «Дорогая» + пт$

60 print «Поздравляю тебя»          ' вывод «Поздравляю тебя»

70 print dn$                                       ' вывод dn$

80 print «Желаю счастья»             ' вывод «Желаю счастья»

90 print «Твой папа»                       ' вывод «Твой папа»

100 end                                               ' кон

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

Та же самая программа на структурном Бейсике:

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

' поздравление                                  ' алг «поздравление»

сls                                                        ' нач

nm$ = «Оля»                                     ' пт$ = «Оля»

dn$ = «с днем рождения»               ' dn$ = «с днем рождения»

print «Дорогая» + nm$                    ' вывод «Дорогая» + пт$

print «Поздравляю тебя»               ' вывод «Поздравляю тебя»

print dn$                                            ' вывод dn$

print «Желаю счастья»                  ' вывод «Желаю счастья»

print «Твой папа»                            ' вывод «Твой папа»

end                                                      ' кон

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

Дорогая Оля

Поздравляю тебя

с днем рождения

Желаю счастья.

Твой папа.

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

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



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

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

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

Правильность программ - правильность результатов, получаемых с их помощью.

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

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

Основные типы операторов языка Бейсик:

- операторы ввода-вывода;

- графические операторы;

- присваивания;

- обращения к функциям;

- описания данных;

- управляющие операторы;

- обращения к подпрограммам.

Примеры операторов ввода-вывода на экран.

Оператор                                                        Действие

print «привет»                                              вывод («привет»)

print «корень=»; х                                       вывод («корень =», х)

input «a=»; а                                                  запрос («а=», а)

input n                                                            ввод (п)

locate st, ps                                                     позиция (st,ps)

Примеры графических операторов:

Оператор                                                        Действие

pset(x,y),c                                                       точка(х,у),с



line(x,y)-(u,v),c                                               линия(х,у)-(и, v), с

line(x,y)-(u,v),c,b                                            рамка(х,у)-(и,у),с

circle(x,y),r,c                                                  окружность(х,у), r,с

circle(x,y),r,c,al,a2                                         дуга(х,у), r,с,а1,а2

paint(x,y),c                                                     закраска(х,у),с

сls                                                                    очистка_экрана

screen 0,0                                                       текстовый_экран

screen 1,0                                                       графический_экран1

screen 2,0                                                       графический_экран2

 

Примеры операторов присваивания.

Присваивания                       Действие                                Результат

а = 0                                        а := 0                                       а = 0

b = а + 1                                 b := a + 1                                b = а + 1 = 1

с = 2*b + 3                              с := 2b + 3                              с = 2 b + 3 = 5

d = b/c                                     d := b/c                                               d = -b/c = 0.2

b = b + 1                                 b := b + 1                                b' = b + 1 = 2

b = b + 1                                 b := b + 1                                b" = b' + 1 = 3

Математические функции с примерами обращения.

Функция        Смысл                                                            Пример                       Результат  

rnd                  - случайное число от 0 до 1             rnd

int (x)              - целая часть числа х                         int (5/3)                                   1

abs (x)             - абсолютное значение числа          abs (-2)                                    2

sqr (x)             - квадратный корень числа              sqr (16)                                   4



sin (x)              - синус                                                sin

(0)                                      0

cos (x)             - косинус                                            cos

(0)                                     1

tan (x)             - тангенс                                             tan

(0)                                     0

atn (x)             - арктангенс                                       atn (0)                                     0

exp (x)             - экспонента                                      ехр (0)                                     1

log (x)              - логарифм натуральный                  log (1)                                      0

К числу управляющих операторов можно отнести условные опе­раторы, имеющие следующие форму записи и смысл:

Условный оператор:                                     Действия ЭВМ:

if <условие> then <оператор>                   если <условие> то <действие>

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

Примеры записи условии - простых и сложносоставных:

Условие:                                             Запись:

х = у                                                    х = у

х ¹

у                                                    х <>

у

х > у                                                    х > у

х < у                                                    х < у

х £

у                                                    х <= у

х ³

у                                                    х >= у

не (х = 1)                                            not (x = 1)

(х > 0) и (у > 0)                                  (х > 0) and (у > 0)

(а = 0) или (b = 0)                              (а = 0) or (b = 0)

Простейшим примером программы с условными операторами является реализация алгоритма «выбор из меню»:



Сценарий «Выбор из меню»



Меню:                                                            <результат >:



1. Новый год                                      1 января

2. День рождения                             1 декабря

3. День знаний                                  1 сентября

выбор=?

<n>

<результат >

Алгоритм и программа выбора по меню, соответствующие этому сценарию:

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

алг «выбор по меню»                                   ' выбор по меню

нач                                                                  cls

вывод («Меню»)                                          print «Меню:»

вывод («I. Новый год»)                               print («1. Новый год»)

вывод («2. День рождения»)                     print («1. День рождения»)

вывод («З. День знаний») print                  («3. День знаний»)

запрос («выбор=», п)                                   input «выбор=», n

если п = 1 то                                               if n = I then

вывод («1 января»)                                   print «1 января»

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

вывод («1 декабря»)                                 print «1 декабря»

если п

= 3 то                                               if n = 3 then

вывод («1 сентября»)                              print «1 сентября»

кон                                                                  end

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

Сравнение

текста программы с описанием алгоритма, а затем ал­горитма со сценарием диалога подтверждает полное соответствие программы заданному сценарию «выбор по меню».


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

 

В о п р о с ы

 

1. Что такое программа?

2. Что такое язык программирования?

3. Каковы основные свойства программ?

4. Какие есть графические операторы?

5. Какие есть операторы ввода- вывода?

6. Какие есть математические функции?

7. Как записываются логические условия?

З а д а ч и

 

1. Составьте сценарий, алгоритм и программу с выбором из меню:

а) поздравления с Новым годом;

б) поздравления с Днем рождения;

в) регистрации даты рождения;

г) регистрации фамилии и имени.

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

а) расчета сдачи за товар;

б) расчета остатка от прибыли;

в) пересчета рубль/доллар;

г) расчета остатка времени до 18.00.

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

а) российского флага;                г) украинского флага;

б) шведского флага;                    д) французского флага;

в) японского флага;                     е) британского флага.

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

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

б) длины пути по времени и скорости движения;

в) средней скорости по времени и длине пути.

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

а) домика;                      г) автомобиля;

б) дерева;                       д) цветка;

в) рыбы;                          е) птицы.


Базы данных на ЭВМ


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

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

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

Фамилия                   Имя                       Рост                     Вес                            Глаза

Иванов

Саша

180

85

синие

Петрова

Оля

165

65

карие

Сидоров

Миша

190

75

зеленые

Реляционные базы - это базы данных, в которых информация хранится в форме таблиц. Каждая из таблиц в такой базе данных имеет строго определенное число столбцов, снабженных именами.

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

Данные об объектах, людях или вещах в этих таблицах записыва­ются в виде строк. В приведенном примере сведения о росте, весе и цвете глаз Петровой Оли записаны во второй строке.

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


Для числовых данных упорядочение

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

      Фамилия                         Имя                         Рост                            Вес                         Глаза

Петрова

Оля

165

65

карие

Иванов

Саша

180

85

синие

Сидоров

Миша

190

75

зеленые

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

      Фамилия                         Имя                         Рост                            Вес                         Глаза

Сидоров

Миша

190

75

зеленые

Петрова

Оля

165

65

карие

Иванов

Саша

180

85

синие

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

Основой для поиска информации в базах данных служат

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

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

запрос:            фамилия = Иванов

запрос:            имя

= Оля

Ответами на запросы будут строки из таблицы приведенного типа. На первый запрос - строки, в которых в графе фамилия стоит «Иванов», а на второй запрос - строки со значением «Оля» в графе имя.

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

запрос:            рост

> 180

запрос:            вес £ 50

Ответами на эти запросы также будут одна или несколько строк из таблицы, в которых рост или

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



Сложносоставные запросы образуются из простейших с исполь­зованием логических связок

и и или. Примеры сложносоставных запросов:

запрос: вес <

80 и глаза = зеленые

запрос: глаза

= синие или глаза = голубые

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

или будут все строки таблицы, которые удовлетворяют первому или второму условию, либо и тому и другому одновременно.

Отличие баз данных от информационно-справочных

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

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

Задача 1. База данных об оценках.

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

Р е ш е н и е. Пусть имеются три товарища: Иванов, Петрова и Сидоров со следующими оценками по физике, математике и инфор­матике:

фамилия            имя             матем             физика    информ

Иванов

Саша

5

4

5

Петрова

Оля

4

4

5

Сидоров

Миша

3

3

4

Примеры запросов:

фамилия = Петрова

имя = Миша

физика > 3

матем > 3 и физика

> 3

матем = 5 или информ = 5

 

В о п р о с ы

1. Что такое база данных?

2. Что такое реляционные базы данных?

3. Что такое сортировка данных?

4. Как упорядочивается информация в базах данных?

5. Что такое запросы к базам данных?



6. Как строятся сложносоставные запросы?

7. Каковы основные возможности баз данных?

 

 З а д а н и я

 

1. Составьте базу данных о кондитерских товарах, указав их назва­ние, вес, цену и вкус. Заполните базу данных на 5-6 наименований конфет. Приведите примеры сложно-составных и простых запросов с нетривиальными ответами.

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

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

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

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

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

7. Составьте по журналу успеваемости базу данных по следующим предметам: а) математике; б) информатике; в) физике; г) литературе.

Укажите запросы на поиск учеников, не имеющих

а) ни одной двойки;                    в) ни одной тройки;

б) ни одной четверки;                 г) ни одной пятерки.

8. Составьте базу данных «Телефонный справочник» с телефонами своих друзей и родных с указанием фамилий и имен. Упорядочите базу данных по фамилиям.


Базы знаний на ЭВМ


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

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

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

мама (Люба, Оля);                          - Люба - мама Оли

оценка (Вова, физика, 5);               - Вова имеет 5 по физике

Обобщенные сведения в базах знаний записываются в форме правил вывода, выражающих определения понятий. Примеры обоб­щенных сведений:

бабушка (х, z) ¬

мама (х, у), мама (у, z)             - бабушка - это мама мамы

двоечник (х) ¬ оценка (х, _ ,2)                             - двоечник - тот,

у кого есть двойки

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

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

- правила определения понятий;

- правила принятия решений;

- способы решения задач;

- правила поведения и т. п.

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

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

Приведем примеры определения понятий.

1. Понятие «мама». Объем понятия - совокупность всех мам. Содержание понятия - женщина, имеющая детей. Формализация понятия на Прологе может выражаться конкретными фактами. При­меры:

мама (Люба, Оля);              - Люба - мама Оли

мама (Зина, Люба);             - Зина - мама Любы

2. Понятие - «бабушка». Объем понятия - совокупность всех бабушек. Содержание понятия - «бабушка - это мама мамы или папы». Формализация этого понятия на Прологе:

бабушка (х, z) ¬ мама (х, у), мама (у, z);                        - бабушка - это мама мамы

бабушка (х, z) ¬ мама (х, у), папа

(у, z);                         - бабушка - это мама папы

3. Понятие «музыкант». Объем понятия - совокупность людей, занимающихся музыкой. Содержание понятия - «музыкант - чело­век, который любит музыку и занимается музыкой». Это понятие на языке Пролог можно записать в виде правила:

музыкант (х) ¬ любит (х, музыка), занятие (х, музыка).

4. Понятие «студент». Объем и содержание понятия - учащиеся в вузах, университетах и колледжах. Определение этого понятия на Прологе можно записать в виде набора правил:

студент (х) ¬ занятие (х, учеба), место (х, университет);

студент (х) ¬ занятие (х, учеба), место (х, институт);

студент (х) ¬ занятие (х, учеба), место (х, колледж);

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

Примеры признаков объектов и соответствующих значений:

цвет - красный, белый, зеленый, черный и т.д.;

вес - определяется в килограммах;

возраст - определяется в годах: 1, 2, 3, ...

Примеры записи признаков на Прологе:



возраст (Иванов, 18);

вес (Иванов, 85);

цвет (Иванов, глаза, синий);

цвет (Иванов, волосы, белый);

Основные возможности баз знаний:

- поиск ответов на сложные вопросы;

- логическая обработка данных;

- моделирование процедур принятия решений;

- обновление и ввод дополнительных данных;

- вывод информации в естественно-языковой форме;

- создание новых баз знаний.

 

В о п р о с ы

 

1. Что такое базы знаний?

2. Как записываются факты на языке Пролог?

3. Как записываются вопросы на языке Пролог?

4. Как записываются правила на языке Пролог?

5. Что такое содержание понятий?

6. Каковы основные возможности баз знаний?

З а д а ч и

1. Составьте базу знаний о книгах в библиотеке. Включите следующие сведения: название книги, жанр книги, автор, главный герой, страна.

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

3. Составьте базу знаний о соревнованиях. База должна содержать две группы фактов.

Первая группа фактов - сведения о командах: названия команды, города, тренер.

Вторая группа фактов - сведения о матчах: даты, команды и счет.


Диалог с программами на Прологе


Диалог с программами на Прологе начинается после нажатия клавиши F4 - начало диалога с программой.

Результатом выполнения этой команды будет появление на экра­не окна диалога:

Файл              Редактор                   Диалог

 

-РЕДАКТОР –

 

мама (                                                 ДИАЛОГ

папа (                                     ? мама(х,вова);

бабуш                                     х = зина

бабуш                                     ДРУГИХ РЕШЕНИЙ НЕТ

 

 

 

F1 Подсказка F3 Открыть Alt-F3 Закрыть F4 Диалог

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

В окне диалога можно, задать серию вопросов

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

Для завершения диалога с программой необходимо закрыть окно диалога с помощью команды Alt-F3 - закрытие текущего окна.



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


Изучение информатики должно заканчиваться экзаменами,

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

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

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

Экзамены в вузах и колледжах, обучающих по программе бакалавриата, служат для проверки знаний студентов в соответствии с госу­дарственными стандартами высшего профессионального образования [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].


Элементы доказательного программирования


Доказательное программирование - это составление программ с доказательством их правильности. Сложность составления и доказа­тельства правильности алгоритмов и программ состоит в следующем.

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

Для утверждений о правильности программ

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

Существуют два подхода к проверке программ - прагматический и доказательный. При прагматическом подходе проверка программ выполняется на ЭВМ путем тестирования.

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

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

По этой же причине не ясно, когда процесс отладки программ - процесс поиска и исправления ошибок на ЭВМ - может считаться завершенным. А выявлены или нет все ошибки в программе при ее отладке не может сказать никто.

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

Рассмотрим в качестве иллюстрации принципов тестирования алгоритм и программу вычисления максимума из трех чисел: а, b, с.

алг «максимум трех чисел»                                   'максимум трех чисел


нач                                                                              cls

ввод (а, b, с)                                                               input a, b, с

если а > b то                                                            if а > b then

тах := a                                                                     max = a

инеc b > с то                                                            elseif b > с then

тах := b                                                                     mах = b

инеc с > а то                                                            elseif с > a then

тах:= с                                                                       mах = с

кесли                                                                          end if

вывод («тах=»,тах)                                                ? «mах=»; mах

кон                                                                              end

 

Запуск этой программы на ЭВМ можно проверить на следующих данных:

Tecт1                           Тест2                           Тест3

? 1 1 2                         ? 1 2 3                         ? 3 2 1

max = 2                       max = 3                       max = 3

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

                             

Контрпример1

? 2 1 3

max = 2

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

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

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


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

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

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

алг «у = х5»                Результаты                 Утверждения

нач

v

:= х×х                        v1 = х×х            Þ        v1 = x2

v := v×v                        v2

= v1×v1          Þ        v2 = x4

у := v×x                        у = v2×x            Þ        у = х5

кон

Справа от алгоритма приведены результаты выполнения присва­иваний. Результатом первого присваивания v := х×х будет значение v1

= х×х переменной v. Результат следующего присваивания v := v×v - второе значение переменной v, равное v2 = v1×v1 . Результатом треть­его присваивания у := v×x будет значение у = v2×x .

На основе приведенных рассуждений, можно сделать три утверж­дения о промежуточных и конечных результатах вычислений:

Результаты                             Утверждения

{ v1 = х×х                     Þ        v1 = х2

{ v2 = v1×v1                  Þ        v2 = x4

{ у = v2×x                     Þ        у = х5

Таким образом можно высказать окончательное

Утверждение. Конечным результатом выполнения будет

у = х5 для любых значений х.

Доказательство. Исходя из описания результатов выполнения присваиваний значение у будет равно

у = v2×x = (v1×v,)×x = ((х×х).(х×х))) ×х = x5.

Что и

требовалось доказать.

Техника анализа и

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



·         разбор случаев;

·         подбор контрпримеров;

·         выделение лемм;

·         индуктивный вывод.

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

алг «у = тах(а, b,с)»                                     Результаты

нач

если а > b то                                            при а > b

у := а                                                        у = а

инес b > с то                                            при b > с

у

:= b                                                        у = b

инес с > а то                                            при с > а

у

:= с                                                        у = с

кесли                                                          при не (b > с)

кон

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

а, при а > b,

у =       b, при b > с и b ³ а,

с, при с > а и с ³ b.

В то же время значение максимума должно быть равно:

а, при а ³ b и а ³ с,

mах =  b, при b ³

с и b ³

а,

с, при с ³ а и с ³ b.

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

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



Контрпримером в данном случае будут значения: а = 2, b = 1, с = 3. Для этих данных по определению mах = 3, а по результатам выполнения алгоритма у = 2. Следовательно, в алгоритме содержится ошибка.

Однако оказывается, что это не единственная ошибка.

Более тон­кие ошибки вскрывает второй контрпример: а = 1, b = 1, c = 1. Для этих данных в алгоритме вовсе не определен результат вычислений у = ? и конечный результат выполнения программы будет непред­сказуем!?

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

 

Постановка задачи            Метод решения

Вычисление mах (а, b, с).

Дано:

а, b, с - три числа,      mх = mах(mах(а,b),с)

Треб.:

mх - максимум,         mах(х,у) =   х, при х ³ у

Где:

mх = mах (а, b, с).                              у, при у ³ х

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

алг «тх = тах(а,b,с)»                                   Результаты

нач

если а ³  b то                                                при а ³ b

тх := а                                                      mx = a

иначе                                                              при b > а

mх := b                                                      mх = b

кесли { mх = mах(а,b) }                             при с < mх

если с ³ mх то                                           при с ³



mх := с                                                    mх' = с

кесли

кон

Доказательство правильности алгоритмов можно проводить двумя способами. Первый способ - анализ правильности при по­строении алгоритмов. Второй способ - анализ правильности после построения алгоритмов.

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


Для рассмотренного алгоритма это доказательство изложено выше.

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

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

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

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

Лемма: Конечными результатами выполнения алгоритма

Алгоритм                                          Результаты

если а > b то                                     при а ³ b

тх := а                                           mx = a

иначе                                                  при b > a

тх

:= b                                           mx = b

кесли

является значение mx = max(а, b) для любых значений а и b.

Доказательство. Результатом вычислений здесь будут значения

а при а ³ b

mx = 

b при а < b

что совпадает с определением max (а, b).

С помощью этой леммы легко доказать правильность алгоритма в целом.

{ mх = max (а, b) }                Результаты

если с ³ mx то                      при с ³ mx

mx := с                               mx' = с

кесли                                      mx' = mx

при с < mx

Утверждение. Конечным результатом выполнения алгоритма вы­числения максимума будет значение mx' = max (а, b, с) для любых значений а, b и с.



Доказательство. В силу предположения предшествующее значе­ние переменной mx = max(a,b). Отсюда получаем, что

 с, при с ³ mx        

mx¢ =                                        = max(a,b,c).

 mx, при с < mx

Что и требовалось доказать.

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

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

В качестве примера использования индуктивных рассуждений рассмотрим алгоритм вычисления среднего арифметического после­довательности чисел. В приводимом алгоритме предполагается, что последовательность чисел размещена в массиве X[1:N].

алг «среднее значение»

массив X[1:N]

нач                                                                  Результаты:

от k = 1 до N цикл

S := S * (k-l)/k + X[k]/k                       Sk

= Sk-1*(k-l)/k + X[k]/k

кцикл                                                         [k = (1...N)]

Xcp := S                                                     Xcp = S

кон

Этот алгоритм обычно считается ошибочным (?!). «Ошибкой» в этом алгоритме считается отсутствие присваивания S := 0 перед началом цикла.

Разберем результаты выполнения алгоритма на первых трех ша­гах:

S1 = S0×(l - 1)/1 + Х[1]/1 = S0×0/1 + Х[1]/1 = Х[1]/1;

S2 = S1×(2 - 1)/2 + Х[2]/2 = S1×1/2 + Х[2]/2 = Х[1]/2 + Х[2]/2;

S3 = S2×(3 - 1)/3 + Х[3]/3 = S2×2/3 + Х[3]/3 = Х[1]/3 + Х[2]/3 + Х[3]/3.

Можно утверждать, что на первых трех шагах результатом является среднее арифметическое обрабатываемых чисел. На основе этих примеров можно сделать индуктивное утверждение - «на каждом очередном k-м шаге выполнения цикла результатом будет среднее арифметическое»



Sk

= Sk-1×(k-l)/k + X[k]/k = X[l]/k + X[2]/k + ... + X[k]/k.

Доказательство этого утверждения проводится с помощью мате­ матической индукции. На первом шаге при k = 1 оно уже доказано. Допустим, что оно справедливо на (k -1)-м шаге

Sk-1

= X[l]/(k-l) + X[2]/(k-l) + ... + X[k-l]/(k-l).

Подставим его в описание результатов цикла на k-м шаге

Sk= Sk-1×(k-l)/k +X[k]/k.

Тогда результат выполнения цикла на k-м шаге оказывается рав­ным

Sk

= X[l]/k + X[2]/k + ... + X[k-l]/k + X[k]/k,

т. е. среднему арифметическому первых k чисел.

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

SN

= SN-1×(N-1) + X[N]/N = X[1]/N + ... + X[N]/N.

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

Xcp = SN = X[1]/N + ... + X[N]/N.

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

Индукция - это вывод общих суждений из частных примеров. При анализе циклов она используется для подбора индуктивных утверждений о промежуточных результатах выполнения циклов. Однако для доказательства правильности индуктивных утверждений о результатах выполнения циклов используется полная математи­ческая индукция.

Математическая индукция - это принцип доказательства после­довательностей утверждений Р(1), Р(2), Р(3), ..., P(N), .... когда известно, что верны первые утверждения для n = 1, 2, 3 и из истин­ности (n - 1)-го утверждения следует истинность n-го утверждения:

Принцип математической индукции:

если первое утверждение Р(1) истинно

и из утверждения Р(n - 1) следует

утверждение Р(n), то истинны все

утверждения Р(1), Р(2), Р(3), ..., Р(n), ... .

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



алг «нахождение минимума»

массив x[1:N]

нач                                                                  Результаты:

от k = 1 до N цикл

если x[k] < min то

тп := x[k]                                         mnk = { x[k], при x[k] < mnk-1,

все                                                          { mnk-1, в ином случае

кцикл                                                         [ k = (1 ... N)]

Min := тп                                                                  Min = mnN

кон

Утверждение. Приведенный алгоритм определения минимального значения последовательности чисел неправильный.

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

Результаты выполнения первого шага цикла при k = 1:

 х[1] при х[1] < mn0

mn1

=                                      = min (х[1], mn0).

             mn0

при х[1] £

mn0   

    

Следовательно, результатом будет

mn1 = min (x[l], mn0)

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

mnk

= min (x[k], Min(x[k-l], ..., х[1], mn0) =  Min (x[k], x[k-1], ..., х[1], mn0).

В силу математической индукции это утверждение справедливо при k = N:

mnN

= Min (x[N], x[N - 1], ..., x[2], х[1], mn0),

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

Min = mnN

= Min (x[N], x[N - 1], ..., x[2], х[1], mn0).

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

В самом деле, если значение mn0 окажется меньше любого из значений последовательности х[1], ....


x[N], то конечный результат вычислений будет неправильным. В частности, при реализации алгоритма на Бейсике неправильный результат будет получен, если последовательность будет состоять только из положительных чисел. Например, для последовательности чисел: 1, 2, 3, ..., N.

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

алг «нахождение минимума»

массив х[1:п]

нач

   тп := x[1]

  от k = 1 до N цикл

    если x[k] < тп то

      тп = x[k]

    все

   кцикл

  Min

= тп

кон

 

 

Результаты:

mn0

= х[1]

[k = (1 ... N)]



Min = mnN

Утверждение. Для любой последовательности чисел x[l:N] конечным результатом вычислений будет значение Min = Min (х[1], ..., x[N]).

Доказательство. Воспользуемся результатами анализа выполнения алгоритма, рассмотренного ранее. Различие между ними состоит в добавлении перед началом цикла присваивания mn := х[1], которое задает начальное значение переменной mn, равное mn0 = х[1].

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

Min = mnN = Min(x[N], x[N-l], ..., х[2], х[1], mn0) =

        = Min(x[N], x[N-l], ..., x[2], x[l], x[l]) =  Min(x[N], .... х[1]).

Что и требовалось.

Рассмотренные примеры являются образцами доказательств

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

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

В о п р о с ы

 

1. Как показать наличие ошибок в алгоритме?

2. Сколь долго может продолжаться отладка программ?

3. Зачем нужны доказательства в анализе алгоритмов?

4. Из чего состоит техника доказательств правильности?

5. Когда применяется разбор случаев?



6. Что такое леммы?

7. Что такое индуктивные рассуждения?

3 а д а ч и

 

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

а) подсчет суммы целых чисел;

б) подсчет суммы нечетных чисел;

в) подсчет членов арифметической прогрессии;

г) подсчет членов геометрической прогрессии.

2. Для последовательности чисел х1, х2,..., хN, приведите постановку, алгоритм решения и разбор правильности следующих задач:

а) подсчет суммы всех чисел;

б) вычисление среднего арифметического чисел;

в) определение наибольшего из чисел;

г) определение наименьшего из чисел.

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

а) нахождение самого высокого ученика;

г) нахождение самого легкого ученика;

д) нахождение среднего роста учеников;

е) нахождение суммарного веса учеников.

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

а) подсчет сумм элементов матрицы по столбцам;

в) нахождение минимального значения в каждом столбце;

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

ж) нахождение наибольшего из минимальных значений в столбцах;

з) нахождение наименьшего из максимальных значений в строках.

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

а) найти точку, наиболее удаленную от центра координат;

б) соединить пару наиболее удаленных точек;

в) найти три точки, образующие треугольник с наибольшим пери­метром;

г) найти три точки, образующие треугольник с наибольшей пло­щадью.


Элементы языка Пролог


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

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

Основная идея Пролога как языка записи

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

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

Факты - это конкретные сведения о ком-то либо о чем-то. Факты на языке Пролог записываются в форме предикатов с конкретными аргументами-значениями. Примеры записи фактов на Прологе:

папа (Вова, Лена);                           - Вова - папа Лены

любит (Лена, музыка);                   - Лена любит музыку

оценка (Лена, русский, 5);                         - У Лены 5 по русскому языку

Вопросы на Прологе - это запросы к совокупности данных или процедурам, хранящимся, в ЭВМ. Запись вопросов начинается со знака ?, за которым записывается предикат или группа предикатов, разделяемых запятыми. Примеры записи простых вопросов на языке Пролог:

? папа (х, Лена)                                - Кто папы Лены?

х = Вова

? мама (х, у)                                      - Кто у кого - мама ?

НЕТ

? оценка (х, _ , 5)                              - Кто имеет оценки 5?


х = Лена

Здесь буквы х, у - обозначения переменных, а числа и слова - конкретные значения аргументов в соответствующих предикатах. Знак подчеркивания «_» представляет неопределенное значение, которое несущественно для ответа на вопросы.

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

                

? мама (х, у), мама (у, Оля)            - Кто мама у мамы Оли?

х = Зина у = Люба

? мама (х, у), папа (у, Оля)             - Кто мама у папы Оли?

НЕТ

Правила в Прологе - это правила логического вывода. Слева в правилах записывается следствие, а справа - предусловие. Пред­условие может состоять из одного или нескольких предикатов, раз­деляемых запятыми. Примеры записи правил вывода на Прологе:

студент (х) ¬ занятие (х, учеба);                          - Студент - тот, кто занят учебой;

нумизмат (х) ¬ собирает (х, монеты);                - Нумизмат - тот, кто собирает монеты.

Примеры вопросов на использование этих правил:

? студент (х)                          - Кто - студент?

х =

Алеша    

х = Лена

? нумизмат (у)                      - Кто

- нумизмат?

у = Алеша

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

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

что им нравится;

что они коллекционируют;

чем они занимаются;

какие оценки они имеют.

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



нравится (<имя>, <вещь>);

собирает (<имя>, <вещь>);

занимается (<имя>, <предмет>);

оценка (<имя>, <предмет>, <балл>);

Вместо <имя>, <вещь>, <предмет>, <балл> при составлении базы знаний необходимо подставить конкретную информацию о конкрет­ных друзьях. Записывать имена будем с большой буквы в имени­тельном падеже. Далее,

<вещь> и <предмет>

- это существительные в именительном падеже,

<балл> - целое число от 1 до 5.

Пусть об Оле и Алеше известно следующее:

1. Оле нравится музыка. Она собирает фотографии любимых пев­цов. Занимается домоводством. Оля имеет 4 по русскому языку и  5 по алгебре.

2. Алеше нравится история, он собирает монеты, естественно, име­ет 5 по истории, занимается в археологическом кружке.

Соответствующая база данных на языке Пролог:

нравится (Оля, музыка);               - Оле нравится музыка

нравится (Алеша, история);         - Алеше нравится история

собирает (Оля, фотографии);        - Оля собирает фотографии

собирает (Алеша, монеты);           - Алеша собирает монеты

собирает (Алеша, значки);            - Алеша собирает значки

оценка (Оля, русский, 4);               - Оля имеет 4 по русскому языку

занимается (Алеша, бизнес);         - Алеша занимается бизнесом

оценка (Оля, алгебра, 5);               - Оля имеет оценку 5 по алгебре

оценка (Алеша, история, 5);          - Алеша имеет оценку 5 по истории

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

? занимается (Алеша, футбол) - Занимается ли Алеша футболом?

нет

? нравится (Оля, музыка)     - Нравится ли Оле музыка?

да

 

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


Например:

? нравится (х, у)                                                       - Кому что нравится?

х = Оля                      у = музыка

х = Алеша                 у = история

Если какая- то часть информации по той или иной причине не нужна, то вместо соответствующей переменной в вопросе ставится знак подчеркивания «_»:

? собирает (_ , х)                   - Что собирают друзья?

 х

= фотографии

х = монеты

х = значки

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

? занимается (х, музыка)               - Кто занимается музыкой ?

нет

? занимается (Алеша, у)                  - Чем занимается Алеша ?

у = бизнес

? собирает (х, монеты)                    -

Кто собирает монеты ?

х = Алеша

? оценка (х, _ , 5)                              - Кто имеет пятерки?

х = Оля

х = Алеша

Примеры сложносоставных вопросов:

1. Кто занимается бизнесом и собирает монеты?

? занимается (х, бизнес), собирает (х, монеты)

х = Алеша

2. Какие оценки имеет тот, кто собирает монеты?

? собирает (х, монеты), оценка (х, р, z)

х = Алеша

р = история

z = 5

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

книголюб (х) ¬ нравится (х, книги),                  - Книголюб - тот, кто

собирает (х, книги)                                                  любит и собирает книги

бизнесмен (х) ¬ собирает (х, монеты),                - Бизнесмен - тот, кто

занятие (х, бизнес)                                                   собирает монеты и занима­ ется бизнесом

Примеры использования правил-определений:

? книголюб (х)                      - Кто - книголюб?          

НЕТ

? бизнесмен (у)                      - Кто - бизнесмен ?

у = Алеша

 

 

В о п р о с ы

1. Как записываются факты на языке Пролог?

2. Как записываются вопросы на языке Пролог?

3. Как записываются правила в языке Пролог?



З а д а ч и

 

1. Опишите на языке Пролог данные о своей семье: о маме, папе, сестрах, братьях, дедушках и бабушках - кто кому приходится мамой и папой. Укажите вопросы для определения родственных отношений.

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

а) сластена;                         д) спортсмен;

б) филателист;                    е) бизнесмен;

в) математик;                      ж) музыкант;

г) программист;                  з) мусорщик.

3. Опишите в форме фактов для себя и своих ближайших друзей-одноклассников данные об оценках по предметам:

а) литература;                    г) физкультура;

б) математика;                   д) информатика;

в) физика;                             е) история.

4. Подберите правила определения понятий:

а) математик;                      д) физик;

б) историк;                           е) лирик;

в) двоечник;                         ж) троечник.

г) отличник;


Элементы математической логики


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

Все компьютерные программы, демонстрирующие

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

Логика - это наука, изучающая правильность суждений, рассуж­дений и доказательств. Примеры суждений: «снег белый», «2´2 = 5», «Земля круглая», «информатика - наука», «генетика - лженаука».

Суждения могут быть истинными или ложными. Истинность или ложность суждений проверяется их соответствием действительности. Пример истинного суждения - «снег белый».

Пример ложного суж­дения - «генетика - лженаука».

Суждение истинно, если оно отражает действительное положение вещей. Примеры истинных суждений: «снег белый», «2´2 = 4», «театр - это искусство».

Суждение ложно, если оно противоречит истинному положению вещей. Примеры ложных утверждений - «2´2 = 5», «снег - черный», «Земля плоская».

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

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

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


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

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

Основными объектами в математической логике являются - высказывания и предикаты. Первые изучаются в исчислении выска­зываний, а вторые - в исчислении предикатов.

Высказывания - это суждения, о которых может быть известно - что они истины или ложны. В исчислении высказываний не иссле­дуется - о чем утверждается в этих суждениях.

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

А

= «снег белый»

В1 = «вода теплая»

В2

= «земля твердая»

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

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

- это суждения о некото­рых переменных объектах или их свойствах. Примеры предикатов:

А(х) = «цвет яблока - х»

В(х, у) = «х

< у»

где х, у - это некоторые переменные (объекты).

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

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


Обозначения предикатов в матема­тической логике схожи с обозначениями обычных математических функций: Р(х), Q(x,y) и т. д.

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

любит (Маша, х);

цена (конфеты, с).

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

любит (Маша, цветы)                                - Маша любит цветы

любит (Саша, машины)                             - Саша любит машины

цена (цветы, 1000)                                       - цена цветов 1000

цена (мороженое, 2500)                               - цена морженого 2500

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

? любит (х, конфеты)                                  - Кто любит конфеты?

х = Маша

? цена (конфеты, с)                                     - Какова цена конфет?

с = 1000

 

В о п р о с ы

1. Что изучает математическая логика?

2. Что изучает логика?

3. Что такое высказывание?

4. Что такое предикат?

5. Когда суждения истинны?

6. Когда суждения ложны?

З а д а ч и

1. Приведите примеры истинных и ложных утверждений

а) из арифметики;

б) из геометрии;

в) из биологии;

г) из жизни.

2. Выразите отрицания для высказываний:

а) «мы пойдем в кино»;

б) «х = 0 или

х = 1»;

в) «х = 0 и

у = 0»;

г) «а = 0 и

b = 0 и

с = 0»;

д) «х = 0 или у = 0 или z = 0».

е) «мы не пойдем никуда»;

ж) «а = 0 или

b = 0»;

з) «х > 0 и х < 100».


Контроль знаний на ЭВМ


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

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

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

1) для проверки знаний на занятиях с использованием ЭВМ;

2) в качестве экзаменатора на зачетах и экзаменах;

3) в качестве тренажеров на самостоятельных занятиях с ЭВМ.

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

Особенностью данного электронного учебника является его

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

Электронным учебником по информатике можно пользоваться на компьютерах IBM PC с операционными системами MS DOS и Windows. В среде MS DOS запуск электронного учебника осуществ­ляется из каталога TEACHER, в котором находится программа, с помощью команды

> menu

Если запуск прошел успешно, то на экране появится заставка с названием программы, а затем - окно регистрации, в котором не­обходимо указать свою фамилию, имя и группу:

Информация    Регистрация    Работа    Темы    Протокол    Выход

 

Зарегистрируйтесь:

Фамилия: ___________

Имя: ______________

Группа: _____________

Дата:     01/01/1998

 

 

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

1) чтение разделов учебника;

2) обучение с использованием тестов;

3) контроль знаний учащихся.

В режиме «чтение» на экране можно читать разделы электронного учебника, организованные в главы и разделы точно так же, как и в бумажном учебнике. Пример

оглавления:



Информация            Регистрация             Работа            Темы              Протокол    Выход

 

Иванов

 

Глава 1. Информация и персональные ЭВМ

Глава 2. Элементы информационных технологий

Глава 3. Элементы «искусственного интеллекта»

Глава 4. Алгоритмы и начала программирования

Глава 5. Технология решения задач на ЭВМ

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



Информация            Регистрация             Работа            Темы              Протокол      Выход

 

Иванов

Глава 1.1. Информация и персональные ЭВМ

1.1.1. Введение в информатику

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

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

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

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

Пример контрольного вопроса:



Информация            Регистрация             Работа            Темы              Протокол   Выход

 

Иванов

Глава 1.1. Информация и персональные ЭВМ

1.1.1. Введение в информатику



Контрольный вопрос

Информация - [_____] о ком-то

или о [_____], передаваемые

в форме [____] и сигналов.

 

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

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

ЭВМ выводит на экран оценку «молодец»,

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

Оценка «хорошо» ставится, если не менее 50% слов совпадают с эталоном из учебника. В случаях, когда более половины слов отли­чается от эталонных ответов, выводится оценка «нехорошо».

Оценка «плохо» выводится, если не введено ни одного слова.

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

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

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

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


При этом при анализе ответа необходимо осмысление подбираемых фраз на предмет их истинности.

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

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

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

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

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

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

При этом все ответы записываются в протокол

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



-----------------------------------<ИТОГИ>------------------------------------

> Количество тестов =15

> Отлично =11

> Хорошо = 3

> Нехорошо = 1

> Плохо = 0

>!> Совпало ответов = 87 % <!<

>!> 0тсутствуют ответы = 0 % <!<

-----------------------------------------------------------------------------------

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

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

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

 

Фамилия: Чуков

Имя: Андрей

Группа: 434

Дата: 10/01/1997

###################################

Режим: Контроль

###################################

>@

Глава 2. Элементы информационных технологий.

>@ 2.4. Базы знаний на ЭВМ.

Признак - логическая [характеристика]

[объекта] / субъекта / [процесса].

------------------------------------------------------------------------------------

Определение понятия - совокупность [признаков],

характеризующих [содержание] понятия.

------------------------------------------------------------------------------------

Содержание понятия - совокупность [признаков],

выделяющих {объект}, отвечающих данному

понятию, [среди] других [объектов].

------------------------------------------------------------------------------------

--------------------------------------<ИТОГИ>--------------------------------



> Количество тестов =15

> Отлично =11

> Хорошо = 3

> Нехорошо = 1

> Плохо = 0

>!> Совпало ответов = 87 % <!<

>!>Отсутствуют ответы = 0 % <!<

----------------------------------------------------------------------------

<СИСТЕМА ЗАКОНЧИЛА РАБОТУ>*<10/01/1995>

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

 

В о п р о с ы

 

1. Что такое - электронные учебники?

2. Что такое - выборочные ответы?

3. Когда ответ считается правильным?

4. Когда и как получить подсказки?

5. Как добиться хорошей успеваемости?

З а д а н и я

1. Зарегистрируйтесь в электронном учебнике.

2. Сравните оглавления электронного и бумажного учебников.

3. Пролистайте первый раздел электронного учебника.

4. Проработайте тесты первого раздела учебника.

5. Ответьте на контрольные вопросы первого раздела.


Назначение интерпретатора Пролога


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

Данный интерпретатор может использоваться на персональных компьютерах IBM PC с операционной системой MS DOS или Windows. Для работы интерпретатора достаточно иметь оперативную память не менее 250 Кбайт и накопитель на гибком или жестком диске.



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


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

Согласно приказу министра образования Российской Федерации № 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 точки».

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



х

у

0

0

0

3

4

0

5

10

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

Сценарий



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

<х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. «Ломаная».



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

х

у

0

1

1

0

0

1

1

1

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

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

Tecт1.

(Основной случай)

0

0

0

1

1

0

1

1

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

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

0.5              0.5

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

0

0

0

1

1

1

1

0

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

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

отсутствуют

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

0

0

0

1

0.5

0

1

1

1

0

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

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

0.5              0

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

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>

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

            ………

     отсутствуют

Метод решения данной задачи может быть основан на вычислении точек пересечения отрезков (х1, у1) - (x2, у2) и (х3, y3) - (х4, y4) как точек пересечения линий, проходящих через заданные отрезки, с помощью системы уравнений:



 (y2

– y1 )×( x – x1) - (x2 – x1)×(y – у1) = 0;

 (у4

– у3)×(x – x3) - (x4 – x3)×(у – y3) = 0.

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

 (у2

– у1)×х - (х2 – х1)×у = (у2 – y1)×х1 - (x2

– x1)×y1;

 (у4

– y3)×х - (х4 – х3) ×у = (у4 – у3)×х3- (x4 – x3)×y3,

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

х = Dx/D;

у = Dy/D;

D = (у2 - у1)×(х4 - x3) - (x2 - x1)×(y4

-  y3);

 Dx = [(y2 - yl)×xl - (х2 – x1)×y1] - (x4

– х3) - (x2 – x1)×[(y4 – y3)×x3 - (х4

– х3)×y3];

Dy = (у2 - у1)×[(у4

– у3)×х3

- (x4 - x3)×у3] - [(у2 – y1)×x1 - (х2

– x1)×y1]×(y4 – y3).

Факт пересечения пар отрезков может быть установлен из этих же уравнений подстановкой в правые части координат точек альтерна­тивного отрезка и сравнением значений этих выражений. А именно отрезок [(х3, у3) - (х4, у4)] пересекает линию, проходящую через отрезок [(x1, y1) - (х2, у2)], если эти выражения имеют разные знаки:

(у2

- у1)×(х3 – x1) - (х2 – х1)×(y3 – у1) ´ (у2 - у1)×(х4

– x1) - (х2 – x1)×(y4 – y1) £

0.

Соответственно, отрезок [(х1, у1) - (х2, у2)] пересекает линию, проходящую через отрезок [(х3, у3) - (х4, у4)], если аналогичные выражения имеют разные знаки:

(у4

– у3)×(х1

– х3) - (х4 – х3)×(у1 – у3)´(у4

– у3)×(х2

– х3) - (х4 – х3)×(у2 – у3) £ 0.

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

В последнем случае общая часть отрезков находится из взаимо­расположения отрезков [(х1, у1) - (х2, у2)] и [(х3, у3) - (х4, у4)] на прямой.


В данной ситуации взаиморасположение вершин отрезков можно выяснить, вычислив взаиморасположение между ними на прямой относительно отрезка [(х1, у1) - (х2, у2)] по следующим фор­мулам:

d1 = 0;                                            

d2 = (х2 –

х1)×(х2 – х1) + (у2 – у1)×(у2 - 1);

d3 = (х3 – х1)×(x2

– х1) + (у3 - у1)×(у2 - 1);

d4 = (х4 – х1)×(х2

– х1) + (у4 – y1)×(y2 - 1).

Если d2 < min (d3, d4) или max (d3, d4) < 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 в подпрограмме ввода данных.


Операции с файлами


Для выполнения операций с файлами на дисках - записи, чте­ния, поиске, смене каталогов в настоящем интерпретаторе необхо­димо перейти в режим «Файл» нажатием клавиши F2 - работа с файлами. Результатом будет появление на экране следующего меню:

Открыть..  F3          

Сохранить F2          

Сохранить как..      

Смена Каталога..

           

Вызов DOS  

Выход    Alt-X

При переходе в режим «Открытие файлов» на экране появится окно:

-[_]                  — Открыть окно —           

 

 Имя

 *.*

Файлы

APP.PRL                   PROLOG. EXE                    Открыть

BLOK1.PRL             PROLOG.HLP                     Отмена

FAMILY.PRL          ..\                                             Помощь

HOM1.PRL

HOMES.PRL

 

D:\PROLOG\*.*

 

APP.PRL                   0                      Сен 8, 1991                            5:01pm

В этом окне перечислены имена файлов в текущем каталоге, ука­занном в предпоследней строке (обычно в каталоге PROLOG).

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

Для перехода в другой подкаталог, имя которого заканчивается символом « \ », требуется выбрать это имя и нажать клавишу ввода Enter. Для возврата в предыдущий каталог выбирается имя « ../ ».

Для записи текстов программ на диски необходимо перейти в режим работы с файлами (F2

- работа с файлами) и выбрать один из двух режимов:

Сохранить F2

Сохранить как ...

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

 

[_]         ----- Сохранить как ---- 

 

Новое имя:   D:\PROLOG\HOMES.PRL

Окей    Отмена

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

Для завершения работы с интерпретатором необходимо перейти в меню «Файл» и указать в нем подпункт «Выход». Этого же можно достичь нажатием клавиш Alt-X.

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



Описания фактов


Факты в языке Пролог описываются в следующей форме:

факт:

<имя>(<арг>[,<арг> ...]);

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

имя:

<буква>[<буква><цифра> ...]

Буквы могут быть выбраны из русского и латинского алфавитов.

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

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

Словосочетание:

<слово>[<слово> ...]

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

слово:

<буква>[<буква><цифра> ...]

Числа в данной реализации Пролога - это только целые числа (отрицательные - со знаком минус):

число:

[—]<цифра>[<цифра> ...]

Примеры записи чисел - 0, 1, +3, -25.

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




Основные логические операции


Суждения в математической логике могут быть простыми и сложносоставными. Примеры простых суждений:

х = 1                рост < 160

А                     цена (х, у)

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

не, выражающих три основных логических операции:

логическая связка не                         -

отрицание суждений;

логическая связка или                      - конъюнкция

суждений;

логическая связка и                          -

дизъюнкция суждений.

Примеры сложносоставных суждений:

не А                                                                - неверно суждение А

С или В                                              - истинно С или В

(х > 0) и (у > 0)                                  - (х больше 0) и (у

больше 0)

(глаза = синие) или (глаза = голубые)

Логическая связка не используется для выражения отрицаний. Примеры:

не (глаза = синие),                            - неверно, что глаза синие

не (А или

В),                                     - неверно, что выполняется А или В

не (любит (Саша, конфеты))            - неверно, что Саша любит конфеты

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

Отрицание не А истинно или ложно в зависимости от истинности исходного суждения А. Свойства отрицания не как логической связки можно описать таблицей истинности:

Таблица истинности:

А                     не А

да

нет

нет

да

Свойства отрицаний:

НЕ1: Отрицание ложно, если суждение истинно.

НЕ2: Отрицание истинно, если суждение ложно.

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

не

(х = 0)        º          (х ¹ 0)

не (х ¹

0)        º          (х = 0)

не

(х > 0)        º          (х £ 0)


не

(х < 0)        º          (х ³ 0)

не

(х ³ 0)        º          (х < 0)

не

(х £ 0)        º          (х > 0)

Свойства отрицаний, записанные в таблицу истинностности, могут быть описаны как факты на языке Пролог:

не (да, нет);

не (нет, да);

После ввода этих фактов в ЭВМ с помощью запросов можно перепроверить свойства отрицаний:

? не (А, нет)

А = да

? не (А, да)

А = нет

Логическая связка и в математической логике называется конъ­юнкцией. Таблица истинности

конъюнкции:

А                           В                           А и В

да

да

да

да

нет

нет

нет

да

нет

нет

нет

нет

Свойства конъюнкции:

И1: Конъюнкция А и В истинна, когда истинны оба суждения.

И 2: Конъюнкция А и В ложна, когда ложно хотя бы одно из суж­дений А или В.

Логическая связка или в математической логике называется дизъ­юнкцией. Таблица истинности

дизъюнкции:

 

 

А                            В                          А или В

да

да

да

да

нет

да

нет

да

да

нет

нет

нет

Свойства дизъюнкции:

ИЛИ1: Дизъюнкция А или В истинна, когда истинно любое из суждений А или В.

ИЛИ2: Дизъюнкция А или В ложна, когда ложны оба суждения А и В.

Свойства конъюнкции и дизъюнкции также можно описать в виде фактов на языке Пролог:

Дизъюнкция:                                     Конъюнкция:

или (да, да, да);                                 и2 (да, да, да);

или (да, нет, да);                               и2 (да, нет, нет);

или (нет, да, да);                               и2 (нет, да, нет);

или (нет, нет, нет);                           и2 (нет, нет, нет);

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

? или (А, В, нет)                               ? и 2 (А, В, да)

А = нет В = нет                                 А = да В = да



? или (А, В, да)                                 ? и 2 (А, В, нет)

А = да В = да                                     А = да В = нет

А = да В = нет                                   А = нет В = да

А = нет В = да                                   А = нет В = нет

Одной из важнейших логических связок математической логики является импликация А ® В. Эта связка в математической логике используется для определения правил логического вывода.

Импликация А ® В

- это логическое следование. Импликация А ® В

читается: «если А, то В». Первое суждение в импликации называется посылкой, а второе суждение - следствием.

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

а) с использованием высказываний:

если «на улице дождь», то «на улице мокро»,

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

любит (х, конфеты) ® сластена (х).

Таблица истинности импликации:

А                         В                       А ® В

да

да

да

да

нет

нет

нет

да

да

нет

нет

да

Свойства импликации:                       

П1: «Импликация А ® В ложна,

когда посылка А истинна, а следствие В - ложно».

П2: «Импликация А ® В истинна,

когда истинно следствие либо ложны и посылка и следствие».

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

сластена (х) ¬ любит (х, конфеты);

 

Описание этого правила позволяет вводить в ЭВМ вопросы о «сластенах» и получать осмысленные ответы, исходя из сведений, хранящихся в базе данных:

? сластена (х)    - Кто сластена?

х = Маша

 

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

Задача 1. Проверьте закон двойного отрицания в исчислении высказываний



не (не А) º А

Р е ш е н и е . Рассмотрим объединенную таблицу истинности вы­сказываний

      А                   не А               не (неА)

да

нет

да

нет

да

нет

 

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

(не А) º А.

Задача 2. Сравните с помощью таблиц истинности отрицание дизъюнкции и отрицание конъюнкции не (А и

В) и не (А или В).

Р е ш е н и е .

А                        В                    А и В                 не (А и В)              А или В           не (А или В)

да

да

да

нет

да

нет

да

нет

нет

да

да

нет

нет

да

нет

да

да

нет

нет

нет

нет

да

нет

да

 

В о п р о с ы

 

1. Когда истинно отрицание?

2. Когда ложна дизъюнкция?

3. Когда истинна конъюнкция?

4. Когда ложна импликация?

З а д а н и е

1. Составьте таблицы истинности для утверждений:

а) (не А) и (не В);       в) (не

А) или (не В);

б) А и (не В);               г) А или (не

В).

2. Сравните с помощью таблиц истинности логические выражения:

а) не (А и В);               в) (не А) или

(не В);

б) не (А и В);               г) (не А) или

(не В).

3. Проверьте по таблицам истинности логические законы:

а) отрицание конъюнкции:

не (А и

В) = (не А) или (не

В);

б) отрицание дизъюнкции:

не (А или

В) = (не А) и (не В);

в) отрицание импликации:

не (А ® В) º (не В) ® (не

А).


Основные свойства алгоритмов


Алгоритм относится к фундаментальным понятиям

информатики. На понятии алгоритма построено все основные принципы програм­мирования - составления программ для вычислительных машин.

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

Пример диалогового алгоритма:

Алгоритм                                                      Блок-схема

алг «приветствие»                                                             ¯

нач                                                                  запрос («Ваше имя=», NN)

запрос («Ваше имя=», NN)                                                 ¯

вывод («Добрый день», NN)                 вывод («Добрый день», NN)     

кон                                                                                          ¯

            

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

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

Приведем примеры описания алгоритма и программы в структу­рированной записи:

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


алг «приветствие»                                      ' приветствие

нач                                                                  сls

запрос («Ваше имя=», NN)                        input «Ваше имя=», NN$

вывод («Добрый день», NN)                      print «Добрый день», NN$

кон                                                                  end

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

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

Программа, приведенная справа, записана на языке Бейсик

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

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

С точки зрения информатики алгоритмы, записанные в такой обобщенной записи, позволяют выразить общую логику работы про­грамм,

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

В качестве примера приведем реализацию этого же диалогового алгоритма на самой ранней версии языка Бейсик, использовавшего­ся на самых первых персональных компьютерах:

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

алг «приветствие»                                      10 ' приветствие

нач                                                                  20 сls



запрос («Ваше имя=», NN)                     30   input «Ваше имя=», NN$

вывод («Добрый день», NN)                   40   print «Добрый день», NNS

кон                                                                  50 end

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

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

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

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

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

Алгоритм считается правильным, если он дает правильные резуль­таты для любых допустимых начальных условиях. Правильность алгоритмов гарантирует правильность результатов их выполнения.

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


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

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

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

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

а := 0                                                               а = 0                  

b := а + 1                                                        b ' = а + 1 = 1

b := b + 1                                                        b " = b' + 1 = 2

Запись присваиваний читается:

а := 0                                       - «переменной а присвоить значение 0»;

b := b + 1                                - «переменной b присвоить значение b + 1».

Записи в колонке результатов читаются так:

а = 0                                        - «значение а равно 0»;

b' = b + 1                                - «значение b' равно b + 1».

Здесь а и b - программные переменные - область машинной па­мяти, в которой хранятся их значения а и b. В отличии от обычных математических переменных программные переменные могут полу­чать новые значения. В частности, присваивание b: = b + 1 запи­сывает в программную переменную b

новое значение b', равное величине b + 1, где b - прежнее значение переменной b.

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

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


Рассмотрим в качестве примера сценарий алгоритма рисования домика на экране ЭВМ.

Сценарий «Домик»

 

 

 

 

 

 

 

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

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

алг «Домик»                                                  '

Домик

нач                                                                  screen 2,0

линия (130,40)-( 100,100), красная            line (150,40)-(100,100),8

линия (130,40)-(200,100), красная             line (150,40)-(200,100),8

рамка(100,100)-(200,200), белая                line (100,100)-(200,200),15,b

рамка(130,120)-(170,160), синяя               line (130,120)-(170,160),3,b

кон                                                                  end

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

Экран ЭВМ

 

 

 

 

 

 

 

 

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

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

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

алг «расчет прибыли»                                ' расчет прибыли

нач                                                                  сls

запрос («доходы =», d)                                input «доходы =», d

запрос («расходы =», r)                              input «расходы =», r

р:

= d - r                                                        р = d - r

вывод («прибыль =», р)                               print «прибыль =», р

кон                                                                  end



 

Сценарий диалога                                        Протокол диалога

доходы =?<d>                                                доходы =? 1000

расходы =? <г>                                             расходы =? 700

прибыль = <р>                                              прибыль = 300

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

Задача:            расчет прибыли.

Треб.:              р - прибыль.

Дано:              r - расходы;

d - доходы.

Где:                 d = r + р.

При:                 d > 0.   

                    

Для оценки правильности полученных результатов нужно сверить расходы и прибыль с доходами. В нашем случае это должно быть 700 + 300 = 1000, что выражает правильный конечный результат при указанных данных.

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

Операция                               Результат

р := d - r                     р = d – r

 

Подставляя в условие постановки задачи это значение, получаем:

d = r + p = r + (d - r) = d       - верное тождество.

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

 

В о п р о с ы

 

1. Что такое алгоритм?

2. Каковы основные виды алгоритмов?

3. Что такое однозначность алгоритмов?

4. Что такое результативность алгоритмов?

5. Что такое правильность алгоритмов?

6. Что такое массовость алгоритмов?

7. Что такое алгоритмические ошибки?

З а д а ч и

1. Составьте сценарий, алгоритм и программу:

а) поздравления с Новым годом;

б) поздравления с Днем рождения;

в) регистрации даты рождения;

г) регистрации фамилии и имени.

2. Составьте сценарии диалога, алгоритм и программу:

а) расчета сдачи за товар;

б) расчета остатка от прибыли;

в) пересчета рубль/доллар;

г) расчета остатка времени до 18.00.

3. Составьте сценарий, алгоритм и программу вычислений:

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

б) длины пути по времени и скорости движения;

в) средней скорости по времени и длине пути.

4. Составьте картинки, алгоритмы и программу рисования:

а) российского флага;                г) украинского флага;

б) шведского флага;                    д) французского флага;

в) японского флага;                     е) британского флага.

5. Составьте сценарий, алгоритмы и программу на Бейсике вывода изображений:

а) яхты;                           д) автомобиля;

б) трактора;                  е) усадьбы;

в) дерева;                       ж) цветка;

г) рыбы;                                          з) птицы.


Основные возможности Интернет


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

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

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

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

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

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

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


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

Региональная вычислительная сеть объединяет компьютеры в пределах определенного региона. Примерами региональных сетей являются корпоративные сети ЭВМ в банках и корпорациях, а также в промышленных и коммерческих предприятиях.

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

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

Скорость, наиболее распространенных современных модемов со­ставляет 2400, 9600, 14400, 19200, 22800 и 33600 Бод. Для электрон­ной почты можно использовать любой из этих модемов. Для работы в сети Интернет требуются модемы со скоростью передачи не ниже 19200 Бод.

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

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



Сетевые программы - это программы получения доступа к ин­формации, информационным ресурсам и информационным сис­темам, используемым в вычислительной сети. Примерами таких программ является сетевые пакеты Internet Explourer

фирмы Microsoft и Netscape Navigator фирмы Netscape, созданные для рабаты на компьютерах IBM PC с операционной системой Windows.

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

Основой современной информационной компьютерной индустрии и сети Интернет является всемирная распределенная сеть электрон­ных библиотек WWW - World Wide Web. Электронные библиотеки в этой сети размещены на специальных серверах.

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

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

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

www. prometеy. ankey.ru

В рассматриваемом примере имя сервера состоит из четырех час­тей.


Первое слово www - это признак подключения сервера к сети Интернет. Второе имя prometey - это имя системы дистанционного обучения Прометей. Третье имя ankey - это имя корпорации Анкей, которой принадлежит данный сервер. Последнее четвертое слово ru - это идентификатор сектора России в сети Интернет.

Примерами электронных библиотек в сети Интернет могут слу­жить серверы различных центральных газет, журналов - сервер га­зеты Известия,

сервер журнала Итоги, сервер радиостанции Русское Радио.

В Интернете Вы можете найти несколько игровых серверов, а также серверы Центров дистанционного обучения ведущих москов­ских и российских вузов - МЭСИ (Московский государственный университет Экономики, Статистики и Информатики) и МИЭМ (Московский Институт Электроники и Математики).

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

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

Стандартный заголовок электронного письма выглядит следую­щим образом:

From:             адрес отправителя

То:                  адрес получателя

Сс:                  другие адреса отправки

Subject:

         тема сообщения

Пример почтового адреса в сети Интерент:

vitkay@mail.ru

Первое имя vitkay - это идентификатор владельца электронного почтового ящика. Второе имя - адрес почтового сервера mail.ru. Здесь mail - идентификатор отечественной почтовой системы Mail-Ru, в которой любой из Вас может открыть себе бесплатный электронный почтовый ящик.

Для поиска информации в сети Интернет в нашей стране и за рубежом используется несколько информационно-поисковых сис­тем.


Среди отечественных систем наиболее известны системы Апорт, Ремблер и Яндекс, зарубежных -

Altavista, Infoseek, Yahoo.

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

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

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

 

В о п р о с ы

1. Что такое Интернет?

2. Что такое вычислительная сеть?

3. Какими бывают вычислительные сети?

4. Что такое сервер?

5. Что такое - информационные ресурсы?

6. Что такое

WWW?

7. Что такое гипертекст?

8. Что такое электронная почта?

9. Как образуются адреса в сети Интернет?

10. Как ищется информация в сети Интернет?

З а д а н и я

1. Найдите в сети Интернет сервер радиостанции

«Русское радио».

2. Найдите в сети Интернет сервер газеты

Известия.

3. Найдите в сети Интернет игровой сервер.

4. Найдите в сети Интернет вузы, занимающиеся дистанционным обучением.

5. Найдите в сети Интернет серверы с рефератами по истории и литературе.

6. Откройте себе почтовый ящик в Интернет.


Основы безошибочного программирования


Основной недостаток традиционной практики

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

Однако, так как число ошибок в программах

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

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

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

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

Более того, при систематическом использовании спецификаций

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

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

Для составления программ на любом языке программирования

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

Сценарий «Галерея картинок»



Список картинок:

1. треугольник

2. прямоугольник

3. кольцо

номер = ? <N>

 n =1                                   n = 2                        n = 3

 

В соответствии с этими четырьмя картинками построим три вспо­могательных алгоритма рисования отдельных картинок из «Галереи» и общий алгоритм выбора картинок в соответствии с принятым сценарием:

алг «Галерея картинок»

нач                                                                  алг «рисуиок_треугольника»

вывод («Список картинок:»)                 нач

вывод («1. треугольник»)                           линия(150,50)-(100,100)

вывод («2. прямоугольник»)                       линия(150,50)-(200,100)

вывод («3. кольцо»)                                      линия(100,100)-(200,100)

запрос («номер=», п)                               кон

графический_экран

если п = 1 то                                            алг «рисунок_прямоугольника»

рисунок_треугольника                      нач

инес п

= 2 то                                                 рамка(50,50)-(150,100)

рисунок_прямоугольника                  кон

инес п = 3 то

рисунок_кольиа                                   алг «рисунок_кольца»

иначе                                                         нач

вывод («нет такого рисунка»)              окружность( 100,100),20

все                                                                   окружность(100,100),50

кон                                                                  кон

 

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



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

Приведем примеры составления сложных алгоритмов и программ с циклами с использованием спецификаций. Первый пример - построение алгоритма и программы изображения на экране картинки «Звездное небо» из n случайных точек:



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

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

алг «звездное небо»                          ' звездное небо

нач                                                      сls

запрос(«звезд=», п)                          input «звезд=», n

графический_экран                        screen 2,0

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

x:

= случайное [0:200]                     х = rnd*200

у: = случайное [0:200]                     у = rnd*200

точка (х,у)                                        pset (x,y),3

кцикл                                                next k

кон                                                      end

Второй пример - составление с использованием спецификаций алгоритма и программы игры «Угадай-ка». В этой игре ЭВМ «зага­дывает» число от 0 до 100, а человек должен его отгадать, вводя пробные числа с клавиатуры. Для составления алгоритма и програм­мы примем следующий сценарий:

Сценарий «Угадай-ка»

Угадай число от 0 до 100

число = ? < х>

*

мало

много

молодец, умница

 

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


Выход из цикла происходит после совпадения ответа с числом, задуманным ЭВМ:

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

алг «угадай-ка»                                 ' угадай-ка

нач                                                      сls

вывод («Угадай число»)                 print «Угадай число»

вывод («от 1 до 100»)                     print «от 1 до 100»

z: = случайное [0:100]                     z = int (rnd* 100)

цикл                                                  do

запрос( «число=», х)                      input «число=», х

при х = z вых                                    if х = z then exit do

если х <

z то                                   if х < z then

вывод («мало»)                             print «мало»

инеc х > z то                                   elseif х > z then

вывод («много»)                            print «много»

все                                                    end if

кцикл                                               loop

вывод («молодец, умница»)          print «молодец, умница»

кон                                                      end

Сравнение алгоритма со сценарием показывает их полное соот­ветствие друг другу.

В о п р о с ы

 

1. Сколько ошибок содержится в программах?

2. Как долго длится отладка программ?

3. Что такое спецификации программ?

4. Зачем нужны спецификации?

5. Можно ли гарантировать отсутствие ошибок в программах?

6. Что такое систематический подход к алгоритмизации?

З а д а ч и

 

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

2. Составьте сценарий и алгоритм диалога с выбором по меню;

а) национальных флагов;

б) каталога строительных блоков;

в) набора рисунков;

г) каталога строений.

3. Предложите сценарии и алгоритмы рисования на экране абстракт­ных рисунков:

а) из случайных разноцветных точек;

б) из случайных разноцветных отрезков;

в) из случайных разноцветных рамок;

г) из случайных разноцветных окружностей;

д) из случайных разноцветных кругов;

е) из случайных разноцветных окошек.

4. Составьте сценарий и алгоритм, моделирующий на экране бро­уновское движение частиц.


Персональные компьютеры


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

Персональные компьютеры - это малогабаритные вычислитель­ные машины, которые могут быть установлены на любом рабочем месте. Наиболее известны и распространены персональные компью­теры IBM PC и Macintosh.

Минимальный состав персональных компьютеров:

1) системный блок;

2) дисплей;

3) клавиатура.

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

Общий вид персонального компьютера

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

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

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

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

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


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

В персональных компьютерах IBM PC используются процессоры фирмы Intel. В компьютерах младших моделей процессоры Intel - 86, 286, 386 и 486, а в старших моделях процессоры серии Pentium - Pentium, Pentium II, Pentium III и т. д. В персональных компьютерах Macintosh применяются процессоры фирмы Motorola.

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

Минимальной единицей информации считается бит. Бит - это ве­личина, принимающая значение 0 или 1. Любая другая информация может быть закодирована последовательностью из нулей и единиц. Именно в таком виде вся информация представляется в памяти ЭВМ.

Единицей памяти в современных ЭВМ считается байт. Байты - это 8-разрядные двоичные числа вида - 00000000, 00000001, ..., 11111111. Один байт записывается в виде 8 двоичных знаков инфор­мации - нулей и единиц:

1 байт = 8 бит.

Для измерения памяти большого объема используются следую­щие единицы:

1 Кбайт = 1024 байт   (1 килобайт);

1 Мбайт = 1024 Кбайт (1 мегабайт);

1 Гбайт = 1024 Мбайт (1 гигабайт).

Машины первого поколения имели оперативную память порядка нескольких килобайт, компьютеры второго поколения - десятки килобайт, а машины третьего поколения - сотни килобайт.

Оперативная память в персональных компьютерах типа IBM PC и Macintosh составляет несколько мегабайт. В больших современных ЭВМ объем оперативной памяти достигает порядка десятков мега­байт, а в компьютерах новых поколений - сотни и тысячи мегабайт.

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


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

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

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

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

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

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

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

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



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

Скорость передачи информации по линиям связи оценивается в бодах и килободах. Скорость в один бод - это передача одного бита в секунду:

1 бод

= 1 бит/секунда.

1 Кбод

= 1024 бод.

 

В о п р о с ы

 

1. Какие устройства входят в состав персональных компьютеров?

2. Что такое процессор?

3. Каково быстродействие современных процессоров?

4. В каких единицах измеряется объем памяти компьютеров?

5. Каков объем оперативной памяти современных компьютеров?

6. Каковы объемы памяти на гибких дисках?

7. Каковы объемы памяти на жестких дисках?

8. Каковы объемы памяти на компакт-дисках?