Теория по логике


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Первичный и тестовый баллы. Шкалироварие
результатов
Подготовкой контрольно
измерительных
материалов для проведения ЕГЭ в России занимается
Федеральный институт педагогических измерений
ФИПИ:
www.fipi.ru
Для объективной оценки уровня выполненной
работы каждого участника ЕГЭ, по сравнению с
другими участниками экзамена, применяется специальная методика шкалирования результатов
ЕГЭ.
В ЧЕМ СУТЬ ПРОЦЕДУРЫ
ШКАЛИРОВАНИЯ?
При проведении ЕГЭ в экзамене участвует множество выпускников из разных образовател
ьных
учреждений, они имеют неодинаковый уровень подготовки и выполняют многообразные варианты
КИМ. В связи с этим встает вопрос, как объективно оценить и, самое главное, сравнить уровень их
подготовленности, ведь все выпускники имеют равные права при сдаче
выпускных экзаменов и
при поступлении в вуз?
В перечне терминов ЕГЭ существуют понятия "первичный балл" и "тестовый балл".
Шкалирование
это процедура перевода первичных баллов в тестовые, процесс формирования
правил начисления тестовых баллов по результ
атам проведения экзаменов на основе
статистических данных.
Первичный балл
это предварительный балл ЕГЭ, который получается путем прямого
суммирования числа правильных ответов, каждый из которых имеет определенный коэффициент
от 1 до 4. Максимальное кол
ичество первичных баллов за все задания КИМа по информатике
составляет 40 баллов.
ТЕСТОВЫЙ БАЛЛ И МЕТО
ДИКА ШКАЛИРОВАНИЯ
В диапазоне первичных баллов по общеобразовательному предмету выбираются два граничных
значения первичных баллов
ПБ1 и ПБ2, разделяющи
е группы участников с различным уровнем
подготовки по данному предмету.
ПБ1 выбирается как наименьший первичный балл, получение которого свидетельствует об
усвоении участником экзамена основных понятий и методов по информатике.
ПБ2 выбирается как наименьши
й первичный балл, получение которого свидетельствует о высоком
уровне подготовки.
Соответствующие граничные тестовые баллы ТБ1 и ТБ2 определяются с учетом результатов
сдачи ЕГЭ по России. При этом первичному баллу 0 ставится в соответствие тестовый балл 0,
максимальному первичному баллу ПБmax ставится в соответствие тестовый балл 100.
Все промежуточные первичные баллы между 0, ПБ1, ПБ2 и ПБmax переводятся в тестовые,
пропорционально распределенные между соответствующими значениями тестовых баллов:
При
таком преобразовании может случиться так, что промежуточные первичные баллы
соответствуют дробным значениям тестовых. В этом случае производится округление тестового
балла до ближайшего большего целого.
Также стоит заметить рост производной после прохожден
ия ПБ2. В середине один первичный
балл чаще равняется одному тестовому, а после ПБ2 один первичный по информатике почти
всегда увеличивает тестовый балл даже на два балла. Это значит, что "выгодно" готовиться так,
чтобы соревноваться не со середнячками, а
с сильными выпускниками.
Можно смотреть и с обратной стороны: когда Вы готовились на 100 баллов, обидно потерять даже
один первичный балл
это приведет к потере сразу двух тестовых баллов.
Планирование экзамена. Тайм
менеджмент на
экзамене
Традиционное по
следовательное выполнение заданий на экзамене может оказаться не лучшим
решением для Вас. Например, если Вы знаете, что задание С4 вы сумеете написать без
синтаксических и логических ошибок только при напряженной концентрации внимания, которая
будет у Вас
только в первый час после начала экзамена. Значит С4 Вам нужно решать первым,
конечно, строго ограничив себя по времени. То же относится к задаче В15, где требуется решить
сложное логическое уравнение или систему уравнений
вы можете оказаться просто не с
пособны
ее решать на третьем часу напряженной работы.
Большое количество ошибок совершается по глупости, по неаккуратности и из
за неправильно
прочитанного условия. Изготовители КИМ
профессионалы
На экзамен не допускается проносить электронные устройства
вроде мобильного телефона,
однако стоит обзавестись электронными или механическими наручными часами, или даже
будильником с крупным циферблатом. Контроль времени
одна из важнейших составляющих
успешной сдачи ЕГЭ.
Делайте перерывы во время экзамена! Нево
зможно поддерживать высокую концентрацию в
непрерывно течение четырех часов.
Внимательный читатель спецификации экзамена ЕГЭ по информатике в награду получит
информацию о предполагаемом количестве минут на выполнение соответствующих заданий. Я
собрал ее
для Вас в таблицу:
Если в процессе подготовки Вы будете решать много тренировочных заданий, и каждый раз
будете отмечать сколько времени у Вас заняло решение того или иного примера, Вы сможете
накопить свою личную информацию о времени выполнения заданий
Итак, создайте план выполнения экзамена ДО экзамена и неукоснительно следуйте ему! Если Вы
задерживаете выполнение одного задания, Вы автоматически заваливаете другую часть ЕГЭ. В
этом плане должно быть предусмотрено время как для переноса ответов в блан
к ответов, так и
для проверки всех заданий, включая внимательное "добуквенное" перечитывание условий.
Особенности сдачи экзамена по информатике на
бумаге
Сдача информатики на бумаге приводит к исключению возможности проверки более половины (!)
умений, пред
усмотренных программой школы в курсе информатики. На бумаге невозможно
проверить как выпускник научился делать презентации, редактировать картинки или
администрировать операционную систему.
К решению задач ЕГЭ по информатике нужно готовиться отдельно и доп
олнительно к
традиционным урокам информатики в школе!
Мы рады приветствовать Вас на наших дистанционных занятиях, но без напряженной и
самостоятельной работы Вас никто не сможет научить решать задачи ЕГЭ. Поэтому в курсе
подготовки к ЕГЭ по информатике для
Вас подготовлено большое количество домашних заданий
от восьми до двенадцати задач на каждую неделю.
Спецификация ЕГЭ по информатике 2014 года
Вся необходимая информация о содержании ЕГЭ по информатике находится в двух документах:
Спецификация КИМ ЕГЭ
по информатике,
Кодификатор элементов содержания и требований к уровню подготовки выпускников.
Обязательно ознакомьтесь с этими документами!
Текущие их версии доступны по ссылке:
http://fipi.ru/bi
naries/1517/infEGE2014.zip
Числа и цифры
Для начала проведём границу между числом и цифрой.
Число
основное понятие математики,
используемое для количественной характеристики, сравнения, нумерации объектов и их
частей.
Цифры
это знаки, используемые для
записи
чисел
. Цифры бывают разные, самыми
распространёнными являются арабские цифры, представляемые известными нам знаками от нуля
(0) до девяти (9); менее распространены римские цифры, мы их можем иногда встретить на
циферблате часов или в обозначении век
а (XIX век).
Итак, запомним: число
это абстрактная мера количества, цифра
это знак для записи числа.
Существует два основных способа
кодирования чисел
(то есть записи с помощью цифр):
непозиционные системы счисления;
позиционные системы счисления.
непозиционных
системах счисления величина числа не зависит от положения цифр в
представлении чисел. Простейшая непозиционная система счисления
унарная, где число
изображается соответствующим количеством палочек. Ярким примером непозиционной системы
счисл
ения является римская система.
Позиционные системы счисления
Позиционная система счисления
система счисления, в которой значение цифры в записи
числа зависит от её позиции в числе.
Число
это абсолютное понятие, выражающее количество. Одно и то же
число
может иметь
различную
запись
в разных системах счисления.
Цифра
это символ, используемый для записи чисел.
Разряд
это положение цифры в числе.

ПРИМЕР
Запись 12 обозначает число двенадцать, а 21
двадцать один.
Позиционная система счисления
определяется натуральным числом
,
называемым
основанием системы счисления
. Систему счисления с основанием
называют
ричной, в частности, двоичной (
), троичной (
), десятичной (
) и т. д.
Количество цифр, используемых в системе счисления,
определяется её основанием. В десятичной
системе цифр десять, в двоичной системе
две. То есть в
ричной системе счисления
количество цифр равно
, при этом используются цифры от 0 до
При записи чисел в позиционной системе, отличной от десятичной, п
ринято писать основание
справа внизу:
, где
Примеры чисел:
11001
число в двоичной системе счисления,
221
число в троичной системе счисления,
число в восьмеричной системе
счисления,
число в десятичной системе счисления,
Для обозначения цифр, больших 9, обычно используют латинские буквы: A (10), B (11), C (12), … .
Так, в частности, в 16
ричной системе, часто применяемой в информатике,
используются цифры 0,
1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
Развернутая форма записи числа
Когда мы записываем число в десятичной системе счисления (
), мы как бы раскладываем его
в сумму единиц (
), десяток (
), сотен (
), тысяч (
) и т.
д., при этом количество в каждом
разряде строго меньше 10.
Число
ричной системе счисления представляется также в виде суммы целых степеней
числа
с коэффициентами:
+
Перевод в десятичную систему счисления
осуществляется прямым вычислением по этой
формуле.
ПРИМЕР
101100
Чтобы уменьшить количество операций при переводе числа, можно переписать формулу в таком
виде:
(…((
)…)
Такой способ вычисления называется схемой Горнера для систем счисления.
Перевод в произвольную систему счисления
Мы знаем, что число
можно представить в виде
. Что будет, если мы поделим это
число на
с остатком? Получим
неполное частное
+…+
и остаток
, ведь все члены суммы делятся на
без остатка, а последний член
в результате
деления даёт 0 и
в остатке, так как максимальное значение цифры всегда на единичку меньше
основания системы. Итак, мы
получили самую правую цифру
как остаток от деления и число
как результат деления числа
. Если мы будем продолжать так делить, то
получим и все остальные цифры справа налево:
, …,
ПРИМЕР ПЕРЕВОДА ЧИСЛ
А В ДВОИЧНУЮ СИСТЕМУ
СЧИСЛЕНИЯ
Например, найдем представление числа 25 в двоичной системе счисления:
, остаток 1;
, остаток 0;
, остаток 0;
, остаток 1;
, остаток 1.
Что и следовало ожидать, получили:
11001
Обратите внимание, что мы продолжаем
делить, пока неполное частное не станет равным нулю.
Представим число 25 в троичной системе счисления:
, остаток 1;
, остаток 2;
, остаток 2.
Получили число:
221
Для закрепления наших знаний проделаем вычисления для восьмеричной и
десятичной систем
счисления.
Восьмеричная
система счисления:
, остаток 1;
, остаток 3.
Результат:
Десятичная
система счисления:
, остаток 5;
, остаток 2.
Результат:

Позиционные системы счисления позволяют легко
производить арифметические расчёты
столбик.
Двоичная система счисления
Среди позиционных систем счисления особое место занимает
двоичная система счисления
В двоичной системе всего две цифры
ноль и один.
При переходе на одну позицию
влево
значение
цифры
возрастает в два раза.
СВОЙСТВА ЧИСЕЛ В ДВО
ИЧНОЙ СИСТЕМЕ СЧИСЛЕ
НИЯ
четные числа оканчиваются на 0, нечетные
на 1;
числа, которые делятся на 4, оканчиваются на 00; …; числа, которые делятся на
, оканчиваются
нулей.
числа вида
записываются
в двоичной системе как единица и
нулей, например:
10000
числа вида
записываются в двоичной системе k единицами, например:
1111
если число N принадлежит интервалу
, в его двоичной записи будет всего k цифр,
например, для
числа 125:
128
1111101
(7 цифр);
если известна двоичная запись числа N, то двоичную запись числа
можно легко получить,
приписав в конец ноль, например:
1111
11110
111100
1111000
ПЛЮСЫ ДВОИЧНОЙ СИСТЕ
МЫ:
нужны
технические устройства только с двумя устойчивыми состояниями (есть ток
нет тока,
намагничен
не намагничен и т. п.);
выполнение операций с двоичными числами для компьютера намного проще, чем с десятичными;
таблицы сложения и умножения в двоичной систем
е намного меньше, чем в десятичной.
МИНУСЫ ДВОИЧНОЙ СИСТ
ЕМЫ:
простые десятичные числа записываются в виде бесконечных двоичных дробей;
одно и то же число в двоичной записи имеет больше разрядов, чем в десятичной;
запись числа в двоичной системе однородна,
то есть содержит только нули и единицы; поэтому
человеку сложно ее воспринимать.
Примеры задач A1
Пример задачи №1
Сколько единиц в двоичной записи числа
2084
РЕШЕНИЕ ЧЕРЕЗ ПРЯМОЙ
ПЕРЕВОД
переводим число
2084
в двоичную систему:
2084
100000100100
считаем
единицы
Ответ:

Пример задачи №2
Дано:
332
. Какое из чисел с, записанных в двоичной системе счисления,
удовлетворяет неравенству
11011001
11011100
11010111
11011001
Нужно перевести все числа в одну систему счисления и сравнить.
Операции в позиционных системах счисления
Операции сложения, вычитания, умножения и деления во всех позиционных системах счисления
делаются по одной алгоритмической схеме с переносом разряда при его заполнении более
основания и займами из старших разрядов
при вычитании. Эти алгоритмы известны вам как
алгоритмы вычисления
«столбиком».
В двоичной системе счисления операции в столбик выполняются тривиально, поскольку таблицы
сложения и умножения имеют размер 2х2:
Пример умножения чисел в двоичной системе счисления:
Двоичная система счисления
Среди позиционных систем счисления особое место занимает
двоичная система счисления
В двоичной системе всего две цифры
ноль и один.
При переходе на одну позицию
влево
знач
ение цифры
возрастает в два раза.
СВОЙСТВА ЧИСЕЛ В ДВО
ИЧНОЙ СИСТЕМЕ СЧИСЛЕ
НИЯ
четные числа оканчиваются на 0, нечетные
на 1;
числа, которые делятся на 4, оканчиваются на 00; …; числа, которые делятся на
, оканчиваются
нулей.
числа вида
записываются в двоичной системе как единица и
нулей, например:
10000
числа вида
записываются в двоичной системе k единицами, например:
1111
если число N принадлежит интервалу
, в его двоичной записи будет всего k цифр,
например, для числа 125:
128
1111101
(7 цифр);
если известна двоичная запись числа N, то двоичную запись числа
можно легко получить,
приписав в конец ноль, например:
1111
11110
111100
1111000
ПЛЮСЫ ДВОИЧНОЙ
СИСТЕМЫ:
нужны технические устройства только с двумя устойчивыми состояниями (есть ток
нет тока,
намагничен
не намагничен и т. п.);
выполнение операций с двоичными числами для компьютера намного проще, чем с десятичными;
таблицы сложения и умножения в
двоичной системе намного меньше, чем в десятичной.
МИНУСЫ ДВОИЧНОЙ СИСТ
ЕМЫ:
простые десятичные числа записываются в виде бесконечных двоичных дробей;
одно и то же число в двоичной записи имеет больше разрядов, чем в десятичной;
запись числа в двоичной сист
еме однородна, то есть содержит только нули и единицы; поэтому
человеку сложно ее воспринимать.
Сложные задачи ЕГЭ на системы счисления
Классификация задач B7
Ищется цифра в наборе чисел.
Ищется основание одной или нескольких систем счисления.
Ищется одно
или несколько чисел в заданных системах счисления.
Методы решения в зависимости от задачи тоже разные.
Некоторые решаются "в лоб" переводом из системы счисления в систему счисления.
Знанием свойств чисел в различных системах счисления.
Выполнением арифмети
ческих операций в заданной системе счисления.
Составлением целочисленного уравнения.
Задачи на составление нескольких вариантов уравнения, каждый из которых нужно решить.
Задача на перебор слов и системы счисления
ЗАДАЧА НА ПЕРЕБОР СЛ
ОВ И СИСТЕМЫ СЧИСЛЕН
Все 5
буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.
Вот начало списка:






АААОА


Запишите слово, которое стоит на
м месте
от начала списка.
РЕШЕНИЕ
Если заменить букву
на 0,
на 1, а
на 2, то
становится очевидной параллель получающихся
"слов" с числами в троичной системе счисления:
00000
00001
00002
00010


При этом заметно, что номер числа в списке не совпадает со значением самого числа на 1.
Таким образом на 150
м месте стоит число 149.
Для ответа на попрос о слове нужно перевести 149 в троичную СС, и записать обратно буквами.
149
12112
Ответ: ОУООУ
Битовые логические операции
Битовые операции отличаются от логических операций тем, что применяются к каждому биту
отдельно.
Битовое
отрицание (NOT)
Побитовое отрицание (или побитовое НЕ, или дополнение)
это операция, которая заменяет
каждый бит числа на противоположный. Другими словами, на той позиции, где в двоичном
представлении числа был 0, в результате будет 1, и, наоборот, где б
ыла 1, там будет 0. Например:
Битовое И (AND)
Побитовое И
это бинарная операция, действие которой эквивалентно применению логического
И к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях
операндов. Другими
словами, если оба соответствующих бита операндов равны 1,
результирующий двоичный разряд равен 1; если же хотя бы один бит из пары равен 0,
результирующий двоичный разряд равен 0. Пример:
0011
0101
Битовое ИЛИ (OR)
Побитовое ИЛИ
это бинарная
операция, действие которой эквивалентно применению
логического ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичных
представлениях операндов. Другими словами, если оба соответствующих бита операндов равны
0, двоичный разряд результата р
авен 0; если же хотя бы один бит из пары равен 1, двоичный
разряд результата равен 1. Пример:
ИЛИ
0011
0101
Битовое исключающее ИЛИ (XOR)
Побитовое исключающее ИЛИ (или побитовое сложение по модулю два)
это бинарная
операция, действие которой
эквивалентно применению логического исключающего ИЛИ к каждой
паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов.
Другими словами, если соответствующие биты операндов различны, то двоичный разряд
результата равен 1; если ж
е биты совпадают, то двоичный разряд результата равен 0. Пример:
Искл. ИЛИ
0011
0101
Первое русское название операции обусловлено тем, что результат данной операции отличается
от результата «ИЛИ» только в одном случае из 4 случаев входа
обоих 1
(случай одновременной
истинности аргументов «исключается»). В русской языке значение данной логической связки
передаётся союзом «либо».
Алфавитный подход к измерению количества
информации
1 бит
количество информации, равное информации в одном двоичном
разряде.
Мощность алфавита
количество символов в нем.
Информационный объем
одного символа
алфавита в битах может быть вычислен по следующей таблице:
Количество
вариантов
4
8
16
32
64
128
256
512
1024
Количество бит
информации
То
есть с помощью
бит можно закодировать
различных вариантов символов. Для
алфавита, содержащего промежуточное между степенями двойки количество символов,
количество необходимых бит нужно округлять в большую сторону. (Лучше, если у нас окажутся
двоичные коды, которым не соответствуют ни один символ алфавита, чем если окажется, что
некоторые символы невозможно закодировать выбранным количеством бит, так как все
комбинации уже соответствуют другим символам.)
Чтобы найти информационный объем сообщен
ия (текста)
, нужно умножить количество
символов
на число бит для кодирования одного символа
Если алфавит имеет мощность
, то количество всех возможных «слов» (символьных цепочек)
длиной
(без учета смысла) равно
; для двоичного
кодирования (мощность алфавита
получаем известную формулу:
Степени двойки до десятой включительно полезно знать наизусть.
Единицы измерения объема информации
В качестве единицы информации условились принять один
бит
(англ.
bit
binary digit
двоичная
цифра
Бит в теории информации
количество информации, необходимое для различения двух
равновероятных событий.
Одним битом может быть выражено одно из двух понятий: 0 или 1 (да или нет, черное или белое,
истина или ложь и т.п.).
На практике ч
аще применяется более крупная единица
байт
, равная восьми битам.
С помощью одного байта можно закодировать
различных событий.
Широко используются также ещё более крупные производные единицы информации:
1 Кибибайт (Кб) = 1024 байт =
байт,
1 Ме
бибайт (Мб) = 1024 Кбайт =
байт,
1 Гибибайт (Гб) = 1024 Мбайт =
байт,
1 Тебибайт (Тб) = 1024 Гбайт =
байт,
1 Пебибайт (Гб) = 1024 Тбайт =
байт.
Обратите внимание на правильное именование двоичных чисел. Приставки схожи с СИ: они
начинаются
на те же слоги, но второй слог у всех двоичных приставок
би (
англ.
binary
«двоичный»). Стандарт был утверждён на международном уровне в марте 1999 года
Международной электротехнической комиссией.
Чем больше число, тем большего значения может достигать
ошибка, вызванная неправильным
пониманием использованной приставки. В частности, разница между «двоичным» и «десятичным»
килобайтом 2,4%, в то время как между двоичным и десятичным гигабайтом
уже более 7%. Для
того, чтобы разрешить эту путаницу, и были в
ведены особые двоичные приставки, отличные от
«близких» по численному значению десятичных.
В задачах ЕГЭ и ГИА следует понимать приставки исключительно как двоичные.
Кодирование информации
Кодирование
это перевод информации с одного языка на другой (запи
сь в другой системе
символов, в другом алфавите). При этом обычно кодированием называют перевод информации с
«человеческого» языка на формальный, например, в двоичный код, а
декодированием
обратный переход. Один символ исходного сообщения может заменятьс
я одним символом нового
кода или несколькими символами, а может быть и наоборот
несколько символов исходного
сообщения заменяются одним символом в новом коде (так, китайские иероглифы обозначают
целые слова и понятия).
Кодирование может быть
равномерное
неравномерное
; при
равномерном кодировании все символы кодируются кодами равной длины; при неравномерном
кодировании разные символы могут кодироваться кодами разной длины, это затрудняет
однозначное декодирование или даже делает его невозможным.
Скорост
ь передачи информации
Любой канал связи имеет ограниченную пропускную способность (скорость передачи
информации), это число ограничивается свойствами аппаратуры и самой линии (кабеля).
Объем переданной информации Q вычисляется по формуле
, где q
про
пускная
способность канала (в битах в секунду или подобных единицах), а t
время передачи.
Кодирование звуковой информации
При оцифровке звука в памяти запоминаются отдельные значения сигнала, который нужно выдать
на динамик или наушники, при этом
количе
ство отсчетов, запоминаемых за 1 секунду,
определяется частотой дискретизации.
1 Гц (один герц)
это один отсчет в секунду, а 8 кГц
это 8000 отсчетов в секунду
Глубина кодирования
это количество бит, которые выделяются на один отсчет.
Для хранения инф
ормации о звуке длительностью N секунд, закодированном с частотой
дискретизации x Гц и глубиной кодирования Z бит потребуется N*x*Z бит памяти.
Например, при кГц, глубине кодирования 16 бит на отсчёт и длительности звука 128 секунд
требуется 8000 * 16 *
128 = 1638400 бит =2000 Кбайт, то есть около 2 Мбайт.
Двухканальной записи (стерео)
объем памяти, необходимый для хранения данных одного канала,
умножается на 2, при четырехканальной (квадро)
на 4.
История современной логики
Логика
«наука о правильном
мышлении», «искусство рассуждения»
наука о формах, методах
и законах интеллектуальной познавательной деятельности, формализуемых с помощью
логического языка.
Цель применения методов логического мышления и законов логики
получение знания на основе
имею
щейся информации и достижение истины. Логика служит одним из инструментов почти любой
науки.
Главная задача классической логики
определить, как прийти к выводу из предпосылок, то
есть правильное рассуждение.
Краткая история логики
Логика как явный анализ
методов рассуждения получила развитие только в трёх традициях: в
китайской, индийской и греческой. Возникла во всех трёх культурах в IV веке до нашей эры.
Современная логика происходит из греческой
аристотелевской логики
" при посредничестве
арабо
мусульманских философов и средневековых европейских логиков. В конце XIX
начале
XX веков были заложены основы
формальной логики
, а затем так называемой
математической
логики
Оказалось, что для обнаружения истинностного значения выражений естествен
ного языка можно
применять математические методы. Использование символической логики отличает современную
логическую науку от традиционной.
Формальная логика
Начальной ступенью формальной логики можно считать традиционную логику, а математическую
логику
её следующей ступенью, использующей математические методы, символический
аппарат и логические исчисления.
Кратко изложим понятия формальной логики.
Основными формами мышления являются
понятие
высказывание
(суждение)
умозаключение.
Понятие
это форма мы
шления, отражающая наиболее существенные признаки предмета,
отличающие его от других предметов.
Высказывание
это форма мышления, выраженная с помощью понятий, посредством которой
что
либо утверждают или отрицают о предметах, их свойствах и отношениях меж
ду ними.
Высказывание может быть либо
истинным
, либо
ложным
Высказывание называется
простым
, если никакая его часть сама не является высказыванием,
составным
, если оно состоит из простых высказываний.
Обоснование истинности или
ложности простых
высказываний решается вне рамок логики
Высказывания могут быть выражены повествовательным предложением на естественном языке,
но также могут быть записаны языком символической логики.
Умозаключения
различают по направлению логического следования:
Дедуктивные (от общего к частному).
Индуктивные (от частного к общему).
Трансдуктивные (по аналогии
от одной степени общности к такой же степени общности).
По достоверности вывода умозаключения делят на достоверные и правдоподобные.
Теория множеств
ИСТОРИЯ
В 1870 году немецкий математик Георг Кантор разработал свою программу стандартизации
математики, в рамках которой любой математический объект должен был оказываться тем или
иным
«множеством»
. При этом общему понятию «множества» Кантор давал мало что
говорящие
определения вроде «множество есть многое, мыслимое как единое», и т. д. Многие крупные
математики поддержали Кантора в его намерении перевести всю математику на теоретико
множественный язык. (В частности, теория множеств стала фундаментом теории
меры и
интеграла, топологии и функционального анализа.)
Однако вскоре был обнаружен
ряд теоретико
множественных антиномий
: оказалось, что при
использовании теоретико
множественных представлений некоторые утверждения могут быть
доказаны вместе со своими
отрицаниями. В начале XX века Бертран Рассел, изучая канторовскую
теорию множеств, пришел к парадоксу (с тех пор известному как парадокс Рассела). Таким
образом, была продемонстрирована несостоятельность канторовской идеи стандартизации
математики. После о
бнаружения этой антиномии часть математиков решила полностью отказаться
от использования теоретико
множественных представлений, а другая часть математиков,
возглавленная Д. Гильбертом, разработала несколько вариантов аксиоматизации теории
множеств.
Круги
йлера
геометрическая схема, с помощью которой можно изобразить отношения между
подмножествами, для наглядного представления. Изобретены Леонардом Эйлером. Особенного
расцвета графические методы достигли в сочинениях английского логика Джона Венна (1843
1923), подробно изложившего их в книге «Символическая логика», изданной в Лондоне в 1881
году. Поэтому такие схемы иногда называют Диаграммы Эйлера
Венна. Важный частный случай
кругов Эйлера
диаграммы Эйлера
Венна, изображающие все
комбинаций n с
войств, то
есть конечную булеву алгебру.
Основные понятия
В основе теории множеств лежат первичные понятия:
множество
и отношение
быть
элементом
множества (обозначается как
«x есть элемент множества A»).
Над множествами определены следующие
операции
объединение (или сумма) (обозначается как
пересечение (или произведение) (обозначается как
разность (обозначается как
, реже
симметрическая разность (обозначается как
Для множеств определены следующие
бинарные отношения
отношение равенства (обозначается как
отношение включения (обозначается как
Операции алгебры логики
Базовыми элементами, которыми оперирует алгебра логики, являются
высказывания
.
Высказывания обозначают строчными буквами
логическими
переменными
. Возможные
значения логической переменной: 1
истина
, 0
ложь
. Высказывания строятся из
логических
переменных
логических констант
1 и 0 при помощи
операций
отрицание (унарная операция),
конъюнкция, логическое умножение
(бинарная),
дизъюнкция, логическое сложение (бинарная),
эквивалентность («тогда и только тогда, когда») (бинарная),
импликация («следовательно») (бинарная),
сложение по модулю два («исключающее или»),
штрих Шеффера,
стрелка
Пирса и
другие.
Приоритет логических операций
: если в выражении нет скобок, сначала выполняются все
операции «НЕ», затем
«И», затем
«ИЛИ», и самая последняя
«импликация».
ИЗОБРАЖЕНИЯ ЛОГИЧЕСК
ИХ ОПЕРАЦИЙ В ВИДЕ О
ПЕРАЦИЙ НАД
МНОЖЕСТВАМИ
Таблицы
истинности
В алгебре логики используются следующие логически операции: НЕ, И, ИЛИ, XOR, импликация,
эквивалентность.
ОПЕРАЦИЯ НЕ
A истинно когда «не А» ложно.
ОПЕРАЦИЯ И
«A и B» истинно тогда и только тогда, когда А и B истинны
одновременно.
И называется также логическим умножением или конъюнкцией.
ОПЕРАЦИЯ ИЛИ
«A или B» истинно, когда истинно А или B, или оба вместе.
Можно сказать, что «A или B» ложно тогда и только тогда, когда ложны А и В
одновременно.
ИЛИ называют логическим сложением или дизъюнкцией.
ОПЕРАЦИЯ XOR (ИСКЛЮЧ
АЮЩЕЕ ИЛИ)
B» истинно тогда, когда истинно А или B, но не оба одновременно.
Эту операцию также называют "сложение по модулю два".
ОПЕРАЦИЯ ИМПЛИКАЦИИ
B» истинно, если из А может следовать B.
Если из истины следует ложь, то следствие ложно. При этом из лжи корректными следствиями
может получиться все, что угодно, поэтому в остальных случаях
импликация истинна.
ЭКВИВАЛЕНТНОСТЬ (ТОЖ
ДЕСТВО)
B» истинно тогда и только тогда, когда А и B равны.
Таблицы истинности можно составить и для произвольной логической функции
F(a, b, c…).
В общем случае таблицы истинности имеют размер
строк комбинаций для N независимых
логических переменных.
Поскольку таблица истинности выражения состоит из строк со всеми возможными комбинациями
значений переменных, она полностью определяет
значение выражения.
Удобные обозначения логических операций
Обозначения логических операций И, ИЛИ и НЕ в классической математической логике (
интуитивно непонятны, не проявляют аналогии с обычной алгеброй.
Альтернативные обозначения
«НЕ»
черта
сверху;
«И»
знак умножения (
логическое умножение
«ИЛИ»
знак «+» (
логическое сложение
Продемонстрируем мощь альтернативных обозначений логических операций:
0 = 0
не очевидно
0 = 0
очевидно!
0 = 1
не очевидно
1 + 0 = 1
очевидно!
1 = 1
не очевидно
1 + 1 = 1
не очевидно, но можно смириться
Итак, таблицы истинности для И и ИЛИ можно не учить, нужно запомнить только одно исключение:
1 + 1 = 1
Логические переменные и логические функции
Логическая переменная
это простое
(атомарное) высказывание, ложность или истинность
которого лежит вне рамок формальной логики.
В соответствии с законами комбинаторики,
логическая функция
F(A,B,C…) от N логических
переменных определена на множестве мощности 2 в степени N, а всего возможных
логических
функций, зависящих от N переменных
Например, логических функций от 2 переменных всего 16 штук, а от 3 переменных
уже 256 штук.
Логические функции могут быть однозначно заданы как посредством
составных логических
высказываний
, так и
посредством
таблиц истинности
Для функций с большим количеством логических переменных таблицы истинности имеют большой
размер. Если известна только часть таблицы истинности, функция недоопределена, то есть
частичной таблице могут соответствовать несколько
разных логических функций.
Соответствующее логическое выражение также однозначно определить нельзя, однако можно
отбросить те выражения, которые заведомо не подходят под данную частичную таблицу.
Законы алгебры логики
Простые законы логики:
закон
повторения
третий
лишний
¯¯¯¯¯
закон поглощения
Свойства логических операций
коммутативность
(переместительный)
ассоциативность
(сочетательный)
)=(
)=(
дистрибутивность
(распределительный)
)=(

Законы отрицания:
закон двойного отрицания
¯¯¯¯¯¯¯¯¯¯
закон де Моргана
для сложения
¯¯¯¯¯¯¯¯¯¯¯¯
закон де Моргана
для умножения
¯¯¯¯¯¯¯¯¯¯
¯¯¯¯¯
¯¯¯¯¯
Представление импликации, эквиваленции и XOR
импликация
эквиваленция
¯¯¯¯¯
(антиэквиваленция)
¯¯¯¯¯
Сложные запросы для поисковых систем
Задача 1
В таблице приведены запросы к поисковому серверу. Расположите
номера запросов в порядке
возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для
обозначения логической операции «ИЛИ» в запросе используется символ
, а для логической
операции «И»
принтеры & сканеры & продажа
принтеры & продажа
принтеры
продажа
принтеры
сканеры
продажа
РЕШЕНИЕ
Запишем запросы как логические выражения с предикатами:
,


,


,





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

Задача 2
Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом
режиме составил таблицу ключевых
слов для сайтов этого сегмента. Вот ее фрагмент:
Ключевое слово
Количество сайтов, для которых
это слово является ключевым
сканер
принтер
монитор
Сколько сайтов будет найдено по запросу
(принтер
сканер) & монитор
если по запросу
принтер
сканер
было найдено 450 сайтов, по запросу
принтер & монитор
40,
а по запросу
сканер & монитор
РЕШЕНИЕ

Обозначим высказывания через C, П, М и нарисуем эти области виде кругов Эйлера.
Запросу (П
C) & M соответствует объединение областей 4, 5
и 6.
Количество сайтов, удовлетворяющих запросу в области
, будем обозначать через
Уравнения, которые определяют запросы:
сканер
200
принтер
250
принтер
сканер
450
Из первого и третьего уравнений сразу
следует
200
450
250
Из второго уравнения
250
250
Поскольку количество сайтов не может быть отрицательной величиной,
Учитываем, что
принтер & монитор
сканер & монитор
В результате:
(принтер | сканер) & монитор
Ответ
Предикаты
Предикат
любое математическое высказывание, в котором есть по меньшей мере одна
переменная. Т.е. предикат
это функция с множеством значений {0,1} (или «ложь» и «истина»),
определённая на некотором множестве. Например:
Предикаты, так же, как обычные высказывания, принимают два значения истинное и ложное,
поэтому к ним применимы все операции логики высказываний. Результатом этих операций также
является предикат.
Законы алгебры логики
Простые законы логики:
закон повторения
третий
лишний
¯¯¯¯¯
закон поглощения
Свойства логических операций
коммутативность
(переместительный)
ассоциативность
(сочетательный)
)=(
)=(
дистрибутивность
(распределительный)
)=(

Законы отрицания:
закон двойного отрицания
¯¯¯¯¯¯¯¯¯¯
закон де Моргана
для сложения
¯¯¯¯¯¯¯¯¯¯¯¯
закон де Моргана
для умножения
¯¯¯¯¯¯¯¯¯¯
¯¯¯¯¯
¯¯¯¯¯
Представление импликации, эквиваленции и XOR
импликация
эквиваленция
¯¯¯¯¯
¯¯¯¯¯
Zglbwd\b\Ze_gpby












































знак
как бы «фиксирует» значение: в абсолютных адресах и имя столбца, и номер строки
зафиксированы
в относительных адресах
знаков
доллара нет, такие адреса
при копировании изменяются:
номер столбца (строки) изменяется на столько, на сколько отличается номер столбца (строки),
где оказалась скопированная формула, от номера столбца (строки) исходной ячейки; вот что
будет, если формулу
=B2+C3 (в ней оба адреса
относительные) скопировать из D5 во все
соседние ячейки:
в смешанных адресах
часть адреса (строка или столбец)
абсолютная, она «зафиксирована»
знаком
, а вторая часть
относительная; относительная часть изменится при
копировании так
же, как и для относительной ссылки:
Примечание:
Ссылки на ячейки, используемые в качестве аргументов функции, следует вводить
на английском языке.
Существует два основных способа ввода формул в ячейку: ввести ее
полностью вручную или
указать адреса используемых в ней ячеек указателем мыши прямо в
рабочем листе.

Функции работы с диапазонами ячеек
Запись B2:C4 означает диапазон, то есть, все ячейки внутри прямоугольника, ограниченного
ячейками B2 и C4:
Например, по формуле =SUM
(B2:C4) вычисляется сумма значений ячеек B2, B3, B4, C2, C3 и C4
В заданиях государственных экзаменов ГИА и ЕГЭ могут использоваться следующие стандартные
функции:
СЧЕТ (количество непустых числовых ячеек)
COUNT;
СУММ (сумма)
SUM;
СРЗНАЧ (среднее з
начение)
AVERAGE;
МИН (минимальное значение)
MIN;
МАКС (максимальное значение)
MAX.
При этом нужно помнить, что эти функции, являясь математическими, при вычислении не
учитывают как пустые ячейки, так и ячейки с текстом.
Например, ячейка А2
пуста
тогда функция AVERAGE
(A1:B2) вернет значение 2 (а не 1,5, если бы А2 учитывался как ноль), а
COUNT
(A1:B2) вернет значение 3, а не 4.
Анализ диаграмм в электронных таблицах
Диаграмма
это способ наглядного представления информации, заданный в
виде таблицы чисел.
Демонстрация данных с помощью хорошо продуманной диаграммы помогает лучше понять их и
часто может ускорить работу. В частности, диаграммы очень полезны для наглядного
представления той информации, которая содержится в больших наборах чи
сел, чтобы узнать, как
эти наборы связаны между собой. Быстро создав диаграмму, можно определить тенденции и
структуру процесса, что практически невозможно сделать, имея лишь набор чисел.
Диаграммы создаются на основе чисел, содержащихся в рабочем листе. О
бычно данные,
используемые в диаграммах, расположены в одном листе или в отдельном файле, но это вовсе не
обязательно. Одна диаграмма может использовать данные из любого количества листов и даже из
любого количества рабочих книг.
Табличный процессор
позвол
яет создавать самые различные
типы диаграмм:
Гистограмма
. Используется для отображения дискретных данных, которые являются
противоположностью непрерывным данным.
Линейчатая
. Представляет собой гистограмму, повернутую на 90° по часовой стрелке.
Преимущество
использования таких диаграмм состоит в том, что метки категорий читаются на
них проще.
График
. Часто применяются для отображения непрерывных данных. Например, при отображении
объема продаж в виде графика наглядно видно тенденцию их изменения со временем.
Круговая
. Диаграмму полезно использовать, если вы хотите показать пропорции или части чего
либо относительно целого. Обычно круговая диаграмма не применяется для более, чем 56 точек
данных, в противном случае ее трудно понять.
Точечная
. Известны под назван
ием диаграммы рассеивания. Отличаются от остальных типов
диаграмм тем, что по обеим осям такой диаграммы откладываются значения. Данный тип
диаграмм часто используют для того, чтобы показать взаимосвязь между двумя переменными.
С областями
. Диаграмма похож
а на раскрашенный различными цветами график. Стопки рядов
данных позволяют представить вклад каждого ряда данных в общую сумму.
Кольцевая
. Напоминают круговые диаграммы с вырезанной серединой. Отличие состоит в том,
что кольцевые диаграммы могут представля
ть не сколько рядов данных. Ряды данных
отображаются в виде концентрических колец. Кольцевые диаграммы нескольких рядов могут
потерять наглядность.
Лепестковая
. Имеет отдельную ось для каждой категории, причем все оси исходят от центра.
Значение точек данн
ых отмечается на соответствующей оси. Если в ряду данных все точки имеют
одинаковые значения, то лепестковая диаграмма принимает вид круга.
Поверхность
. Отображают два или несколько рядов данных в виде поверхности. В отличие от
остальных диаграмм, в этом с
лучае OpenOffice Calc применяет различные цвета для выделения
значений, а не рядов данных.
Биржевая
. Полезны для отображения информации о ценах на бирже. Для них требуется от 3 до 5
наборов данных.
Цилиндрическая, Коническая, Пирамидальная
. Такие диаграммы
можно использовать вместо
линейчатых диаграмм или гистограмм.
Количестве траекторий в направленном графе
(В9)
Если в город Т можно приехать только из городов X, Y, и Z, то число различных путей из города A
в город Т равно сумме числа различных путей
проезда из A в X, из A в Y и из A в Z, то
есть
, где
обозначает количество путей из вершины A в некоторую вершину i.
Если в графе дорог есть замкнутые пути
циклы, то количество различных путей бесконечно.
Задача о количестве траекторий на
схеме
дорог
ПРИМЕР
На рисунке
схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно
двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей
из города А в город К?

РЕШЕНИЕ
Если в город Т
можно приехать только из городов X, Y, и Z, то число различных путей из города A
в город Т равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то
есть
, где
обозначает количество путей из вершины A в некоторую вершину i.
Если в графе дорог есть замкнутые пути
циклы, то количество различных путей бесконечно.
Базы данных
Базой данных
является представленная в объективной форме совокупность самостоятельных
материалов (статей, расчетов, нормативных актов, судебных решений и
иных подобных
материалов), систематизированных таким образом, чтобы эти материалы могли быть найдены и
обработаны с помощью электронной вычислительной машины (ЭВМ) (Гражданский кодекс РФ, ст.
1260).
Общепризнанная единая формулировка понятия БД отсутствует
. Часто используются следующие
отличительные признаки:
БД хранится и обрабатывается в вычислительной системе.
Таким образом, любые внекомпьютерные хранилища информации (архивы, библиотеки,картотеки
и т. п.) базами данных не являются.
Данные в БД логически
структурированы (систематизированы) с целью обеспечения возможности
их эффективного поиска и обработки в вычислительной системе.
Структурированность подразумевает явное выделение составных частей (элементов), связей
между ними, а также типизацию элементов
и связей, при которой с типом элемента (связи)
соотносится определённая семантика и допустимые операции.
БД включает метаданные, описывающие логическую структуру БД в формальном виде (в
соответствии с некоторой метамоделью).
В соответствии с ГОСТ Р ИСО МЭК
ТО 10032
2007, «постоянные данные в среде базы данных
включают в себя схему и базу данных. Схема включает в себя описания содержания, структуры и
ограничений целостности, используемые для создания и поддержки базы данных. База данных
включает в себя набор
постоянных данных, определенных с помощью схемы. Система управления
данными использует определения данных в схеме для обеспечения доступа и управления
доступом к данным в базе данных».
Из перечисленных признаков только первый является строгим, а другие до
пускает различные
трактовки и различные степени оценки. Можно лишь установить некоторую степень соответствия
требованиям к БД.
В такой ситуации не последнюю роль играет общепринятая практика. В соответствии с ней,
например, не называют базами данных файлов
ые архивы, Интернет
порталы илиэлектронные
таблицы, несмотря на то, что они в некоторой степени обладают признаками БД. Принято считать,
что эта степень в большинстве случаев недостаточна (хотя могут быть исключения).
Распространенная ошибка
некорректное
использование термина «база данных» вместо термина
«система управления базами данных». Эти понятия необходимо различать!
Классификация БД
по модели данных:
иерархические,
сетевые,
реляционные,
объектные,
объектно
ориентированные,
объектно
реляционные.
Система управления базами данных (СУБД)
совокупность программных и лингвистических
средств общего или специального назначения, обеспечивающих управление созданием и
использованием баз данных.
Реляционные базы данных
Реляционная СУБД (РСУБД)
СУБД, управ
ляющая реляционными базами данных.
Понятие
реляционный
(англ. relation
отношение) связано с разработками известного
английского специалиста в области систем баз данных
Эдгара Кодда
(Edgar Codd).
Эти модели характеризуются простотой структуры данных,
удобным для пользователя табличным
представлением и возможностью использования формального аппарата алгебры отношений и
реляционного исчисления для обработки данных.
Реляционная модель ориентирована на организацию данных в виде
двумерных таблиц
. Каждая
яционная таблица представляет собой двумерный массив и обладает следующими
свойствами:
каждый элемент таблицы
один элемент данных
все ячейки в столбце таблицы однородные, то есть все элементы в столбце имеют одинаковый
тип (числовой, символьный и т. д.)
каждый столбец имеет уникальное имя
одинаковые строки в таблице отсутствуют
порядок следования строк и столбцов может быть произвольным
Базовыми понятиями
реляционных СУБД являются:
атрибут
отношение
кортеж
Отношение
фундаментальное понятие реляционной
модели данных. По этой причине модель
и называется реляционной (от английского relation
отношение).
Отношение имеет простую графическую интерпретацию, оно может быть представлено в виде
таблицы, столбцы (поля, атрибуты) которой соответствуют вхождениям д
оменов в отношение, а
строки (записи)
наборам из n значений, взятых из исходных доменов. Число строк (кортежей) n,
называют
кардинальным числом
отношения (
кардинальностью
),или
мощностью
отношения.
Такая таблица обладает рядом свойств:
В таблице нет двух о
динаковых строк.
Таблица имеет столбцы, соответствующие атрибутам отношения.
Каждый атрибут в отношении имеет уникальное имя.
Порядок строк в таблице произвольный.
Под
атрибутом
здесь понимается вхождение домена в отношение. Строки отношения
называются
кортежами
Далее следует формализованное определение введённых понятий.
Заголовок Hr (или схема) отношения r
конечное множество упорядоченных пар вида , где
A называется именем атрибута, а T обозначает имя некоторого базового типа или ранее
определенного домена, то есть множества допустимых значений. По определению требуется,
чтобы все имена атрибутов в заголовке отношения были различны.
Кортеж tr, соответствующий заголовку Hr
множество упорядоченных триплетов вида ,
по одному тако
му триплету для каждого атрибута в Hr. Третий элемент
триплета
должен являться допустимым значением типа данных или домена T. Замечание: так как имена
атрибутов уникальны, то указание домена в кортеже излишне.
Тело Br отношения
неупорядоч
енное множество различных кортежей tr.
Значением Vr отношения r называется пара множеств Hr и Br.
Полезно также понятие
первичного ключа
это такой набор атрибутов, который однозначно
определяет кортеж и минимален среди всех своих подмножеств (то есть нел
ьзя убрать ни один из
атрибутов). При добавлении новых записей первичный ключ обязан оставаться первичным ключом
(например, неверным будет использование в качестве первичного ключа набора Имя + Отчество +
Фамилия сотрудника, даже если на момент создания та
блицы полных тёзок среди заносимых в
неё людей не было).
НОРМАЛИЗАЦИЯ РЕЛЯЦИОННОЙ БД
Нормальная форма
свойство отношения в реляционной модели данных, характеризующее его
с точки зрения избыточности, которая потенциально может привести к логически
ошибочным
результатам выборки или изменения данных.
Нормальная форма определяется как совокупность требований, которым должно удовлетворять
отношение. Процесс преобразования отношений базы данных к виду, отвечающему нормальным
формам, называется нормализац
ией.
Нормализация предназначена для приведения структуры базы данных к виду, обеспечивающему
минимальную логическую избыточность, и не имеет целью уменьшение или увеличение
производительности работы или же уменьшение или увеличение физического объёма БД.
онечной целью нормализации является уменьшение потенциальной противоречивости хранимой
в БД информации. Общее назначение процесса нормализации заключается в следующем:
исключение некоторых типов избыточности;
устранение некоторых аномалий обновления;
разра
ботка проекта базы данных, который является достаточно «качественным» представлением
реального мира, интуитивно понятен и может служить хорошей основой для последующего
расширения;
упрощение процедуры применения необходимых ограничений целостности.
Устране
ние избыточности производится, как правило, за счёт декомпозиции отношений таким
образом, чтобы в каждом отношении хранились только первичные факты (то есть факты, не
выводимые из других хранимых фактов).
При том, что идеи нормализации весьма полезны для п
роектирования баз данных, они отнюдь не
являются универсальным или исчерпывающим средством повышения качества БД. Это связано с
тем, что существует слишком большое разнообразие возможных ошибок и недостатков в
структуре БД, которые нормализацией не устраня
ются.
Несмотря на эти рассуждения, теория нормализации является очень ценным достижением
реляционной теории и практики, поскольку она даёт научно строгие и обоснованные критерии
качества проекта БД и формальные методы для усовершенстования этого качества.
Этим теория
нормализации резко выделяется на фоне чисто эмпирических подходов к проектированию,
которые предлагаются в других моделях данных.
Более того, можно утверждать, что во всей сфере информационных технологий практически
отсутствуют методы оценки и
улучшения проектных решений, сопоставимые с теорией
нормализации реляционных баз данных по уровню формальной строгости.
ПЕРВАЯ НОРМАЛЬНАЯ ФО
РМА (1NF)
Отношение находится в первой нормальной форме (1НФ) тогда и только тогда, когда в любом
допустимом
значении отношения каждый его кортеж содержит только одно значение для каждого
из атрибутов.
В реляционной модели отношение всегда находится в первой нормальной форме по определению
понятия отношение. Что же касается различных таблиц, то они могут не быть
правильными
представлениями отношений и, соответственно, могут не находиться в 1НФ.
ВТОРАЯ НОРМАЛЬНАЯ ФО
РМА (2NF)
Отношение находится во второй нормальной форме, если оно находится в первой нормальной
форме, и при этом любой его атрибут, не входящий в сост
ав потенциального ключа,
функционально полно зависит от каждого потенциального ключа.
Функционально полная зависимость означает, что атрибут функционально зависит от всего
составного потенциального ключа, но при этом не находится в функциональной зависимос
ти от
какой
либо из входящих в него частей. Или другими словами: в 2NF нет неключевых атрибутов,
зависящих от части составного потенциального ключа.
Второе важное значение второй нормальной формы состоит в том, что она по определению
запрещает наличие некл
ючевых атрибутов, которые вообще не зависят от потенциального ключа.
Таким образом, 2NF запрещает создавать отношения как несвязанные (хаотические, случайные)
наборы атрибутов.
ТРЕТЬЯ НОРМАЛЬНАЯ ФО
РМА (3NF)
Отношение находится в 3NF тогда и только тогда, к
огда выполняются следующие условия:
Отношение находится во второй нормальной форме;
Каждый неключевой атрибут отношения находится в нетранзитивной (то есть прямой)
зависимости от потенциального ключа.
Таким образом, отношение находится в 3NF тогда и только
тогда, когда оно находится во 2NF и
отсутствуют транзитивные зависимости неключевых атрибутов от ключевых. Транзитивной
зависимостью неключевых атрибутов от ключевых называется следующая: {A} → {B} и {B} → {C},
где {A}
потенциальный ключ, {B} и {С}
зличные множества неключевых атрибутов.
СУБД
Основные
функции
СУБД:
управление данными во внешней памяти (на дисках);
управление данными в оперативной памяти с использованием дискового кэша;
журнализация изменений, резервное копирование и восстановление
базы данных после сбоев;
поддержка языков БД (язык определения данных, язык манипулирования данными).
Обычно современная СУБД содержит следующие
компоненты
ядро, которое отвечает за управление данными во внешней и оперативной памяти,
ижурнализацию,
процес
сор языка базы данных, обеспечивающий оптимизацию запросов на извлечение и
изменение данных и создание, как правило, машинно
независимого исполняемого внутреннего
кода,
подсистему поддержки времени исполнения, которая интерпретирует программы манипуляции
анными, создающие пользовательский интерфейс с СУБД
а также сервисные программы (внешние утилиты), обеспечивающие ряд дополнительных
возможностей по обслуживанию информационной системы.
Используемые в настоящее время:
MySQL
Oracle
PostgreSQL
SQLite
Firebird
DB2
Microsoft Access
Microsoft SQL Server
Разбор задачи на реляционные БД про
родственников
Во фрагменте базы данных представлены сведения о родственных отношениях. Определите на
основании приведенных данных фамилию и инициалы бабушки Лобановой
А.И.
Таблица 1
Фамилия_И.О.
Пол
Лобанов Т.М.
Макаревич И.Т.
Белых У.В.
Макаревич А.И.
Лобанова А.И.
Макаревич В.В.
Белых А.Н.
Рабинович Н.Т.
Рабинович Н.А.
Таблица 2
ID_Родителя
ID_Ребенка
Белых У.В.
Лобанов Т.М.
Рабинович Н.Т.
Макаревич В.В.
РЕШЕНИЕ
Ответ 2 заведомо неверен, т.к. лицо мужского пола не может быть бабушкой.
По первой таблице определяем идентификатор Лобановой А.И.
Далее чтобы найти родителей работаем со второй таблицей: ищем записи, где код ребенка равен

Итак, родители имеют коды 58 и 31
Теперь во второй таблице ищем бабушек и дедушек, где идентификатор ребенка равен 58 или 31.
Потенциально их может быть че
тыре, но в таблице находятся только два соответствующих
индентификатора
это 82 и 95.
Расшифровываем чьи это ID по первой таблице: Белых А.Н. (мужского пола) и Рабинович Т.Н
(женского пола); последняя и является искомой бабушкой.
Ответ:
Операционная сис
тема
Операционная система
, сокр. ОС (англ. operating system, OS)
комплекс управляющих и
обрабатывающих программ, которые, с одной стороны, выступают как интерфейс между
устройствами вычислительной системы и прикладными программами, а с другой стороны
редназначены для управления устройствами, управления вычислительными процессами,
эффективного распределения вычислительных ресурсов между вычислительными процессами и
организации надёжных вычислений. Это определение применимо к большинству современных
опер
ационных систем общего назначения.
В большинстве вычислительных систем операционная система является основной, наиболее
важной (а иногда и единственной) частью системного программного обеспечения. С 1990
х годов
наиболее распространёнными операционными сис
темами являются системы семейства
Windows
системы класса
UNIX
(особенно Linux и Mac OS). С 2000
х большое распространение получили
мобильные компьютеры (смартфоны и планшеты) и с ними ОС Android и iOS.
ОС является необходимой составляющей ПО ПК, без нее
компьютер не может работать в
принципе.
ОС выполняет базовые функции:
управляет файловой системой (просмотр, удаление, копирование, перемещение,
переименование);
запуск и завершение прикладных программ;
всевозможный сервис (информация о параметрах, их
настройка, оптимизация работы и тд)
Разработчикам прикладных программ ОС позволяет не думать о деталях реализации и
функционирования устройств, предоставляя минимально необходимый набор функций по работе
с ним.

Разработчикам прикладных программ ОС позв
оляет не думать о деталях реализации и
функционирования устройств, предоставляя минимально необходимый набор функций по работе с
ним.
Основные функции
ОС:
Выполнение по запросу программ тех достаточно элементарных (низкоуровневых) действий,
которые
являются общими для большинства программ и часто встречаются почти во всех
программах (ввод и вывод данных, запуск и остановка других программ, выделение и
освобождение дополнительной памяти и др.).
Загрузка программ в оперативную память и их выполнение.
тандартизованный доступ к периферийным устройствам (устройства ввода
вывода).
Управление оперативной памятью (распределение между процессами, организация виртуальной
памяти).
Управление доступом к данным на энергонезависимых носителях (таких как жёсткий ди
ск,
оптические диски и др.), организованным в той или иной файловой системе.
Обеспечение пользовательского интерфейса.
Сетевые операции, поддержка стека сетевых протоколов.
Дополнительные функции
Параллельное или псевдопараллельное выполнение задач
(многозадачность).
Эффективное распределение ресурсов вычислительной системы между процессами.
Разграничение доступа различных процессов к ресурсам.
Организация надёжных вычислений (невозможности одного вычислительного процесса
намеренно или по ошибке повл
иять на вычисления в другом процессе), основана на
разграничении доступа к ресурсам.
Взаимодействие между процессами: обмен данными, взаимная синхронизация.
Защита самой системы, а также пользовательских данных и программ от действий пользователей
(злонаме
ренных или по незнанию) или приложений.
Многопользовательский режим работы и разграничение прав доступа.
центральная часть операционной системы, управляющая выполнением процессов,
ресурсами вычислительной системы и предоставляющая процессам координи
рованный доступ к
этим ресурсам. Основными ресурсами являются процессорное время, память и устройства ввода
вывода. Доступ к файловой системе и сетевое взаимодействие также могут быть реализованы на
уровне ядра.
В СОСТАВ ОС НЕПРЕМЕН
НО ВХОДЯТ:
Программный
модуль
, управляющий файловой системой: процесс работы компьютера в
сводится к обмену файлами между устройствами
Командный процессор
специальная программа, которая запрашивает у пользователя
команды и выполняет их. Пользователь может дать команду запуска
программы, выполнения
какой
либо операции над файлами (копирование, удаление, переименование), вывода документа
на печать и так далее. Операционная система должна эту команду выполнить
Драйверы
программы, которые управляют работой устройств. Каждому устр
ойству
соответствует свой драйвер. Технология «Plug and Play» (подключи и играй) позволяет
автоматизировать подключение новых устройств. В процессе установки Windows определяет тип
и конкретную модель установленного устройства и подключает необходимый для
его
функционирования драйвер. При включении компьютера произво
дится загрузка драйверов в
оперативную память. Пользователь имеет возможность вручную установить или переустановить
драйверы.
Программные модули
графического интерфейса
программы, позволяющие
пользователю
вводить команды с помощью мыши.
Графический интерфейс пользователя (ГИП, ГПИ)
разновидность пользовательского
интерфейса, в котором элементы интерфейса (меню, кнопки, значки, списки и т. п.),
представленные пользователю на дисплее, исполнен
ы в виде графических изображений.
В отличие от интерфейса командной строки, в ГПИ пользователь имеет произвольный доступ (с
помощью устройств ввода
клавиатуры, мыши, джойстика и т. п.) ко всем видимым экранным
объектам (элементам интерфейса) и
осуществляет непосредственное манипулирование ими.
Чаще всего элементы интерфейса в ГИ реализованы на основе метафор и отображают их
назначение и свойства, что облегчает понимание и освоение программ неподготовленными
пользователями.
Одним из требований к
хорошему графическому интерфейсу программной системы является
концепция
«делай то, что я имею в виду»
или DWIM (англ. Do What I Mean). DWIM требует, чтобы
система работала предсказуемо, чтобы пользователь заранее интуитивно понимал, какое
действие выполнит
программа после получения его команды.
Утилиты
сервисные программы для обслуживания дисков (проверять, сжимать,
дефрагментировать и тд), выполнения операций с файлами (архивировать, копировать и тд), и
работы в компьютерных сетях
Справочная система
получение информации о функционировании ОС в целом и о работе её
отдельных модулей
Файлы ОС
хранятся во внешней, долговременной памяти (на жестком, гибком или лазерном
диске). Но программы могут выполняться, только если они находятся в оперативной памяти,
поэтому файлы ОС необходимо загрузить в оперативную память.
ЗАГРУЗКА ОС:
Диск
(жесткий, гибкий или лазерный), на котором находятся файлы операционной системы и с
которого производится ее загрузка, называется
системным
После включения ПК производится
загрузка ОС с системного диска в
оперативную память
.
Загрузка должна выполняться в соответствии с программой загрузки. Однако для того чтобы
компьютер выполнял какую
нибудь программу, эта программа должна уже находиться в
оперативной памяти. Разрешение это
го противоречия состоит в последовательной, поэтапной
загрузке операционной системы.
В ПЗУ содержатся программы тестирования ПК и первого этапа загрузки ОС
это
BIOS
(Basic
Input/Output System
базовая система ввода/вывода).
После включения питания
роцессор
начинает выполнение программы самотестирования
компьютера POST (Power
ON Self Test). Производится тестирование работоспособности
процессора, памяти и других аппаратных средств компьютера
После проведения самотестирования специальная программа в BI
OS, начинает поиск загрузчика
ОС. Происходит поочередное обращение к имеющимся дискам и поиск на определенном месте (в
первом загрузочном секторе диска) наличия специальной программы
Master Boot
(программы
загрузчика ОС).
Master Boot загружается в ОС и е
й передается управление работой компьютера. Программа
ищет файлы операционной системы на системном диске и загружает их в оперативную память в
качестве программных модулей
Инсталляция программ
процедура установки большинства программных продуктов, при
которой
используется специальная дистрибутивная копия.
Копирование программного продукта на жесткий диск называется установкой. Файл с программой
имеет расширение .EXE .COM .BAT Он работает автономно или в сопровождении служебных
файлов. Запустить программ
значит начать её работу. Но данный программный продукт должен
быть совместим с аппаратными средствами
Итак, ОС выполняет две группы функций
предоставление пользователю или программисту вместо реальной аппаратуры компьютера
расширенной виртуальной
машины, с которой удобней работать и которую легче
программировать;
повышение эффективности использования компьютера путем рационального управления его
ресурсами в соответствии с некоторым критерием.
Если говорить подробнее, то в функции ОС будут включены:
Управление процессами
Управление памятью
Управление файлами и внешними устройствами
Защита данных и администрирование
Интерфейс прикладного программирования
Пользовательский интерфейс
и т.д.
Если говорить о пользовательском интерфейсе, то операционная сис
тема должна обеспечивать
удобный интерфейс не только для прикладных программ, но и для человека, работающего за
терминалом.
В ранних операционных системах пакетного режима функции пользовательского интерфейса были
сведены к минимуму и не требовали наличия
терминала. Команды языка управления заданиями
набивались на перфокарты, а результаты выводились на печатающее устройство.
Современные ОС поддерживают развитые функции пользовательского интерфейса для
интерактивной работы за терминалами двух типов: алфавитн
цифровыми и графическими.
При работе за алфавитно
цифровым терминалом пользователь имеет в своем распоряжении
систему команд, мощность который отражает функциональные возможности данной ОС. Обычно
командный язык ОС позволяет запускать и останавливать при
ложения, выполнять различные
операции с файлами и каталогами, получать информацию о состоянии ОС (количество
работающих процессов, объем свободного пространства на дисках и т. п.), администрировать
систему. Команды могут вводиться не только в интерактивном
режиме с терминала, но и
считываться из так называемого командного файла, содержащего некоторую последовательность
команд.
Программный модуль ОС, ответственный за чтение отдельных команд или же последовательности
команд из командного файла, иногда называю
т командным интерпретатором.
Ввод команды может быть упрощен, если операционная система поддерживает графический
пользовательский интерфейс. В этом случае пользователь для выполнения нужного действия с
помощью мыши выбирает на экране нужный пункт меню или
графический символ.
Файловые системы
Файловая система
порядок, определяющий способ организации, хранения и именования
данных на носителях информации. Она определяет формат содержимого и физического хранения
информации, которую принято группировать в виде
файлов. Конкретная файловая система
определяет размер имени файла (папки), максимальный возможный размер файла и раздела,
набор атрибутов файла. Некоторые файловые системы предоставляют сервисные возможности,
например, разграничение доступа или шифрование
файлов.
Древесная логическая структура файлов часто состоит из набора файловых систем,
состыкованных или «смонтированных» друг с другом. В результате этого монтирования возникает
виртуальная файловая система, т.е. новый уровень абстракции поверх конкретно
й реализации
файловой системы. Достигается единообразный доступ клиентским приложениям к различным
типам файловых систем. Она может быть использована для устранения различий между
файловыми системами Windows, Mac OS и Unix так, что приложения могут получит
ь доступ к
файлам на локальных файловых системах, не зная тип файловой системы, к которой они
получают доступ.
Задачи на файловые системы
ПРИМЕР 1
Определите, какое из указанных имен файлов удовлетворяет маске:
?hel*lo.c*
hello.c
hello.cpp
hhelolo.cpp
hhelolo.c
ПРИМЕР 2
Перемещаясь из одного каталога в другой, пользователь последовательно посетил каталоги
DOC
USER
SCHOOL
A:
LETTER
INBOX
. При каждом перемещении пользователь либо
спускался в каталог на уровень ниже, либо поднимался на уровень выше.
Каково полное имя
каталога, из которого начал перемещение пользователь?
DOC

A:
\
SCHOOL
USER
DOC
DOC
USER
SCHOOL
ПРИМЕР 3
Каталог содержит файлы с именами
а)
q.c
qq.cpp
qq.c
г)
q1.c1
д)
qaa.cmd
е)
q12.cpp
Определите, в каком порядке будут показаны файлы, если выбрана сортировка по типу (по
возрастанию).
авгдбе
авгдеб
абвгде
авдбег
ПРИМЕР 4
Для групповых операций с файлами используются маски имен файлов. Маска представляет собой
последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также
могут встречаться следующие символы: Символ «?» (вопросительный знак) означает ровно один
произвольный символ. Символ «*» (звездочка) означает любую последовательно
сть символов
произвольной длины, в том числе «*» может задавать и пустую последовательность. Определите,
по какой из масок будет выбрана указанная группа файлов:

1234.xls
23.xml
234.xls
23.xml
*23*.?x*
?23?.x??
?23?.x*
*23*.???
Командная строка
Windows
Cmd.exe
интерпретатор командной строки для операционных систем OS/2, Windows CE и для
семейства операционных систем, базирующихся на Windows NT: Windows 2000, Windows XP,
Windows Vista, Windows 7, Windows Server 2003 и Windows Server 2008.
Cmd.exe является
аналогом
COMMAND
COM
, которая использовалась в MS
DOS
, Windows 95 и Windows 98.
Командная строка
(или
«консоль»
это текстовый интерфейс между человеком и компьютером,
в котором инструкции компьютеру даются путём ввода с клавиатуры тексто
вых строк (команд).
Интерфейс командной строки противопоставляется управлению программами на основе меню, а
также различным реализациям графического интерфейса.
Вызвать командную строку можно набрав в меню, появляющемуся по нажатию Win
r, команду cmd,
и на
жав Enter.
HELP!
Про остальные команды можно узнать прямо в командной строке при помощи команды help:
�help dir


�help cd
CD
ПЕРЕНАПРАВЛЕНИЕ ВЫВО
Перенаправление вывода консольной программы в файл осуществляется при помощи символа >.
WINDOWS
��Debugdir dir_output.txt
WINDOWS
�Debugtype dir_output.txt
8381
WINDOWS
Debug

07:20
IR0;DIR
.


07:20
IR0;DIR
..

23:15
572 blastcln.log

07:20
0

dir_output.txt

22:20
6 826 mrt.log

00:02
2 328 mrteng.log

13:01

10:36
0 PASSWD.LOG

01:07
IR0;DIR

23:26
IR0;DIR
UserMode
Интересные программы командной строки
SHUTDOWN.EXE
Windows Remote Shutdown Tool
. Позволяет выключать или перезапускать
локальный или
удаленный компьютер. Использование без параметров команды shutdown приведет к выходу из
системы текущего пользователя.
PING.EXE
TCP/IP Ping Command
. С помощью отправки сообщений с эхо
запросом по
протоколу
ICMP
проверяет соединруение на уровн
е протокола IP с другим компьютером,
поддерживающим
TCP
/IP. После каждой передачи выводится соответствующее сообщение с эхо
ответом. Ping
это основная
TCP
/IP
команда, используемая для устранения неполадки в
соединении, проверки возможности доступа и разр
ешения имен. Команда ping, запущенная без
параметров, выводит справку.
TRACERT.EXE
TCP/IP Traceroute Command
. Определяет путь до точки назначения с помощью посылки в точку
назначения эхо
сообщений протокола Control Message Protocol (
ICMP
) с постоянным увел
ичением
значений срока жизни (Time to Live,
). Выведенный путь
это список ближайших интерфейсов
маршрутизаторов, находящихся на пути между узлом источника и точкой назначения. Ближний
интерфейс представляют собой интерфейс маршрутизатора, который явля
ется ближайшим к узлу
отправителя на пути. Запущенная без параметров, команда tracert выводит справку.
IPCONFIG.EXE
IP Configuration Utility
. Утилита командной строки Ipconfig служит для отображения всех текущих
параметров сети
TCP
/IP и обновления параметр
DHCP
DNS
. При вызове команды ipconfig без
параметров выводится только IP
адрес, маска подсети и основной шлюз для каждого сетевого
адаптера.
TCP/IP Netstat Command.
Отображение активных подключений
TCP
, портов, прослушиваемых
компьютером,
статистики Ethernet, таблицы маршрутизации IP, статистики IPv4 (для протоколов
IP,
ICMP
TCP
UDP
) и IPv6 (для протоколов IPv6, ICMPv6,
TCP
через IPv6 и
UDP
через IPv6).
Запущенная без параметров, команда nbtstat отображает подключения
TCP
NSLOOKUP.EXE
едоставляет сведения, предназначенные для диагностики инфраструктуры
DNS
. Для
использования этого средства необходимо быть знакомым с принципами работы системы
DNS
sfc.exe
System File Checker
. Сканирует и проверяет версии всех защищенных системных файлов
после
перезапуска компьютера. Для выполнения команды sfc необходимо войти в систему в качестве
члена группы администраторов. Если программа sfc находит, что защищенный файл был
переопределен, подходящая версия файла восстанавливается из
папки
системный_кор
невой_каталог
system32
dllcache, а затем заменяет неправильный файл.
Открытие командной строки в Windows 8
Командная строка включена в Windows
8 и Windows
RT, хотя по умолчанию она не отображается
на начальном экране. Можно добавить командную строку на
начальный экран, чтобы открывать ее
быстрее.
Открытие командной строки
Быстро проведите пальцем от правой границы экрана и затем коснитесь элемента Поиск.
(Если вы используете мышь, переместите указатель в верхний правый угол экрана, затем вниз и
щелкните
Поиск.)
Введите командная строка в поле поиска, щелкните или коснитесь вначале Приложения, а затем
Командная строка.
При использовании мыши можно также открыть командную строку, наведя указатель на левый
нижний угол, щелкнув правой кнопкой мыши изображение
для предварительного просмотра и
выбрав пункт “Командная строка” или “Командная строка (администратор)”.
адресация
Интернет состоит из многих тысяч корпоративных, научных, правительственных и домашних
компьютерных сетей. Объединение сетей разной архите
ктуры и топологии стало возможно
благодаря протоколу
IP
(англ.
Internet Protocol
) и принципу маршрутизации пакетов данных.
Протокол IP был специально создан агностическим в отношении физических каналов связи. То
есть любая система (сеть) передачи цифровых
данных, проводная или беспроводная, для которой
существует стандарт инкапсуляции в неё IP
пакетов, может передавать и трафик Интернета.
Агностицизм протокола IP, в частности, означает, что компьютер или маршрутизатор должен знать
тип сетей, к которым он не
посредственно присоединён, и уметь работать с этими сетями; но не
обязан (и в большинстве случаев не может) знать, какие сети находятся за маршрутизаторами.
На стыках сетей специальные маршрутизаторы (программные или аппаратные) занимаются
автоматической с
ортировкой и перенаправлением пакетов данных, исходя из IP
адресов
получателей этих пакетов. Протокол IP образует единое адресное пространство в масштабах
всего мира, но в каждой отдельной сети может существовать и собственное адресное
подпространство, кот
орое выбирается исходя из класса сети. Такая организация IP
адресов
позволяет маршрутизаторам однозначно определять дальнейшее направление для каждого
пакета данных. В результате между отдельными сетями Интернета не возникает конфликтов, и
данные беспрепят
ственно и точно передаются из сети в сеть по всей планете и ближнему космосу.
Internet Protocol или IP (англ. internet protocol
межсетевой протокол)
маршрутизируемый
сетевой протокол, являющийся протоколом сетевого уровня семейства
TCP/IP
Протокол IP
используется для негарантированной доставки данных, разделяемых на так
называемые пакеты от одного узла сети к другому. Это означает, что на уровне этого протокола
(третий уровень сетевой модели OSI) не даётся гарантий надёжной доставки пакета до адресата.
В частности, пакеты могут прийти не в том порядке, в котором были отправлены,
продублироваться (когда приходят две копии одного пакета; в реальности это бывает крайне
редко), оказаться повреждёнными (обычно повреждённые пакеты уничтожаются) или не прибыть
вовсе. Гарантию безошибочной доставки пакетов дают протоколы более высокого (транспортного
уровня) сетевой модели OSI
например, TCP
которые используют IP в качестве транспорта.
Задача по адресации в Интернете
ПРИМЕР 1
Петя записал IP
адрес школьного
сервера на листке бумаги и положил его в карман куртки. Петина
мама случайно постирала куртку вместе с запиской. После стирки Петя обнаружил в кармане
четыре обрывка с фрагментами IP
адреса. Эти фрагменты обозначены буквами А, Б, В и Г.
Восстановите IP
адр
ес. В ответе укажите последовательность букв, обозначающих фрагменты, в
порядке, соответствующем IP
адресу.
ПРИМЕР 2
com
.edu
.net
htm
ftp
Доступ к файлу htm.net, находящемуся на сервере com.edu, осуществляется по протоколу
ftp. В
таблице фрагменты адреса файла закодированы буквами от А до Ж. Запишите
последовательность этих букв, кодирующую адрес указанного файла в сети Интернет.
Маска локальной сети
В терминологии сетей TCP/IP маской сети называют 32
разрядное двоичное числ
о, которое
определяет, какая часть IP
адреса
узла сети относится к адресу сети, а какая
к адресу узла в
этой сети.
В маске подсети старшие биты, отведенные в IP
адресе компьютера для адреса сети, имеют
значение 1; младшие биты, отведенные в IP
адресе ко
мпьютера для адреса компьютера в
подсети, имеют значение 0. Например, маска подсети может иметь вид:
11111111 11111111 11100000 00000000 (255.255.224.0)
Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу
сети и его
маске.
Это значит, что 19 старших бит в IP
адресе содержит адрес сети, оставшиеся 13 младших бит
содержат адрес компьютера в сети.
Маски обычно записываются в виде четверки десятичных чисел
по тем же правилам, что и IP
адреса.
ПРИМЕР 3
По заданным IP
адр
есу узла сети и маске определите адрес сети:
IP
адрес: 10.8.248.131
Маска: 255.255.224.0
При записи ответа выберите из приведенных в таблице чисел 4 фрагмента четыре элемента IP
адреса и запишите в нужном порядке соответствующие им буквы без точек.
ПРИМЕР 4
Если маска подсети 255.255.255.240 и IP
адрес компьютера в сети 58.68.0.44, то порядковый
номер компьютера в сети равен _____?
ПРИМЕР 5
Если маска подсети 255.255.240.0 и IP
адрес компьютера в сети
162.198.75.44, то порядковый
номер компьютера в сети равен _____ ?
ПРИМЕР 6
Для некоторой подсети используется маска 255.255.252.0. Сколько различных адресов
компьютеров допускает эта маска?
Примечание.
На практике два из возможных адресов не используются
для адресации узлов сети:
адрес сети, в котором все биты, отсекаемые маской, равны 0, и широковещательный адрес, в
котором все эти биты равны 1.
ПРИМЕР 7
Для узла с IP
адресом 224.128.112.142 адрес сети равен 224.128.64.0. Чему равен третий слева
байт маск
и? Ответ запишите в виде десятичного числа.
ПРИМЕР 8
Для узла с IP
адресом 158.198.228.220 адрес сети равен 158.198.128.0. Чему равен третий слева
байт маски? Ответ запишите в виде десятичного числа.
ПРИМЕР 9
Для узла с IP
адресом 153.209.23.240 адрес сети
равен 153.209.20.0. Чему равен третий слева
байт маски? Ответ запишите в виде десятичного числа.
ПРИМЕР 10
Для узла с IP
адресом 248.228.120.242 адрес сети равен 248.228.112.0. Чему равен третий слева
байт маски? Ответ запишите в виде десятичного числа.
рафические исполнители системы КУМИР
Все исполнители системы КУМИР допускают как программируемое поведение, так и работу в
интерактивном режиме при помощи пульта.
Простейшую программу можно составить, выполнив задание при помощи пульта, а затем
переписав в
виде последовательности действий протокол выполненных команд.
Исполнитель Кузнечик
Кузнечик действует на вещественной прямой и может находиться в любой ее точке с целым
значением. Начальное местоположение
точка, соответствующая числу ноль.
Кузнечик
понимает следующие команды:
вперед
(цел расстояние),
назад
(цел
расстояние),
перекрасить
. Расстояние должно соответствовать возможной длине прыжка
кузнечика, установленной в текущем задании.
Задание состоит в закрашивании клеток, помеченных флажком.
Исполн
итель Водолей
Даны три стакана, объем каждого стакана
целое число (Стакан С может иметь размер 0. В этом
случае он не показывается).
У игрока есть следующие возможности:
1. долить нужный стакан доверху ("из крана");
2. вылить всю воду из указанного стака
на (при этом стакан становится пустым);
3. перелить воду из одного стакана в другой (если удается перелить всю воду, то первый стакан
становится пустым; в противном случае второй стакан становится полным, а остаток остается в
первом стакане.
Пример. Стакан
A имеет объем 10 литров, стакан B имеет объем 6 литров; в стакане А находится
7 литров воды, а в стакане B
2 литра. Если перелить воду из стакана B в стакан А, то в стакане
А станет 8 литров, а в стакане B
ничего. Если перелить воду из стакана А в ста
кан B, то в стакане
А станет 3 литра, а в стакане B
6 литров (стакан будет наполнен доверху).
Цель игры
получить в каком
либо из стаканов указанное количество воды (начальное
количество воды в каждом стакане также задано). Таким образом, задание игры В
одолей состоит
из семи целых чисел:
1. объемы каждого из стаканов (три числа);
2. начальное количество воды в каждом из стаканов (три числа);
3. требуемое количество воды (одно число).
В окне Водолея под каждым стаканом показан его объем, бирки справа от к
аждого стакана
показывают текущий объем воды в нем. В окошке вверху окна (на темно
синем фоне) показано
количество воды, которое нужно получить, это же количество отмечено зеленой полоской на
каждом из стаканов. Работа с Водолеем через пульт понятна интуит
ивно.
При программировании Водолея доступны следующие команды:
наполни А, наполни B, наполни
C, вылей А, вылей B, вылей C, перелей из A в B, перелей из A в C, перелей из B в A,
перелей из B в C, перелей из C в A, перелей из C в B
Исполнитель Черепаха
Испо
лнитель Черепашка знаком большинству школьников и заслуженно любим. Цель Черепашки
создать рисунок на арене. У Черепашки есть возможность поворачиваться налево и направо на
заданное количество градусов, перемещаться вперед и назад, поднимать и опускать х
вост.
Опущенный хвост оставляет за собой след.
Размер стороны арены
500 пикселей. Единица перемещения черепахи соответствует одному
пикселю. При запуске исполнителя арена пуста. Черепаха находится в центре, хвост опущен. Тело
черепахи можно скрыть кликну
в по полю.
Черепаха понимает следующие команды:
поднять хвост, опустить хвост, влево (вещ), вправо
(вещ), вперед (вещ), назад (вещ)
Исполнитель Чертежник
Чертежник действует на координатной плоскости и предназначен для построения рисунков,
чертежей и граф
иков.
Команды управления "чертежником"
поднять перо
опустить перо
сместиться в точку (арг
вещ х,у)
сместиться на вектор (арг вещ х,у).
В команде сместиться в точку в качестве (х,у) выступают абсолютные значения координат, а
сместиться на вектор
значения приращений по соответствующим осям;
При перемещении опущенного пера за ним остается след
отрезок от старого положения пера до
нового, а при перемещении с поднятым пером следа не остается).
Также есть одна команда обратной связи
перо опущено
сполнитель Робот
Робот действует на поле ограниченного размера со стенками в заданных местах.
Команды управления "роботом"
вверх
вниз
вправо
влево
закрасить
(штриховка той
клетки, где находиться исполнитель в момент применения данной команды). По
командам
перемещения исполнитель перемещается на одну клетку в заданном направлении, но если
мешает стена, то "робот" не может пройти)
Также есть 8 команд обратной связи (по две на каждое направление)
либо свободно, либо
стена. Например,
справа свободно
или
справа стена
Задания для Робота наиболее интересны, отличаются большим разнообразием, позволяют
исполнителю интерактивно реагировать на ситуацию на поле.
Динамическое программирование в задачах
ЕГЭ
ПРИМЕР
У исполнителя Утроитель две команды, которым
присвоены номера:
1. прибавь 1
2. умножь на 3
Первая из них увеличивает число на экране на 1, вторая
утраивает его. Программа для
Утроителя
это последовательность команд. Сколько есть программ, которые число 1
преобразуют в число 20? Ответ обоснуйте.
ОТВЕТ

Структура программы на языке Pascal
Программа на языке PascalABC.NET имеет следующий вид:



Первая строка называется
заголовком программы
и не является обязательной.
Раздел
uses
начинается с ключевого слова uses, за которым следует список имен модулей и
пространств имен .NET, перечисляемых через запятую.
Раздел описаний
может включать разделы
описания переменных, констант, меток, типов, процедур и функций, которые следуют дру
г за
другом в произвольном порядке.
Далее следует
блок begin/end
, внутри которого находятся операторы, отделяемые один от другого
символом “точка с запятой”.
Раздел uses и раздел описаний могут отсутствовать.
Например:



readln(a,b);



x := a/b;



writeln(x);
Синтаксис, семантика и прагматика
Что значит "знать язык программирования"? А что означает знать русский язык? Это означает
умение понимать речь и письменный текст на этом языке, видеть орф
ографические,
грамматические, синтаксические и пунктуационные ошибки в тексте, а также излагать собственные
мысли на этом языке.
С языками программирования немного проще
на них не разговаривают, а только пишут, причём
правила языка строго формализованы.
Однако излагать свои мысли приходится синтаксически
безошибочно, так как "осознанием" текста будет заниматься бездушный компьютер, исполняющий
ровно то, что написано.
Описание языка программирования состоит из задания синтаксиса и семантики.
Синтаксис
о самая простая часть описания алгоритмического языка. На уровне грамматики
определяются корректные последовательности символов
лексемы. Если последовательность
символов принадлежит языку, то она считается синтаксически правильной. Для программы это
озна
чает, что транслятор на ней не выдает ошибки. Но синтаксическая правильность не
гарантирует даже осмысленности программы. Таким образом, синтаксис определяет лишь одну
сторону языка.
Семантика
это соответствие между синтаксически правильными программами
и действиями
абстрактного исполнителя, то есть это смысл синтаксических конструкций.
Цель программиста
получить нужный ему эффект в результате исполнения программы на
конкретном оборудовании. Но, составляя программу, он думает о программе как об абстракт
ной
сущности и чаще всего совсем не хочет знать о регистрах, процессоре и других объектах
конкретного оборудования. В соответствии с позицией программиста моделью вычислений языка
программирования естественно считать то, какой абстрактный вычислитель задае
тся описанием
языка. Эта позиция подкрепляется также тем, что трансляция и исполнение может осуществляться
на разных конкретных вычислителях. Следуя этой точке зрения, мы, говоря о модели программы,
всегда имеем в виду ее образ в виде команд абстрактного,
а не конкретного вычислителя.
Прагматика
задает конкретизацию абстрактного вычислителя для данной вычислительной
системы. Часто стандарт языка программирования не полностью задаёт поведение исполнителя,
оставляя некоторые вольности, которые производителя
ми транслятора языка реализуются так или
иначе.
Реализованный язык всегда является прагматическим компромиссом между абстрактной моделью
вычислений и возможностями ее воплощения. Поэтому программисту для предсказуемого
поведения программы бывает важно знат
ь особенности данного конкретного компилятора, а также
особенности архитектуры, для которых пишется программа.
Лексемы и идентификаторы в Pascal
В исходном файле набор символов, в который не входит пробел, называется
лексемой
. Лексемы
разделяются любым
количеством пробелов или символов управления (в диапазоне от 0 до 32).
Например, в следующем сегменте,
пять лексем: идентификатор Writeln, левая и правая круглые скобки, точка с запятой и строка
'Hello, World!'
Программы
это пос
ледовательности лексем, которые сообщают компилятору,
какой код нужно генерировать. Существуют несколько типов лексем. Например, идентификаторы,
зарезервированные слова, операторы и т.п.
ИДЕНТИФИКАТОРЫ
Идентификаторы
это лексемы, которые имеют
определенное значение. Идентификаторы
начинаются с буквы (A
Z или a
z) или символа подчеркивания, и могут содержать буквы, символы
подчеркивания и цифры (0
9). Максимальная длина идентификатора в некоторых версиях Pascal
255 символов, в других только пер
вые 63 символа имеют значение. В любом случае при выборе
идентификатора для функции или переменой рекомендуется ограничиться разумным количеством
символов, чтобы текст
этим идентификатором был читабельным.
Pascal не чувствителен к регистру, поэтому иденти
фикаторы WriteLn, writeln и WRITELN являются
идентичными. Зарезервированные слова, имена процедур и переменные являются примерами
идентификаторов.
Область действия идентификатора
(т.е. место, где он может быть использован) простирается
от момента описания
до конца блока, в котором он описан. Область действия глобального
идентификатора, описанного в модуле, простирается на весь модуль, а также на основную
программу, к которой данный модуль подключен в разделе uses.
ЗАРЕЗЕРВИРОВАННЫЕ СЛ
ОВА
Зарезервированные
слова
это идентификаторы, которые имеют определенное значение в
Pascal. Это значение не может быть изменено или заменено каким
либо способом. Ниже
приведен список зарезервированных слов PascalABC.NET:
and array as begin case class const constructor dest
ructor div do downto else end event except
file final finalization finally for foreach function goto if implementation in inherited initialization
interface is label lock mod nil not of operator or procedure program property raise record repeat
Будем также называть зарезервированные слова
ключевыми
ОПЕРАТОРЫ И РАЗДЕЛИТ
ЕЛИ
Операторы и разделители
это лексемы, которые также имеют определенное значение. Ниже
привед
ен список допустимых операторов и разделителей и их назначение:
Лексема

Использование
оператор адреса
Оператор переадресации указателя
Сложение или дополнение значений в множество
Вычитание или удаление значений из множества
Умножение или пересечение множеств
Вещественное деление
div
Целое деление
mod
Модуль (остаток от целого деления)
Круглые скобки
Нижний разделитель, константы множества
Оператор присваивания
Оператор выбора поля
Разделитель
Разделитель диапазона
Разделитель Type или Case
Равно
Меньше
Больше
Меньше или равно
Больше или равно
Не равно
and
Логическое И
Оператор множества
Логическое НЕ
Логическое ИЛИ
shl
Поразрядный левый сдвиг, заменяющий правую часть нулями
shr
Поразрядный правый сдвиг, заменяющий левую часть нулями
Логическое ИСКЛЮЧАЮЩЕЕ ИЛИ
ПРОГРАММНЫЕ
КОММЕНТАРИИ
Хороший программист знает, что комментарии в исходном коде программы могут быть очень
полезны. Классические комментарии Pascal выделяются символами "{" и "}" или "(* " и "*)". Все
комментарии игнорируются во время компиляции. Комментарии не мо
гут содержать вложенные
комментарии, которые выделяются такими же разделителями. Ниже приведен пример
традиционных комментариев Паскаля:
В PascalABC.NET имеется С
подобные способы указать комментарий. Комментарием также
считается любая последовательность символов после символов // и до конца строки:
Коммент
арии, выделенные разными символами, могут быть вложенными:
Переменные и константы в Pascal
Описание переменных
Переменные могут быть описаны в разделе описаний, а также непосредственно внутри любого
блока begin/end.
Раздел описания переменных начинается со служебного слова var, после которого следуют
элементы описания вида
или
или
Имена в списке перечисляются через запятую. Например:
В последних трех случаях тип переменной определяется по типу правой части.
Описание констант
Раздел описания именованных констант начинается со служебного слова const, после которого
следуют эл
ементы описания вида
или
Например
Концепция присваивания
Присваивание
механизм, позволяющий динамически изменять связь переменных с их
значениями. Это одно из центральных конструкций в императивных языках программирова
ния.
Эффективно и просто реализуется на архитектуре современных компьютеров: на физическом
уровне результат операции состоит в проведении записи и перезаписи ячеек памяти или регистров
процессора.
Общий синтаксис простого присваивания выглядит следующим об
разом:
<выражение слева> = <выражение справа>
«Выражение слева» должно после вычисления привести к местоположению объекта данных, к
целевой переменной, идентификатору ячейки памяти, в которую будет производиться запись.
Такие ссылки называются «левосторонн
ими значениями» (англ.
lvalue). Типичные примеры
левостороннего значения
имя переменной (x), путь к переменной в пространстве имён и
библиотеках (Namespace.Library.Object.AnotherObject.Property), путь к массиву с выражением на
месте индекса (this.a[i+j*k
]).
Выражение справа
должно обозначать тем или иным способом ту величину, которая будет
присвоена объекту данных. Таким образом, даже если справа стои
т имя той же переменной, что и
слева, интерпретируется оно иначе
такие ссылки называются «правосторон
ними значениями»
(англ.
rvalue).
Разбор задач на переменные (B2)
ПРИМЕР 1
Определите значение переменной
после выполнения следующего фрагмента программы.


a;


2*b;
РЕШЕНИЕ
Можно выполнить вручную все действия, отмечая
текущие значения переменных в таблице:
a := 5;
a := 5;
a := a+6;
a := 5;
a := a+6;
b :=
a := 5;
a :=
a+6;
b :=
c := a
Ответ

ПРИМЕР 2
Определите значение переменной c после выполнения следующего фрагмента программы.

a / 2 * b;

c := b

a


c := a

2 * b;
РЕШЕНИЕ
a := 40;
b := 10;
10

самый сложный оператор:
b :=
a / 2 * b;
умножение и деление имеют равный приоритет, поэтому сначала выполнится деление, а потом
умножение
результат:
b :=
(40 / 2) * 10 =
20 * 10 =
200
a := 40;
b := 10;
10

b :=
a/2 * b;
очевидно, что теперь условие «a < b» ложно, поэтому выполняется оператор, стоящий после
слова else:
c := a
2*b = 40
2*(
200) = 440
Ответ:
Сумма и произведение последовательности
чисел
Задача
накопления суммы или произведения встречается в программировании довольно часто и
звучит в частности так:

Дана последовательность чисел, завершающаяся числом 0. Найдите сумму всех этих чисел.
Ввод
Вывод





РЕШЕНИЕ НА ЯЗЫКЕ PYT
HON

= int(input())



sum_int += x



x = int(input())

РЕШЕНИЕ НА ЯЗЫКЕ PAS
CALABC.NET



summa:= 0;



readln(x);



�while x 0 do begin







summa += x;







readln(x);



end;

При поиске суммы чисел начальное значение переменной, в которой происходит накопление
результата, должно равняться нулю.
ПРОИЗВЕДЕНИЕ ПОСЛЕДО
ВАТЕЛЬНОСТИ ЧИСЕЛ
Дана последовательность чисел, завершающаяся числом 0. Найдите
произведение всех этих
чисел.
Ввод
Вывод




Решение на языке Python



proizvedenie *= x



x = int(input())
Решение на языке PascalABC.NET





readln(x);



�while x 0 do begin






*= x;







readln(x);



end;
Очевидно, при поиске произведения начальное значение переменной, в которой происходит
накопление результата,
должно равняться 1.
Отметим также, что в этой задаче нельзя поменять местами строки
proizvedenie
*= x; и
readln(x);
внутри цикла, поскольку иначе итоговый результат всегда будет равен 0!
ВАРИАНТ ПОИСКА СУММЫ
С ИСПОЛЬЗОВАНИЕМ СПИ
СКА
На языке Python возможн
о решение при помощи создания списка и использования встроенной
функции sum:



a.append(x)



x = int(input())
Однако оно не лишено недостатка: сумма вычисляется не в один проход по данным, а в два.
Следовательно потребуется память на сохранение значений всех чисел потока, а само
вычисление будет происходить медленно из
за двойной работы.
Однако, когда список уже есть, использование встроенной функции является оптимальным
решением.
Оператор цикла
while в Pascal
Цикл с предусловием
цикл, который выполняется пока истинно некоторое условие, указанное
перед его началом. Это условие проверяется до выполнения тела цикла, поэтому тело может быть
не выполнено ни разу (если условие с самого начала ложно).





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




write(1);
Оператор цикла repeat
until в Pascal
Цикл с постусловием
цикл, в котором условие проверяется после
выполнения тела цикла.
Отсюда следует, что тело всегда выполняется хотя бы один раз. В языке Паскаль этот цикл
реализует оператор
repeat..until
; в Си
do…while
На языке Pascal цикл с постусловием имеет следующий вид::



В отличие от цикла
while
, условие вычисляется после очередной итерации цикла, и если оно
истинно, то происходит выход из цикла. Таким образом, операторы, образующие тело цикла
оператора
repeat
, выполняются по крайней мере один раз.
Обычно оператор
repeat
используют в ситуациях, где условие нельзя проверить, не выполнив
тело цикла. Например:



read(x);
Если условие всегда оказывается ложным, то может произойти зацикливание, как и в случае
while


write(1);

Оператор цикла for в Pascal
Цикл с параметром в языке Паскаль обозначается ключевым словом
for
и имеет одну из двух
форм:




или




Текст от слова
for
до слова
включительно называется
заголовком
цикла, а оператор после
телом
цикла.
Переменная после слова
for
называется
параметром
цикла.
Переменная
параметр
цикла также называется «итератор» по своей фу
нкции, т. к. она
отсчитывает итерации.
Для первой формы цикла с ключевым словом to параметр цикла меняется от начального значения
до конечного значения, увеличиваясь всякий раз на единицу, а для второй формы ключевым
словом
downto
уменьшаясь на единицу. Д
ля каждого значения переменной
параметра
выполняется тело цикла. Однократное повторение тела цикла называется итерацией цикла.
Значение параметра цикла после завершения цикла считается неопределенным.
Переменная
параметр цикла может иметь любой порядковый
тип (к ним относятся целые типы,
логический, символьный, перечислимый и диапазонный тип). При этом начальное и конечное
значения должны быть совместимы по присваиванию с переменной
параметром цикла.
Например:



en: (red,green,blue,white);



f
or en := red to blue do







write(Ord(en):2);



Writeln;



for var c := 'a' to 'z' do







write(c);
Если для цикла
for … to
начальное значение переменной цикла больше конечного значения или
для цикла
for … downto
начальное значение перемен
ной цикла меньше конечного значения, то
тело цикла не выполнится ни разу.
Если цикл используется в подпрограмме, то переменная
параметр цикла должна быть описана как
локальная.
Изменение переменной
параметра цикла внутри цикла является логической ошибкой.
Например,
следующий фрагмент является ошибочным:



i := 1;



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



for i := 1 to 10 do
begin







for j := 1 to 10 do











write((j*i):4);







Writeln;



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



for i := 1 to 5 do







write(i);
Цикл for в Python
Цикл
for
, также называемый циклом с параметром, в
языке Питон богат возможностями. В
цикле
for
указывается переменная и множество значений, по которому будет пробегать
переменная. Множество значений может быть задано списком, кортежем, строкой или диапазоном.
Вот простейший пример использования цикла, где
в качестве множества значений используется
кортеж:
print(i, '
th color of rainbow is ', color, sep = '')
i += 1
В этом примере переменная
color
последовательно принима
ет значения ‘red’, ‘orange’ и т.д. В
теле цикла выводится сообщение, которое содержит название цвета, то есть значение
переменной
color
, а также номер итерации цикла
число, которое сначала равно 1, а потом
увеличивается на один (инструкцией
с кажд
ым проходом цикла).
В списке значений могут быть выражения различных типов, например:
print(i)
При первых трех итерациях цикла переменная i будет принимать значение типа
int
, при
последующих трех
типа
str
ФУНКЦИЯ RANGE
Как правило, циклы
for
используются либо для повторения какой
либо последовательности
действий заданное число раз, либо для изменения значения переменной в цикле от некоторого
начального значения до некоторого конечного.
Для повторения цикла
некоторое заданное число раз n можно использовать цикл
r вместе с
функцией
range
В качестве n может использоваться числовая константа, переменная или произвольное
арифметическое выражение (например, 2 ** 10). Если значен
ие n равно нулю или отрицательное,
то тело цикла не выполнится ни разу.
Если задать цикл таким образом:
то индексная переменная i будеть принимать значения от a до b
1, то есть первый параметр
функции range, вызываемо
й с двумя параметрами, задает начальное значение индексной
переменной, а второй параметр
значение, которая индексная переменная принимать не будет.
Если же a≥b, то цикл не будет выполнен ни разу. Например, для того, чтобы просуммировать
значения чисел от
1 до n можно воспользоваться следующей программой:
sum += i
В этом примере переменная i принимает значения 1, 2, …, n, и значение переменной sum
последовательно увеличивается на указанные значения.
Наконец, чтобы орга
низовать цикл, в котором индексная переменная будет уменьшаться,
необходимо использовать функцию
с тремя параметрами. Первый параметр задает
начальное значение индексной переменной, второй параметр
значение, до которого будет
изменяться индексная п
еременная (не включая его!), а третий параметр
величину изменения
индексной переменной. Например, сделать цикл по всем нечетным числам от 1 до 99 можно при
помощи функции
, а сделать цикл по всем числам от 100 до 1 можно при
помощи
Более формально, цикл
при d > 0 задает значения индексной
переменной i = a, i = a + d, i = a + 2 * d и так для всех значений, для которых i < b. Если же d < 0, то
переменная цикла принимает все значения i > b.
Цикл
while в Python
Цикл
while
(“пока”) позволяет выполнять одну и ту же последовательность действий, пока
проверяемое условие истинно.
Условие записывается до тела цикла и проверяется до выполнения тела цикла. Как правило,
цикл
while
используется, когда
невозможно заранее определить точно количество шагов.
Синтаксис цикла while в простейшем случае выглядит так:
При выполнении цикла while сначала проверяется условие. Если оно ложно, то выполнение цикла
прекращается и упра
вление передается на следующую инструкцию после тела цикла while. Если
условие истинно, то выполняется инструкция, после чего условие проверяется снова и снова
выполняется инструкция. Так продолжается до тех пор, пока условие будет истинно. Как только
усло
вие станет ложно, работа цикла завершится и управление передастся следующей инструкции
после цикла.
Например, следующий фрагмент программы напечатает на экран квадраты всех целых чисел от 1
до 10
print(i) i += 1
В этом примере пер
еменная i внутри цикла изменяется от 1 до 10. Такая переменная, значение
которой меняется с каждым новым проходом цикла, называется счетчиком. Заметим, что после
выполнения этого фрагмента значение переменной i будет равно 11, поскольку именно при i==11
ловие i<=10 впервые перестанет выполняться.
Видно, что цикл
может заменять цикл
Вот еще один пример использования цикла
while
для определения количества цифр натурального
числа n:
n //= 1

length += 1
В этом цикле мы отбрасываем по одной цифре числа, начиная с конца, что эквивалентно
целочисленному делению на 10 (
), при этом считаем в переменной
, сколько раз
это было сделано.
Впрочем, в языке Питон есть и другой способ р
ешения этой задачи:
Еще раз подчеркнем отличие цикла while от цикла for:
while
используется тогда, когда мы
заранее не знаем, сколько раз должны повторять некоторое действие.
Анализ цифр числа
При помощи операции взятия остатка можно
легко узнать последнюю цифру числа: это остаток
при делении на основание системы счисления.
Например, последняя цифра числа 15328 в 10
ной системе счисления равна 15328 mod 10.
Если же необходимо достать
ю цифру по старшинству (т.
е. справа), то нужно вн
ачале поделить
число на на единицу меньшую степень основания системы счисления:
15328
mod
(3−1)
, третья цифра справа.
Решим задачу нахождения суммы цифр данного числа
(при этом нам заранее неизвестно,
сколько в этом числе разрядов). Будем брать
остаток при делении на 10 до тех пор, пока это
возможно, прибавлять его к некоторой переменной (искомой сумме), а затем целочисленно делить
число
на 10 (обрезая последнюю цифру). На языке Pascal это можно записать так:

n, sum: longint;

readln(n);

sum := 0;

�while (n 0) do


begin



sum += n mod 10;



n := n div 10;

end;

writeln(sum);
Еще одна похожая задача
перевернуть число
. То есть, если
12345
, то результатом работы
программы будет
54321
. Будем действовать
схожим образом
отрезать цифру от данного числа,
пока это можно сделать и прибавлять ее к некоторой переменной
, но прибавлять не просто
так, а предварительно умножая
на 10, чтобы "подвинуть" разряды.


n, ans, tmp: longint;



readln(


ans := 0;


tmp := 10;


�while (n 0) do



begin




ans := ans * tmp;




ans += n mod 10;




n := n div 10;


end;


writeln(ans); end.
Анализ программы, содержащей
подпрограммы, циклы и ветвления
ПРИМЕР ЗАДАНИЯ
Получив на вход число x,
эта программа печатает два числа, L и M. Укажите наибольшее из таких
чисел x, при вводе которых алгоритм печатает сначала 3, а потом 7.

readln(x);

L:=0; M:=0;

�while x 0 do begin
L:=L+1;
if M (x mod 10) then be
M:=x mod 10;
end;
x:= x div 10;

end;

writeln(L); write(M);
В переменной L окажется число цифр числа, а в переменной M
наибольшая цифра.
Ответ:
Примеры задач на исправление программ
ПРИМЕР 1
Требовалось написать
программу, которая вводит с клавиатуры координаты точки на плоскости (x,
действительные числа) и определяет принадлежность точки заштрихованной области, включая
ее границы. Программист торопился и написал программу неправильно. Вот она:

�if y=0 then



if y=2
x*x









else






Последовательно выполните следующее:
Перерисуйте и заполните таблицу, которая показывает, как работает программа пр
и аргументах,
принадлежащих различным областям (A, B, C, D, E, F и G). Точки, лежащие на границах областей,
отдельно не рассматривать.
В столбцах условий укажите "да", если условие выполнится, "нет" если условие не выполнится,
" (прочерк), если условие
не будет проверяться, «не изв.», если программа ведет себя по
разному для разных значений, принадлежащих данной области. В столбце "Программа выведет"
укажите, что программа выведет на экран. Если программа ничего не выводит, напишите "
(прочерк). Если д
ля разных значений, принадлежащих области, будут выведены разные тексты,
напишите «не изв». В последнем столбце укажите "да" или "нет".
Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это
можно сделать несколькими сп
особами, поэтому можно указать любой способ доработки
исходной программы).
ПРИМЕР 2
Требовалось написать программу, которая вводит с клавиатуры координаты точки на плоскости (x,
действительные числа) и определяет принадлежность точки заштрихованной
области, включая
ее границы. Программист торопился и написал программу неправильно. Вот она:



�if x = 0 then
�if y = sin(x) then



Последовательно выполните следующее:
Приведите пример таких чисел x, y, при которых программа неверно решает поставленную
задачу.
Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это
можно сделать несколькими способ
ами, поэтому можно указать любой способ доработки
исходной программы).
Процедуры и функции в Pascal
Описание процедур и функций
Процедура или функция представляет собой последовательность операторов, которая имеет имя,
список параметров и может быть
вызвана из различных частей программы. Функции, в отличие от
процедур, в результате своего выполнения возвращают значение, которое может быть
использовано в выражении. Для единообразия функции и процедуры
называются
подпрограммами
Любая используемая в про
грамме процедура или функция должна быть предварительно описана в
разделе описаний.
Описание процедуры имеет вид:



Описание функции имеет вид:



Операторы подпрограммы, окаймленные операторными скобками
begin/end
, называются телом
этой подпрограммы.
Имя, параметры, результат
Список фор
мальных параметров вместе с окружающими скобками может отсутствовать. Он
состоит из одной или нескольких секций, разделенных символом “
”. Каждая секция состоит из
списка переменных, перечисляемых через запятую, после которого следуют двоеточие и тип.
Кажд
ая секция может предваряться ключевым словом
var
или
const
, что указывает на то, что
параметры передаются по ссылке
Пример описания процедуры приводится ниже:





res := a + b;

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





Add := a + b;

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





i:Integer;





Result := real.MaxValue;




for i:= 0 to a.Length
1 do








if a[i] Result then












Result := a[i];

Если внутри функции не присвоить имени функции или переменной
Result
некоторое значение, то
функция вернет в результате своего вызова непредсказуемое значение.
окальные и глобальные переменные
Переменная
именованная область памяти, имеющая тип.
Данные, находящиеся в переменной (то есть по данному адресу памяти),
называются
значением
этой переменной.
По зоне видимости различают
локальные
глобальные
переменные.
Локальные доступны только конкретной подпрограмме, глобальные
всей программе. С
распространением модульного и объектного программирования, появились ещё
общие
переменные (доступные для определённых уровней иерархии подпрограмм).
Область видимости опре
деляет класс памяти, но иногда локальные (с точки зрения области
видимости идентфиикатора) переменные могут быть статическими (по классу памяти).
Пример статической локальной переменной на языке Си:

static int
the_counter
= 0;
the_counter++;

Ограничение зоны видимости позволяет использовать одинаковые имена переменных в разных
подпрограммах, при этом защищает от ошибок взаимного использования переменных.
Переменные должны быть по
возможности локальными
Прямой и обратный ход рекурсии
Чтобы понять рекурсию, нужно понять рекурсию
В программировании
рекурсия
вызов функции (процедуры) из неё же самой, непосредственно
(простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например,
функция A вызывает функцию B, а функция B
функцию A.
Количество вложенных вызовов функции или процедуры называется
глубиной
рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное
определение теоретически способно оп
исывать бесконечно большое число объектов. С помощью
рекурсивной программы же возможно описать бесконечное вычисление, причём без явных
повторений частей программы.
Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих
зада
ч может оказаться и первоначальная, но в упрощенной форме.
Например, для вычисления F(N) может понадобиться вычислить F(N−1). Иными словами, частью
алгоритма вычисления функции будет вычисление этой же функции.
Пример рекурсивного алгоритма: N!=(N−1)!
N,
если N=0, то N!=1
Любое рекурсивное определение состоит из двух частей. Одна часть определяет понятие через
него же, другая часть
через иные понятия.
Процедура является
рекурсивной
, если она обращается сама к себе прямо или косвенно (через
другие
процедуры).
Заметим, что при косвенном обращении все процедуры в цепочке
рекурсивные. Все сказанное о
процедурах целиком относится и к функциям.
ПРИМЕР РЕКУРСИВНОЙ Ф
УНКЦИИ ВЫЧИСЛЕНИЯ ФА
КТОРИАЛА НА PASCAL

Рекурсия изнутри
Это может показаться удивительным, но самовызов функции/процедуры ничем не отличается от
вызова другой функции/процедуры. Что происходит, если
одна функция вызывает другую? В
общих чертах следующее:
в памяти размещаются параметры, передаваемые функции (но не параметры
переменные, т. к.
они передаются по ссылке!);
для внутренних переменных вызываемой функции также отводится новая область памяти
(несмотря на совпадение их имен и типов с переменными вызывающей функции);
запоминается адрес возврата в вызывающую функцию;
управление передается вызванной функции.
Если функцию или процедуру вызвать повторно из другой функции/процедуры или из нее самой,
будет выполняться тот же код, но работать он будет
с другими значениями параметров и
внутренних переменных
. Это и дает возможность рекурсии.
Прямой и обратный ход рекурсии
Действия, выполняемые функцией до входа на следующий уровень рекурсии, называются
ыполняющимися
на прямом ходу рекурсии
, а действия, выполняемые по возврату с более
глубокого уровня к текущему,
выполняющимися
на обратном ходу рекурсии
ДЕМОНСТРАЦИЯ ХОДА РЕ
КУРСИИ НА PASCAL

При запуске этой программы, будет выведено:
Прямой ход рекурсии. Глубина =
Прямой ход рекурсии. Глубина = 2
Прямой ход рекурсии. Глубина = 3
Прямой ход рекурсии. Глубина = 4
Обратный ход рекурсии. Глубина = 4
Обратный ход рекурсии. Глубина = 3
Обратный ход рекурсии. Глубина = 2
Обратный ход рекурсии. Глубина = 1
Программы с исп
ользованием рекурсии на
Pascal
ЗАДАЧА 1
Запишите рекурсивную функцию, вычисляющую сумму натуральных чисел m и n, в которой из
арифметических операций используется только прибавление и вычитание единицы.
Если первое число равно нулю, то ответом будет второ
е, иначе сведем задачу к нахождению
суммы чисел, одно из которых на 1 меньше первого, а второе
на 1 больше второго.
РЕШЕНИЕ НА ЯЗЫКЕ PAS
CAL

if a = 0 then



sum := b

else



sum := sum(a

1, b + 1);

a, b: longint;

readln(a, b);

writeln(sum(a, b));

ЗАДАЧА 2.
Дано число n. Нужно напечатать его цифры через пробел, при этом массив использовать нельзя.
Если число состоит из одной цифры, напечатаем ее. Если цифр больше одной,
вызовем нашу
процедуру от
, а после этого напечатаем последнюю цифру. То есть, мы как бы
откладываем в стек печатание очередной цифры до тех пор, пока рекурсии не дойдет до конца
того момента, когда останется только одна цифра. Это будет первая ц
ифра числа, она
напечатается и пойдет “скручивание” рекурсии в обратном порядке.
РЕШЕНИЕ НА ЯЗЫКЕ PAS
CAL

if n 10 then



write(n, ' ')

else begin



p(n div 10);



write(n mod 10, ' ');

end;

n: longint;

readln(n);

p(n);
Массивы в Pascal
Массив
представляет собой набор элементов одного типа, каждый из которых имеет свой номер,
называемый
индексом
(индексов может быть несколько, тогда массив называется многомерным).
Тип статического массива
конструируется следующим образом:
Соответственно, объявление массива в простейшем случае выглядит так:


a: array [1..10] of longint;

Тип индекса должен быть
порядковым
. Обычно тип индекса
представляется в виде a..b, где a и b
константные выражения целого, символьного или перечислимого типа. Например:



MyEnum = (w1,w2,w3,w4,w5);



Arr = array [1..10] of integer;



a1, a2: Arr;



b: array ['a'..'z'] of char;



c: array



d: array [1..3] of array [1..4] of real;
При описании можно также задавать инициализацию массива значениями:



a: Arr := (1,2,3,4,5,6,7,8,9,0);


cc: array [1..3,1..4] of real := ((1,2,3,4), (5,6,7,8), (9,0,1,2));
Статические
массивы одного типа можно присваивать друг другу, при этом будет производиться
копирование содержимого одного массива в другой:
Выход за границы изменения индекса является серьезной ошибкой.
Размер массива грамотно задавать через
константу
(const
N = 30;), а не вписывать число в
каждый цикл; тогда, если нужно будет переделать программу для массива другого размера,
достаточно будет изменить всего одно число в начале программы.
Пример 1.
Считаем с клавиатуры число n, а затем сохраним n целых чисел в
массив a.

a: array[1..100] of longint;

i, n: longint;

read(n);

for i := 1 to n do



read(a[i]);
Пример 2.
Считаем с клавиатуры число n, а затем заполним массив последовательными числами
от 1 до n. Выведем массив на экран.

a:
array[1..100] of longint;

i, n: longint;

read(n);

for i := 1 to n do



a[i] := i;

for i := 1 to n do



write(a[i], ' ');

Пример 3.
Считаем с клавиатуры число n, а затем n чисел в массив. Переставим элементы
массива в обратном поряд
ке и выведем измененный массив на экран.
Заметим, что первый элемент поменяется с n
м, второй с (n
вым, …, i
ый c (n
i + 1)
ым. Тогда
код на языке Pascal быть записан так:

a: array[1..100] of longint;

i, n: longint;

read(n);

for i



read(a[i]);



for i := 1 to n div 2 do



swap(a[i], a[n

i + 1]);



for i := 1 to n do



write(a[i], ' ');

Пример задания с двумерным массивом
Cложность подобных задач в том, что все действия выполнять в уме или на
бумаге, не используя
компьютер для отладки.
Номер строки
это первый индекс массива, а номер столбца
второй.
ПРИМЕР
Дан фрагмент программы, обрабатывающей двухмерный массив A размера n×n.

c := A[i,i];

A[i,i] := A[k,i]


A[k,i] := c;
Представим массив в виде квадратной таблицы, в которой для элемента массива A[i,j] величина i
является номером строки, а величина j
номером столбца, в котором расположен элемент. Тогда
данный алгоритм меняет местами
два столбца в
таблице
две строки в таблице
элементы диагонали и k
ой строки таблицы
элементы диагонали и k
го столбца таблицы
Циклический сдвиг в массиве: Pascal
Обсудим несколько задач, в которых будет идти речь о сдвиге элементов массива.
ЗАДАЧА 1. ЦИКЛИЧЕСКИ
Й СДВИГ
МАССИВА ВЛЕВО
Дано число n, а затем n целых чисел. Нужно считать эти числа в массив, и написать
программу, которая будет циклически сдвигать заданный массив на один элемент влево,
первый элемент при этом должен оказаться последним.
Например, массив
a=[1,2,3,4,5] после такого сдвига станет таким: a = [2,3,4,5,1].
ОБСУЖДЕНИЕ
Первое, что приходит в голову: перебрать первые n
1 элементов и каждому из них
присвоить значение правого соседа.
Однако, в таком случае значение первого элемента
исходного
массива будет безвозвратно потеряно. Поэтому предварительно
нужно
сохранить его в отдельную переменную.



РЕШЕНИЕ НА ЯЗЫКЕ PAS
CAL
var


a: array[1..100] of longint;


c, i, n: longint;
begin








read(a[i]);




for i := 1 to n





a[i] := a[i + 1];


a[n] := c;


for i := 1




write(a[i], ' ');
end.




ЗАДАЧА 2. ЦИКЛИЧЕСКИ
Й СДВИГ МАССИВА ВПРА
Дано число n, а затем n целых чисел. Нужно считать эти числа в массив, и
написать
программу, которая будет циклически сдвигать заданный массив на один элемент
вправо,
последний элемент при этом должен оказаться первым.
Например, массив
a=[1,2,3,4,5]
после такого сдвига станет таким:
a = [5,1,2,3,4]
ОБСУЖДЕНИЕ
Аналогично решению задачи
1, запишем значение последнего элемента массива в
отдельную переменную.
Затем переберем элементы массива с индексами от 2 до n и
каждому из них присвоим значение левого соседа.
А затем перезапишем первый элемент.
Однако, есть некоторая тонкость
если пер
ебирать элементы массива слева направо,
все они окажутся равными первому элементу исходного массива! Действительно,
пусть
наш массив. Тогда на первом шаге
a[2]:=a[1]
, на втором
a[3]:=a[2]
, то
есть, на первом шаге исходное значение второго элемента м
ассива будет безвозвратно
потеряно,
и в
мы на самом деле запишем
. Для того, чтобы избежать этой
ошибки, будем перебирать элементы массива справа налево (от n
ого ко 2
ому).



РЕШЕНИЕ НА ЯЗЫКЕ PAS
CAL
var


a: array[1..1000] of longint;


i, n, c:
begin








read(a[i]);




for i := n downto 2 do


begin




a[i] := a[i

1];


end;








write(a[i], ' ');
end.
Сортировка методом пузырька
Перед тем, как излагать этот
метод сортировки, внимательно прислушаемся к одному
небольшому примечанию.
Массив упорядочен по возрастанию, если меньшие числа в нем
стоят раньше больших.
Чем меньше число, тем раньше оно должно стоять в массиве,
чем больше число
тем позже. Другими сло
вами, чем больше число, тем больше его
номер в массиве (индекс).
Если мы последовательно рассмотрим все пары соседних чисел, и в каждой из них это
свойство выполняется, то массив можно считать упорядоченным.
Именно на этом и базируется основная идея сортир
овки методом пузырька (также
называемого методом обмена). Будем сравнивать пары соседних элементов массива.
Если в какой
то паре большее число стоит левее меньшего, то их надо поменять местами.
Рассмотрим работу метода на примере. Пусть дан массив из 6 це
лых чисел, которые
необходимо расположить в порядке возрастания.
4 3 5 8 6 2
Двигаться будем слева направо (хотя это не принципиально).
Шаг 1
. Сравним 4 и 3. Число 4 больше (а значит должно стоять правее)
меняем местами
эти элементы. Новый массив:
3 4 5
8 6 2
Независимо от того, меняли мы местами элементы или нет
просто переходим к
следующей паре.
Шаг 2
. Сравним 4 и 5. Числа в паре стоят в «правильном» порядке
меньшее левее
большего. Ничего не делаем с этими элементами. Массив остается:
4 3 5 8 6 2
Переходим к следующей паре.
Шаг 3
. Сравниваем 5 и 8. Эти числа также стоят в «правильном» порядке, поэтому массив
не изменяется:
4 3 5 8 6 2
Берем следующую пару.
Шаг 4
. Сравниваем 8 и 6. Здесь большее число стоит левее меньшего, поэтому меняем
числа места
ми, получаем новый массив:
4 3 5 6 8 2
Переходим к следующей паре.
Шаг 5
. Сравниваем 8 и 2.Опять большее число левее меньшего
переставляем числа.
4 3 5 6 2 8
Пары закончились.
Правда, массив пока мало похож на отсортированный. Однако, можно сделать одно
важное наблюдение:
после полного прохода по массиву хотя бы одно число (а
именно
самое большое) будет поставлено на свое место
. Именно поэтому этот метод
носит название «метод пузырька» или просто «пузырек». Наибольшее число, как пузырек
из глубины стак
ана с газировкой, «всплывает» на поверхность (на последнее место в
массиве) и остается там.
Теперь, если мы сделаем второй проход по массиву, то еще одно число встанет на свое
место (а может быть и не одно, но об этом чуть позже). Значит, чтобы гарантирова
нно
получить отсортированный массив, надо сделать столько проходов, сколько элементов в
массиве.
Впрочем, достаточно сделать
проход, потому что когда все числа кроме одного будут
на своих местах, последнее тоже само собой окажется на своем месте.
Итак, мы выяснили, что для успешной сортировки надо сделать
проход,
сравнению на каждом проходе. Таким образом структура программы
двойной
цикл. Внешний цикл
по количеству проходов, внутренний
по тем парам элементов,
которые мы сравниваем.
РЕАЛИЗАЦИЯ СОРТИРОВК
И МАССИВА МЕТОДОМ ПУ
ЗЫРЬКА НА ЯЗЫКЕ PYTH
ON
def BubbleSort(A):







РЕАЛИЗАЦИЯ СОРТИРОВК
МАССИВА МЕТОДОМ ПУЗЫ
РЬКА НА ЯЗЫКЕ PASCAL
type


massiv = array[1..1000] of longint;
var


a: massiv;


i, n: longint;
procedure bubbleSort(var a: massiv);
var


i, j: longint;
begin


for j := 1 to n

1 do




for i := 1 to n

1 do






�if a[i] a[i +









swap(a[i], a[i + 1]);
end;
begin


readln(n);


for i := 1 to n do




read(a[i]);


bubbleSort(a);


for i := 1 to n do




write(a[i], ' ');
end.



По структуре программы видно, что такая сортировка
требует
операций. То есть
время работы программы можно оценить как
Модернизация сортировки методом пузырька
Приведем пару соображений по оптимизации написанного кода. Представим себе,
что у нас есть массив на два миллиона чисел, и мы уже сделали миллион проходов. Это
значит,
что как минимум миллион чисел в массиве уже стоят на своих законных местах в
конце массива. Следовательно, нет никакого смысла проходить правую половину массива,
потому что там никаких изменений точно уже не будет. Итак, если на первом проходе мы
делаем
сравнение, то на втором достаточно
, на третьем
достаточно
и так
далее по мере увеличения количества чисел, которые стоят на своих местах. Таким
образом кусочек программы, отвечающий за сортировку можно переписать так:
PYTHON:
def BubbleSort(A):



PASCAL:
procedure bubbleSort(var a: massiv);
var


i, j: longint;
begin


for j := 1 to n

1 do




for i :=
1 to n

j do






�if a[i] a[i + 1] then









swap(a[i], a[i + 1]);
end;



Количество операций (а вместе с ним и время работы) нам удалось сократить
вдвое. Хотя, следует признать, что оценка времени работы алгоритма все еще
составляет
Второе соображение для оптимизации метода простого обмена основано на таком
утверждении: если за полный проход в массиве не сделано ни одной перестановки, то его
можно считать отсортированным. Что значит «не сделано ни одной перестановки»? Это
значит, что
все пары соседних чисел расположены «правильно», то есть большее число
идет позже меньшего, поэтому они в перестановках не нуждаются. Это позволяет
значительно сократить время в случаях, когда более или менее повезло с исходными
данными.
Например, в массив
е 8, 1, 2, 3, 4, 5, 6 будет вообще достаточно одного прохода,
чтобы вытолкнуть восьмерку на последнее место.
Существенных изменений в структуре программы не будет
как был двойной цикл,
так и остался. Просто внешний цикл будет заменен на цикл с условием.
Программа в этом
случае может выглядеть, например, так:
PYTHON:
def BubbleSort(A):
j = len(A)

1

IsNotOrdered = True
while IsNotOrdered:
IsNotOrdered = False
for i in range(0, j):
�if A[i] A[i + 1]:

A[i], A[i + 1] = A[i + 1], A[i]
IsNotOrdered = True
j
-
= 1



PASCAL:
procedure bubbleSort(var a: massiv);
var


i, j: longint;


isNotOrdered: boolean;
begin


isNotOrdered := true;


j := n

1;


while isNotOrdered do



begin




isNotOrdered := false;




for i := 1 to j do






�if a[i] a[i + 1] then begin








swap(a[i], a[i + 1]);








isNotOrdered := true;






end;




dec(j);


end;
end;



Стоит заметить, что в худшем случае (а именно, если на входе дан массив,
упорядоченный в другую сторону) время работы все равно будет составлять
и по
количеству операций сравнения программа не будет отличаться от предыдущего примера.
Есть различные алгоритмы, построенные на основе пузырьковой сортировке.
Например, в
шейкерной сортировке внутренний цикл проходится поочередно слева
направо, затем справа налево. А в сортировке Шелла элементы переставляются не
соседние элементы, а элементы, отстоящие на большее расстояние, что позволяет
быстрее перемещать элементы по спис
ку, выполняя сразу несколько шагов.
Списки в Python
Большинство программ работает не с отдельными переменными, а с набором переменных.
Например, программа может обрабатывать информацию об учащихся класса, считывая список
учащихся с клавиатуры или из файла,
при этом изменение количества учащихся в классе не
должно требовать модификации исходного кода программы.
Раньше мы сталкивались с задачей обработки элементов последовательности, например,
вычисляя наибольший элемент последовательности. Но при этом мы не
сохраняли всю
последовательность в памяти компьютера, однако, во многих задачах нужно именно сохранять
всю последовательность, например, если бы нам требовалось вывести все элементы
последовательности в возрастающем порядке (“отсортировать последовательнос
ть”).
Для хранения таких данных можно использовать структуру данных, называемую в Питоне список
(в большинстве же языков программирования используется другой термин “массив”). Список
представляет собой последовательность элементов, пронумерованных от 0, ка
к символы в строке.
Список можно задать перечислением элементов списка в квадратных скобках, например, список
можно задать так:
В списке Primes
элементов, а именно,
Список Rainbow состоит из 7 элементов, каждый из которых является строкой.
Также как и символы строки, элементы списка можно индексироват
ь отрицательными числами с
конца, например,
1] == 13, Primes[
6] == 2.
Длину списка, то есть количество элементов в нем, можно узнать при помощи функции len,
например, len(A) == 6.
Рассмотрим несколько способов создания и считывания списков. Прежде
всего можно создать
пустой список (не содержащий элементов, длины 0), в конец списка можно добавлять элементы
при помощи метода append. Например, если программа получает на вход количество элементов в
списке n, а потом n элементов списка по одному в отдел
ьной строке, то организовать считывание
списка можно так:
A.append(int(input())
В этом примере создается пустой список, далее считывается количество элементов в списке,
затем по одному считываются элементы списка и д
обавляются в его конец.
Для списков целиком определены следующие операции: конкатенация списков (добавление
одного списка в конец другого) и повторение списков (умножение списка на число). Например:
В результате
список C будет равен [1, 2, 3, 4, 5], а список D будет равен [4, 5, 4, 5, 4, 5]. Это
позволяет по
другому организовать процесс считывания списков: сначала считать размер списка и
создать список из нужного числа элементов, затем организовать цикл по переме
нной i начиная с
числа 0 и внутри цикла считывается i
й элемент списка:
A[i] = int(input())
Вывести элементы списка A можно одной инструкцией print(A), при этом будут выведены
квадратные скобки вокруг
элементов списка и запятые между элементами списка. Такой вывод
неудобен, чаще требуется просто вывести все элементы списка в одну строку или по одному
элементу в строке. Приведем два примера, также отличающиеся организацией цикла:
print(A[i])
Здесь в цикле меняется индекс элемента i, затем выводится элемент списка с индексом i.
print(elem, end = ' ')
В этом примере элементы списка выводятся в одну строку, разделенные пробелом, при этом в
цикле меняется не инде
кс элемента списка, а само значение переменной (например, в цикле for
elem in [‘red’, ‘green’, ‘blue’] переменная elem будет последовательно принимать значения ‘red’,
‘green’, ‘blue’.
Обращение массива
Для того, чтобы переставить элементы массива A длины N
в обратном порядке, нужно разбить из
на пары первый
последний, второй
предпоследний и т. д. и поменять местами элементы в
каждой паре. При этом нужно обратить внимание, что пар не N, а [N/2].
ПРИМЕР КОДА НА ЯЗЫКЕ
PYTHON



На языке питон можно сделать то же самое короче, воспользовавшись срезами списков:
A = A[::
Циклический сдвиг в массиве
Сдвиг на k элементов влево:

=

A[k:]
+

A[:k]
Сдвиг на k элементов вправо:

=

A[
k:]
+

A[:
k]
Такой сдвиг требует дополнительную память для хранения срезов, пропорциональную длине
массива.
Символьный тип данных в Pascal
Символьный тип
В зависимости от компилятора Pascal символьный тип char занимает 1 или 2 байта. В компиляторе
FreePascal,
Borland Pascal, Turbo Pascal и других традиционных компиляторах
1 байт. В
Строковый тип
Строки имеют тип string, состоят из набора последовательно расположенных символов char и
используются для представления текста.
В компилятора
х FreePascal, Borland Pascal, Turbo Pascal строка имеет максимальную длину 255. В
PascalABC.NET строки могут иметь произвольную длину. К символам в строке можно обращаться,
используя индекс: s[i] обозначает i
тый символ в строке, нумерация начинается с еди
ницы. Если
индекс i выходит за пределы длины строки, то генерируется исключение.
Операция + для строк означает конкатенацию (слияние) строк. Например: 'Петя' + 'Маша' =
'ПетяМаша'.
Для описания строк заданного конечного размера используется тип string[n],
где n
константа
целого типа, указывающая длину строки.
Функции Ord и Chr
Для преобразования между символами и их кодами в кодировке Windows (CP1251) используются
стандартные функции Chr и Ord:
функция, возвращающая символ с кодом n в кодировке
Windows;
функция, возвращающая значение типа byte, представляющее собой код символа c в
кодировке Windows.
Обработка кода символа
ПОЛУЧЕНИЕ ЧИСЛОВОГО
ЗНАЧЕНИЯ ЦИФРЫ

ПОЛУЧЕНИЕ ЗАДАННОЙ Б
УКВЫ АЛФАВИТА
Стандартные функции обработки строк
К строкам применимы все операции сравнения <, >, <=, >=, =, <>.
Кроме этого, к строкам и
символам применима операция
конкатенации
(слияния) + , ее результат
имеет строковый тип. Например, 'a' + 'b' = 'ab'.

function Pos(subs,s: string): integer;

Возвращает позицию подстроки subs в строке s. Если не найдена, возвращает 0

function Length(s: str

Возвращает длину строки

function Copy(s: string; index,count: integer): string;

Возвращает подстроку строки s длины count с позиции index

procedure Insert(source: string; var s: string; index: integer);

Вставляет подстроку source в стро
ку s с позиции index

function LowerCase(s: string): string;
Возвращает строку в нижнем регистре

function UpperCase(s: string): string;

Возвращает строку в верхнем регистре

function StrToInt(s: string): integer;

Преобразовать строку s в целое число и
записать результат в переменную n

procedure Val(s: string; var value: integer; var err: integer);
Преобразует строковое представление s целого числа к числовому значению и записывает его в
переменную value. Если преобразование успешно, то err=0, иначе err>

procedure Val(s: string; var value: real; var err: integer);
Преобразует строковое представление s вещественного числа к числовому значению и
записывает его в переменную value. Если преобразование успешно, то err=0, иначе err>0

procedure Str(i: integer
Преобразует целое значение i к строковому представлению и записывает результат в s

procedure Str(r: real; var s: string);

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

s :string;

Readln(s);

�while s 'asdf' do

begin
Writeln('s = "', s, '"');
Readln(s);

end;

Writeln('The End!');
Простота разбора, когда числа вначале, а
строка в конце

Number :integer;

mathMark :integer;

physMark :integer;

fullName :string;

Read(Number);

Read(mathMark, physMark);

Readln(fullName);

Writeln('name = ', fullName,
', math = ', mathMark,
', phys = ', physMark,
', num = ', number);
Перевод чисел из любой системы счисления в
ную (работа со
строкой посимвольно)

�if (c = '0') and (c = '9') then
result := Ord(c)

Ord('0')

els
result := 10 + Ord(c)

Ord('A')

�else if (c = 'a') and (c = 'z') then
result := 10 + Ord(c)

Ord('a')

else
result := 0;

s :string;

x, q, i :integer;



x := 0;

for i := 1 to Length(s) do
x := x*q + digitValue(s[i]);

Writeln(x);
Символьный тип данных в Pascal
Символьный тип
В зависимости от компилятора Pascal символьный
тип char занимает 1 или 2 байта. В компиляторе
FreePascal, Borland Pascal, Turbo Pascal и других традиционных компиляторах
1 байт. В
Строковый тип
Строки имеют тип string, состоят из набора последовательно расположенных символов
char и
используются для представления текста.
В компиляторах FreePascal, Borland Pascal, Turbo Pascal строка имеет максимальную длину 255. В
PascalABC.NET строки могут иметь произвольную длину. К символам в строке можно обращаться,
используя индекс: s[i]
обозначает i
тый символ в строке, нумерация начинается с единицы. Если
индекс i выходит за пределы длины строки, то генерируется исключение.
Операция + для строк означает конкатенацию (слияние) строк. Например: 'Петя' + 'Маша' =
'ПетяМаша'.
Для описания ст
рок заданного конечного размера используется тип string[n], где n
константа
целого типа, указывающая длину строки.
Функции Ord и Chr
Для преобразования между символами и их кодами в кодировке Windows (CP1251) используются
стандартные функции Chr и Ord:
функция, возвращающая символ с кодом n в кодировке Windows;
функция, возвращающая значение типа byte, представляющее собой код символа c в
кодировке Windows.
Обработка кода символа
ПОЛУЧЕНИЕ ЧИСЛОВОГО
ЗНАЧЕНИЯ ЦИФРЫ

ПОЛУЧЕНИЕ ЗАДАННОЙ Б
УКВЫ АЛФАВИТА
Стандартные функции обработки строк
К строкам применимы все
операции сравнения <, >, <=, >=, =, <>.
Кроме этого, к строкам и символам применима операция
конкатенации
(слияния) + , ее результат
имеет строковый тип. Например, 'a' + 'b' = 'ab'.

function Pos(subs,s: string): integer;

Возвращает позицию подстроки subs
в строке s. Если не найдена, возвращает 0

function Length(s: string): integer;

Возвращает длину строки

function Copy(s: string; index,count: integer): string;

Возвращает подстроку строки s длины count с позиции index

procedure Insert(source: string; v

Вставляет подстроку source в строку s с позиции index

function LowerCase(s: string): string;
Возвращает строку в нижнем регистре

function UpperCase(s: string): string;

Возвращает строку в верхнем регистре

function StrToI

Преобразовать строку s в целое число и записать результат в переменную n

procedure Val(s: string; var value: integer; var err: integer);
Преобразует строковое представление s целого числа к числовому значению и записывает его в
переменную value. Если преобразование успешно, то err=0, иначе err>0

procedure Val(s: string; var value: real; var err: integer);
Преобразует строковое представление s вещественного числа к числовому значению и
записывает его в переменную value. Если прео
бразование успешно, то err=0, иначе err>0

procedure Str(i: integer; var s: string);
Преобразует целое значение i к строковому представлению и записывает результат в s

procedure Str(r: real; var s: string);

Преобразует вещественное значение r к строковому
представлению и записывает результат в s
Все эти функции, кроме разве только Length, могут быть реализованы самостоятельно, но лучше
помнить и уметь использовать эти функции.
Переменные
счетчики
Переменные
счетчики
Часто требуется подсчитать, сколько раз
во время вычислений наступает то или иное событие
(выполняется то или иное условие). Для этого вводится вспомогательная переменная, которой в
начале присваивается нулевое значение, а после каждого наступления события она
увеличивается на единицу.
Пример 1
Пользователь вводит 10 чисел. Определить, сколько из них являются одновременно
четными и положительными.
Pascal
Python

readln(x);

�if (x mod 2 = 0) and (x 0) then
Counter :=
�if x%2 == 0 and x 0:
Пример 2:
Пользователь
вводит 10 чисел. Проверить, упорядочены ли они по возрастанию.
В разделе, посвященном переменным флагам, эта задача решена с помощью логической
переменой. Решим ее теперь с помощью счетчика. Последовательность будет упорядочена, если
нет ситуаций, когда по
следующее число меньше предыдущего. Подсчитаем количество таких
ситуаций, и если оно окажется нулевым, то последовательность упорядочена.
Pascal
Python

x2 := x;

readln(x);

�if x2 x then
Counter
:= Counter + 1;
x2 = x
x = int(input())
�if x2 x:
counter +=
1



Использование переменной
флага
Флаг
это полотнище правильной (как правило, прямоугольной) формы прикрепленное к древку
или поднимаемое на
специальной мачте (флагштоке). Исторически флаги появились для передачи
простых сигналов на поле боя. Например: подняли флаг, и конница понеслась в атаку! В
простейшем случае с помощью флага передается информация объемом 1 бит (одно из двух: флаг
поднят и
ли нет).
Переменная
флаг
это, как правило, переменная логического типа, значение которой
сигнализирует о состоянии вычислительного процесса. Приведем несколько примеров, когда
результат может характеризоваться всего одной логической переменной:
Подводитс
я баланс коммерческого предприятия. Дальнейшие действия могут зависеть от того,
будет он положительным или отрицательным. Если отрицательный, надо просить кредит,
положительный
планировать отдых в Крыму. В общем, самая существенная информация
может быть
передана одним битом.
Решаем квадратное уравнение. Если дискриминант не отрицательный
ищем корни. Для хода
вычислительного процесса важен факт не отрицательности, который также содержит 1 бит
информации и может, таким образом, быть сохранен с помощью лог
ической переменной.
Детям на уроке физкультуры велено построиться по росту. Если они построились не по росту,
надо на них наорать. Опять действия учителя зависят от информации объемом 1 бит.
Но кто и кому может передавать информацию в ходе выполнения прогр
аммы? Дело в том, что при
разработке больших программ происходит разделение задачи на более мелкие подзадачи (блоки),
каждая из которых решается отдельно и, может быть даже, разными людьми. В этом случае один
блок, закончив свою работу должен передать ее р
езультат другому блоку. Здесь и могут
пригодиться флаги.
Не обязательно
использовать в качестве флага именно логическую переменную. В принципе
флагом может считаться любая переменная, принимающая небольшое количество возможных
значений, каждое из которых х
арактеризует тот или иной результат вычислительного процесса.
ПРИМЕР ИСПОЛЬЗОВАНИЯ
ФЛАГА
Задача
проверка упорядоченности последовательности.
Пользователь вводит последовательность чисел, завершающуюся нулем. Требуется проверить,
упорядочены ли они по
возрастанию.
Если очередное введенное число (x) будет меньше предыдущего (old_x), то флаг Growing примет
начение False и сохранит это значение до конца цикла.
Задачи С4 на обработку текста
ЗАДАЧА 1
На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В
первой строке сообщается количество учащихся N, каждая из следующих N
строк имеет формат:
<Фамилия> <Инициалы> <номер школы>
где <Фамилия>
строка, состоящая не более чем из 20 символов, <Инициалы>
строка,
состоящая из 4
х символов (буква, точка, буква, точка), <номер школы>
не более чем
двузначный номер. <Фамилия> и <
Инициалы>, а также <Инициалы> и <номер школы> разделены
одним пробелом. Пример входной строки:
Иванов П.С. 57
Требуется написать как можно более эффективную программу (укажите используемую версию
языка программирования, например, Borland Pascal 7.0), кот
орая будет выводить на экран
информацию, из какой школы было меньше всего участников (таких школ может быть несколько).
При этом необходимо вывести информацию только по школам, пославшим хотя бы одного
участника. Следует учитывать, что N>=1000.
РЕШЕНИЕ НА

uchastnikov :array[1..99] of integer;

N, k, school_number, min :integer;

min_found :boolean;

c :char;

for school_number := 1 to 99 do

Readln(N);

for k := 1 to N

begin
Readln(school_number);
uchastnikov[school_number] += 1;

end


min_found := False;

for school_number := 1 to 99 do

begin
�if (uchastnikov[school_number] 0) and
(not min_found or (uchastnikov[school_number] min)) then
begin
min := uchastnikov[school_number];
min_found := True;

end;

end;

for school_number := 1 to 99 do
if uchastnikov[school_number] = min then
Writeln(school_number);

РЕШЕНИЕ НА PYTHON
lastname, initials, school_number = input().split()
school_number = int(school_number)
uchastnikov[school_number] += 1
if uchastnikov[school

(not min_found or uchastnikov[school_number] min_number):
min_number = uchastnikov[school_number]
min_found = True

if uchastnikov[school_number] == min_number:
print(school_number)


ЗАДАЧА 2
На вход программы подается текст на английском языке, заканчивающийся точкой (другие
символы “.” в тексте отсутствуют). Требуется написать программу, которая будет определять и
выводить на экран английскую букву,
встречающуюся в этом тексте чаще всего, и количество там
таких букв. Строчные и прописные буквы при этом считаются не различимыми. Если искомых букв
несколько, то программа должна выводить на экран первую из них по алфавиту. Например, пусть
файл содержит с
ледующую запись:
It is not a simple task. Yes!
Чаще всего здесь встречаются буквы I, S и T (слово Yes в подсчете не учитывается, так как
расположено после точки). Следовательно, в данном случае программа должна вывести два
символа, разделенных пробелом:
РЕШЕНИЕ НА PASCALABC

c, max_char :char;

frequency :array['a'..'z'] of integer;

max_frequency :integer;

for c := 'a' to 'z' do
frequency[c] := 0;

Read(c);

�while (c '.') do

begin
if LowerCase(c) in ['a'..'z', 'A'..'Z
frequency[LowerCase(c)] += 1;
Read(c);

end;

max_frequency := 0;

for c := 'a' to 'z' do
�if frequency[c] max_frequency then
begin
max_frequency := frequency[c];
max_char := c;
end;

Writeln(UpperCase(max_char)

РЕШЕНИЕ НА PYTHON

if
char == '.':
break

char = char.upper()

if 'A' = char = 'Z':
�if frequency[i] max_frequency:
max_frequency = frequency[i]
max_

ЗАДАЧА 3
На вход программы подается 366 строк, которые содержат информацию о среднесуточной
температуре всех дней 2008 года. Формат каждой из строк следующий: сначала записана дата в
виде dd.mm (на запись номера дня и номера месяца в числовом формате отводится строго два
символа, день от месяца отделен точкой), затем через пробел записано значение температуры
число со знаком плюс или минус, с точностью до 1 цифры после десятичной точ
ки. Данная
информация отсортирована по значению температуры, то есть хронологический порядок нарушен.
Требуется написать программу на языке Паскаль или Бейсик, которая будет выводить на экран
информацию о месяце (месяцах), среднемесячная температура у кото
рого (которых) наименее
отклоняется от среднегодовой. В первой строке вывести среднегодовую температуру. Найденные
значения для каждого из месяцев следует выводить в отдельной строке в виде: номер месяца,
значение среднемесячной температуры, отклонение от
среднегодовой температуры.
РЕШЕНИЕ НА PASCALABC

average_for_month :array[1..12] of double := (0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

m
onth :integer;

temperature, average_for_year, difference, min_difference :double;



c :char;

for var i := 1 to N do

begin
//dd.mm temperature
read(month);
readln(temperature);
a
verage_for_month[month] += temperature;

end;


average_for_year := 0;

for month := 1 to 12 do
average_for_year += average_for_month[month];

average_for_year /= N;


for month := 1 to 12 do
average_for_month[month] /= days_in_month[month];


min_difference := abs(average_for_month[1]

average_for_year);

for month := 2

begin
difference := abs(average_for_month[month]

average_for_year);
if difference min_difference then
min_difference := difference;

end;


Writeln(average_for_year);


for month := 1 to 12 do

begin
difference := average_for_month[month]

average_for_year;
if abs(difference) = min_difference then
Writeln(month, ' ', average_for_month[month], ' ', dif

end;

РЕШЕНИЕ НА PYTHON
#dd.mm temperature
date, temperature = input().split()
day, month = date.split('.')
temperature = float(temperature)
month = int(month)

1 #January
average_for_month[month] += temperature
average_for_month[month] /= days_in_month[month]

average_for_year)
differe

average_for_year)
if difference min_difference:
min_difference = difference

difference = average_for_month[month]

average_for_year
if abs(difference) == min_difference:
print(month + 1, average_for_month[month], difference)
Символьный тип данных в Pascal
Символьный тип
В зависимости
от компилятора Pascal символьный тип char занимает 1 или 2 байта. В компиляторе
FreePascal, Borland Pascal, Turbo Pascal и других традиционных компиляторах
1 байт. В
Строковый тип
Строки имеют тип string, состоят из набора
последовательно расположенных символов char и
используются для представления текста.
В компиляторах FreePascal, Borland Pascal, Turbo Pascal строка имеет максимальную длину 255. В
PascalABC.NET строки могут иметь произвольную длину. К символам в строке мож
но обращаться,
используя индекс: s[i] обозначает i
тый символ в строке, нумерация начинается с единицы. Если
индекс i выходит за пределы длины строки, то генерируется исключение.
Операция + для строк означает конкатенацию (слияние) строк. Например: 'Петя'
+ 'Маша' =
'ПетяМаша'.
Для описания строк заданного конечного размера используется тип string[n], где n
константа
целого типа, указывающая длину строки.
Функции Ord и Chr
Для преобразования между символами и их кодами в кодировке Windows (CP1251) исполь
зуются
стандартные функции Chr и Ord:
функция, возвращающая символ с кодом n в кодировке Windows;
функция, возвращающая значение типа byte, представляющее собой код символа c в
кодировке Windows.
Обработка кода символа
ПОЛУЧЕНИЕ ЧИСЛОВОГО
ЗНАЧЕНИЯ ЦИФРЫ

ПОЛУЧЕНИЕ ЗАДАННОЙ Б
УКВЫ АЛФАВИТА
Сортировка методом пузырька
Перед тем, как излагать этот метод сортировки, внимательно прислушаемся к одному небольшому
примечанию.
Массив упорядочен по возрастанию, если меньшие числа в нем стоят раньше
больших.
Чем меньше число, тем раньше оно должно стоять в массиве, чем больше чи
сло
тем
позже. Другими словами, чем больше число, тем больше его номер в массиве (индекс).
Если мы последовательно рассмотрим все пары соседних чисел, и в каждой из них это свойство
выполняется, то массив можно считать упорядоченным.
Именно на этом и баз
ируется основная идея сортировки методом пузырька (также называемого
методом обмена). Будем сравнивать пары соседних элементов массива. Если в какой
то паре
большее число стоит левее меньшего, то их надо поменять местами.
Рассмотрим работу метода на приме
ре. Пусть дан массив из 6 целых чисел, которые необходимо
расположить в порядке возрастания.
4 3 5 8 6 2
Двигаться будем слева направо (хотя это не принципиально).
Шаг 1
. Сравним 4 и 3. Число 4 больше (а значит должно стоять правее)
меняем местами эти
лементы. Новый массив:
3 4 5 8 6 2
Независимо от того, меняли мы местами элементы или нет
просто переходим к следующей
паре.
Шаг 2
. Сравним 4 и 5. Числа в паре стоят в «правильном» порядке
меньшее левее большего.
Ничего не делаем с этими элементами. Ма
ссив остается:
4 3 5 8 6 2
Переходим к следующей паре.
Шаг 3
. Сравниваем 5 и 8. Эти числа также стоят в «правильном» порядке, поэтому массив не
изменяется:
4 3 5 8 6 2
Берем следующую пару.
Шаг 4
. Сравниваем 8 и 6. Здесь большее число стоит левее меньшего,
поэтому меняем числа
местами, получаем новый массив:
4 3 5 6 8 2
Переходим к следующей паре.
Шаг 5
. Сравниваем 8 и 2.Опять большее число левее меньшего
переставляем числа.
4 3 5 6 2 8
Пары закончились.
Правда, массив пока мало похож на отсортированный.
Однако, можно сделать одно важное
наблюдение:
после полного прохода по массиву хотя бы одно число (а именно
самое
большое) будет поставлено на свое место
. Именно поэтому этот метод носит название «метод
пузырька» или просто «пузырек». Наибольшее число,
как пузырек из глубины стакана с
газировкой, «всплывает» на поверхность (на последнее место в массиве) и остается там.
Теперь, если мы сделаем второй проход по массиву, то еще одно число встанет на свое место (а
может быть и не одно, но об этом чуть позже)
. Значит, чтобы гарантированно получить
отсортированный массив, надо сделать столько проходов, сколько элементов в массиве.
Впрочем, достаточно сделать
проход, потому что когда все числа кроме одного будут на своих
местах, последнее тоже само собой ок
ажется на своем месте.
Итак, мы выяснили, что для успешной сортировки надо сделать
проход, по
сравнению на
каждом проходе. Таким образом структура программы
двойной цикл. Внешний цикл
по
количеству проходов, внутренний
по тем парам
элементов, которые мы сравниваем.
РЕАЛИЗАЦИЯ СОРТИРОВК
И МАССИВА МЕТОДОМ ПУ
ЗЫРЬКА НА ЯЗЫКЕ PYTH
ON


РЕАЛИЗАЦИЯ СОРТИРОВК
И МАССИВА МЕТОДОМ ПУ
ЗЫРЬКА НА ЯЗЫКЕ PASC

massiv = array[1..1000] of longint;

a: massiv;

i, n: longint;

i, j: longint;

for j := 1 to n

1 do



for i := 1 to n

1 do





�if a[i] a[i + 1] then








swap(a[i], a[i + 1]);

readln(n);

for i := 1 to n do



read(a[i]);

bubbleSort(a);

for i := 1 to n do



write(a[i], ' ');

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

PASCAL:

i, j: longint;

for j := 1 to n

1 do



for i := 1 to n

j do





�if a[i] a[i + 1] then








swap(a[i], a[i + 1]);

Количество операций (а вместе с ним и время работы) нам удалось сократить вдвое. Хотя,
следует признать, что оценка времени работы алгоритма все еще составляет
Второе соображение для оптимизации метода простого обмена основано на таком утверждении:
если за полный проход в массиве не сделано ни одной перестановки, то его можно считать
отсортированным. Что значит «не сделано ни одной перестановки»? Это значит, что все пары
соседних чисел расположены «правильно», то есть большее число идет позже меньше
го, поэтому
они в перестановках не нуждаются. Это позволяет значительно сократить время в случаях, когда
более или менее повезло с исходными данными.
Например, в массиве 8, 1, 2, 3, 4, 5, 6 будет вообще достаточно одного прохода, чтобы вытолкнуть
восьмерку
на последнее место.
Существенных изменений в структуре программы не будет
как был двойной цикл, так и остался.
Просто внешний цикл будет заменен на цикл с условием. Программа в этом случае может
выглядеть, например, так:
PYTHON:
j = len(A)

1

IsNotOrdered = True
while IsNotOrdered:
IsNotOrdered = False
for i in range(0, j):
�if A[i] A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i]
IsNotOrdered = True
j
-
= 1

PASCAL:

i, j: longint;

isNotOrdered: boolean;

isNotOrdered := true;

j := n

1;

while isNotOrdered do


begin



isNotOrdered := false;



for i := 1 to j do





�if a[i] a[i + 1] then begin







swap(a[i], a[i + 1]);







isNotOrdered := true;





end;



dec(j);

end;

Стоит заметить, что в худшем случае (а именно, если на входе дан массив, упорядоченный в
другую сторону) время работы все равно будет составлять
и по
количеству операций
сравнения программа не будет отличаться от предыдущего примера.
Есть различные алгоритмы, построенные на основе пузырьковой сортировке. Например, в
шейкерной сортировке внутренний цикл проходится поочередно слева направо, затем справа
алево. А в сортировке Шелла элементы переставляются не соседние элементы, а элементы,
отстоящие на большее расстояние, что позволяет быстрее перемещать элементы по списку,
выполняя сразу несколько шагов.
Частотный анализ и взлом алфавитной замены
Шерлок Хо
лмс в рассказе «Пляшущие человечки» проявляет себя как криптоаналитик, разгадав
шифр алфавитной замены при помощи
частотного анализа
Частотный анализ основывается на предположении о существовании нетривиального
статистического распределения отдельных
символов и их последовательностей как в открытом
тексте, так и в шифротексте, которое, с точностью до замены символов, будет сохраняться в
процессе шифрования и дешифрования.
Упрощённо, частотный анализ предполагает, что частота появления заданной буквы ал
фавита в
достаточно длинных текстах одна и та же для разных текстов одного языка. При этом в случае
моноалфавитного шифрования если в шифротексте будет символ с аналогичной вероятностью
появления, то можно предположить, что он и является указанной зашифров
анной буквой.
Частотный анализ будет отличаться от сортировки подсчетом отсутствием необходимости
воссоздавать отсортированный список из массива частот.
ПРИМЕР ПОИСКА ЧАСТОТ
СИМВОЛОВ В ТЕКСТЕ НА
ЯЗЫКЕ PYTHON
Программа сортировки цифр подсчётом

Freq :array[0..9] of integer;

i, N, digit :integer;

for digit := 0 to 9 do
Freq[digit] := 0;

Readln(N);

for i := 1 to N do

begin
Read(digit);
Freq[digit] += 1;

end;



for digit := 0 to 9 do

Writeln;



for digit := 0 to 9 do
for i := 1 to Freq[digit] do
Write(digit, ' ');

Write
Программа частостного анализа латинских
букв

Freq :array['a'..'z'] of integer;


i, N :integer;








begin

end;



Программа подсчёта количества чисел больше
среднего арифмет
ического


Freq :array[0..1000] of integer


i, N, number :integer;

average :real;

more_than_average :integer;

for number := 0 to 1000 do
Freq[number] := 0;

Readln(N);

for i := 1 to N do

begin
Read(number);
Freq[number] += 1;

end;



average := 0;

for number :
average += number*Freq[number];

average := average/N;



more_than_average := 0;

for number := ceil(average) to 1000 do
more_than_average += Freq[number];



nd.
Программа поиска какие школы прислали
меньше всего учеников

c :char;

school :integer;

repeat
read(c);

until c = ' ';

repeat
read(c);

until c = ' ';

Readln(school);

read_school := school;

pupil_number :array [1..99] of integer;

school, i, N :integer;

min_pupil :integer;

for school := 1 to 99 do

pupil_number[school] := 0;

Readln(

for i := 1 to N do begin
school := read_school();
pupil_number[school] += 1;

end;

min_pupil :=
1;

for school := 1 to 99 do
�if pupil_number[school] 0 then
if (pupil_number[school] min_pupil) or
(min_pupil =
1)
then
min_pupil := pupil_number[school];



for school := 1 to 99 do
if pupil_number[school] = min_pupil then
Writeln(school);
Задача 1 на занятии (сортировка)
В соревнованиях по многоборью (из M видов спорта) участвуют N
спортсменов (N < 1000) . На
вход программе в первой строке подается число спортсменов N, во второй
число видов спорта
M. В каждой из последующих N строк находится информация в следующем формате:
<Фамилия> <Имя> <Баллы>
где <Фамилия>
строка, состоящая н
е более, чем из 20 символов без пробелов, <Имя>
строка,
состоящая не более, чем из 12 символов без пробелов, <Баллы>
M целых чисел, обозначающие
количество баллов, набранных спортсменом в каждом из видов многоборья.
<Фамилия> и <Имя>, <Имя> и <Баллы>,
а также отдельные числа в поле <Баллы> разделены
ровно одним пробелом. Пример входных строк:


Иванов Сергей 100 30 78 13
Петров Антон 90 16 98 14
Сидоров Юрий 100 70 30 21
Программа должна выводить результирующую таблицу, содержащую список спортсменов,
отсортированный по убыванию суммы баллов, набранные суммы и занятые места.
В данном случае программа должна вывести
Иванов Сергей 221 1
Сидоров Юрий 221 1
Петров Антон 218 2

РЕШЕНИЕ НА PYTHON

РЕШЕНИЕ НА PASCAL
Задача 2 на занятии (три минимума и равные
третьему)
На вход программе подаются сведения о сдаче экзаменов учениками 9
классов некоторой
средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не
превосходит 100, каждая из следующих N строк имеет следующий формат:
<Фамилия> <Имя> <оценки>,
где <Фамилия>
строка, состоящая не более чем из
20 символов, <Имя>
строка, состоящая не
более чем из 15 символов, <оценки>
через пробел три целых числа, соответствующие оценкам
по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним
пробелом. Пример входной строки:
Ивано
в Петр 4 5 3
Требуется написать как можно более эффективную программу, которая будет выводить на экран
фамилии и имена трех худших по среднему баллу учеников. Если среди остальных есть ученики,
набравшие тот же средний балл, что и последний из трех худших,
то следует вывести и их
фамилии и имена.
РЕШЕНИЕ НА PASCAL
Задача 3 на занятии (три первых места)
На вход программе подаются сведения о сдаче экзаменов учениками 9
х классов некоторой
средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не
превосходит
100, каждая из следующих N строк имеет следующий формат:
<Фамилия> <Имя> <оценки>
где <Фамилия>
строка, состоящая не более чем из 20 символов, <Имя>
строка, состоящая не
более чем из 15 символов, <оценки>
через пробел три целых числа, соответствующи
е оценкам
по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним
пробелом. Пример входной строки:
Иванов Петр 4 5 3
Требуется написать как можно более эффективную программу, которая будет выводить на экран
фамилии и имена учен
иков, занявших первое, второе и третье место по среднему баллу. Учтите,
что на каждом месте может быть несколько учеников.
РЕШЕНИЕ НА PYTHON
Записи в Pascal
Запись
представляет собой набор элементов разных типов, каждый из которых имеет свое имя и
называется полем записи. Тип записи конструи
руется следующим образом:


Пример записи:













Name: string;







Age, Weight: integer;







Type:
PersonType;



end;
При описании переменной или константы типа запись можно использовать инициализатор записи
(как и в Object Pascal):






male);
Присваивание записей копирует содержимое полей одной переменной
записи в другую:
При этом слева и справа от знака присваивания используются имена записей одинакового типа.
Чтобы обратиться к отдельной компоненте записи, необходимо задать и
мя записи и через точку
указать имя нужного поля, например:
Такое имя называется
составным
Обращение к полям записей можно упростить, если воспользоваться оператором with. Он
позволяет заменить составные имена, характеризующие каждо
е поле, просто на имена полей, а
имя записи определить в операторе присоединения with:






Age := 22;



Type := female;
Такая алгоритмическая конструкция полностью идентична следующей:


Программа: вывести обладателей
наиредчайшей оценки







1000;

tPupil = record
name :string;

end;



result := '';

repeat
read(c);
result := result + c;

until c = ' ';

markFrequency :array[2..5] of in

mark, rarestMark, N :integer;

pupils :array[1..maxPupilNumber] of tPupil;

Readln(N);

for var i := 1 to N do

begin
for var k := 1 to 3 do
begin
Read(mark);
markFrequ
pupils[i].marks += [mark];
end;
Readln();

end;




rarestMark := 0;

for mark := 2 to 5 do
�if markFrequency[mark] 0 then
if (rarestMark = 0)
or (markFrequency[mark] markFreq
rarestMark := mark;




for var i := 1 to N do
if rarestMark in pupils[i].marks then
Writeln(pupils[i].name);
Программа: конечный автомат для летописи
времён года
В летописи дана последовательность времён года. Требуется писать "снять шарф", "снять шапку",
"одеть шапку", "одеть шарф" при переходах, соответственно, зима
весна, весна
лето, лето
осень,
осень
зима.
Переходы зима
зима, весна
весна, лето
лето, осень
осень
являются допустимыми, но действий
предпринимать не нужно (время года не изменилось).
Если время года перескочило, например, сразу с зимы в лето или сразу с весны на зиму, то
последовательность времён года не корректна, и это нужно вывести, а программу ост
ановить.
Записи в летописи идут по порядку и каждая в новой строке:
ПРИМЕР ВВОДА

ПРИМЕР ВЫВОДА
ПРОГРАММА

tSeason = (Winter, Spring,

seasonName :array [Winter..Autumn] of string[6] =

inputSeason :string;

season :tSeason;

Readln(inputSeason);

season := Winter;

while seas
Inc(season);

result := season;

Write(seasonName[season]);

i, N :integer;

newSeason, currentSeason :tSeason;

seasonSuccesionIsRight :boolean;

Readln(N);

seasonSuccesionIsRight := True;

currentSeason := readSeason();

for i := 1 to N do

begin
newSeason := readSeason();
case currentSeason of
Winter: if newSeason = Winter then continue
else if newSeason = Spring
currentSeason := newSeason;
end else begin
seasonSuccesionIsRight := False;
break;
end;
Spring: if newSeason = Spring then c
else if newSeason = Summer then begin
currentSeason := newSeason;
end else begin
seasonSuccesionIsRight := False;
break;
end;
Summer: if newSeason = Summer then continue
else if newSeason = Autumn then begin
currentSeason := newSeason;
end else begin
seasonSuccesionIs
break;
end;
Autumn: if newSeason = Autumn then continue
else if newSeason = Winter then begin
currentSeason := newSeason;
end else begin
seasonSuccesionIsRight := False;
break;
end;
end;

end;

if seasonSuccesionIsRight then

else
Программа: Любовь с первого взгляда
Программа "Любовь с первого взгляда"
Даны участники передачи: 6 человек.
Их параметры: имя, пол, возраст, музыка, хобби, работа,

желаемое количество детей
Двое подходят друг другу,
если:

1) разный пол

2) возраст юноши >= возраста девушки

3) желаемое количество детей отличается не более чем на 1
Юноша и девушка подходят лучше, если больше совпадает по интересам
(музыка, хобби, работа).
Задача: вывести через дефис пару, котора
я едет отдыхать вместе.

РЕШЕНИЕ НА ЯЗЫКЕ PAS
CAL


SexType = (Male, Female);

Person = record
name :string;
sex :SexType;
age :integer;
interest: array[1..3] of string;
children :integer;

end;

Read(c); Result := '';

�while c ' ' do

begin
Result := Result + c;
Read(c);

end;

Read(c);



else


begin

end;

Read(c);

Read(Result);

Read(c);

p.name :=

p.sex := ReadSex;

p.age := ReadAge;

for i := 1 to 3 do
p.interest[i] := ReadStringToSpace;

Read(p.children);

Result := True;

if a.sex = b.sex then

Result := Fals


else if (a.sex = Male) and (a.age b.age) or
�(a.sex = Female) and (a.age b.age) then
Result := False

else if abs(a.children

�b.children) 1 then
Result := False

{else


Result := 0;

for i := 1 to 3 do
if a.interest[i] = b.interest[i] then
inc(Result);

Writeln(p.name);

x, y :Person;

MaxInterest, i, k :integer;

A :array[1..6] of Person;

for i := 1 to 6 do ReadPerson(A[i]);


for i := 2 to 6 do
for k := 1 to i
1 do
if Fit(A[i], A[k]) then
if CoinsideInterest
begin
x := A[i];
y := A[k];
end;

WritePerson(x);

WritePerson(y);
Программа: Наименьшее число, произведение
цифр которого равно N
УСЛОВИЕ
Напишите программу, которая по введённому
натуральному числу N выдаёт наименьшее число M,
произведение цифр которого (в десятичной записи) равно N, или 0, если такого числа M не
существует.
ПРИМЕЧАНИЕ
Данная задача решается почти так же, как разложение на множители.

N :integer; //N = 500

digits :array[1..maxDigits] of integer;

digits_top :integer := 0;

digit :integer;

Readln(N);

for digit := 9 downto 2 do
begin

digits_top := digits_top + 1;
digits[digits_top] := digit;
N := N div digit;
end;



if N = 1 then

begin
for var i := digits_top downto 1 do
Write(dividors[i]);
Wr

end


begin

end;
Программа на занятиии №1
Имеется список результатов голосования избирателей за несколько партий,
в виде списка
названий данных партий. На вход программе в первой строке подается количество избирателей в
списке N. В каждой из последующих N строк записано название партии, за которую проголосовал
данный избиратель, в виде текстовой строки. Длина строки
не превосходит 50 символов, название
может содержать буквы, цифры, пробелы и прочие символы.
Пример входных данных:

Party one
Party two
Party three
Party three
Party two
Party three
Программа должна вывести список всех партий, встречающихся в исходном сп
иске, в порядке
убывания количества голосов, отданных за эту партию. При этом название каждой партии должно
быть выведено ровно один раз, вне зависимости от того, сколько голосов было отдано за данную
партию. Пример выходных данных для приведенного выше пр
имера входных данных:
Party three
Party two
Party one
При этом следует учитывать, что количество голосов избирателей в исходном списке может быть
велико (свыше 1000), а количество различных партий в этом списке не превосходит 10.
РЕШЕНИЕ НА PASCAL
Программа на занятии №2
Популярная газета объявила конкурс на выбор лучшего фильма, для которого стоит снять
продолжение. На выбор читателей было предложено 10 фильмов. Вам предлагается написать
эффективную, в том числе и по используемой памяти, программу, которая будет статистич
ески
обрабатывать результаты sms
голосования по этому вопросу, чтобы определить популярность
того или иного фильма. Следует учитывать, что количество голосов в списке может быть очень
велико. На вход программе в первой строчке подается количество пришедших
sms
сообщений N.
В каждой из последующих N строк записано название фильма. Пример входных данных:

Белое солнце пустыни
Бриллиантовая рука
Белое солнце пустыни
Белое солнце пустыни
Гараж
Бриллиантовая рука
Программа должна вывести список всех фильмов,
встречающихся в списке, в порядке убывания
(невозрастания) количества отданных за них голосов с указанием этого количества голосов.
Название каждого фильма должно быть выведено только один раз. Пример выходных данных для
приведенных входных данных:
Белое с
олнце пустыни 3
Бриллиантовая рука 2
Гараж 1

РЕШЕНИЕ НА PYTHON
Программа на занятии №3
Вам необходимо написать программу распознавания чисел, записанных прописью. Сначала на
вход программе подается обучающий блок, состоящий из 27 строк. Первые 9 строк содержат
слова «один», «два», …, «девять», следующие 9 строк
слова «одиннадцать», «двенад
цать», …
«девятнадцать», следующие 9 строк
слова «десять», «двадцать», …, «девяносто». Все слова
записаны маленькими русскими буквами без лишних пробелов в начале и в конце строки.
Затем на вход программе подается значение N
количество записей, которые
необходимо
обработать. Следующие N строк содержат записанные словами числа. Каждое число записано по
русски, маленькими буквами, без ошибок. Если число состоит из нескольких слов, между словами
находится ровно один пробел, лишних пробелов в начале и в кон
це строк нет.
Напишите эффективную программу, которая определит сумму тех входных чисел, которые
находятся в интервале от 1 до 99.
Размер памяти, которую использует Ваша программа, не должен зависеть от длины исходного
списка.
Перед текстом программы кратк
о опишите используемый вами алгоритм решения задачи.
Пример входных данных (обучающий блок показан в примере с сокращениями):
один
два
девяносто

двадцать восемь
два миллиона
четырнадцать
сто двадцать три
тысяча девятьсот восемьдесят четыре
Пример вых
одных данных для приведённого выше примера входных данных:

РЕШЕНИЕ НА PYTHON
Программа на занятии №4
Радиотелескоп пытается получать и анализировать сигналы из космоса. Различные шумы
переводятся в последовательность вещественные
неотрицательные числа, заданные с точностью
до 1 знака после десятичной точки. Для того чтобы описывать различные участки космоса, данные,
получаемые из одного района, было решено характеризовать числом, равным максимальному
произведению, которое можно пол
учить, перемножая значения сигналов, приходящих из этого
района. То есть требуется выбрать такое непустое подмножество сигналов (в него может войти как
один сигнал, так и все поступившие сигналы), произведение значений у которого будет
максимальным. Если т
аких подмножеств несколько, то выбрать можно любое из них.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую
версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать
результаты экспер
имента, находя искомое подмножество. Сигналов может быть очень много, но
не может быть меньше трех. Все сигналы различны.
Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.
На вход программе в первой строке подается количес
тво сигналов N. В каждой из последующих N
строк записано одно вещественное число с точностью до 1 знака после десятичной точки. Все
числа различны.
Пример входных данных:


12.3
0.1
100.2
0.3
1.4
Программа должна вывести в порядке возрастания номера
сигналов, произведение которых будет
характеризовать данную серию. Нумерация сигналов ведется с единицы.
Пример выходных данных для приведенного выше примера входных данных:
1 3 5

РЕШЕНИЕ НА PASCAL
Сортировка методом пузы
рька
Перед тем, как излагать этот метод сортировки, внимательно прислушаемся к одному небольшому
примечанию.
Массив упорядочен по возрастанию, если меньшие числа в нем стоят раньше
больших.
Чем меньше число, тем раньше оно должно стоять в массиве, чем
больше число
тем
позже. Другими словами, чем больше число, тем больше его номер в массиве (индекс).
Если мы последовательно рассмотрим все пары соседних чисел, и в каждой из них это свойство
выполняется, то массив можно считать упорядоченным.
Именно на э
том и базируется основная идея сортировки методом пузырька (также называемого
методом обмена). Будем сравнивать пары соседних элементов массива. Если в какой
то паре
большее число стоит левее меньшего, то их надо поменять местами.
Рассмотрим работу метода
на примере. Пусть дан массив из 6 целых чисел, которые необходимо
расположить в порядке возрастания.
4 3 5 8 6 2
Двигаться будем слева направо (хотя это не принципиально).
Шаг 1
. Сравним 4 и 3. Число 4 больше (а значит должно стоять правее)
меняем мест
ами эти
элементы. Новый массив:
3 4 5 8 6 2
Независимо от того, меняли мы местами элементы или нет
просто переходим к следующей
паре.
Шаг 2
. Сравним 4 и 5. Числа в паре стоят в «правильном» порядке
меньшее левее большего.
Ничего не делаем с этими
элементами. Массив остается:
4 3 5 8 6 2
Переходим к следующей паре.
Шаг 3
. Сравниваем 5 и 8. Эти числа также стоят в «правильном» порядке, поэтому массив не
изменяется:
4 3 5 8 6 2
Берем следующую пару.
Шаг 4
. Сравниваем 8 и 6. Здесь большее число стоит л
евее меньшего, поэтому меняем числа
местами, получаем новый массив:
4 3 5 6 8 2
Переходим к следующей паре.
Шаг 5
. Сравниваем 8 и 2.Опять большее число левее меньшего
переставляем числа.
4 3 5 6 2 8
Пары закончились.
Правда, массив пока мало похож на от
сортированный. Однако, можно сделать одно важное
наблюдение:
после полного прохода по массиву хотя бы одно число (а именно
самое
большое) будет поставлено на свое место
. Именно поэтому этот метод носит название «метод
пузырька» или просто «пузырек».
Наибольшее число, как пузырек из глубины стакана с
газировкой, «всплывает» на поверхность (на последнее место в массиве) и остается там.
Теперь, если мы сделаем второй проход по массиву, то еще одно число встанет на свое место (а
может быть и не одно, но о
б этом чуть позже). Значит, чтобы гарантированно получить
отсортированный массив, надо сделать столько проходов, сколько элементов в массиве.
Впрочем, достаточно сделать
проход, потому что когда все числа кроме одного будут на своих
местах, последнее
тоже само собой окажется на своем месте.
Итак, мы выяснили, что для успешной сортировки надо сделать
проход, по
сравнению на
каждом проходе. Таким образом структура программы
двойной цикл. Внешний цикл
по
количеству проходов, внутренний
по т
ем парам элементов, которые мы сравниваем.
РЕАЛИЗАЦИЯ СОРТИРОВК
И МАССИВА МЕТОДОМ ПУ
ЗЫРЬКА НА ЯЗЫКЕ PYTH
ON


РЕАЛИЗАЦИЯ СОРТИРОВК
И МАССИВА МЕТОДОМ ПУ
ЗЫРЬКА НА ЯЗЫКЕ PASC

massiv = array[1..1000] of longint;

a: massiv;

i, n: longint;

i, j: longint;

for j := 1 to n

1 do



for i :=

1 do





�if a[i] a[i + 1] then








swap(a[i], a[i + 1]);

readln(n);

for i := 1 to n do



read(a[i]);

bubbleSort(a);

for i := 1 to n do



write(a[i], ' ');

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

PASCAL:

i, j: longint;

for j := 1 to n

1 do



for i := 1 to n

j do





�if a[i] a[i + 1] then








swap(a[i], a[i + 1]);

Количество операций (а вместе с ним и время работы) нам удалось сократить вдвое. Хотя,
следует признать, что оценка времени работы
алгоритма все еще составляет
Второе соображение для оптимизации метода простого обмена основано на таком утверждении:
если за полный проход в массиве не сделано ни одной перестановки, то его можно считать
отсортированным. Что значит «не сделано ни
одной перестановки»? Это значит, что все пары
соседних чисел расположены «правильно», то есть большее число идет позже меньшего, поэтому
они в перестановках не нуждаются. Это позволяет значительно сократить время в случаях, когда
более или менее повезло с
исходными данными.
Например, в массиве 8, 1, 2, 3, 4, 5, 6 будет вообще достаточно одного прохода, чтобы вытолкнуть
восьмерку на последнее место.
Существенных изменений в структуре программы не будет
как был двойной цикл, так и остался.
Просто внешний ц
икл будет заменен на цикл с условием. Программа в этом случае может
выглядеть, например, так:
PYTHON:
j = len(A)

1

IsNotOrdered = True
while IsNotOrdered:
IsNotOrdered = False
for i in range(0, j):
�if A[i] A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i]
IsNotOrdered = True
j
-
= 1

PASCAL:

i, j: longint;

isNotOrdered: boolean;

isNotOrdered := true;

j := n

1;

while isNotOrdered do


begin



isNotOrdered := false;



for i := 1 to j do





�if a[i] a[i + 1] then begin







swap(a[i], a[i + 1]);







isNotOrdered := true;





end;



dec(j);

end;

Стоит заметить, что в худшем случае
(а именно, если на входе дан массив, упорядоченный в
другую сторону) время работы все равно будет составлять
и по количеству операций
сравнения программа не будет отличаться от предыдущего примера.
Есть различные алгоритмы, построенные на основе пузырьковой сортировке. Например, в
шейкерной сортировке внутренний цикл проходится поочередно слева направо, затем справа
налево. А в сортировке Шелла элементы переставляются не соседние элементы, а элементы
,
отстоящие на большее расстояние, что позволяет быстрее перемещать элементы по списку,
выполняя сразу несколько шагов.
Частотный анализ и взлом алфавитной замены
Шерлок Холмс в рассказе «Пляшущие человечки» проявляет себя как криптоаналитик, разгадав
шифр
алфавитной замены при помощи
частотного анализа
Частотный анализ основывается на предположении о существовании нетривиального
статистического распределения отдельных символов и их последовательностей как в открытом
тексте, так и в шифротексте, которое, с
точностью до замены символов, будет сохраняться в
процессе шифрования и дешифрования.
Упрощённо, частотный анализ предполагает, что частота появления заданной буквы алфавита в
достаточно длинных текстах одна и та же для разных текстов одного языка. При эт
ом в случае
моноалфавитного шифрования если в шифротексте будет символ с аналогичной вероятностью
появления, то можно предположить, что он и является указанной зашифрованной буквой.
Частотный анализ будет отличаться от сортировки подсчетом отсутствием необ
ходимости
воссоздавать отсортированный список из массива частот.
ПРИМЕР ПОИСКА ЧАСТОТ
СИМВОЛОВ В ТЕКСТЕ НА
ЯЗЫКЕ PYTHON
Программа на занятии №1
Гоночная трасса состоит из двух основных дорог и нескольких переездов,
позволяющих перейти с одной дороги на другую. На всех участках, включая
переезды, движение разрешено только в одну сторону, поэтому переезд
возможен только с дороги A на дорогу B. Гонщи
к стартует в точке A0 и
должен финишировать в точке BN. Он знает, за какое время сможет пройти
каждый участок пути по каждой дороге, то есть время прохождения участков
A0A1, A1A2, …, AN
1AN, B0B1, B1B2, …, BN
1BN. Время прохождения всех
переездов A0B0, A1B
1, …, ANBN одинаково и известно гонщику. Необходимо
определить, за какое минимальное время гонщик сможет пройти трассу.
Напишите эффективную,в том числе по используемой памяти, программу
для решения этой задачи.
Перед текстом программы кратко опишите алго
ритм решения и укажите
язык программирования и его версию.
ВХОДНЫЕ ДАННЫЕ
В первой строке задаётся количество участков трассы N. Во второй строке
задаётся целое число t
время (в секундах) прохождения каждого из
переездов A0B0, A1B1, …, ANBN. В каждой из
последующих N строк записано
два целых числа ai и bi, задающих время (в секундах) прохождения
очередного участка на каждой из дорог. В первой из этих строк указывается
время прохождения участков A0A1 и B0B1, во второй
A1A2 и B1B2 и т.д.
ВЫХОДНЫЕ ДАННЫЕ
Программа должна на печатать одно целое число: минимально возможное
время прохождения трассы (в секундах).
ПРИМЕР ВХОДНЫХ ДАННЫ


320 150
200 440
300 210
ПРИМЕР ВЫХОДНЫХ ДАНН

РЕШЕНИЕ НА PYTHON (Н
Е ЭФФЕКТИВНОЕ ПО ПАМ
ЯТИ)

РЕШЕНИЕ НА PYTHON (Э
ФФЕКТИВНОЕ)
Программа на занятии №2
Найти количество автомобилистов, которые
предпочитают такой же автомобиль, как Путин. В
списке ровно один человек с фамилией Путин. У каждого автовладельца не более одного
автомобиля одной марки. Фамилии у всех автовладельцев различаются.
Данные о автовладельцах сохранены в следующем формате:
Фам
илия Марка машины
Список не упорядочен.
Количество опрошенных N может быть больше 100000, однако различных марок машин в данном
списке не более 1000. Фамилия не содержит пробела, а марка машины может содержать один или
несколько пробелов. Число N вводится
в первой строке.
ПРИМЕР ВВОДА

Иванов Бентли
Миронов Лада Калина
Николаев Мерседес
Прохоров Ё
мобиль
Путин Лада Калина
Тарасова Мерседес
ПРИМЕР ВЫВОДА:

РЕШЕНИЕ НА PYTHON
Программа на занятии №3
Хакер Вася заснифферил текстовое содержание HTTP протокола Иры с сайтом Вк
онтакте.
В этих сообщениях в зашифрованном виде при помощи шифра Цеpаря передается пароль.
Он выделил пароли, но Ира часто ошибается в пароле, поэтому их довольно много.
Вася хочет проанализировать пароли по частоте, найти три наиболее популярные, и
расш
ифровать их, зная, что первый символ
латинское 'a'.
Шифр Цезаря состоит в циклическом сдвиге букв в рамках некоторого алфавита, в данном случае
в рамках латинского алфавита от a до z.
Помогите Васе осуществить криптоанализ собранных данных.
В пароле ис
пользуются только строчные латинские буквы.
ПРИМЕР ВВОДА

qwer
lkjh
lkjh
wert
qwer
piou
xcvb
wert
wert
lkjh
ПРИМЕР ВЫВОДА
aivx
azyw

РЕШЕНИЕ НА PYTHON

РЕШЕНИЕ НА PASCAL
Обход графа в глубину с подсчётом компонент
связности
N =
G = {}
for i in range(N):
a, b, weight = input().split()
if a not in G:
G[a] = {}
G[a][b] = float(weight)
if b not in G:
G[b] = {}
G[b][a] = flo
vertexes = sorted([a for a in G])
print(end = '
t')
print(*vertexes, sep = '
t')
for a in vertexes:
print(a, e
t')
for b in vertexes:
if b in G[a]:
print(G[a][b], end = '
t')
else:
print(end = '
t')
print()
called.add(x)
for friend in G[x]:
if friend not in called:
print(x, friend)
callFriends(G, called, friend)
components_number = 0
for vertex in G:
if vertex not in called:
components_
callFriends(G, called, vertex)
Демонмонстрационный вариант ЕГЭ по
информатике
Часть А

Дано:
235
. Какое из чисел K, записанных в троичной системе счисления,
удовлетворяет неравенству
21012
22101
21020

21100
А2.
Между
населёнными пунктами A,B,C,D,E,F построены дороги, протяжённость которых приведена в
таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно
только по построенным дорогам).

15


16


17


20

А3.
Дан фрагмент таблицы истинности выражения F.
Какое выражение соответствует F?


x


x


x


x
А4.
В каталоге находятся файлы со следующими именами:
Ishtar.jpeg
katana.jpg
katana.jar
krakatau.jpg
potato.jpeg
putasu.jpeg
taxi.jpg
Определите, по какой из масок будет выбрана указанная группа файлов:
Ishtar.jpeg
katana.jpg
krakatau.jpg
potato.jpeg
putasu.jpeg
?*ta*?.jp*
*?ta*?.j*
*?ta?*.jp?

*ta*.jp*
А5.
Автомат получает на вход трехзначное
десятичное число. По этому числу строится новое число по
следующим правилам.
Перемножаются первая и вторая, а также вторая и третья цифры числа.
Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).
Пример.
Исходное
число: 157. Произведения: 1*5=5, 5*7=35. Результат: 535.
Определите, какое из предложенных чисел может быть результатом работы автомата.

1214


1612


2433


244

А6.
Ниже приведены фрагменты таблиц базы данных канцелярского магазина. За какую самую низкую
цену
в магазине можно купить карандаш?
Изделие
Артикул
Авторучка
Фломастер
Карандаш
Фломастер
Авторучка
Карандаш
Артикул
Размер
Цвет
Цена
красный
синий
синий
синий
зеленый
зеленый
синий
красный
красный
А7.
На рисунке приведен фрагмент электронной таблицы. Какое число появится в ячейке C4, если
скопировать в нее формулу из ячейки D3? В D3 формула

8


18


21


26

А8.
Производится одноканальная (моно) звукозапись с частотой дискретизации 256 Гц. При записи
использовались 4096 уровней дискретизации. Запись длится 10 минут, её результаты
записываются в файл, причём каждый сигнал
кодируется минимально возможным и одинаковым
количеством битов. Какое из приведенных ниже чисел наиболее близко к размеру полученного
файла, выраженному в килобайтах?

16


25


64


225

А9.
По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б,
В, Г. Для кодирования
букв А, Б, В используются 5
битовые кодовые слова: А
00101, Б
01011, В
10110. Для этого
набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее
чем в трёх позициях. Это свойство важно для расш
ифровки сообщений при наличии помех. Какое
из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство
выполнялось для всех четырёх кодовых слов?
10000
01110
11000
не подходит ни одно из указанных выше слов
А10.
На числовой
прямой даны три отрезка: P = [5,10], Q = [15,20] и R=[25,30]. Выберите такой интервал
A, что формулы
)→(
)→(
тождественно равны, то есть принимают равные значения при любом значении переменной х (за
исключением, возможно, конечного числа
точек).
[5, 10]
[15, 20]
[10, 20]
[15, 25]
А11.
Для регистрации на сайте некоторой страны пользователю необходимо придумать пароль длиной
ровно 15 символов. В пароле можно использовать десятичные цифры и 11 различных символов
местного алфавита, причем
все буквы используются в двух начертаниях
строчные и прописные.
Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый
пароль
одинаковым и минимально возможным количеством байт. Определите объем памяти,
необходимый для хра
нения 30 паролей.
360 байт
450 байт
330 байт
300 байт
А12.
В программе описан одномерный целочисленный массив A с индексами от 0 до 10. Ниже
представлен фрагмент этой программы, в котором значения элементов массива сначала
задаются, а затем меняются.
for
i:=0 to 10 do





A[i]:=3*i;

for i:=1 to 10 do





A[i]:=A[i] mod 3;

Чему будут равны элементы этого массива?
Все элементы будут равны 3.
Все элементы будут равны 1.
Все элементы будут равны 0.
Все элементы будут равны своим индексам.
А13.
Сколько
клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную
ниже программу, РОБОТ уцелеет (не врежется в стену) и остановится в той же клетке, с которой
он начал движение?

1


2


3


4





Ответы:
А1.3
А2.1
А3.3
А4.1
А5.2
А6.5
А7.2
А8.4
А9.3
А10.1
А11.4
А12. 3
А13. 2
Часть B
В1.
Исполнитель ПОДВИГАТОР имеет только две команды, которым присвоены номера:
Умножь на 2
Умножь на 4
Выполняя команду номер 1, ПОДВИГАТОР прибавляет к числу на экране 1, а выполняя команду
номер 2, умножает число на экране на 2. Укажите минимальное число команд, которое должен
выполнить исполнитель, чтобы получить из числа 32 число
4096.

3


4


5


6

В2.
Определите значение переменной с после выполнения следующего фрагмента программы:


10* b else


70


80


90


100

В3.
В электронной таблице записаны данные о количестве
участников
региональных олимпиад:
Воронеж
Тула
Курск
Смоленск
Физика
Химия
История
Биология
Выберите диаграмму, которая отражает количественный состав участников из разных городов (на
диаграмме
название города обозначено первой буквой его названия):

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

60


62


64


66

В5.
Определите, что будет напечатано в результате работы следующего фрагмента программы:

n := 4;

s := 15;

while s = 250 do begin



s
s + 12;



n := n + 2

end;


write(n) end.

39


40


42


44

В6.
Алгоритм вычисления значения функции F(n), где n
натуральное число, задан следующими
соотношениями:
Чему равно значение функции F(0)?
В7.
Десятичное число 71 в некоторой системе счисления записывается как «78». Определите
основание системы счисления.

9


10


11


12

В8.
Ниже записана программа. Получив на вход число x, эта программа печатает два числа, a
и b.
Укажите наименьшее из таких
чисел , при вводе которых алгоритм печатает сначала 3, а потом 12.

readln(x);


a:=0; b:=1;

�while x0 do begin


a:=a+1;




b:=b*(x mod 7);



x:= x div 3

end;


writeln(a); write(b);
В9.
На рисунке
схема дорог,
связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно
двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей
из города А в город К?

12


15


16


20

В10.
Документ объёмом 20 Мбайт можно передать с
одного компьютера на другой двумя способами:
А. Сжать архиватором, передать архив по каналу связи,
распаковать.
Б. Передать по каналу связи без использования архиватора.
Какой способ быстрее и насколько, если:
средняя скорость передачи данных по каналу
связи составляет 220 бит в секунду;
объём сжатого архиватором документа равен 20%
исходного;
время, требуемое на сжатие документа,
5 секунд, на распаковку
1 секунда?
В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу
после
буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого.
Так, например, если способ Б быстрее способа А на 50 секунд, в ответе нужно написать Б50.
Единицы измерения «секунд», «сек.», «с.» к ответу добавлять не нужно.
A106

122

А48
Б2
В11.
В терминологии сетей TCP/IP маской подсети называется 32
разрядное двоичное число,
определяющее, какие именно разряды IP
адреса компьютера являются общими для всей подсети
в этих разрядах маски стоит 1. Обычно маски записываются в виде че
тверки десятичных чисел
по тем же правилам, что и IP
адреса. Для некоторой подсети используется маска 255.255.254.0.
Сколько различных адресов компьютеров теоретически допускает эта маска, если два адреса
(адрес сети и широковещательный) не используют?

1
04


110


115


126

В12.
В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим
запросам в некотором сегменте Интернета:
Запрос
Количество
страниц
(тыс.)
март & май
472
май & апрель
май & (март | апрель)
Сколько
страниц (в тысячах) будет найдено по запросу *март & апрель & май*

277


2200


3400


370

В13
У исполнителя ПОДВИГАТОР две команды, которым присвоены номера:
Умножь на 2
Умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 65536?

377


879


987


1596

В14.
Определите, какое число будет напечатано в результате выполнения следующего алгоритма:

F := 15*(5+x)*(5+x)+125;

a :=
25; b := 25;



M := a; R := F(a);

for t := a
�if F(t) R then begin
M := t;

R := F(t);
end;

end;

writeln(M);

27


127


25


131

В15.
Сколько различных решений имеет система уравнений?
) = 1
) = 1
) = 1
где
,…,
логические переменные? В ответе не нужно перечислять все различные наборы
значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать
количество таких наборов.

121


36


84


215

Ответы
В1.2
В2.3
В3.3
В4.2
В5.4
В6.7
В7.1
В8.11
В9.4
В10.2
В11.4
В12.1
В13. 4
В14.3
В15.1
Часть С.
С1.
Требовалось написать программу, которая вводит с клавиатуры координаты точки на плоскости (x,
действительные числа) и определяет принадлежность точки заштрихованной области, включая
ее границы. Программист торопился и написал программу неправильно. Вот
она:
2 then

if y=4
x*x then



if








else






Последовательно выполните следующее.
Перерисуйте и заполните таблицу, которая показывает,
как работает программа при аргументах,
принадлежащих различным областям (А, В, С, D и Е). Границы (точки
4, 2, 8 и 14) принадлежат
заштрихованным областям.
В столбцах условий укажите «да», если условие выполнится, «нет», если условие не выполнится,
» (п
рочерк), если условие не будет проверяться, «не изв.», если программа ведет себя по
разному для разных значений, принадлежащих данной области. В столбце «Программа выведет»
укажите, что программа выведет на экран. Если программа ничего не выводит, напишите
(прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты,
напишите «не изв.». В последнем столбце укажите «Да» или «Нет».
Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы.
С2.
Дан
массив, содержащий 70 целых чисел. Опишите на одном из языков программирования
алгоритм, позволяющий найти и вывести наименьшее содержащееся в массиве положительное
число, десятичная запись которого оканчивается цифрой 7. Гарантируется, что в массиве есть
хотя бы один положительный элемент, десятичная запись которого оканчивается цифрой 7.
Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не
описанные ниже, но разрешается не использовать часть из них.

for



readln(a[i]); … end.
С3.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки
ходят по очереди, первый ход делает Петя. За один ход игрок может до
бавить в кучу один камень
или добавить в кучу восемь камней. Например, имея кучу из 15 камней, за один ход можно
получить кучу из 16 камней или 23 камня. У каждого игрока, чтобы делать ходы, есть
неограниченное количество камней. Игра завершается в тот мом
ент, когда количество камней в
куче становится не менее 35. Победителем считается игрок, сделавший последний ход, то есть
первым получивший кучу, в которой будет 35 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 34.
При каких S: 1а) Пе
тя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?
Назовите два значения S, при которых Петя может выиграть своим вторым ходом?
Назовите два значения S, при которых Ваня выигрывает своим первым или вторым ходом?
Ответ
1а. для всех S от 27 до
1б. S = 26
2. S = 18, 25
3. S = 17, 24
С4.
Как сдать ЕГЭ по информатике на 100 баллов
До введения ЕГЭ абитуриенты должны были готовиться к экзаменам в каждый из вузов, куда
собирались подавать документы. Каждый вуз был волен устанавливать свои требования к знаниям
поступающих, критерии оценивания
знаний часто сильно различались с системой выставления
общеобразовательной школы. ЕГЭ ограничил вузы во введении своих вступительных испытаний и
сильно упростил абитуриенту жизнь,
уяснив к чему конкретно нужно готовиться по каждому из
предметов.
по случайной или объективной причине (плохо себя чувствовал, не выспался, случайно попались
неудач
ные вопросы и т. п.), мог собраться с силами и сдать экзамены в другой вуз на порядок
лучше. С ЕГЭ такое не проходит!
Согласно официальным разъяснениям о том, кто допускается к повторной сдаче ЕГЭ, в
2013 году
выпускники этого
года, получившие на ЕГЭ неудовлетворительный результат по русскому языку
или математике
абитуриенты, которые не сдавали ЕГЭ по уважительным причинам (болезнь или другие
обстоятельства, подтвержденные документально)
или другие обстоятельства, подтвержденные документально)
участники ЕГЭ, результаты которых были отменены государственной экзаменационной комиссией
(ГЭК) или федеральной экзаменационной комиссией (ФЭК), если
конфликтная комиссия
проведения ЕГЭ.
К повторной сдаче не допускаются:
выпускники, не явившиеся на экзамен без уважительной причины
участники, результаты которых были
отменены государственной экзаменационной комиссией в
связи с выявлением фактов нарушения участником госэкзамена установленного порядка
Хорошая новость
: сдать экзамен по информатике на 100 баллов можно!
Для того, чтобы Ваша умственная работа
на единственно экзамене произошла эффективно,
необходимо подготовиться: во
первых стратегически, во
вторых тактически.
знании материала.
Тактическая подготовка сос
тоит в том, чтобы быть выспавшимся, бодрым, спокойным и веселым к
началу экзамена, спланировать экзамен, иметь часы и следовать своему плану выполнения
экзамена.

Приложенные файлы

  • pdf 9603569
    Размер файла: 1 MB Загрузок: 0

Добавить комментарий