extracted_text:
МИНИСТЕРСТВО ПРОСВЕЩЕНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Департамент образования, науки и молодежной политики
Воронежской области
Калачеевского
муниципального района

МБОУ
  Новомеловатская СОШ

РАССМОТРЕНО
Методическим объединением учителей
руководитель МО начальных классов
______________Бирюкова
  С.Г. Протокол №___
от
  "28" 082022 г.

СОГЛАСОВАНО
Заместитель директора по УВР
______________Наветняя Л.Я.
  Протокол №___
от "28" 08  2022 г.
РАБОЧАЯ ПРОГРАММА
(ID 1961787)
учебного предмета
«Технология»

УТВЕРЖДЕНО
И.о.директора
  МБОУ
Новомеловатская СОШ
______________Нерушев
  А.Н. Приказ №___
от
  "30" 082022 г.

для
1 класса начального общего образования на 2022-2023 учебный год
Составитель: Каплина Любовь Павловна
учитель начальных классов
Медвежье 2022

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Программа по учебному предмету
«Технология» включает: пояснительную записку, содержание обучения, планируемые
результаты освоения программы учебного предмета, тематическое планирование.
Пояснительная записка отражает общие цели
и задачи изучения предмета, характеристику психологических предпосылок к его
изучению младшими школьниками; место в структуре учебного плана, а также
подходы к отбору содержания, планируемым результатам и тематическому
планированию.
Содержание обучения раскрывается через
модули. Приведён перечень универсальных учебных действий — познавательных,
коммуникативных и регулятивных, формирование которых может быть достигнуто
средствами учебного предмета «Технология» с учётом возрастных особенностей обучающихся
начальных классов. В первом классе предлагается пропедевтический уровень
формирования УУД, поскольку становление универсальности действий на этом этапе
обучения только начинается. В познавательных универсальных учебных действиях
выделен специальный раздел «Работа с информацией». С учётом того, что
выполнение правил совместной деятельности строится на интеграции регулятивных
УУД (определённые волевые усилия, саморегуляция, самоконтроль, проявление
терпения и доброжелательности при налаживании отношений) и коммуникативных УУД
(способность вербальными средствами устанавливать взаимоотношения), их перечень
дан в специальном разделе — «Совместная деятельность».
Планируемые результаты включают
личностные, метапредметные результаты за период обучения, а также предметные
достижения младшего школьника за каждый год обучения в начальной школе.
ОБЩАЯ ХАРАКТЕРИСТИКА УЧЕБНОГО ПРЕДМЕТА «ТЕХНОЛОГИЯ»
Предлагаемая программа отражает вариант
конкретизации требований Федерального государственного образовательного
стандарта начального общего образования по предметной области (предмету)
«Технология» и обеспечивает обозначенную в нём содержательную составляющую по
данному учебному предмету.
В соответствии с требованиями времени и
инновационными установками отечественного образования, обозначенными во ФГОС
НОО, данная программа обеспечивает реализацию обновлённой концептуальной идеи
учебного предмета «Технология». Её особенность состоит в формировании у
обучающихся социально ценных качеств, креативности и общей культуры личности.
Новые социально-экономические условия требуют включения каждого учебного
предмета в данный процесс, а уроки технологии обладают большими специфическими
резервами для решения данной задачи, особенно на уровне начального образования.
В частности, курс технологии обладает возможностями в укреплении фундамента для
развития умственной деятельности обучающихся начальных классов.
В курсе технологии осуществляется реализация широкого
спектра межпредметных связей.
Математика — моделирование,
выполнение расчётов, вычислений, построение форм с учетом основ геометрии,
работа с геометрическими фигурами, телами, именованными числами.
Изобразительное искусство —
использование средств художественной выразительности, законов и правил
декоративно-прикладного искусства и дизайна.
Окружающий мир — природные формы и
конструкции как универсальный источник инженернохудожественных идей для
мастера; природа как источник сырья, этнокультурные традиции.
Родной язык — использование
важнейших видов речевой деятельности и основных типов учебных текстов в
процессе анализа заданий и обсуждения результатов практической деятельности.
Литературное чтение — работа с текстами для создания
образа, реализуемого в изделии.
Важнейшая особенность уроков технологии в
начальной школе — предметно-практическая деятельность как необходимая
составляющая целостного процесса интеллектуального, а также духовного и
нравственного развития обучающихся младшего школьного возраста.
Продуктивная предметная деятельность на
уроках технологии является основой формирования познавательных способностей
школьников, стремления активно знакомиться с историей материальной культуры и
семейных традиций своего и других народов и уважительного отношения к ним.
Занятия продуктивной деятельностью
закладывают основу для формирования у обучающихся социально-значимых
практических умений и опыта преобразовательной творческой деятельности как
предпосылки для успешной социализации личности младшего школьника.
На уроках технологии ученики овладевают
основами проектной деятельности, которая направлена на развитие творческих черт
личности, коммуникабельности, чувства ответственности, умения искать и
использовать информацию.
ЦЕЛИ ИЗУЧЕНИЯ УЧЕБНОГО ПРЕДМЕТА «ТЕХНОЛОГИЯ»
Основной целью предмета является
успешная социализация обучающихся, формирование у них функциональной
грамотности на базе освоения культурологических и конструкторскотехнологических
знаний (о рукотворном мире и общих правилах его создания в рамках исторически
меняющихся технологий) и соответствующих им практических умений, представленных
в содержании учебного предмета.
Для реализации основной цели и
концептуальной идеи данного предмета необходимо решение системы приоритетных
задач: образовательных, развивающих и воспитательных.
Образовательные задачи курса:
формирование общих представлений о культуре и организации
трудовой деятельности как важной
части общей культуры человека;
становление элементарных базовых знаний и представлений о
предметном (рукотворном) мире как
результате деятельности человека, его взаимодействии с
миром природы, правилах и технологиях создания, исторически развивающихся и
современных производствах и профессиях;
формирование основ чертёжно-графической грамотности, умения
работать с простейшей
технологической документацией
(рисунок, чертёж, эскиз, схема); формирование элементарных знаний и
представлений о различных материалах, технологиях их
обработки и соответствующих умений.
Развивающие задачи:
развитие сенсомоторных процессов, психомоторной координации,
глазомера через формирование
практических умений;
расширение культурного кругозора, развитие способности
творческого использования полученных
знаний и умений в практической деятельности;
развитие познавательных психических процессов и приёмов
умственной деятельности посредством
включения мыслительных операций в
ходе выполнения практических заданий; развитие гибкости и вариативности
мышления, способностей к изобретательской деятельности.
Воспитательные задачи: воспитание уважительного
отношения к людям труда, к культурным традициям, понимания
ценности предшествующих культур, отражённых в материальном
мире;
развитие социально ценных личностных качеств:
организованности, аккуратности, добросовестного
и ответственного отношения к работе, взаимопомощи, волевой
саморегуляции, активности и инициативности;
воспитание интереса и творческого отношения к продуктивной
созидательной деятельности, мотивации успеха и достижений, стремления к
творческой самореализации;
становление экологического сознания, внимательного и
вдумчивого отношения к окружающей
природе, осознание взаимосвязи
рукотворного мира с миром природы; воспитание положительного отношения к
коллективному труду, применение правил культуры
общения, проявление уважения к взглядам и мнению других
людей.
МЕСТО УЧЕБНОГО ПРЕДМЕТА «ТЕХНОЛОГИЯ» В УЧЕБНОМ ПЛАНЕ
Согласно требованиям ФГОС общее число часов на изучение
курса «Технология» в 1 классе — 33 часа (по 1 часу в неделю)

СОДЕРЖАНИЕ УЧЕБНОГО ПРЕДМЕТА

1.  Технологии, профессии
и производства
Природа как источник сырьевых ресурсов и творчества
мастеров.
Красота и разнообразие природных форм, их
передача в изделиях из различных материалов. Наблюдения природы и фантазия
мастера — условия создания изделия. Бережное отношение к природе. Общее понятие
об изучаемых материалах, их происхождении, разнообразии. Подготовка к работе.
Рабочее место, его организация в зависимости от вида работы. Рациональное
размещение на рабочем месте материалов и инструментов; поддержание порядка во
время работы; уборка по окончании работы. Рациональное и безопасное
использование и хранение инструментов.
Профессии родных и знакомых. Профессии,
связанные с изу- чаемыми материалами и производствами. Профессии сферы
обслуживания.
Традиции и праздники народов России, ремёсла, обычаи.
2.  Технологии ручной
обработки материалов
Бережное, экономное и рациональное
использование обрабатываемых материалов. Использование конструктивных
особенностей материалов при изготовлении изделий.
Основные технологические операции ручной
обработки материалов: разметка деталей, выделение деталей, формообразование
деталей, сборка изделия, отделка изделия или его деталей. Общее представление.
Способы разметки деталей: на глаз и от
руки, по шаблону, по линейке (как направляющему инструменту без откладывания
размеров) с опорой на рисунки, графическую инструкцию, простейшую схему. Чтение
условных графических изображений (называние операций, способов и приёмов
работы, последовательности изготовления изделий). Правила экономной и
аккуратной разметки. Рациональная разметка и вырезание нескольких одинаковых
деталей из бумаги. Способы соединения деталей в изделии: с помощью пластилина,
клея, скручивание, сшивание и др. Приёмы и правила аккуратной работы с клеем.
Отделка изделия или его деталей (окрашивание, вышивка, аппликация и др.).
Подбор соответствующих инструментов и
способов обработки материалов в зависимости от их свойств и видов изделий.
Инструменты и приспособления (ножницы, линейка, игла, гладилка, стека, шаблон и
др.), их правильное, рациональное и безопасное использование.
Пластические массы, их виды (пластилин,
пластика и др.). Приёмы изготовления изделий доступной по сложности формы из
них: разметка на глаз, отделение части (стекой, отрыванием), придание формы.
Наиболее распространённые виды бумаги. Их
общие свойства. Простейшие способы обработки бумаги различных видов: сгибание и
складывание, сминание, обрывание, склеивание и др. Резание бумаги ножницами.
Правила безопасной работы, передачи и хранения ножниц. Картон.
Виды природных материалов (плоские —
листья и объёмные — орехи, шишки, семена, ветки). Приёмы работы с природными
материалами: подбор материалов в соответствии с замыслом, составление
композиции, соединение деталей (приклеивание, склеивание с помощью прокладки,
соединение с помощью пластилина).
Общее представление о тканях (текстиле),
их строении и свойствах. Швейные инструменты и приспособления (иглы, булавки и
др.). Отмеривание и заправка нитки в иголку, строчка прямого стежка.
Использование дополнительных отделочных материалов.
3.  Конструирование и
моделирование
Простые и объёмные конструкции из разных материалов
(пластические массы, бумага, текстиль и
др.) и способы их создания. Общее представление о
конструкции изделия; детали и части изделия, их взаимное расположение в общей
конструкции. Способы соединения деталей в изделиях из разных материалов.
Образец, анализ конструкции образцов изделий, изготовление изделий по образцу,
рисунку. Конструирование по модели (на плоскости). Взаимосвязь выполняемого
действия и результата. Элементарное прогнозирование порядка действий в
зависимости от желаемого/необходимого результата; выбор способа работы в
зависимости от требуемого результата/замысла.
4.  Информационно-коммуникативные
технологии
Демонстрация учителем готовых материалов на информационных
носителях.
Информация. Виды информации.
Универсальные учебные действия (пропедевтический
уровень) Познавательные УУД:
ориентироваться в терминах, используемых в технологии
(в пределах изученного); воспринимать и использовать предложенную инструкцию
(устную, графическую); анализировать устройство простых изделий по образцу,
рисунку, выделять основные и
второстепенные составляющие
конструкции; сравнивать отдельные изделия (конструкции), находить сходство и
различия в их устройстве.
Работа с информацией: воспринимать информацию
(представленную в объяснении учителя или в учебнике), использовать
её в работе; понимать и
анализировать простейшую знаково-символическую информацию (схема, рисунок) и
строить работу в соответствии с ней.
Коммуникативные УУД:
участвовать в коллективном обсуждении: высказывать
собственное мнение, отвечать на вопросы,
выполнять правила этики общения: уважительное отношение к
одноклассникам, внимание к мнению другого; строить несложные высказывания,
сообщения в устной форме (по содержанию изученных тем).
Регулятивные УУД:
принимать и удерживать в процессе деятельности
предложенную учебную задачу; действовать по плану, предложенному учителем,
работать с опорой на графическую инструкцию
учебника, принимать участие в коллективном построении
простого плана действий;
понимать и принимать критерии оценки качества работы,
руководствоваться ими в процессе анализа
и оценки выполненных работ;
организовывать свою деятельность: производить подготовку к
уроку рабочего места, поддерживать
на нём порядок в течение урока,
производить необходимую уборку по окончании работы; выполнять несложные
действия контроля и оценки по предложенным критериям.
Совместная деятельность:
проявлять положительное отношение к включению в совместную
работу, к простым видам
сотрудничества; принимать участие в парных,
групповых, коллективных видах работы, в процессе изготовления изделий
осуществлять элементарное сотрудничество.
ПЛАНИРУЕМЫЕ РЕЗУЛЬТАТЫ ОСВОЕНИЯ УЧЕБНОГО ПРЕДМЕТА
«ТЕХНОЛОГИЯ» НА УРОВНЕ НАЧАЛЬНОГО ОБЩЕГО ОБРАЗОВАНИЯ

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

ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ

№
п/п

Наименование
  разделов и тем программы

Количество
  часов

Дата
  изучения

Виды
  деятельности

Виды, формы контроля

Электронные
  (цифровые) образовательные ресурсы

всего

контрольные
  работы

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

Модуль 1.
  ТЕХНОЛОГИИ, ПРОФЕССИИ И ПРОИЗВОДСТВА

1.1.

Природа
  как источник сырьевых ресурсов и творчества мастеров

1

0

1

02.09.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

1.2.

Общее
  понятие об изучаемых материалах, их происхождении, разнообразии

1

0

1

09.09.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

1.3.

Подготовка
  к работе. Рабочее место, его организация в зависимости от вида работы

2

0

2

16.09.2022 23.09.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

1.4.

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

1

0

1

30.09.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

1.5.

Традиции
  и праздники народов России, ремёсла, обычаи

1

0

1

07.10.2022

приводить примеры традиций и
  праздников народов России, ремёсел, обычаев и производств, связанных с
  изучаемыми материалами и производствами;

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

Итого по
  модулю

6

Модуль 2.
  ТЕХНОЛОГИИ РУЧНОЙ ОБРАБОТКИ МАТЕРИАЛОВ

2.1.

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

1

0

1

14.10.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.2.

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

1

0

1

21.10.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.3.

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

1

0

1

28.10.2022

в ходе
  беседы с учителем понимать смысл понятий «конструирование»,
«изделие»,
  «деталь изделия», «образец»;

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.4.

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

1

0

1

11.11.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.5.

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

1

0

1

18.11.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.6.

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

1

0

1

25.11.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.7.

Отделка
  изделия или его деталей
(окрашивание,
  вышивка, аппликация и др.)

1

0

1

02.12.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.8.

Подбор
  соответствующих инструментов и способов обработки материалов в зависимости от
  их свойств и видов изделий

1

0

1

09.12.2022

анализировать
  декоративно-художественные возможности разных способов обработки бумаги,
  например, вырезание деталей из бумаги и обрывание пальцами);

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.9.

Наиболее
  распространённые виды бумаги. Их общие свойства. Простейшие способы обработки
  бумаги различных видов: сгибание и складывание, сминание, обрывание,
  склеивание и др.

1

0

1

16.12.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.10

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

1

0

1

23.12.2022

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.11.

Пластические
  массы, их виды (пластилин, пластика и др.).

1

0

1

13.01.2023

Наблюдать и
  называть свойства пластилина (или других используемых пластических масс):
  цвет, пластичность;

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.12.

Приёмы
  изготовления изделий доступной по сложности формы из них: разметка на глаз,
  отделение части (стекой, отрыванием), придание формы

0.5

0

0.5

Использовать
  стеки при работе с пластичными материалами, а также при отделке изделия или
  его деталей;

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.13.

Виды
  природных материалов (плоские — листья и объёмные — орехи, шишки, семена,
  ветки)

0.5

0

0.5

20.01.2023

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.14.

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

1

0

1

27.01.2023

Отбирать
  природный материал в соответствии с выполняемым изделием; Называть известные
  деревья и кустарники, которым принадлежит собранный природный материал;

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.15.

Общее
  представление о тканях (текстиле), их строении и свойствах

0.5

0

0.5

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.16.

Швейные
  инструменты и приспособления
(иглы,
  булавки и др.)

0.5

0

0.5

03.02.2023

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.17.

Отмеривание
  и заправка нитки в иголку, строчка прямого стежка

0.5

0

0.5

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

2.18.

Использование
  дополнительных отделочных материалов

0.5

0

0.5

10.02.2023

Узнавать,
  называть, выполнять и выбирать технологические приёмы ручной обработки
  материалов в зависимости от их свойств;

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

Итого по
  модулю

15

Модуль 3.
  КОНСТРУИРОВАНИЕ И МОДЕЛИРОВАНИЕ

3.1.

Простые и
  объёмные конструкции из разных материалов (пластические массы, бумага,
  текстиль и др.) и способы их создания

1

0

1

24.02.2023

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

3.2.

Общее представление о конструкции
  изделия; детали и части изделия, их взаимное расположение в общей конструкции

2

0

2

03.03.2023
10.03.2023

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

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

3.3.

Способы
  соединения деталей в изделиях из разных материалов

2

0

2

17.03.2023
24.03.2023

Использовать
  в работе осваиваемые способы соединения деталей в изделиях из разных
  материалов;

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

3.4.

Образец,
  анализ конструкции образцов изделий, изготовление изделий по образцу, рисунку

1

0

1

07.04.2023

Изготавливать
  простые и объёмные конструкции из разных материалов (пластические массы,
  бумага, текстиль и др.), по модели (на плоскости), рисунку;

Устный опрос; Практическая работа;

Учи.ру
РЭШ
Электронный диск

3.5.

Конструирование
  по модели (на плоскости)

2

1

1

14.04.2023
21.04.2023

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

Контрольная
  работа; Тестирование;

Учи.ру
РЭШ
Электронный диск

3.6.

Взаимосвязь
  выполняемого действия и результата. Элементарное прогнозирование порядка
  действий в зависимости от желаемого/необходимого результата; выбор способа
  работы в зависимости от требуемого результата/замысла

2

0

2

28.04.2023 05.05.2023

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

Практическая
  работа;

Учи.ру
РЭШ
Электронный диск

Итого по
  модулю

10

Модуль 4.
  ИНФОРМАЦИОННО-КОММУНИКАТИВНЫЕ ТЕХНОЛОГИИ

4.1.

Демонстрация
  учителем готовых материалов на информационных носителях

1

0

1

12.05.2023

Анализировать
  готовые материалы, представленные учителем на информационных носителях;

Устный опрос;

Учи.ру
РЭШ
Электронный диск

4.2.

Информация.
  Виды информации

1

0

1

19.05.2023

Выполнять
  простейшие преобразования информации (например, перевод текстовой информации
  в рисуночную и/или табличную форму);

Зачет;

Учи.ру
РЭШ
Электронный диск

Итого по
  модулю

2

ОБЩЕЕ
  КОЛИЧЕСТВО ЧАСОВ ПО ПРОГРАММЕ

33

1

32

ПОУРОЧНОЕ ПЛАНИРОВАНИЕ

№
п/п

Тема урока

Количество часов

Дата изучения

Виды, формы контроля

всего

контрольные работы

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

1.

Как работать с учебником? Рукотворный и природный мир
  города и села.

1

0

1

02.09.2022

Устный опрос; Практическая работа;

2.

На земле, на
  воде и в воздухе.

1

0

1

09.09.2022

Устный опрос; Практическая работа;

3.

Природа и творчество.
Природные материалы.

1

0

1

16.09.2022

Устный опрос; Практическая работа;

4.

Листья и фантазии.

1

0

1

23.09.2022

Устный опрос; Практическая работа;

5.

Семена и фантазии.

1

0

1

30.09.2022

Устный опрос; Практическая работа;

6.

Композиция из листьев. Что такое композиция?

1

0

1

07.10.2022

Устный опрос; Практическая работа;

7.

Орнамент из листьев. Что такое орнамент?

1

0

1

14.10.2022

Устный опрос; Практическая работа;

8.

Природные материалы. Как их соединить?

1

0

1

21.10.2022

Устный опрос; Практическая работа;

9.

Материалы для лепки. Что может пластилин?

1

0

1

28.10.2022

Устный опрос; Практическая работа;

10.

В мастерской кондитера. Как работает мастер?

1

0

1

11.11.2022

Устный опрос; Практическая работа;

11.

В море. Какие цвета и формы у морских обитателей?

1

0

1

18.11.2022

Устный опрос; Практическая работа;

12.

Наши проекты. Аквариум.

1

0

1

25.11.2022

Устный опрос; Практическая работа;

13.

Мастерская Деда Мороза и Снегурочки.

1

0

1

02.12.2022

Устный опрос; Практическая работа;

14.

Наши проекты. Скоро Новый год!

1

0

1

09.12.2022

Устный опрос; Практическая работа;

15.

Бумага. Какие у неё есть секреты?

1

0

1

16.12.2022

Устный опрос; Практическая работа;

16.

Бумага и картон. Какие секреты у картона?

1

0

1

23.12.2022

Устный опрос; Практическая работа;

17.

Оригами. Как сгибать и складывать бумагу?

1

0

1

13.01.2023

Устный опрос; Практическая работа;

18.

Обитатели пруда. Какие секреты у оригами?

1

0

1

20.01.2023

Устный опрос; Практическая работа;

19.

Животные зоопарка. Одна основа, а сколько фигурок?

1

0

1

27.01.2023

Устный опрос; Практическая работа;

20.

Наша родная армия.

1

0

1

03.02.2023

Устный опрос; Практическая работа;

21.

Ножницы. Что ты о них знаешь?

1

0

1

10.02.2023

Устный опрос; Практическая работа;

22.

Весенний праздник 8 марта. Как сделать подарокпортрет?

1

0

1

24.02.2023

Устный опрос; Практическая работа;

23.

Шаблон. Для чего он нужен?

1

0

1

03.03.2023

Устный опрос; Практическая работа;

24.

Бабочки. Как изготовить их из листа бумаги?

1

0

1

10.03.2023

Устный опрос; Практическая работа;

25.

Орнамент в полосе. Для чего нужен орнамент?

1

0

1

17.03.2023

Устный опрос; Практическая работа;

26.

Весна. Какие
  краски у весны?

1

0

1

24.03.2023

Устный опрос; Практическая работа;

27.

Настроение весны. Что такое колорит?

1

0

1

07.04.2023

Устный опрос; Практическая работа;

28.

Праздники
  и традиции весны. Какие они?

1

0

1

14.04.2023

Устный опрос; Практическая работа;

29.

Мир тканей. Для чего нужны ткани?

1

0

1

21.04.2023

Устный опрос; Практическая работа;

30.

Игла-труженица. Что умеет игла?

1

0

1

28.04.2023

Устный опрос; Практическая работа;

31.

Вышивка. Для чего она нужна?

1

0

1

05.05.2023

Устный опрос; Практическая работа;

32.

Прямая строчка и перевивы.
Для чего они нужны?

1

0

1

12.05.2023

Практическая работа;

33.

Проверка знаний и умений, полученных в 1 классе.

1

1

0

19.05.2023

Контрольная
  работа; Зачет;

ОБЩЕЕ КОЛИЧЕСТВО ЧАСОВ
ПО ПРОГРАММЕ

33

1

32

УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
ОБРАЗОВАТЕЛЬНОГО ПРОЦЕССА

ОБЯЗАТЕЛЬНЫЕ УЧЕБНЫЕ МАТЕРИАЛЫ ДЛЯ УЧЕНИКА
Технология, 1 класс/Лутцева Е.А., Зуева Т.П., Акционерное
общество «Издательство «Просвещение»; Введите свой вариант:
МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ДЛЯ УЧИТЕЛЯ
Методическое пособие с поурочными разработками
"Технология" авт. Е.А.Лутцева, Т.П.Зуева Москва
"Просвещение" 2014
ЦИФРОВЫЕ ОБРАЗОВАТЕЛЬНЫЕ РЕСУРСЫ И РЕСУРСЫ СЕТИ ИНТЕРНЕТ
Учи.ру,
РЭШ
https://www.klass39.ru/klassnye-resursy/
https://www.uchportal.ru/load/47-2-2 http://school-collection.edu.ru/
http://um-razum.ru/load/uchebnye_prezentacii/nachalnaja_shkola/18
http://internet.chgk.info/ http://www.vbg.ru/~kvint/im.htm

МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
ОБРАЗОВАТЕЛЬНОГО ПРОЦЕССА

УЧЕБНОЕ ОБОРУДОВАНИЕ
Учебник, рабочие тетради;
Таблицы к основным разделам материала,
содержащегося в программе; Наборы сюжетных (предметных) картинок в соответствии
с тематикой.
ОБОРУДОВАНИЕ ДЛЯ ПРОВЕДЕНИЯ ПРАКТИЧЕСКИХ РАБОТ
1.Набор цветной бумаги;
2.  Набор цветного
картона;
3.  Набор белого картона;

4.Ножницы с тупыми концами;
5.Клей – карандаш, клей ПВА, кисточка для клея;
6.Пластилин не менее 8 цветов, стеки, дощечка;
7.Природный материал;
8. Папка на молнии с ручками для принадлежностей по
технологии.

file_name: Технол.1 кл. Рабочая программа ID1968127.pdf

alt: МИНИСТЕРСТВО ПРОСВЕЩЕНИЯ РОССИЙСКОЙ

alt: Важнейшая особенность уроков технологии в начальной школе — предметно-практическая деятельность как необходимая составляющая целостного процесса интеллектуального, а также духовного и нравственного развития обучающихся младшего школьного…

alt: МЕСТО УЧЕБНОГО ПРЕДМЕТА «ТЕХНОЛОГИЯ»

alt: СОДЕРЖАНИЕ УЧЕБНОГО ПРЕДМЕТА 1

alt: МЕТАПРЕДМЕТНЫЕ РЕЗУЛЬТАТЫ ОБУЧАЮЩЕГОСЯ

alt: России; строить рассуждения о связях природного и предметного мира, простые суждения (небольшие тексты) об объекте, его строении, свойствах и способах создания; объяснять последовательность совершаемых действий…

alt: «инструмент», «приспособление», «конструирование», «аппликация»; выполнять задания с опорой на готовый план; обслуживать себя во время работы: соблюдать порядок на рабочем месте, ухаживать за инструментами и…

alt: ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ № п/п

alt: Наиболее распространённые виды бумаги

alt: ПОУРОЧНОЕ ПЛАНИРОВАНИЕ № п/п

alt: Весна. Какие краски у весны? 1 0 1 24

alt: УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

alt: МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

tags: ПОЯСНИТЕЛЬНАЯ ЗАПИСКА; ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ; ПОУРОЧНОЕ ПЛАНИРОВАНИЕ

title: РАБОЧАЯ ПРОГРАММА (ID 1961787) учебного предмета «Технология» для 1 класса начального общего образования на 2022-2023 учебный год


extracted_text:
ЭФФЕКТИВНОСТЬ И ПРАВИЛЬНОСТЬ
В этом разделе
мы обсудим понятия, которые являются частью данного формального введения в
теорию алгоритмов. О

них всегда
нужно помнить при самостоятельной разработке алгоритмов. Первое из них – эффективность,
а второе – пра- вильность.
Эффективность алгоритма. Хотя современные машины способны
выполнять миллионы операций в секунду, эффек- тивность по-прежнему остается
важнейшим аспектом разработки алгоритмов. Зачастую выбор между эффективным и
неэф- фективным решением задачи может на самом деле означать выбор между
реализуемым и нереализуемым способом ее реше- ния.
Рассмотрим задачу, с которой сталкивается секретарь университета при
поиске личных дел студентов и их заполнении. Хотя в университете на протяжении
любого семестра фактически числится около 10 000 студентов, секретарю в
действи- тельности приходится иметь дело с более чем 30 000 личных дел,
поскольку за несколько предыдущих лет многие из студен- тов зарегистрировались
для изучения хотя бы одной из преподаваемых в университете дисциплин, но не
смогли закончить цикл обучения. Теперь предположим, что все личные дела
хранятся в компьютере секретаря в виде списка, упорядоченного по
идентификационным номерам каждого из студентов. Чтобы найти личное дело
некоторого студента, секретарь должен выполнить поиск по его идентификационному
номеру в общем списке.
Мы уже познакомились с двумя алгоритмами поиска в
подобных списках последовательным и двоичным поиском. Сейчас нам нужно дать
ответ на вопрос, почувствует ли секретарь разницу между
этими двумя алгоритмами? Начнем с
рассмот- рения последовательного
поиска.
При заданном идентификационном номере студента алгоритм
последовательного поиска начинает работу с начала спи- ска и последовательно
сравнивает каждый выбираемый элемент с искомым числом. Не зная, что
представляет собой искомое число, мы не можем определить, насколько далеко
потребуется просматривать список. Все же можно утверждать, что для множества
выполненных операций поиска их средняя глубина будет равна приблизительно
половине длины списка, хотя в отдельных случаях поиск потребует меньшего числа
операций, а в других – большего. Можно сделать вывод, что при много- кратном
выполнении последовательного поиска на каждый случай в среднем приходится
приблизительно 15 000 просмот- ренных личных дел. Если выборка каждого личного
дела из памяти и сравнение его номера с искомым выполняется за де- сять
миллисекунд (десять тысячных долей секунды), то среднее время поиска будет
составлять 150 с или две с половиной минуты. Если секретарю придется так долго
ожидать появления на экране монитора личного дела интересующего его сту- дента,
несомненно, что этот вариант совершенно неприемлем. Даже если время выборки и
проверки каждой записи сокра- тить до одной миллисекунды, на поиск личного дела
студента все равно потребуется в среднем около 15 с – все еще слиш- ком много
для среднего времени ожидания ответа, которое можно считать приемлемым.
В противоположность этому, алгоритм двоичного поиска начинает работу
со сравнения искомого значения со средним элементом списка. Если это не искомый
элемент, то область поиска сразу же сужается до половины исходного списка, т.е.
после проверки среднего элемента списка из 30 000 личных дел алгоритм двоичного
поиска в большинстве случаев выберет для дальнейшего рассмотрения только 15 000
дел. После второго этапа область поиска в большинстве случаев сократится до
7500 дел, после третьего – до 3750 и т.д. В результате искомое значение будет
найдено при выборе, самое большее, 15 эле- ментов списка, состоящего из 30 000
дел. Таким образом, если каждое выбранное значение обрабатывается за 10
миллисе- кунд, процесс поиска нужного личного дела потребует не более 0,15 с, а
это означает, что с точки зрения секретаря личное дело любого студента будет
появляться на экране практически мгновенно. Можно сделать обоснованное
заключение, что выбор между алгоритмом последовательного поиска и алгоритмом
двоичного поиска в данном случае имеет большое значе- ние2.
Этот пример иллюстрирует важность той области компьютерных наук,
которую называют анализом алгоритмов. Эта область связана с изучением
необходимых алгоритмам ресурсов, таких, как время или используемый объем
памяти. Основ- ным практическим применением результатов подобных исследований
является оценка относительных достоинств альтерна- тивных алгоритмов. В нашем
случае мы проанализировали время, требующееся алгоритмам последовательного и
двоичного поиска, что позволило нам определить, какой из них больше подходит в
данном конкретном случае. В общем случае такой анализ осуществляется в более
широком контексте. Это означает, что при рассмотрении алгоритмов, выполняющих
поиск в списке, мы не ограничимся списком фиксированной длины, но пытаемся
вывести формулу эффективности алгоритма для списков произвольной длины. Такой
анализ включает изучение ситуаций, в которых алгоритм демонстрирует свои
наилуч- шие свойства, ситуаций, когда его эффективность минимальна, а также
оценку его средней производительности.
В предыдущем случае выполненный нами анализ заключался в оценке средней
производительности алгоритма после-
довательного
поиска, а также определении той производительности, которую алгоритм двоичного
поиска продемонстрирует в наихудшем случае. Хотя мы рассматривали список
определенной длины, несложно обобщить наши рассуждения на случай списка
произвольной длины. В частности, при применении к списку из п элементов
алгоритму последовательного поиска в среднем потребуется проверить n/2
элементов, тогда как алгоритму двоичного поиска в самом худшем случае
потребуется проверить только log2n элементов. (В данном
случае выражение log2n представляет логарифм числа п по
основанию 2, кото- рый показывает, сколько раз число n можно разделить
на два.)
Давайте попробуем проанализировать аналогичным образом алгоритм
сортировки методом вставки. Поскольку основ- ным действием в реализации данного
алгоритма является сравнение двух имен, наш подход будет состоять в подсчете
коли- чества таких сравнений, которые потребуется выполнить при сортировке
списка длиной п элементов.
Вспомним, что при сортировке методом вставки осуществляется выбор
некоторого элемента, называемого опорным; после этого он сравнивается с
предшествующими ему элементами, пока для него не будет найдено надлежащее
место, после чего опорный элемент вставляется в соответствующую позицию.
Алгоритм начинается с выбора второго элемента списка в качестве опорного. По
мере его выполнения в качестве опорных выбираются следующие элементы – пока не
будет достиг-

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

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

алгоритма сортировки методом
вставки к списку из п элементов потребует выполнения

n -1

