алг «сортировка массива» sortmas: 'сортировка массива
нач '
от k = 1 до N-1 цикл for k = 1 to N-1
xmn := x(k) xmn = x(k)
imn := k imn = k
от i = k + 1 до N цикл for i = k + 1 to N
если x(i) < xmn то if x(i) < xmn then
xmn := x(i) xmn = x(i)
imn := i imn = i
кесли end if
кцикл next i
Imn := L(imn) Imn = L(imn)
xmn := x(imn) xmn = x(imn)
L(imn) := L(k) L(imn) = L(k)
x(imn) := x(k) x(imn) = x(k)
L(k) :=Imn L(k) = Imn
x(k) := xmn x(k) = xmn
кцикл next k
кон return
Лемма 4. Результатами выполнения алгоритма сортировки массива будут последовательность чисел, упорядоченная по возрастанию
х(1)' £ х(2)' £ ... £ x(N)'
и последовательность индексов в массиве L[1:N], удовлетворяющих условиям
x(k)' = p(L(k)) для всех k = 1, .... N.
Доказательство. Первое утверждение об упорядоченности значений х(1)' £ х(2)' £... £ x(N)' массива x[l:N] по завершении алгоритма следует из доказательства правильности алгоритма упорядочения последовательности чисел. Для доказательства второго утверждения рассмотрим результаты перестановок значений элементов:
Imn := L(imn) Imn = L(imn)
xmn :=x(imn) xmn = x(imn)
L(imn) := L(k) L(imn)' = L(k)
x(imn) := x(k) x(imn)' = x(k)
L(k) := Imn L(k)' = Imn = L(imn)
x(k) := xmn x(k)' = xmn = x(imn)
Перед началом выполнения алгоритма упорядочения массива в алгоритме сортировки данных массив индексов L[1:N] и упорядочиваемый массив x[l:N] получают значения, удовлетворяющие следующим соотношениям:
х(i)' = P(L(i) для всех i = 1, ..., N.
Покажем, что эти соотношения сохраняются после каждого шага цикла. Действительно, на каждом очередном k-м шаге цикла будут получены следующие результаты:
Imn = L(imn)
xmn = x(imn) == p(L(imn))
L(imn)' = L(k)
x(imn)' = x(k) = p(L(k)) = p(L(imn)')
L(k)' = Imn = L(imn)
x(k)' = xmn= x(imn) = p(L(imn)) = p(L(k)')
Следовательно, после каждого шага цикла для переставленных элементов массивов сохраняются соотношения
x(i)' = p(L(i)) для всех i = 1, ..., N.
Что и требовалось доказать.
Утверждение. Конечным результатом выполнения алгоритма и подпрограммы сортировки данных будет список данных, в котором последовательность значений р1', р2', ..., рN' будет упорядочена:
p1'£ р2' £ … £pN'
Доказательство. В соответствии с доказанной выше леммой 4 значения в массиве x[l:N] после выполнения алгоритма упорядочения чисел будут удовлетворять условиям
х(1)' £ х(2)' £ ... £ x(N)'.
В силу этой же леммы 4 значения индексов в массиве L[1:N] будут удовлетворять соотношениям x[k]' = p(L(k)) для всех k = 1, ..., N.
Конечным результатом алгоритма сортировки данных является вывод значений из массива p[l:N] в соответствии с массивом индексов L[1:N]. Таким образом, очередные значения последовательности p1', p2',... будут равны:
р1' = p(L(l)) = х(1)',
p2'= р(L(2)) = х(2)'и т. д.
В силу упорядоченности значений х(1)', х(2)', ..., x(N)' получаем, что значения выходной последовательности будут также упорядочены:
p1'£ р2' £ … £pN'
Что и требовалось доказать.
Следовательно, весь комплекс алгоритмов и подпрограмм полностью соответствует поставленной задаче и гарантирует получение правильных результатов, при любых допустимых исходных данных.
Проверка на ЭВМ программы сортировки товаров, составленной таким систематическим образом, при указанных исходных данных дает следующие результаты:
товары:
яблоки, 500, 200
огурцы, 400, 250
арбузы, 200, 600
персики, 800, 100
остатки:
яблоки, 2500, 100
огурцы, 2000, 150
арбузы, 1200, 200
персики, 2000, 0
выручка = 880000
сортировка:
персики, 2000, 0
яблоки, 2500, 100
огурцы, 2000, 150
арбузы, 1200, 200
Таким образом, выполнение программы подтверждает правильность составленного комплекса алгоритмов. Полное и исчерпывающее обоснование их правильности приведено выше.
В о п р о с ы
1. Что такое сложные алгоритмы и программы?
2. Что такое упорядоченная последовательность?
3. Что такое упорядочение методом «пузырька»?
4. Как доказывается правильность сложных программ?
5. Что такое разработка программ «сверху-вниз»?
З а д а ч и
1. Составьте алгоритм и программу обработки данных о товарах и постройте обоснование их правильности для следующих задач:
а) подсчет планируемых доходов от продажи товаров;
б) подсчет начальной суммы вложений реализации товаров;
в) подсчет планируемой прибыли от продажи товаров;
г) подсчет текущей задолженности.
2. Составьте алгоритм и программу сортировки данных о товарах и постройте обоснование их правильности для следующих задач:
а) сортировка данных по начальному количеству;
б) сортировка данных по остаточному количеству;
в) сортировка данных по начальной стоимости;
г) сортировка данных по продажной цене.
3. Составьте алгоритм и программу сортировки данных о товарах по следующим признакам и приведите обоснование их правильности:
а) по доле планируемых доходов от реализации товаров;
б) по доле прибыли от реализации товаров;
в) по доле убыточности реализации товаров.
Глава 6. ЭКЗАМЕНЫ ПО ИНФОРМАТИКЕ
6.1. Экзамены и зачеты по информатике
Изучение информатики должно заканчиваться экзаменами, на которых проверяется знание основ информатики и умения решать задачи на персональных ЭВМ. Зачеты по информатике могут проводиться по завершении каждого из разделов курса информатики либо в конце курса по совокупности практических заданий.
Зачеты и экзамены по информатике могут и должны проводиться с помощью и использованием персональных ЭВМ. При дистанционном образовании персональные компьютеры являются основным средством обучения и поэтому экзамены по информатике должны проводиться только с помощью ЭВМ.
На зачетах должны проверяться уровень изучения курса информатики и выполнение компьютерных заданий. Проверка знаний и анализ выполнения заданий по информатике могут и должны проверяться на ЭВМ. В качестве средств контроля могут и должны использоваться бумажные копии результатов тестирования и выполнения заданий на ЭВМ.
Экзамены в вузах и колледжах, обучающих по программе бакалавриата, служат для проверки знаний студентов в соответствии с государственными стандартами высшего профессионального образования [I], утвержденными правительством Российской Федерации в 1994 г.
В соответствии с государственными стандартами образования все студенты должны освоить технику работы на персональных компьютерах, а также методы и средства накопления, передачи и обработки информации с помощью ЭВМ. Практические вопросы подтверждаются выполнением соответствующих заданий на ЭВМ, а теоретические вопросы - тестированием знаний с использованием компьютеров.
Для студентов гуманитарного и юридического профиля дополнительно требуются знания принципов представления знаний в ЭВМ и принципов работы систем искусственного интеллекта. Для студентов инженерного и экономического профиля дополнительно требуются знания основ программирования и решения задач обработки данных на ЭВМ.
На зачетах в соответствии с требованиями государственных стандартов должны быть проверены минимальные умения работы на персональных ЭВМ, отвечающих минимальному уровню компьютерной грамотности и выражающихся в выполнениии следующих учебных заданий:
1) оформление на ЭВМ стихотворения или юмористического рассказа, подготовленных с помощью редактора текстов;
2) оформление на ЭВМ рекламы или забавного рисунка, созданных с помощью графического редактора;
3) проведение поиска информации в сети Интернет по своим личным и профессиональным вопросам и проблемам.
Базовый уровень знаний основ информатики и владения средствами ЭВМ проверяется на зачетах или экзаменах по результатам самостоятельного выполнения на ЭВМ следующих учебных заданий:
1) организация на ЭВМ базы данных о товарах, услугах или фирмах со своими сведениями в некоторой системе управления базами данных;
2) организация на ЭВМ базы знаний о своих знакомых, друзьях или круге предметов с самостоятельно подобранными правилами вывода.
3) организация на ЭВМ калькуляций и расчетов закупок товаров или сметы затрат с помощью электронных таблиц.
Для студентов инженерных и экономических специализаций и направлений бакалавриата дополнительно должны быть проверены знания основ алгоритмизации и программирования, а также умения решать профессиональные задачи с помощью персональных ЭВМ.
Для проверки этого уровня изучения основ алгоритмизации и программирования на зачетах и экзаменах могут быть проверены результаты выполнения следующих учебных задании:
1) организация на ЭВМ диалоговой процедуры или программы с использованием диалоговой системы программирования;
2) организация на ЭВМ обработки данных на основе самостоятельно составленных алгоритмов и программ;
3) самостоятельное составление алгоритмов и программ решения задач вплоть до отладки и получения результатов на ЭВМ.
Высшим уровнем изучения основ информатики является овладение технологией решения профессиональных задач с помощью ЭВМ. Это уровень изучения курса информатики проверяется по результатам выполнения следующих учебных заданий: