LINEBURG


страница 1
(всего 10)

ќ√Ћј¬Ћ≈Ќ»≈

—лед. стр. >>

"јлгоритмы в школьной
информатике"


—оставитель:

ёрцева —ветлана —ергеевна
гимнази€ 42
2


—ќƒ≈–∆јЌ»≈

§ 1 ¬¬≈ƒ≈Ќ»≈ ¬  ќћѕ№ё“≈–Ќ”ё јЋ√ќ–»“ћ» ” 5
јЌјЋ»« јЋ√ќ–»“ћј 6
§ 2 ѕ–»Ќ÷»ѕџ ѕ–ќ¬≈– » ”„≈ЅЌџ’ » ќЋ»ћѕ»јƒЌџ’ «јƒј„ ѕќ
»Ќ‘ќ–ћј“» ≈ 9
§ 3.„»—Ћј 11
3.1 ÷»‘–џ „»—Ћј 11
3.2 ѕ–ќ—“џ≈ „»—Ћј 12
3.2.1 ѕ–ќ—“џ≈ ƒ≈Ћ»“≈Ћ» 16
3. 3 „»—Ћј ‘»ЅќЌј„„» 16
4.1 ѕќЌя“»≈ —ќ–“»–ќ¬ » 19
4.1.1 —ќ–“»–ќ¬ ј ѕ–ќ—“џћ ќЅћ≈Ќќћ 20
4.2 ѕќ»—  ƒјЌЌџ’ 22
4.2.1 Ћ»Ќ≈…Ќџ… ѕќ»— . 22
4.2.2 Ѕ»Ќј–Ќџ… ѕќ»—  23
5.1 ѕ–яћјя Ћ»Ќ»я » ќ“–≈«ќ  ѕ–яћќ… 25
5.3 “–≈”√ќЋ№Ќ»  30
5.3.1 ѕЋќўјƒ№ ЋёЅќ√ќ “–≈”√ќЋ№Ќ» ј 30
5.3.2 «јћ≈„ј“≈Ћ№Ќџ≈ Ћ»Ќ»» » “ќ„ » “–≈”√ќЋ№Ќ» ј. 30
5.3.3 —¬ќ…—“¬ј “–≈”√ќЋ№Ќ» ќ¬. 31
5.4 ћЌќ√ќ”√ќЋ№Ќ»  32
5.4.1 ќѕ–≈ƒ≈Ћ≈Ќ»≈ ¬џѕ” Ћќ—“» ћЌќ√ќ”√ќЋ№Ќ» ј 33
5.4.2 ѕЋќўјƒ№ ѕ–ќ—“ќ√ќ ѕЋќ— ќ√ќ ћЌќ√ќ”√ќЋ№Ќ» ј 34
§6. ѕ≈–≈Ѕќ– » ћ≈“ќƒџ ≈√ќ —ќ –јў≈Ќ»я. 36
6.1 NP – ѕќЋЌџ≈ «јƒј„» 36
6.1.1 –≈Ў≈Ќ»≈ NP-ѕќЋЌџ’ «јƒј„ 36
6.1.1.1 “»ѕџ –≈ ”–—»¬Ќџ’ јЋ√ќ–»“ћќ¬ 37
6.1.2 ѕ–»ћ≈–џ NP - ѕќЋЌџ’ «јƒј„ 37
6.2 ѕ≈–≈Ѕќ– ¬ј–»јЌ“ќ¬ 39
6.3 ѕ≈–≈Ѕќ– — ¬ќ«¬–ј“ќћ 41
6.4 ѕ≈–≈Ѕќ– — ќ“—≈„≈Ќ»≈ћ ¬≈“¬≈… » — Ћ≈»¬јЌ»≈ћ ¬≈“¬≈… 41
6.5 ƒ»Ќјћ»„≈— ќ≈ ѕ–ќ√–јћћ»–ќ¬јЌ»≈ 44
6.5.1 јЋ√ќ–»“ћ ƒ»Ќјћ»„≈— ќ√ќ ѕ–ќ√–јћ»–ќ¬јЌ»я 44
6.5.2 ”—Ћќ¬»я ѕ–»ћ≈Ќ≈Ќ»я ƒ»Ќјћ»„≈— ќ√ќ ѕ–ќ√–јћћ»–ќ¬јЌ»: 45
6.5.3 –≈јЋ»«ј÷»я јЋ√ќ–»“ћј ƒѕ 45
6.5.3.1 —¬≈ƒ≈Ќ»≈ «јƒј„»   ѕќƒ«јƒј„јћ 45
6.5.3.2 ѕќЌя“»≈ –≈ ”––≈Ќ“Ќќ√ќ —ќќ“ЌќЎ≈Ќ»я 46
6.5.3.3 ѕ–ј¬»Ћ№Ќџ≈ –≈ ”––≈Ќ“Ќџ≈ —ќќ“ЌќЎ≈Ќ»я 46
6.5.3.4 »—ѕќЋ№«ќ¬јЌ»≈ “јЅЋ»÷ ƒЋя «јѕќћ»ЌјЌ»я –≈Ў≈Ќ»…
ѕќƒ«јƒј„ 47
6.5.3.6 ¬ќ——“јЌќ¬Ћ≈Ќ»≈ –≈Ў≈Ќ»я ѕќ ћј“–»÷≈ 51
6.6 ¬ќЋЌќ¬џ≈ јЋ√ќ–»“ћџ. 60
6.7 «∆јƒЌџ≈» јЋ√ќ–»“ћџ 63
6.7.1 ”—Ћќ¬»я ѕ–»ћ≈Ќ≈Ќ»я «∆јƒЌџ’» јЋ√ќ–»“ћќ¬ 63
§7. √–ј‘џ 64
7.1 ќ—Ќќ¬Ќџ≈ ѕќЌя“»я » ќѕ–≈ƒ≈Ћ≈Ќ»я 64
7.2 —ѕќ—ќЅџ ќѕ»—јЌ»я √–ј‘ќ¬: 66
7.2.1 ћј“–»÷ј —ћ≈∆Ќќ—“». 66
7.2.2 ѕ≈–≈„≈Ќ№ –≈Ѕ≈– 67
7.2.3 —ѕ»—ќ  —ћ≈∆Ќџ’ ¬≈–Ў»Ќ 67
3
7.3 ѕќЌя“»≈ ƒќ—“»∆»ћќ—“» 68
7.4 ѕќ»— »  –ј“„ј…Ў»’ ѕ”“≈… ¬ √–ј‘≈ 69
7.4.1 ѕќ»—  ¬ √Ћ”Ѕ»Ќ” 70
7.4.2 ѕќ»—  ¬ Ў»–»Ќ”. 72
7.4.3 ¬ќЋЌќ¬ќ… јЋ√ќ–»“ћ. 73
4
ѕќя—Ќ»“≈Ћ№Ќјя «јѕ»— ј.

ѕревращение программировани€ из удела немногих интеллектуалов в
отрасль промышленности современного информационного общества
предъ€вл€ет школьной информатике требовани€ по об€зательному изучению
определенных глав фундаментальной информатики. »нформатика в
современной российской школе состоит из двух локальных составл€ющих:
- алгоритмизаци€ и программирование;
- офисные и сетевые технологии.
Ќадо заметить, что изучение первой части с течением времени
потер€ло свой приоритет, хот€ нельз€ отрицать тот факт, что изучение
программировани€ полезно не только с точки зрени€ подготовки некоторых
профессиональных навыков, но и как средство развити€ операционного и
системного мышлени€.
ƒанное методическое пособие подготовлено по материалам,
используемым в курсе информатики классов профил€ “»нформатика -
математика” и зан€ти€х олимпийской сборной по программированию
гимназии є42 г.Ѕарнаула, ведущий игрок которой (√озман ƒима) принимал
непосредственное участие в отладке текстов приведенных программ.
¬ пособии большое внимание удел€етс€ оптимальности реализации
задачи с точки зрени€ оптимальности алгоритма ее решени€ (что фактически
не рассматриваетс€ в школьном курсе). ѕримеры задач реализованы на
€зыке ѕаскаль, который €вл€етс€ не только стартовым €зыком
профессионального программировани€, но и оптимален при реализации
олимпиадных задач.
–азделы пособи€ достаточно независимы, что позвол€ет их изучать
непоследовательно, при этом темы, рассматриваемые в отдельных разделах,
имеют свои сложности.  ак показывает опыт, при использовании данных
материалов следует соблюдать принцип дидактической спирали: изучать
разделы не целиком, а частично – последовательно, т.е. возвращатьс€ к
каждому разделу вс€кий раз на более глубоком уровне.
—троение всех разделов одинаково: небольшие теоретические
выкладки, по€снени€ их на примерах и задачи дл€ самосто€тельного
решени€.
ћетодическое пособие предназначено как дл€ преподавателей в
качестве материалов к уроку или дополнительным зан€ти€м, так и дл€
самосто€тельной работы увлекающихс€ программированием школьников.
5

§ 1 ¬¬≈ƒ≈Ќ»≈ ¬  ќћѕ№ё“≈–Ќ”ё јЋ√ќ–»“ћ» ”

јлгоритм должен быть определен
настолько четко, чтобы его указани€м
мог следовать даже компьютер.
ƒональд Ё. нут

ѕредметом обсуждени€ данного раздела станут алгоритмы, и следует
дать формальное определение этого пон€ти€. ¬ современной научной и
любой другой литературе, оперирующей пон€тием "информаци€", очень
много определений алгоритма, но далеко не все они могут быть применимы в
области программировани€, поэтому за основу возьмем представление об
алгоритме как описание некоторого вычислительного процесса и введем
некоторые уточнени€.
‘орма записи алгоритма (формат) и его содержание не произвольны, а
подчинены определенным ограничени€м. ‘орматы известны различные:
словесное описание, графические (блок-схема или диаграммы Ќасси-
Ўнейдермана).
¬ данном учебном пособии предпочтение отдано "первичной" форме –
словесному описанию с нумерацией шагов и дополнительными
комментари€ми.
ќпредел€ющей особенностью вычислительного процесса €вл€етс€
возможность расчленить его на отдельные, дискретные действи€. ¬торой
особенностью €вл€етс€ последовательность действий процесса,
оформленных как предписание алгоритма. ѕредписаний должно быть
конечное число, каждое из них должно быть точным и не допускать
неопределенного толковани€. “очное предписание вызывает шаг алгоритма.
¬есь процесс, включающий все шаги от начала до завершени€, должен быть
конечен. ѕроцесс должен преследовать конкретную цель, котора€, в свою
очередь, должна быть достижимой. јнализ алгоритма позвол€ет оценить, как
велико число шагов. ѕредставить алгоритм без входных и/или выходных
данных довольно затруднительно: зачем он тогда нужен?  роме входных и
выходных данных, алгоритм, как правило, предусматривает временное
формирование промежуточных данных, которые вновь поступ€т на
обработку. ѕоэтому при конструировании алгоритма необходимо строго
определить каждый его шаг, предусмотрев возможные состо€ни€ процесса и
соответствующие инструкции дл€ их обработки. “олько такой алгоритм при
неоднократном применении к одинаковым входным данным всегда приведет
к одному итогу.
¬ противоположность детерминированному (завис€щему от входных
данных), в алгоритме стохастическом заложена некотора€ неопределенность
в выборе очередной инструкции. ¬ыбор конкретной инструкции происходит
на основе веро€тностного механизма, т.е. разработчик планирует, что
6
независимо от выбранного продолжени€, конечный результат будет
удовлетвор€ть услови€м поставленной задачи.

јЌјЋ»« јЋ√ќ–»“ћј

ѕоразительно, скольким
программистам приходитс€ слишком
дорогим способом вы€сн€ть,что их
программа не может обработать
входные данные раньше, чем через
несколько дней машинного времени.
Ћучше было бы предугадать такие
случаи с помощью карандаша и бумаги.
S.E. Goodman,
S.T.Hedetniemi

јнализ алгоритма должен дать четкое представление о емкостной и
временной сложности алгоритма.
≈мкостна€ сложность - это размеры пам€ти, в которой предстоит
размещать все данные, участвующие в вычислительном процессе.   ним
относ€тс€: входные данные, промежуточные и выходна€ информаци€.
¬озможно, что не все перечисленные наборы требуют одновременного
хранени€ (возможно применение динамических структур), что позвол€ет
экономить затраты пам€ти.
¬опрос о временной трудоемкости алгоритма гораздо сложнее. ѕусть
поставлена некотора€ задача и спроектирован алгоритм ее решени€, который
описывает вычислительный процесс, завершающийс€ за конечное число
действий - шагов.
–еальное врем€ выполнени€ каждого отдельного шага зависит от
конкретного вычислительного устройства, т.е. непосредственным
участником вычислительного процесса (но не алгоритма!) €вл€етс€ ѕ 
(быстродействие и т.д.).
ј как зависит врем€ выполнени€ программы от построенного
алгоритма?
 ак известно, решение одной задачи может быть реализовано минимум
несколькими алгоритмами. Ќас интересует тот, который в сравнении с
конкурентами, нуждаетс€ в наименее продолжительном по времени
вычислительном процессе.
—корость реализации выбираемого алгоритма может существенно
зависеть от содержани€ набора входных данных. Ѕыстрый "в среднем"
механизм способен давать сбои в отдельных "плохих" случа€х. ¬ этом случае
предпочтение отдаетс€ медленному в "среднем", но надежному в худших
ситуаци€х алгоритму.
7
ƒава€ оценку быстродействи€ алгоритма, следует рассмотреть
поведение вычислительного процесса в среднем и, отдельно, в
экстремальных дл€ него услови€х.
ћоделирование "плохих" случаев всегда св€зано с содержанием самого
алгоритма:
- проверка поведени€ алгоритма на "границе" диапазона входных
данных;
- проверка на максимально больших по объему входных данных.
”мение предвидеть "нехорошие" ситуации - отличие
квалифицированного алгоритмиста от обыкновенного "кодера".
¬ насто€щее врем€ в св€зи с превращением программировани€ в
промышленную индустрию сформировалась специализаци€ "тестеры
программ", которые занимаютс€ составлением таких тестов, чтобы алгоритм
прошел через "огонь и воду".
¬ременна€ эффективность алгоритма не св€зана с качествами
определенного ѕ . –ечь идет о количестве шагов алгоритма, каждый из
которых реализуетс€ некоторым числом машинных операций. ћожно
привести такое сравнение: человек, использующий плохой алгоритм,
подобен повару, отбивающему м€со отверткой: едва съедобный и
малопривлекательный результат достигаетс€ ценой больших условий.
ѕоэтому анализ алгоритма требует такой детализации алгоритма, чтобы в
отношении отдельного шага не требовалась его дальнейша€ алгоритмическа€
проработка. ¬озможны две ситуации: либо фиксированное врем€ такого шага
определено некоторым набором простых (без циклов) команд €зыка
программировани€, либо речь идет об "укрупненном" шаге, в отношении
которого соответствующий анализ уже проводилс€ и результаты известны.

ѕ–»ћ≈–
јлгоритм обмена двух переменных A и B реализуетс€ за 3 шага,
независимо от того, к какому типу простых переменных он примен€етс€. —
точки зрени€ количества машинных операций, две разные ситуации - обмена
содержимым между переменными, занимающими одно или два машинных
слова - неравноценны. Ќо оценка алгоритмической трудоемкости это не
учитывает.

¬ременем работы алгоритма называетс€ число элементарных шагов,
которые он выполн€ет. „то считать элементарным шагом? ќдна строка
псевдокода (простой оператор) требует не более чем фиксированного числа
операций.
—уществует специальный механизм определени€ верхней оценки
временной трудоемкости алгоритма (ќ(f(n)), что означает, что число
операций алгоритма не более f(n)).
≈сли алгоритм св€зан с обработкой N входных элементов и нет
формулы дл€ быстрого вычислени€ результата, то достижение
8
эффективности ќ(n) (линейна€ функци€), следует рассматривать как
большой успех.

ѕ–»ћ≈–
»звестна€ задача о количестве счастливых шестизначных (N- значных)
билетов имеет минимум два решени€:
1. ƒл€ перебора всех шестизначных билетов дл€ каждой цифры можно
организовать свой цикл. “огда временна€ трудоемкость алгоритма
(шесть вложенных циклов) будет пор€дка ќ(N6).
2. ≈динственный цикл перебора всех билетов с определением каждой
цифры числа. ќпределение цифр числа:
- - число единиц в числе ј равно A mod 10,
- - число дес€тков в числе ј равно (A div 10) mod 10 и т.д.
¬ числе, состо€щем из 6 цифр, количество операций не превысит
6*(6+2), где 6- число операций определени€ цифр, а 2- операции сравнени€
сумм цифр.
ƒл€ N цифр: - трудоемкость данного алгоритма < O(N).
”дел€€ внимание возможности оценки временной эффективности
алгоритма, стоит поискать ответ на вопрос: а насколько это нужно
практически?
¬ самом деле, вычислительный процесс должен выполн€тьс€ на
современном ѕ , который работает "довольно быстро". ѕредположим, что в
нашем распор€жении процессор, который способен осуществл€ть дес€ток
миллионов - 107 - микроинструкций за секунду (mips), а спроектированный
алгоритм требует, в среднем, по дес€ть mips на каждый свой шаг. ќчевидно,
что одной секунды машинного времени хватит на миллион - 106 -
алгоритмических шагов вычислительного процесса!

ѕ–»ћ≈–
¬ классе N учеников. –ассмотреть все возможные способы рассадки
всех N учеников на N местах.
ќбычна€ переборна€ задача. ƒл€ N=10 число вариантов N! > 3.5млн.
"’ороший" ѕ  (очень хороший!) справитс€, предположим, за 1 секунду. Ќо
дл€ N=15 времени потребуетс€ в 360360 раз больше дл€ этого же ѕ  или
более 4 суток непрерывного счета, другими словами, примен€ть алгоритм с
трудоемкостью ќ(N!) надо очень осторожно!
ќдним из подходов к решению переборной задачи заключаетс€ в том,
что в зависимости от услови€, алгоритм предусматривает некоторое
сокращение полного перебора, тем самым искусственно понижа€ его
трудоемкость.
ƒругой подход при конструировании алгоритма состоит в том, чтобы
решение исходной, сложной задачи свести к поочередному решению более
простых подзадач, т.к. совокупна€ трудоемкость решени€ подзадач намного
меньше, чем общей задачи. Ётот механизм называют методом декомпозиции
задачи и композиции решени€.
9
ћетоды, основанные на применении обоих указанных подходов,
относ€тс€ к т.н. точным алгоритмам, гарантирующим получение искомого
решени€. Ќазвать универсальными эти методы нельз€, т.к. существует много
типов задач, имеющих экспоненциальную сложность (пор€дка ќ(NN)), что
не позвол€ет "дорешать" их за разумное врем€.
¬ таких случа€х практический выход состоит в получении неточного
решени€ - т.н. приближенные алгоритмы - когда разница между двум€
последовательными приближенными решени€ми становитс€ меньше
требуемой точности. ѕримером использовани€ таких алгоритмов могут быть
задачи вычислени€ числа Pi или вычисление определенного интеграла.
  эвристическим алгоритмам относ€тс€ алгоритмы, позвол€ющие
найти некоторое, заведомо неточное, но удовлетворительное решение задачи.
Ќо в данном случае нельз€ говорить о степени "похожести" результата на
истинное решение. Ёвристический алгоритм дает "усеченное" решение путем
отсеивани€ "малосущественных" условий из постановки задачи. “акое
решение и принимаетс€ как подход€щее.