сравнений. (Второй элемент

сравнивается с
одним элементом (первым), третий элемент – с одним элементом (вторым) и т.д.).
И наоборот, наихудший сценарий имеет место в том случае, когда каждый
опорный элемент потребуется сравнивать со всеми впереди стоящими элементами,
прежде чем удастся найти правильное место его расположения. Очевидно, что в
этом случае исходный список упорядочен в обратном порядке.
Первый опорный элемент
(второй элемент списка)
сравнивается с
одним элементом,
второй опорный элемент
(третий элемент списка) – с двумя элементами
и т.д. (рис. 4.17). Следовательно,
общее
количество  сравнений  при  сортировке  списка  из  n  элементов
составит   1+ 2
+ 3 +
... + (n -1) ,  что эквивалентно
n(n -1)/ 2 или
1/2(n2 – n). В частности, для списка из 10 элементов
алгоритму сортировки методом вставки в наихудшем слу- чае потребуется выполнить
45 сравнений.
В среднем при сортировке методом вставки можно ожидать, что каждый
опорный элемент потребуется сравнить с по-
ловиной
предшествующих ему элементов. В этом случае общее количество выполненных
сравнений будет вдвое меньше, чем в наихудшем случае, т.е. (1/4)(п2
– п) сравнений для списка длины п. Например, если использовать
сортировку методом вставки для упорядочения множества списков из 10 элементов,
то среднее число производимых в каждом случае сравнений будет равно 22,5.

Важность полученного выше результата состоит в том, что количество сравнений,
выполненных алгоритмом сортиров- ки методом вставки, позволяет оценить время,
которое потребуется для выполнения сортировки. Эта оценка была использо- вана
для построения графика, представленного на рис. 4.18. Он показывает, как будет
возрастатьвремя, необходимое для выполнения сортировки методом вставки, при
увеличении длины сортируемого списка.
Рис. 4.17. Работа алгоритма сортировки методом вставки
в наихудшем случае
Данный график построен по
оценкам работы алгоритма в наихудшем случае, когда, исходя из результатов наших
исследова- ний, для списка длиной п требуется выполнить не менее 1/ 2 n2
- n сравнений элементов. На
графике отмечено несколько
конкретных значений длины списка и указано время, необходимое в каждом
случае. Обратите внимание, при увеличении длины списка на одно и то
же количество элементов время, необходимое
для сортировки списка, все больше и больше возрастает. Таким образом, с увеличением длины списка эффективность данного алгоритма уменьшается.

Рис. 4.18. График зависимости времени
сортировки от длины списка при сортировке методом вставки
Выполним аналогичный анализ работы алгоритма двоичного поиска в
наихудшем случае. Как было установлено выше, при использовании этого алгоритма
для поиска в списке из п элементов потребуется проанализировать не более
log2 n эле- ментов. Это позволяет оценить время, необходимое
для выполнения алгоритма при различной длине сортируемого списка. На рис. 4.19
представлен график, построенный по результатам данного анализа. На этом графике
также отмечены конкрет- ные значения длины списка, возрастающие на одну и ту же
величину, и указано соответствующее время выполнения алго- ритма. Обратите
внимание, что темпы роста времени выполнения алгоритма снижаются по мере
увеличения длины списка, т.е. эффективность алгоритма двоичного поиска
возрастает с увеличением длины списка.

Основным отличием между графиками, представленными на рис.
4.18 и 4.19, безусловно, является их общая форма. Именно форма графика,
а не его индивидуальные особенности, демонстрирует, насколько хорошо данный
алгоритм будет справлять- ся с все возрастающими объемами данных. Заметим, что
общая форма графика определяется типом отображаемого выраже- ния, а не его
конкретными особенностями: все линейные выражения изображаются прямой линией,
все квадратичные выраже- ния – параболической кривой, а все
логарифмические выражения порождают
логарифмическую кривую, подобную пред- ставленной на рис. 4.19. Общую форму
кривой принято определять простейшим выражением, порождающим кривую данной
формы. В частности, параболическая форма обычно определяется выражением n2,
а логарифмическая – выражением lgn.

Рис. 4.19. График зависимости времени
поиска от длины списка для алгоритма двоичного поиска
Выше было показано, что форма графика, представляющего зависимость
времени выполнения алгоритма от объема входных данных, отражает общие
характеристики эффективности алгоритма. Поэтому принято классифицировать
алгорит- мы согласно форме их графиков, построенных для самого неблагоприятного
случая. Способ обозначения, используемый для определения этих классов, иногда
называют тета-классами. Алгоритмы, графики которых имеют параболическую форму
(например, сортировка методом вставки), относятся к классу Q(n2), алгоритмы, графики
которых имеют логарифмическую форму (например, двоичный поиск), – к классу Q(lgn). Любой алгоритм из тета-класса Q(lgn) по самой свой сути всегда бо-
лее эффективен, чем алгоритм из тета-класса Q(n2).
Верификация программ. Вспомним, что четвертая фаза процедуры
решения задачи, согласно схеме, предложенной математиком Полиа (см. раздел
4.3), заключается в оценке точности работы программы или верификации (verification)
и определении его потенциала как инструмента для решения других задач. Важность
первой части этой фазы мы проиллюст- рируем следующим примером.
Путешественник, у которого есть золотая цепочка из
семи звеньев, должен остановиться в уединенном отеле на семь ночей. Плата за
каждую проведенную в отеле ночь составляет одно звено его цепочки. Какое
наименьшее число звеньев не- обходимо разрезать, чтобы путешественник мог
платить владельцу отеля одно звено каждое утро, не внося плату заранее?
Первым делом уясним себе, что нет необходимости
разрезать все звенья. Если мы разрежем только второе звено, то и первое, и
второе будут отделены от остальных пяти звеньев. Следуя этому, можно прийти к
решению разрезать только вто- рое, четвертое и шестое звенья цепочки. В
результате все звенья окажутся свободными, причем только три из них будут раз-
резанными (рис. 4.20). Более того, любое меньшее число разрезов оставит два
звена соединенными, поэтому мы заключаем, что правильный ответ для этой задачи
– три звена.
Однако, рассмотрев задачу более внимательно, можно
заметить, что если разрезать только третье звено, то получится три фрагмента
цепочки, состоящие из одного, двух и четырех звеньев (рис. 4.21). С этими
фрагментами мы можем поступить следующим образом.
Первое утро. Отдать владельцу отеля одно
звено.
Второе утро. Забрать у владельца
отеля одно звено и отдать ему фрагмент цепочки из двух звеньев.

Рис. 4.20. Разделение всех звеньев цепочки с помощью
лишь трех разрезов

Рис. 4.21. Решение задачи с помощью лишь одного разреза

Третье утро. Отдать
владельцу отеля одно звено.
Четвертое утро. Забрать у владельца отеля три отданные ему ранее
звена и отдать ему фрагмент цепочки из четырех звеньев.
Пятое утро. Отдать
владельцу отеля одно звено.
Шестое
утро. Забрать у владельца отеля одно звено и отдать ему фрагмент цепочки из
двух звеньев.
Седьмое утро. Отдать
владельцу отеля одно звено.
Следовательно, тот ответ, который мы считали
правильным, на самом деле неверен. Как же убедиться, что новое реше- ние
действительно правильно? В качестве доказательства можно привести следующее
рассуждение. Поскольку в первое ут- ро необходимо отдать владельцу отеля одно
звено, придется разрезать, по крайней мере, одно звено цепочки. Но так как в
новом варианте решения требуется разрезать только одно звено, то это решение должно
быть оптимальным.
Применительно к программированию этот пример
демонстрирует различия между программой, которая выглядит пра- вильной, и
программой, которая действительно является правильной. Это не всегда одно и то
же. Специалистам в области обработки данных известно множество ужасных историй
о том, как программное обеспечение, которое считалось безуслов- но правильным,
все же отказывало в критический момент, поскольку возникшая ситуация
оказывалась для него совершенно непредвиденной. Следовательно, верификация
программного обеспечения – это важное и необходимое дело, а поиск эффек- тивных
методов верификации является активным направлением исследований в области
компьютерных наук.
Одно из самых современных направлений в этой области
заключается в использовании методов формальной логики для доказательства
корректности программ. Это означает, что цель проводимых исследований состоит в
применении формаль- ной логики для доказательства того факта, что реализованный
данной программой алгоритм делает именно то, для чего он предназначен.
Основополагающий тезис заключается в том, что при сведении процесса верификации
к формальной проце- дуре мы застрахованы от некорректных умозаключений,
вытекающих из интуитивной аргументации, как это было в случае с задачей о
золотой цепочке. Давайте рассмотрим данный подход к верификации программ более
подробно.
Подобно тому, как формальное математическое
доказательство основывается на аксиомах (геометрические доказатель- ства часто
базируются на аксиомах Евклидовой геометрии, тогда как доказательства других
утверждений – на аксиомах тео- рии множеств), формальное доказательство
правильности программы основывается на спецификациях, в соответствии с ко-
торыми эта программа разрабатывалась. Чтобы доказать, что программа правильно
сортирует списки имен, мы можем на- чать с предположения о том, что на вход
программы подается список имен. Если программа создана для вычисления средне-
го значения одного или более положительных чисел, мы можем предположить, что
исходными данными для программы яв- ляется одно или несколько положительных
чисел. Короче говоря, доказательство корректности начинается с предположения о
том, что в начале работы программы удовлетворены некоторые условия, называемые предварительными
условиями (pre- condition), или предусловиями.
Следующий этап доказательства корректности заключается
в рассмотрении того, как следствия из этих предусловий распространяются по
программе. С этой целью исследователи изучили различные программные структуры,
пытаясь устано- вить, как выполнение данной структуры влияет на утверждение, о
котором до выполнения этой структуры было известно, что оно истинно. Например,
пусть определенное утверждение о значении переменной Y перед выполнением
приведенной ниже инструкции было истинно:
X ← Y
После выполнения этой инструкции то же утверждение можно сделать о
значении переменной X. Например, если перед выполнением инструкции значение
переменной Y отличалось от 0, то можно сделать заключение, что после выполнения
этой инструкции значение переменной X также будет отличаться от 0.
Несколько более сложным случаем является выполнение оператора if-then-else, например, следующего
вида:
if (условие) then {инструкция
1} else {инструкция 2}.
Если в этом примере известно, что некоторое утверждение было истинно
перед выполнением данной структуры, то не- посредственно перед выполнением
инструкции 1 мы знаем, что истинны как это утверждение, так и проверяемое
условие. В то же время, если должна выполняться инструкция 2, мы знаем,
что должны быть истинны исходное утверждение и отрица- ние проверяемого
условия.
Верификация требуется не только
программному обеспечению. Обсуждаемые
в тексте проблемы верификации касаются не толь- ко программного обеспечения.
Столь же важно получить гарантии, что выполняющая программу аппаратура также не
содержит ошибок. Это подразумевает верификацию как разрабатываемых схем, так и
конструкции всей машины. И в этом случае полученные результаты в значительной
степени зависят от тестирования, задача которого, как и в случае с программным
обеспечением, – выявить скрытые ошибки. Показателен пример машины Mark 1,
созданной в Гарвардском университете в 1940 г., монтажные ошибки в которой
оставались необна- руженными в течение многих лет. Более "свежий"
пример – ошибки в блоке выполнения операций с плавающей точкой, имевшие место в
первых микропроцессорах типа Pentium. В обоих случаях существующие ошибки были
выявлены до каких-либо серьезных последствий.

Если следовать правилам, приведенным выше, доказательство корректности
программы осуществляется путем опреде- ления положений, называемых
утверждениями, которые устанавливаются в различных точках программы. В
результате по- лучается набор утверждений, каждое из которых является
следствием предусловий программы и последовательности инст- рукций, приводящей
к той точке программы, где установлено данное утверждение. Если утверждение,
установленное по- добным образом в конце программы, соответствует спецификациям
того, что требуется получить на ее выходе, то можно сделать заключение о
правильности программы.
В качестве примера рассмотрим типичную циклическую
структуру while-do, представленную на рис. 4.22.
Предпо- ложим, как следствие предусловий, заданных в точке А, мы можем
установить, что определенное утверждение истинно при каждой проверке условия
окончания цикла (точка В) на протяжении всего процесса повторения. Такое
утверждение внутри цикла называется инвариантом цикла (loop invariant).
Как только повторение завершается, выполнение переходит к точке С, где мы можем
заключить, что истинны как инвариант цикла, так и условие его окончания.
(Инвариант цикла остается истин- ным, поскольку проверка условия окончания не
изменяет никаких величин в программе, а условие окончания истинно, по- скольку
в противном случае цикл бы просто не завершился.) Если комбинация этих
положений означает то, что мы хотим видеть на выходе, наше доказательство
корректности можно завершить, просто показав, что компоненты инициализации и
модификации цикла в конечном счете приводят к условию окончания.
Этот метод
анализа можно применить к приведенному выше алгоритму сортировки методом
вставки (см. рис. 4.11).
Внешний цикл в этой программе
основан на следующем инварианте цикла:
Каждый раз при выполнении проверки условия окончания цикла имена,
предшествующие N-му элементу, образуют от- сортированный список.

Рис. 4.22. Использование формального утверждения для
проверки правильности оператора цикла while-do
Условие окончания этого цикла формулируется следующим образом:
Значение N больше, чем длина списка.
Таким образом, как только цикл завершится, мы будем
знать, что оба условия должны быть выполнены, а это означает, что весь список
будет отсортирован.
К сожалению, методы формальной верификации программ не
настолько хорошо разработаны, чтобы их можно было использовать в приложениях
общего типа. Сегодня в большинстве случаев "верификация" программного
обеспечения про- изводится посредством его тестирования при различных исходных
условиях, что весьма ненадежно. Верификация с помо- щью тестирования не
доказывает ничего иного, кроме того, что программа правильно работает в тех
условиях, в которых ее проверяли. Любые дополнительные заключения – это всего
лишь предположения. Ошибки, содержащиеся в программе, ча- ще всего являются
следствием оплошности и недосмотра, что может произойти и при тестировании. В
результате ошибки в программе, такие, как в задаче с золотой цепочкой, могут
остаться и часто остаются незамеченными, хотя были потрачены значительные
усилия, чтобы этого избежать. Драматический случай произошел в компании
AT&T. Ошибка в программном обеспечении, управляющем 114 телефонными
станциями, оставалась незамеченной с момента его установки в декабре 1989 г. и
вплоть до 15 января 1990 г., когда исключительное стечение обстоятельств привело
к тому, что за девять часов было беспричинно заблокировано примерно 5 миллионов
телефонных звонков.
Вопросы для самопроверки
1.  Предположим, было установлено, что при использовании
алгоритма сортировки методом вставки машине требуется в среднем одна секунда
для сортировки списка из 100 элементов. Оцените, сколько времени ей понадобится
для сортировки списков из 1000 и 10 000 элементов?

2.  Приведите примеры алгоритмов, относящихся к каждому из
следующих классов: Q(lgn), Q(n), Q(n2).
3.  Перечислите следующие классы в порядке убывания их
эффективности: Q(n2), Q(lgn),
Q(n), Q(n3).
4.  Проанализируйте следующую задачу и
предлагаемый ответ. Является ли этот ответ правильным? Поясните свои вы- воды.
Задача. Предположим, что в коробке находятся три
карточки. У одной из них обе стороны черного цвета, у второй обе стороны
красного цвета, а у третьей одна сторона черного цвета, а другая – красного. Из
коробки вынимают одну карточку,  и вам разрешается посмотреть на одну из ее
сторон. Какова вероятность того, что вторая сторона этой карточки того же цве-
та, что и та, которую вам показали?
Предлагаемый ответ. Одна вторая. Предположим, что показанная вам
сторона карточки была красного цвета. (Рассу- ждения будут аналогичны и в том
случае, если она будет черного цвета, так как задача симметрична.) Из трех
карточек толь- ко у двух есть красная сторона. Следовательно, карточка, которую
вы увидели, – одна из этих двух. У одной из этой пары карточек вторая сторона
красная, а у другой – черная. Следовательно, вторая сторона у выбранной из
коробки карточки с равной вероятностью может быть как черной, так и красной.
5.
Приведенный ниже программный
сегмент используется, чтобы вычислить частное (не принимая во внимание оста-
ток) двух целых положительных чисел (делимого и делителя) путем подсчета,
сколько раз делитель можно вычесть из дели- мого, пока оставшаяся часть станет
меньше делителя. Например, при делении по этому методу числа 7 на 3 получится
2, так как число 3 можно вычесть из 7 дважды. Правильно ли составлена эта
программа? Обоснуйте свои выводы.
Счетчик
← 0;
Остаток ← Делимое;
repeat {Остаток ← Остаток – Делитель; Счетчик
← Счетчик + 1}
until (Остаток < Делитель) Частное ← Счетчик
6.  Приведенный ниже программный сегмент предназначен для
определения произведения двух неотрицательных целых чисел X и Y посредством вычисления
суммы X копий числа Y. Другими
словами, выражение 3 ´ 4 вычисляется как сумма трех четверок. Правильно ли
составлена эта программа? Обоснуйте это.
Произведение
← Y;
Счетчик ← 1;
while (Счетчик < X) do
{Произведение
← Произведение + Y;
Счетчик
← Счетчик + 1}
7.  Приняв как предусловие, что значение
N – целое положительное число, установите инвариант цикла, который приво- дит к
заключению, что по окончании приведенной ниже программы переменной Сумма будет присвоено значение, равное 0
+ 1 + ... + N.
Сумма ← 0;
I ← 0;
while (I < N) do
{I ← I + 1;
Сумма ← Сумма + I}
Приведите аргументы в пользу
того, что эта программа действительно завершится.
8.   Предположим, что программа и выполняющая ее аппаратура
были формально проверены на корректность. Гаранти- рует ли это правильность их работы?
Упражнения
1.
Приведите примеры
последовательности этапов, удовлетворяющей неформальному определению алгоритма,
приве- денному в начале раздела 4.1, но не удовлетворяющей определению,
приведенному на рис. 4.1.
2.
Объясните различие между неоднозначностью
в предложенном алгоритме и неоднозначностью в представлении ал- горитма.
3.
Поясните, как использование
примитивов помогает устранить неоднозначность в представлении алгоритмов?
4.
Представляет ли следующая
программа алгоритм в строгом смысле этого слова? Поясните свой ответ.
Счетчик ← 0;
while (Счетчик ¹ 5) do
{Счетчик
← Счетчик + 2}
5.
По какой причине приведенная ниже
последовательность этапов не образует алгоритм? Этап 1. Провести отрезок
прямой линии, соединяющий точки с координатами (2, 5) и (6, 11). Этап 2.
Провести отрезок прямой линии, соединяющий точки с координатами (1, 3) и (3, 6).
Этап 3. Провести
окружность с радиусом 2 и центром в точке пересечения проведенных отрезков.
6.
Перепишите
следующий сегмент программы, используя структуру repeat-until
вместо while-do. Убедитесь, что новая версия
программы печатает те же значения, что и исходная.
Счетчик ← 2;
while (Счетчик < 7) do
{напечатать значение переменной Счетчик;
Счетчик ← Счетчик +1}