§ 2 ѕ–»Ќ÷»ѕџ ѕ–ќ¬≈– » ”„≈ЅЌџ’ » ќЋ»ћѕ»јƒЌџ’
«јƒј„ ѕќ »Ќ‘ќ–ћј“» ≈

  программе, реализующей некоторый алгоритм, можно предъ€вить
разнообразные требовани€: структурна€ запись программного кода, наличие
комментариев и т.д.
Ќо, в насто€щее врем€, в программировании дл€ проверки
правильности работы алгоритма и четкости его работы с
входными/выходными данными составл€ютс€ тесты, осуществл€ющие
проверку всех его качеств.
“есты раздел€ютс€ на группы:
1. ѕервый тест должен быть максимально прост, т.к. его цель - проверить,
работает ли программа вообще. ќбычно в качестве первого теста
используетс€ тест из услови€ задачи, который показывает верное понимание
учеником услови€ задачи и соответствие программы форматам входных и
выходных данных.
2. ¬тора€ группа тестов должна отслеживать т.н. вырожденные случаи:
- случаи, когда решение задачи или не существует (в условии задачи
должно быть сказано, что должна сообщать программа в такой
ситуации);
- случаи, коренным образом отличающиес€ от основного алгоритма
решени€, например, нулевые значени€ дл€ числовых входных
данных (при допустимости таких значений в условии), дл€
текстовых - пустой входной файл, либо последовательность из
пробелов и /или символов перевода строки;
- нарушение общности входных данных, требующих специальной
их обработки (например, дл€ квадратного уравнени€ равенство
10
нулю одного из коэффициентов приводит к рассмотрению
отдельных случаев решени€ уравнени€);
3. —ледующа€ группа тестов должна провер€ть граничные случаи, т.е. когда
входные и выходные данные принимают граничные значени€. Ќазначение
подобных тестов – обнаружить возможные программистские ошибки при
реализации даже правильного алгоритма (проверка выбора типов данных,
максимальной точности вычислений, выхода за границу массива данных,
корректности работы с динамической пам€тью и т.д.).
4. √руппа тестов, провер€юща€ правильность алгоритма решени€ задачи в
целом:
- общие тесты, которые провер€ют все ветви логической схемы
алгоритма ("испытание ветвей") - например, при использовании
алгоритмов на графах программа провер€етс€ на данных дл€
св€занного и несв€занного графа, графу без циклов, граф с пустым
множеством ребер и т.д.;
- тесты специального вида, которые провер€ют работоспособность
программы в случае специальной организации входных данных
(например, на входе - данные отсортированы, хот€ это и не
об€зательно, а алгоритм решени€ предусматривает сортировку
данных).
5. ѕри применении эвристических алгоритмов необходимы тесты,
провер€ющие верность/неверность приближенных вычислений.
6. “есты, провер€ющие эффективность используемых алгоритмов. ”проща€
алгоритм или его реализацию, учащиес€ могут неоправданно увеличивать
вычислительную сложность алгоритма, что делает его непригодным дл€
реализации (например, непрохождение по времени алгоритма полного
перебора при больших данных).
7. —лучайные тесты: максимально допустимый объем входных данных.
ƒанные тесты пишутс€ с помощью т.н. генератора и дл€ получени€
выходных данных необходима специальна€ программа, по сложности не
уступающа€ провер€емой программе.

ѕример
–ешить квадратное уравнение a*x^2+b*x+c=0, если 0<=a,b,c<=255.

¬ходной файл: через пробел A,B,C
¬ыходной файл: “Ќет решени€”, если их нет, или значени€ решений через
пробел, если они есть.

“есты:
Input.txt Output.txt
121 -1
000 0
010 0
001 Ќет решени€
11
127 254 127 -1
10 1 255 Ќет решени€
288 -2
573 Ќет решени€
156 -2 -3
13 0 3 Ќет решени€
78 134 15 -0.028 -1.689



§ 3.„»—Ћј

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

страница 1
(всего 10)

ќ√Ћј¬Ћ≈Ќ»≈

—лед. стр. >>

Copyright © Design by: Sunlight webdesign