7.
Перепишите
следующий фрагмент программы, используя структуру while-do вместо repeat-until. Убедитесь, что новая версия печатает
те же значения, что и исходная.
Счетчик ← 1;
repeat {напечатать значение переменной Счетчик;
Счетчик ← Счетчик + 1}
until (Счетчик = 5)
8.  Разработайте алгоритм, который получает на входе некую
конфигурацию из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и перестав- ляет полученные
цифры таким образом, чтобы новая конфигурация представляла собой значение,
следующее по величине за исходным, из числа тех, которые могут быть составлены
из этих цифр (или сообщает, что такой перестановки не существует, если никакие
перестановки не приводят к большему значению). Например, для исходной
конфигурации 5 647 382 901 таким числом будет 5 647 382 910.
9.  В чем отличие формального языка программирования от псевдокода?
10.  В чем отличие между синтаксисом и семантикой?
11.  Четыре шахтера, которые имеют один фонарь,
должны пройти через шахту.
Одновременно по шахте могут
двигаться не больше двух человек, и каждый шахтер, двигаясь в
шахте, должен иметь фонарь. Шахтеры, имена
которых Эндрю, Блэйк, Джонсон и Келли,
могут пройти шахту за одну, две, три
и четыре минуты, соответственно. Когда
два шахтера идут вместе, они движутся
со скоростью более медленного из
них. Каким образом шахтеры могут пройти
через шахту за 15 минут? После того как вы решите задачу, объясните, с чего вы начали
решение.
12.
Допустим, у нас есть большой и
маленький стаканчики для вина. Сначала наполним вином маленький стаканчик и
перельем его в большой стакан. Затем наполним водой маленький стакан, перельем
некоторое количество воды в большой стакан и смешаем его с вином. Теперь будем
переливать смесь обратно в маленький стакан, пока он не наполнится. Чего те-
перь больше в маленьком стакане – воды в вине или вина в воде? После того как
вы решите задачу, объясните ход ваших рассуждений.
13.  Две пчелы, Ромео и Джульетта, живут в разных ульях, но
они встретились и полюбили друг друга. Однажды безвет- ренным весенним утром
они одновременно вылетели из своих ульев, чтобы слетать друг к другу в гости. В
50-ти метрах от ближайшего улья они встретились, но не заметили друг друга и
полетели дальше. Прибыв к месту своего назначения, они потратили одинаковое
время, чтобы выяснить, что того, к кому они прилетели, нет дома, и повернуть
назад. На обратном пути они встретились в точке, находящейся на расстоянии 20
метров от ближайшего улья. На этот раз они увидели друг дру- га и устроили пикник,
прежде чем возвратиться домой. На каком расстоянии друг от друга расположены их
улья? Решив задачу, объясните, с чего вы начали свои рассуждения.
14.  Разработайте алгоритм, который получает на входе две
строки символов и проверяет, является ли первая строка ча- стью второй.
15.  Следующий алгоритм разработан для того, чтобы
напечатать несколько первых чисел Фибоначчи. Определите, что является телом
цикла. Где выполняется операция инициализации управления циклом? Где
выполняется операция модифика- ции? Какая инструкция реализует операцию
проверки? Какой список чисел получится в результате работы алгоритма?
Последнее ← 0;
Текущее ← 1;
while (Текущее < 100) do
{напечатать значение переменной Текущее;
Временное ← Последнее;
Последнее ← Текущее;
Текущее ← Последнее + Временное}
16.
Какую последовательность чисел
напечатает следующий алгоритм, если на входе задать значения 0 и 1?
procedure MysteryWrite (Последний, Текущий)
if (Текущий < 100) then
{напечатать значение переменной Текущий;
Временный ← Текущий + Последний;
применить
процедуру MysteryWrite к значениям Текущий и Временный}
17.
Преобразуйте
процедуру MysteryWrite из предыдущего задания так, чтобы она печатала числа в обратном по- рядке.
18.  Какие буквы будут проверяться, если применить двоичный
поиск (см. рис. 4.13) для поиска значения J в списке А, В, С, D, E, F, G, H, I,
J, К, L, M, N, О? А в случае поиска значения
Z?
19.
Сколько раз в среднем
потребуется сравнивать между собой два элемента при поиске значения
в списке из 6000
элементов с помощью метода последовательного поиска? А что
можно сказать о методе двоичного поиска?
20.   Определите тело цикла в следующей структуре и
подсчитайте, сколько раз оно будет выполнено. Что произойдет, если проверяемое
условие заменить на выражение "while (Счетчик ≠
6)"?
Счетчик
← 1;
while (Счетчик ≠ 7) do
{напечатать значение переменной Cчетчик;
Счетчик ← Счетчик + 3}
21.  Какие проблемы могут возникнуть при реализации на
компьютере следующей программы? (Подсказка. Вспомните об ошибках округления при
выполнении арифметических операций с плавающей
точкой.)
Счетчик ← 0.1;
repeat {напечатать значение переменной Счетчик; Счетчик ← Счетчик
+ 0.1}

until (Счетчик = 1)
22.
Разработайте рекурсивную версию алгоритма Евклида (вопрос 3 к разделу 4.2).
23.   Предположим, что на вход процедур Testl и Test2, приведенных ниже, передано значение 1. Чем будут
отли- чаться напечатанные этими процедурами
результаты?
procedure Test1 (Счетчик)
if (Счетчик
≠ 5)
then {напечатать значение параметра
Счетчик; выполнить процедуру
Test1(Счетчик + 1)}
procedure Test2 (Счетчик)
if (Счетчик ≠ 5)
then {выполнить процедуру Test2(Счетчик + 1);
напечатать значение
параметра Счетчик}
24.   Определите основные составляющие
механизма управления в предыдущей задаче. В частности, какое условие вы- зывает
окончание процесса? Где происходит модификация состояния процесса, приближающая
его к условию завершения? Где инициализируется состояние управляющего процесса?
25.   Разработайте алгоритм генерации
последовательности целых положительных чисел (в возрастающем порядке), ко-
торые имеют только два простых множителя – 2 и 3, т.е. программа должна
генерировать последовательность чисел 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27,
Представляет ли эта программа алгоритм в строгом смысле этого слова?
26.   Ответьте на следующие вопросы
применительно к списку имен Alice, Byron, Carol, Duane, Elaine, Floyd, Gene,
Henry, Iris.
а) Какой
алгоритм поиска (последовательный или двоичный) позволит
быстрее найти имя Gene?
б) Какой алгоритм поиска (последовательный или двоичный) позволит
быстрее найти имя Alice?
в) Какой
алгоритм поиска (последовательный или двоичный) позволит быстрее обнаружить
отсутствие в списке имени
Bruce?
г) Какой
алгоритм поиска (последовательный или двоичный) позволит быстрее обнаружить
отсутствие в списке имени
Sue?
д) Сколько
элементов будет рассмотрено при поиске имени Elaine с использованием метода
последовательного поиска?
Сколько
элементов будет рассмотрено при поиске этого имени с использованием метода
двоичного поиска?
27.   По определению факториал числа 0 равен
1. Факториал целого положительного числа – это произведение данного целого
положительного числа и факториала предшествующего ему целого положительного
числа. Для обозначения факто- риала целого положительного числа п используется
запись п!. Таким образом, факториал числа 3 (обозначается как 3!)
– это 3!= 3*(2!)= 3*(2*(1!))= 3*(2*(1*(0!))) = 3*(2*(1*(1))) = 6. Разработайте
рекурсивный алгоритм вычисления факториала задан- ного числа.
28.   а) Предположим, что вам необходимо отсортировать
список из пяти имен и что вы уже разработали раньше алго- ритм для сортировки
списка из четырех имен. Разработайте алгоритм сортировки списка из пяти имен,
использующий ранее разработанный алгоритм.
б) Разработайте рекурсивный алгоритм сортировки списка
произвольной длины, основанный на методе, используемом для решения предыдущей
задачи.
29.  Головоломка "Ханойская
башня" состоит из трех вертикальных стержней, на один из которых надето
несколько ко- лец последовательно уменьшающихся (в направлении снизу вверх)
размеров. Задача состоит в том, чтобы переместить набор колец на другой
стержень. Разрешается перемещать только одно кольцо за один ход, причем нельзя
надевать большее коль- цо поверх меньшего. Заметим, что головоломка с одним
кольцом решается предельно просто. Если колец несколько, то, пе- реместив на
другой стержень все кольца, кроме наибольшего, наибольшее кольцо можно было бы
перенести на третий стер- жень. После этого задача была бы сведена к
перемещению всех остальных колец на наибольшее. Исходя из этого, разрабо- тайте
рекурсивный алгоритм для решения головоломки "Ханойская башня" с
произвольным числом колец.

30.

Еще один подход к решению
головоломки "Ханойская башня" (упр. 29) состоит в следующем.
Представьте себе, что стержни расставлены по кругу в положениях,
соответствующих отметкам 4, 8 и 12 часов на циферблате. Кольца, находящие- ся
исходно на одном из стержней, нумеруются числами 1, 2, 3 и т.д., начиная с
верхнего. Кольца с нечетными номерами, на- ходящиеся сверху набора, разрешается перемещать
только на стержень, следующий по часовой
стрелке, кольца с четными
номе- рами можно перемещать только против часовой стрелки (при условии, что
такое перемещение не приведет
к помещению больше- го кольца
над меньшим). Учитывая
вышеизложенные требования, вы всегда
должны выбирать кольцо с наибольшим
номером из числа тех, которые доступны для перемещения. Используя такой подход,
разработайте нерекурсивный алгоритм решения голово- ломки "Ханойская башня".
31.  Разработайте циклический и рекурсивный
алгоритмы для распечатки дневной заработной платы рабочего, который в каждый
последующий день получает вдвое больше, чем в предыдущий (первый платеж равен
одному пенни), за 30 дней работы. С какими проблемами, касающимися хранения данных, вам придется столкнуться при реализации вашего решения

на реальной машине?
32.   Разработайте алгоритм для нахождения
значения квадратного корня из положительного числа с помощью следую- щего
метода. В качестве первого приближения выбирается само это число, а последующие
приближения получаются из пре- дыдущих путем вычисления среднего арифметического для предыдущего приближения и
числа, полученного при делении ис-
ходного числа на предыдущее приближение. Проанализируйте возможности управления этим повторяющимся
процессом. В част- ности, какое условие должно
использоваться для его
окончания?
33.  Разработайте алгоритм, который
печатает все возможные варианты перестановки символов в строке из пяти различ-
ных символов.
34.  Разработайте алгоритм, который в
заданном списке имен находит самое длинное имя. Определите, как поведет себя
алгоритм, предложенный вами в качестве решения, если "самых длинных"
имен в списке будет несколько. В частности, как поведет себя ваш алгоритм, если
все имена в списке будут одной длины?
35.  Разработайте алгоритм, который в
заданном списке из пяти или более чисел находит пять наименьших и пять наи-
больших чисел, не сортируя полностью весь список.
36.  Расположите имена Brenda, Doris,
Raymond, Steve, Timothy и William в таком порядке, который при использовании
алгоритма сортировки методом вставки потребует выполнения наименьшего числа
сравнений (рис. 4.11).
37.   Какое максимальное количество
элементов может быть проверено при применении алгоритма двоичного поиска (рис.
4.13) к списку, содержащему 4000 строк? Как оно соотносится с аналогичным
значением для метода последовательного поиска (рис. 4.6)?
38.  Используя нотацию тета-классов,
классифицируйте традиционные школьные
алгоритмы для сложения и умножения в столбик. Другими словами, определите,
сколько отдельных операций сложения необходимо выполнить при суммировании
двух чисел значностью п и сколько отдельных операций умножения потребуется для их перемножения.
39.  Иногда небольшое
изменение условия задачи может вызвать существенные изменения в способе
ее решения. Например, найдите простой алгоритм решения следующей задачи и
определите его тета-класс.
Разделите группу людей на две непересекающиеся
подгруппы (произвольных размеров), такие, чтобы разность между суммами
возрастов членов этих подгрупп была максимальной. Теперь измените условие
задачи так, чтобы требуемая раз- ность была минимальной, и вновь
классифицируйте ваше решение.
40.  Из следующего списка выделите
несколько чисел, сумма которых равна 3165. Насколько эффективен ваш метод ре-
шения задачи?
26, 39, 104,
195, 403, 504, 793, 995, 1156, 1673
41.  Завершится ли цикл в следующей
программе? Поясните свой ответ. Объясните, что могло бы случиться, если бы эта
программа в действительности выполнялась машиной (см. раздел 1.7)
X ← 0;
Y ← 1/2;
while (X ≠ 1) do
{X ← X+Y;
Y ← Y-2}
42.  Следующий фрагмент программы
разработан для вычисления произведения двух неотрицательных целых чисел X и Y
путем вычисления суммы X копий числа Y. Выражение 3 ´ 4 вычисляется посредством нахождения
суммы трех четверок. Правильно ли составлен данный фрагмент? Поясните свой ответ.
Произведение ← 0;
Счетчик ← 0;
repeat {Произведение ← Произведение + Y;
Счетчик ← Счетчик + 1}
until (Счетчик = X)
43.  Следующий фрагмент программы составлен
для определения, какое из двух целых чисел X и Y является большим. Является ли
этот фрагмент правильным? Поясните свой ответ.
Разность ← X—Y;
if (Разность
положительна)
then {напечатать "X больше Y"}
else {напечатать "Y больше X"}
44.  Следующий фрагмент программы должен
находить наибольший элемент в непустом списке целых чисел. Правиль- но ли он
составлен? Поясните свой ответ.
Значение ← значение первого элемента
списка; Текущий ← значение первого элемента списка; while (Текущий
≠ последнему элементу списка) do
{if (Текущий > Значение)
then {Значение ← Текущий}
Текущий ← значение следующего
элемента списка}
45.   а) Определите предусловия для
алгоритма последовательного поиска. Установите инвариант цикла для структуры while в этой программе, который, будучи
объединен с условием окончания цикла, предполагает, что по окончании этого
цикла алгоритм правильно сообщит об успехе или
неудаче.
б) Приведите аргументы в пользу того, что цикл while действительно
завершается.
46.  Опираясь на предусловие для
приведенной ниже программы, утверждающее, что параметрам X и Y присвоены не-
отрицательные целые значения, определите инвариант цикла ее структуры while, который, будучи объединен с
указанным условием окончания, предполагает, что значение переменной Z по
завершении цикла будет X – Y.
Z ← X;
J ← 0;
while (J < Y) do

{Z ←
Z-1;
J ←
J+l}

Скачано с www.znanio.ru

file_name: ЭФФЕКТИВНОСТЬ И ПРАВИЛЬНОСТЬ.docx

alt: ЭФФЕКТИВНОСТЬ И ПРАВИЛЬНОСТЬ

alt: Счетчик = 1) 1. Разработайте рекурсивную версию алгоритма

alt: {Z ← Z-1; J ← J+l}

title: ЭФФЕКТИВНОСТЬ И ПРАВИЛЬНОСТЬ.docx