file_name: технология продуктивного чтения.ppt

alt: Некоторые приемы продуктивного чтения

description:
Некоторые приемы продуктивного чтения
Штейникова О.Н.
учитель русского языка
и литературы МАОУ «СОШ №108»

description:
Чтение – это окошко, через которое дети видят
и познают мир и самих себя.
Оно открывается перед ребёнком лишь тогда,
когда, наряду с чтением,
одновременно с ним и даже раньше,
чем впервые раскрыта книга,
начинается кропотливая работа над словами.
В.А. Сухомлинский

alt: Технология продуктивного чтения

description:
Технология  продуктивного  чтенияЦель – самостоятельное понимание текстов.Средство -  приемы освоения текста до чтения, во время чтения и после чтения.

Достижение этой цели предполагает решение следующих задач:

1. Формирование техники чтения и приемов понимания и анализа текста; Одновременное развитие интереса к самому процессу чтения, потребности читать;

2. Введение детей через литературу в мир человеческих отношений, нравственно-этических ценностей; формирование эстетического вкуса;

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

4.  Приобщение к литературе как  искусству слова и практическое ознакомление с теоретико-литературными понятиями.

alt: Метод 6 вопросов «Кто? Что? Когда?

description:
Метод 6 вопросов
«Кто? Что? Когда? Где? Как?»
             При чтении любого текста необходимо задавать шесть вопросов: «Кто главные действующие лица? Что именно происходит? Когда и где происходит действие? Почему и как?»

alt: Один день из жизни литературного героя»

description:
«Один день из жизни литературного героя».
- Расскажите о своём самом памятном дне в жизни.- Был ли такой день у литературного героя?- Чем он особенный?

description:
 Круг «Вена»
	Это две пересекающихся окружности, в каждой из которых пишется, например характеристика героев, а в месте пересечения окружностей (вене) указывается общее в образах. Данный приём используется для сравнения образов, произведений, исторических эпох и т. д.

description:
 «Письмо по кругу».

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

description:
«Читаем наоборот»

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

description:
«Нарисуйте счастье»

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

alt: Комментированное чтение – это толкование текста в форме объяснений, предположений, рассуждений: читать должны дети, а комментировать – учитель интересные аргументируемые суждения детей вплетать в общий…

description:
Комментированное чтение – это толкование текста в форме объяснений, предположений, рассуждений:

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

alt: Памятка Во время чтения . Прочитай текст, ведя диалог с автором с помощью знаков-подсказок:

description:
Памятка

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

description:
Дневник двойных записей

   1.Учитель дает указание учащимся разделить тетрадь на две части.
    2. В процессе чтения ученики должны в левой части записать моменты, которые поразили, удивили, напомнили о   каких-то    фактах,    вызвали     какие- либо ассоциации; в правой – написать    лаконичный      комментарий: почему     именно   этот  момент удивил, какие ассоциации вызвал, на какие мысли натолкнул.

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

description:
 Достоинства  технологии продуктивного чтения

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

alt: Не мыслям надобно учить, а мыслить»

description:
« Не мыслям надобно учить, а мыслить»
                          Э.Кант

title: Презентация опыта "Технология продуктивного чтения"


file_name: Тест По страницам тех лет.pptx

alt: Тест «По страницам войны» Макарова

description:
Тест
«По страницам войны»

Макарова Юлия

alt: Вторая Мировая война закончилась: 13 января 1945 года 2 сентября 1945 года 12 января 1945 года 9 мая 1945 года

description:
2. Великая Отечественная война длилась:
1418 дней
1126 дней
1512 дней
1653 дня

alt: Мамаев курган» находится в городе:

description:
3. «Мамаев курган» находится в городе:

Киев
Волгоград
Ростов-на-Дону
Москва

description:
4. Выберете летчиков, прославившихся в ходе ВОВ:

Н. С. Хрущев
И. Н. Кожедуб
И. Х. Баграмян
А. И. Покрышкин
Н. Ф. Гастелло
Л. И. Брежнев

description:
5. Определите даты, связанные с ключевыми событиями Сталинградской битвы:

17 июля - 18 ноября 1942 г
4-19 марта 1943 г
23 августа 1942 г. – 2 февраля 1943 г
5 июля - 23 августа 1943 г.
23 ноября 1942 г.
26 октября - 29 ноября 1942 г

description:
6. Какое название было у плана немцев по захвату Москвы?
«Барбаросса»«Тайфун»«Цитадель»«Уран»

description: 7. Какой плакат создал в 1941 году художник Ираклий Тоидзе?

description:
8. Этому человеку звание Маршала Советского Союза было присвоено последний раз. После него это звание больше никому не присваивалось

Дмитрий Тимофеевич Язов

Николай Николаевич Воронов

Семён Константинович Куркоткин

alt: Маршал Победы» это: К.К. Рокоссовский

description:
9. «Маршал Победы» это:

К.К. Рокоссовский

И.С. Конев

Г.К. Жуков

description:
10. Эта медаль стала одной из первых советских медалей военного времени. Первым был награждён Жданов Андрей Александрович - партийный и государственный деятель.

За оборону Ленинграда

Медаль Ушакова

За победу над Японией

За освобождение Праги

description:
11. Многие коллекционеры считают этот орден самым красивым из орденов СССР. Орден является младшим из «полководческих» орденов. Он единственный среди них, имеющий только одну степень.

Орден Красной Звезды

Орден Славы

Орден Александра Невского

description:
Я сделал … ошибок
Самый лёгкий вопрос для меня ….
Вопрос который вызвал затруднения …
Я узнал для себя новое …
Свою работу оцениваю…

title: Тест по ВОВ "По страницам тех лет"


file_name: Ливерморий (Унунгексий).pptx

alt: ХИМИЧЕСКИЙ ЭЛЕМЕНТ ЛИВЕРМОРИЙ

description:
ХИМИЧЕСКИЙ
 ЭЛЕМЕНТ
 ЛИВЕРМОРИЙ

alt: Унунге́ксий (лат. Ununhexium ,

description:
Унунге́ксий (лат. Ununhexium, Uuh), официально предложено название ливерморий(лат.Livermorium, Lv) — 116-й химический элемент VI группы периодической системы,атомный номер 116, атомная масса 293.

Название
Официально предложенное, утверждённое, название ливерморий дано в честь города Ливермор (Калифорния), где располагается Ливерморская национальная лаборатория.

description:
История открытия:
Первые сообщения о синтезе в Беркли (США) элемента №116 появились в 1999 году. Но эти эксперименты не удалось воспроизвести и впоследствии они были признаны сфальсифицированными.В июне 2000 года элемент 116 был синтезирован российскими учеными из Объединенного Института ядерных исследований (Дубна) в результате бомбардировки кюрия ионами кальция-48:96Cm248 + 20Ca48 + => 116 Lv293 + 3nРабота была выполнена в сотрудничестве с Ливерморской национальной лабораторией (США). Было показано также образование в этом эксперименте и других изотопов элемента 116. Образуется изотоп элемента 116 и при a-распаде элемента 118, оганессона:118Og294 => 116 Lv290 + 2He4Все эти изотопы чрезвычайно неустойчивы и, претерпевая a-распад, образуют изотопы флеровия, элемента 114, например:116 Lv292 => 114 Fl288 + 2He4

description:
Последующий a-распад и этого элемента приводил к элементу 112, коперникию. Образование коперникия было доказано по сходству его химических свойств со свойствами ртути. Химическая идентификация 112-го элемента стала подтверждением синтеза элементов с атомными номерами 114 и 116.В июне 2011 года открытие элемента 116 утвердил Международный союз теоретической и прикладной химии (IUPAC), в мае 2012 г. было утверждено название элемента Ливерморий (Lv).Это название было предложено в честь Ливерморской национальной лаборатории имени Лоуренса. Ее ученые уже более 20 лет участвуют в экспериментах по синтезу новых элементов, проводимых в Дубне.

История открытия

alt: Получение Изотопы унунгексия были получены в результате ядерных реакций:

химия

group: Дисциплины

title: Презентация по Химии на тему "Химический  элемент - Ливерморий"


file_name: урок географии в 5 классе _Зачем нам география_.ppt

description:
Зачем нам география и как мы будем ее изучать

География 5 класс
Подготовил и провел учитель географии Лабазанов Ш.А.

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

description:
Наш географический опыт

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

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

Страбон (I в) – греческий историк и географ
Современники так и называли его - географ

alt: Слово «география» греческое и означает « землеописание »

description:
Слово «география» греческое и означает «землеописание»

	Она занимается не только описанием сложных процессов на Земле, но и их объяснением, составлением прогнозов. У истоков географии стояли великие люди: Страбон, которого называли Географ; Эратосфен, написавший сочинение «Географика». С тех пор это слово стало названием науки о планете Земля.

description:
Зачем нам география?

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

alt: «Зачем купцу география?»

description: «Зачем купцу география?»

description: Зачем нам, современным людям, география? Какое она имеет значение для людей и для каждого из нас лично? Есть ли среди родных и близких учащихся люди, чья профессия связана с географией?

description:
Главный вывод

	География помогает нам видеть и раскрывать образ мира, ориентироваться в нем.

alt: ФИЗКУЛЬТМИНУТКА

description: ФИЗКУЛЬТМИНУТКА

description: Каждая наука ставит перед собой задачи, которые изучаются с помощью определенных методов исследования. Используя схему на с. 6 «Задачи географии», учащиеся знакомятся с их особенностями.

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

description:
 Знакомство с учебником и требованиями к уроку географии

Внимательно изучив схему (с. 7), вы будете иметь четкое представление о структуре учебника.

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

description: В конце каждого параграфа имеется рубрика «Запомните», в которой жирным шрифтом выделены основные термины, географические названия и имена. Их необходимо знать и уметь находить на карте. Чтобы лучше усвоить материал параграфа, учащиеся должны отвечать на вопросы и выполнять задания рубрик «Это я знаю», «Это я умею», «Это мне интересно». Первая рубрика помогает усвоить текст параграфа, вторая и третья позволяют учащимся творчески подходить к делу, выполняя различные задания.

description: Верный помощник, к которому учащиеся должны постоянно обращаться, — это раздел «Как лучше работать с учебником, чтобы достичь успеха» в рубрике «Шаг за шагом» (с. 7).    Рубрика «Шаг за шагом» имеется во многих параграфах, она выполняет роль консультанта-помощника, объясняющего, как выполнить то или иное действие.

alt: Обратите внимание на карты, помещенные в конце учебника

description:
Задание 1.

Вы приступили к изучению одной из самых древних наук – географии. Название науки предложил древнегреческий ученый Эратосфен. Слово «география» в переводе с греческого означает землеописание ( ге - Земля, графо – пишу, описываю). На разных этапах развития географии различными были ее содержание и задачи. Прочитайте фрагмент § 1 «Зачем купцу география?». Какой главный вывод вы сделали?

alt: Задание 2. Дополните схему.

description:
Задание 2.

Дополните схему.
   Задачи современной науки географии

Приведите примеры каждой из перечисленных задач

Описывать

alt: Задание 3. Нарисуйте схему «Методы географической науки»

description:
Задание 4.

Дополните схему.

Что изучает география

С помощью чего

Зачем изучают

description:
Задание 5: Выберите информацию, которая является географической

	Санкт-Петербург – знаменитое «окно в Европу», прекраснейший город на Неве, созданный благодаря Петру I. Петербург похож на Венецию – множество мостов, каналов, однако архитектура российского города неповторима. Каждый, кто хоть раз побывал в Санкт-Петербурге, оставляет в нем свое сердце навсегда.
	Город на Неве – Санкт-Петербург – маленькая Европа в России. Петербург считается северной столицей России и однозначно ее культурной столицей. Для того чтобы обойти все достопримечательности, дворцы, музеи и соборы Петербурга, не хватит и месяца. ВУЗы Санкт-Петербурга могут похвастаться самыми выдающимися выпускниками, которые вносят существенный вклад во все сферы жизнедеятельности страны. У Петербурга множество пригородов, которые несут не меньшую историческую и культурную ценность: Петергоф, Павловск, Пушкино и другие. Изделия Петергофской гранильной фабрики хранятся в лучших музеях мира.

alt: Домашнее задание 1. Изучить § 1

description:
 Домашнее задание

1. Изучить § 1. 2. Ответить на вопросы 1-3. 3. Выполнить задание 4.

description:
    4. Выяснить с помощью этикеток, откуда в ваш дом поставлены продукты питания. Заполнить и сделать анализ таблицы.

№

Название продуктов питания

Город

Страна

1

2

3

Общий вывод:

alt: Рефлексия

description: Рефлексия


file_name: 9.3.2.1 Климатообразующие факторы в Казахстане.ppt

alt: Климатообразующие факторы Казахстана

description: Климатообразующие факторы Казахстана

description:
Что такое атмосфера?
Из каких слоёв она
состоит?
Что называют воз-
душной  массой?
Что такое погода?
Что такое климат?
Какие климатообразу-
ющие  факторы вы
знаете?
Чем они отличаются
друг от друга?

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

alt: Виды солнечной радиации прямая рассеянная поглощённая отражённая

description:
Прямая  - та часть солнечной радиации,
которая достигает поверхности Земли беспрепятственно

Рассеянная   - та часть солнечной радиации, которая достигает поверхности Земли не отражаясь облаками

Отражённая   - та часть солнечной радиации, которая отражается от поверхности Земли или облаков

Ппоглощённая  - та часть солнечной радиации, которая тратится на нагрев земной поверхности

Суммарная   - прямая плюс рассеянная  солнечная радиация

Зависит от угла падения солнечных лучей

description:
Циркуляция атмосферы

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

Циркуляция атмосферы – всё разнообразие движений воздуха, или система воздушных течений.

Конвекция  - перенос тепла движущейся
средой

alt: Какие типы воздушных масс вы знаете?

description:
Какие типы воздушных масс вы
знаете?
Какими свойствами они обладают?

АВм - арктические воздушные массы

УВм - умеренные воздушные массы

ТВм - тропические воздушные массы

Какие  воздушные массы влияют на
климат Казахстана?

ЭВм - экваториальные воздушные
массы

description:
Авм
сухие, холодные
весной и осенью заморозки, снег

Увм
зимой тёплые, летом прохладные
приносят осадки

ТВм
жаркие и сухие, на юге РК – засухи,
формируются над Средней Азией

Сибирский антициклон –
область повышенного атмосферного
давления над Восточной Сибирью

title: Климатообразующие факторы


file_name: Двоичная система счисления.ppt

description:
Двоичная система счисления.
Представление чисел в пк.

Учитель информатики ГБОУ ШИ «Олимпийский резерв»
Подзолкина Людмила Сергеевна

9 класс

description:
Представление информации с помощью какого-либо языка называется кодированием. В основу представления информации в компьютере была взята двоичная система счисления.
Система счисления (СС) - это совокупность правил для обозначения и наименования чисел.
Основание системы счисления -  количество символов, используемых для представления числа в данной системе счисления.
Например: в 10-тичной системе счисления основание – 10 (для записи чисел используются цифры от 0 до 9), в 2-ичной системе  счисления основание – 2 (для записи чисел используются 2 цифры 0 и 1)
Двоичная СС содержит в себе две цифры – 0 и 1 (0 - отсутствие электрического сигнала;     1 - наличие сигнала).
.

информация в памяти пк

description:
Арифметические действия в двоичной системе счисления

Сложение

Пример2. Сложить числа 111112 и 1112

Решение:         11111
                   +     111
                     100110

 Пример1.  Сложить числа 1112 и 102.
Решение:     111
                +    10
                   1001

Вычитание

Пример2.  Из числа 1000012  вычесть число 1112
Решение:	_ 100001
        111
    11010

Правило

0-0=0
1-0=1
1-1=0
0-1=1
(занимаем у
старшего разряда)

Пример1. Из числа  10012 вычесть число 1112.

Решение:          _ 1001
                      111
                                10

description:
Правило перевода чисел из одной системы счисления в другую

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

Ответ: 567 = 1000110111

description:
Правило перевода из двоичной системы счисления в десятичную

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

Пример:

description:
ЗАДАНИЕ                   на действия в двоичной системе счисления и перевод чисел

Переведите числа из 10-ой сс в 2-ую сс:
6910
1981
5412
8493
1274

Выполните сложение и вычитание чисел  в 2-ной сс

      110001011
+ -   11101111

      10001011
+ -  10110110

      100001010
+ -    11101011

       110001001
+ -    10101101

Двоичные числа 1011001, 11110, 11011011  перевести в десятичную систему.

alt: Форматы представления чисел целочисленный целые положительные числа целые числа со знаком вещественные с плавающей точкой с фиксированной точкой

description:
   Целые числа могут представляться в компьютере со знаком или без знака.
   Целые числа без знака обычно занимают в памяти один или два байта и принимают в однобайтовом формате значения -
от 000000002 до 111111112 ,
   в двубайтовом формате -
 от 00000000 000000002 до 11111111111111112.

Как представляются в компьютере целые числа?

description:
0

1

Представим число 4210 в двоичной системе счисления, а затем представим как будет выглядеть это число в памяти компьютера.  4210 = 1010102.
Запишем полученное число в восьмиразрядную ячейку. Запись в ячейку производится с конца, то есть последняя цифра числа записывается в последний разряд ячейки, потом предпоследнюю цифру в предпоследний разряд ячейки и так далее пока не закончится число. Свободные разряды слева заполняются нулями.
Самый старший разряд (первый слева) – хранит знак числа. Если число положительное, то этот разряд равен 0, если отрицательное – 1.

Представление целых положительных чисел в форме с фиксированной точкой

Самое большее положительное число, которое можно вписать в восьмиразрядную сетку имеет вид:

Это число 11111112 = 12710 . Максимальное целое положительное число, помещающееся в восьмиразрядную ячейку, равно 127.

0

1

0

1

0

1

0

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

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

Пример:
Внутреннее представление числа  4210 в восьмиразрядной ячейке: 4210 = 1010102
1) 001010102) 11010101 это обратный код 3) + 111010110 получили представление числа – 4210 в восьмиразрядной ячейке.
Старший разряд получил значение 1 автоматически. Единица в старшем разряде – признак отрицательного числа. Сложим числа 42 и – 42. Должны получить 0, проверим:
+ 00101010 11010110100000000 получили число, старший разряд которого выходит за пределы восьмиразрядной ячейки, таким образом восьмиразрядная ячейка заполнена нулями, т.е. полученное при сложение число равно 0.
Представление восьмиразрядного отрицательного числа – Х дополняет представление соответствующего положительного числа Х до значения 28. Поэтому представление отрицательного целого числа называется дополнительным кодом.

Представление целых отрицательных чисел в форме с фиксированной точкой

description:
а) Записать внутреннее представление числа 32 в восьмиразрядную ячейку 3210 = ?2
б) Записать внутреннее представление числа –32 в восьмиразрядную ячейкув) Определить какому десятичному числу соответствует двоичный код 00010101 восьмиразрядного представления целого числа.
г) Определить какому десятичному числу соответствует двоичный код 11111110 восьмиразрядного представления целого числа.

Задание:

intro: Материал к уроку Двоичная система счисления. Представление чисел. Рассмотрены действия в 2-ой сс, правила перевода чисел иъ одной сс в другую с заданиями

title: Презентация к уроку


description:
Знакомство с редактированием векторных данных. Оптимизация местоположения.

Выполнили:
Таиров Бахтиёр, Махситалиев Камрон
студенты группы 617-19

description:
Что такое векторные данные?

Векторные данные являются способом представления объектов реального мира в среде ГИС. Объект – это все, что Вы можете увидеть на ландшафте. Представьте себе, что Вы стоите на вершине холма. Глядя вниз, Вы различаете дома, дороги, деревья, реки и т.д. Все это объекты, которые можно представить в ГИС-приложении. Векторные объекты имеют атрибуты, состоящие из текстовой и числовой информации, описывающей каждый объект.
Векторный объект имеет форму, записанную в виде геометрии. Геометрия состоит из одной или большего числа связанных вершин. Вершина описывает позицию в пространстве, используя оси X, Y и (возможно) Z. Геометрии, которые включают вертикальную ось Z, часто называются 2.5D, т.к. они описывают только высоту или только глубину каждой вершины, но не оба параметра одновременно.

alt: Редактирование векторных данных

description:
Редактирование векторных данных

ГИС-приложение позволяет создавать и изменять геометрию данных в слое. Этот процесс называется оцифровкой. Если слой содержит полигоны (например, сельско-хозяйственные дамбы), ГИС-приложение не позволит создавать линии в этом слое. Аналогично, если Вы хотите изменить форму объекта, то приложение позволит Вам это сделать только в том случае, если новая форма допустима. Например, он не позволит вам редактировать линию таким образом, чтобы она имела только одну вершину – как сказано выше, каждая линия должна иметь по крайней мере две вершины.
Создание и редактирование векторных данных является важной функцией ГИС, так как это один из основных способов создания новых данных об интересующих Вас объектах. Например, вы отслеживаете речное загрязнение. Вы могли бы использовать ГИС для оцифровки всех ливневых водостоков в виде точечных объектов. Кроме того, можно оцифровать саму реку в виде полилинии. И наконец, вы можете взять пробы уровня кислотности вдоль течения реки и оцифровать места забора в виде точек.
Помимо создания собственных данных, существует множество бесплатных векторных данных, которыми Вы можете пользоваться. Например, Вы можете получить данные, обратившись в официальную картографическую службу своей страны.

description:
Масштаб и векторные данные

Масштаб карты – важная проблема, о которой необходимо помнить, работая с векторными данными в ГИС. Создание новых данных чаще всего происходит путем оцифровки существующих бумажных карт или съемкой на местности с помощью геодезического и GPS-оборудования. Карты имеют различные масштабы, и если Вы переносите векторные данные из карты в среду ГИС (например, оцифровывая бумажные карты), эти данные будут иметь те же проблемы, что и исходные данные. Пример показан ниже. Из-за неверно выбранного масштаба могут возникнуть многие проблемы. Например, использование векторных данных, показанных для планирования заповедной части болота может привести к исключению важных частей болот из заповедника! С другой стороны, если Вы хотите создать региональную карту, эти данные могут быть достаточны, и Вы сохраните время и усилия при их создании.

alt: Векторные данные (красные линии), оцифрованные с мелко-масштабной карты (1:1 000 000)

description:
Векторные данные (красные линии), оцифрованныес мелко-масштабной карты (1:1 000 000)

Векторные данные (зелённые линии), оцифрованныес крупно-масштабной карты (1:50 000)

description:
Проблемы с векторными данными

Также векторные данные требуют немалой работы и текущего обслуживания для поддержания точности и достоверности данных. Неточные данные могут появиться, когда инструменты для их создания неверно настроены или люди, создающие данные, были невнимательны, а также когда время и финансы не позволяют достаточной степени точности сбора данных, и т.д. Если Вы располагаете некачественными векторными данными, Вы часто можете обнаружить это, просматривая данные в ГИС-приложении. Например, Вы можете видеть разрывы, когда края прилегающих полигонов некорректно состыкованы. Когда линейный объект неточно прилегает к другому объекту, с которым он должен быть связан, например дорога не доходит до перекрестка или приток не впадает в реку, это также может вызвать проблемы. Ниже показано, как выглядят подобные «недолеты» и «перелеты». Из-за возможности подобных ошибок очень важна внимательная и точная оцифровка.

description:
Направления оптимизации.

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

description:
Оптимизация местоположения.

Пространственный анализ, моделирование, ведение единой географической базы данных различных объектов со всеми их атрибутами и другие возможности ГИС позволяют добиться существенного снижения затрат, сократить время доставки, оптимально использовать имеющиеся ресурсы и повысить качество обслуживания клиентов. Прежде всего, это анализ существующих и планирование новых маршрутов доставки.
Маршрутизация — это не просто путь из точки А в точку Б. Даже в случае единичных доставок, необходимо учитывать несколько факторов (например, в самом простом случае, минимальное время доставки).

description:
Оптимизация местоположения.

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

description:
Задача.

Предстоит решить задачу выбора оптимального местоположения участка для строительства производственного объекта. Критерии выбора следующие:
оптимальные зоны для размещения — открытые пространства, такие как выгоны, пустыри, луга, вырубки и т.д;
предельный угол наклона рельефа — 12,5°;
участок должен располагаться в непосредственной близости от автомобильных дорог;
участок должен располагаться в непосредственной близости от крупных водотоков, поскольку требуется водоснабжение;
необходимая площадь участка — не менее 30 000 м2

description:
Заключения

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

alt: Список литературы https://wiki

description:
Список литературы

https://wiki.gis-lab.info/w/Краткое_введение_в_ГИС._Часть_2:_Векторные_данные

https://www.itweek.ru/idea/article/detail.php?ID=167806

https://tsamsonov.github.io/arcgis-course/weighted-overlay.html

alt: Спасибо за внимание

description: Спасибо за внимание


file_name: Си_ДинСтруктурыДанных.ppt

alt: Тема 1. Указатели Динамические структуры данных (язык

description:
Тема 1. Указатели

Динамические структуры данных(язык Си)

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

description:
2

Статические данные

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

int x, y = 20;
float z, A[10];
char str[80];

alt: Динамические данные размер заранее неизвестен, определяется во время работы программы память выделяется во время работы программы нет имени?

description:
3

Динамические данные

размер заранее неизвестен, определяется во время работы программы
память выделяется во время работы программы
нет имени?

Проблема:
     как обращаться к данным, если нет имени?
Решение:
    использовать адрес в памяти
Следующая проблема:
     в каких переменных могут храниться адреса?
     как работать с адресами?

alt: Указатели Указатель – это переменная, в которую можно записывать адрес другой переменной (или блока памяти)

description:
4

Указатели

Указатель – это переменная, в которую можно записывать адрес другой переменной (или блока памяти).
Объявление:

Как записать адрес:

char  *pC; // адрес символа
           // (или элемента массива)
int   *pI; // адрес целой переменной
float *pF; // адрес вещественной переменной

int m = 5, *pI;
int A[2] = { 3, 4 };
pI = & m;    // адрес переменной m
pI = & A[1]; // адрес элемента массива A[1]
pI = NULL;  // нулевой адрес

&

scanf("%d", &m);

alt: Обращение к данным Как работать с данными через указатель?

description:
5

Обращение к данным

Как работать с данными через указатель?

Как работать с массивами?

int m = 4, n, *pI;
pI = &m;
printf ("m = %d", * pI); // вывод значения
n = 4*(7 - *pI);         // n = 4*(7 - 4) = 12
*pI = 4*(n – m);         // m = 4*(12 – 4) = 32
printf("&m = %p", pI); // вывод адреса

int *pI, i, A[] = {1, 2, 3, 4, 5, 999};
pI = A;     // адрес A[0] записывается как A
while ( *pI != 999 ) { // while( A[i] != 999 )
  *pI += 2; // A[i] += 2;
  pI++;     // i++ (переход к следующему)
  }

*

%p

«вытащить» значение по адресу

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

description:
6

Что надо знать об указателях

указатель – это переменная, в которой можно хранить адрес другой переменной;
при объявлении указателя надо указать тип переменных, на которых он будет указывать, а перед именем поставить знак *;
знак & перед именем переменной обозначает ее адрес;
знак *  перед указателем в рабочей части программы (не в объявлении) обозначает значение ячейки, на которую указывает указатель;
для обозначения недействительного указателя используется константа NULL (нулевой указатель);
при изменении значения указателя на n он в самом деле сдвигается к n-ому следующему числу данного типа, то есть для указателей на целые числа на n*sizeof(integer) байт;
указатели печатаются по формату %p.

alt: Тема 2. Динамические массивы Динамические структуры данных (язык

description:
Тема 2. Динамические массивы

Динамические структуры данных(язык Си)

alt: Где нужны динамические массивы?

description:
8

Где нужны динамические массивы?

Задача. Ввести размер массива, затем – элементы массива. Отсортировать массив и вывести на экран.
Проблема:
	размер массива заранее неизвестен.
Пути решения:
выделить память «с запасом»;
выделять память тогда, когда размер стал известен.
Алгоритм:
ввести размер массива;
выделить память ;
ввести элементы массива;
отсортировать и вывести на экран;
удалить массив.

выделить память

удалить массив

alt: Программа #include void main() { int *A,

description:
9

Программа

 #include <stdio.h>
 void main()
 {
 int *A, N;
 printf ("Введите размер массива > ");
 scanf ("%d", &N);
 A = new int [N];
 if ( A == NULL ) {
   printf("Не удалось выделить память");
   return;
   }
 for (i = 0; i < N; i ++ ) {
   printf ("\nA[%d] = ", i+1);
   scanf ("%d", &A[i]);
   }
 ...
 delete pI;
 }

delete A;

A = new int [N];

выделить память (С++)

освободить память

for (i = 0; i < N; i ++ ) {
  printf ("\nA[%d] = ", i+1);
  scanf ("%d", &A[i]);
  }

работаем так же, как с обычным массивом!

if ( A == NULL ) {
  printf("Не удалось выделить память");
  return;
  }

проверка

alt: Динамические массивы для выделения памяти в языке

description:
10

Динамические массивы

для выделения памяти в языке Си используются функции malloc и calloc;
в языке C++ удобнее использовать оператор new;
          указатель = new тип [размер];
результат работы оператора new – адрес выделенного блока памяти, который нужно сохранить в указателе;
если оператор new вернул нулевой указатель (NULL), память выделить не удалось;
с динамическим массивом можно работать так же, как и с обычным (статическим);
для освобождения блока памяти нужно применить оператор delete:
 		delete указатель;

alt: Ошибки при работе с памятью Запись в «чужую» область памяти: память не была выделена, а массив используется

description:
11

Ошибки при работе с памятью

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

alt: Динамические матрицы Задача. Ввести размеры матрицы и выделить для нее место в памяти во время работы программы

description:
12

Динамические матрицы

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

alt: Вариант 1. Свой блок – каждой строке

description:
13

Вариант 1. Свой блок – каждой строке

Адрес матрицы:
матрица = массив строк
адрес матрицы = адрес массива, где хранятся адреса строк
адрес строки = указатель
адрес матрицы = адрес массива указателей

int **A;

typedef int *pInt;
pInt *A;

или через объявление нового типа данных
pInt = указатель на int

Объявление динамической матрицы:

A[M][0]    ...    A[M][N]

A[0][0]    ...    A[0][N]

alt: Вариант 1. Свой блок – каждой строке typedef int *pInt; void main() { int

description:
14

Вариант 1. Свой блок – каждой строке

typedef int *pInt;
void main()
{
  int M, N, i;
  pInt *A;
  ...
  A = new pInt[M];
  for ( i = 0; i < M; i ++ )
    A[i] = new int[N];
  ...
  for ( i = 0; i < M; i ++ )
    delete A[i];
  delete A;
}

A = new pInt[M];

for ( i = 0; i < M; i ++ )
  A[i] = new int[N];

for ( i = 0; i < M; i ++ )
  delete A[i];

delete A;

// ввод M и N

// работаем с матрицей A, как обычно

выделяем массив указателей

выделяем массив под каждую строку

освобождаем память для строк

освобождаем массив адресов строк

alt: Вариант 2. Один блок на матрицу

description:
15

Вариант 2. Один блок на матрицу

A

Выделение памяти:

A[0]       ...          A[M]

A[0][0] … A[1][0] … A[2][0]        ...            A[M][N]

Освобождение памяти:

A = new pInt[M];
A[0] = new int [M*N];

delete A[0];
delete A;

Расстановка указателей:

for ( i = 1; i < N; i ++ ) A[i] = A[i-1] + N;

alt: Тема 3. Структуры Динамические структуры данных (язык

description:
Тема 3. Структуры

Динамические структуры данных(язык Си)

alt: Структуры Структура – это тип данных, который может включать в себя несколько полей – элементов разных типов (в том числе и другие структуры)

description:
17

Структуры

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

Свойства:
автор (строка)
название (строка)
год издания (целое число)
количество страниц (целое число)

Задача: объединить эти данные в единое целое

struct Book {
  char author[40]; // автор, символьная строка
  char title[80];  // название, символьная строка
  int year;	       // год издания, целое число
  int pages;	 // количество страниц, целое число
  };

Как ввести новый тип данных-структур?

структура

название

поля

alt: Как работать со структурами? Объявление:

description:
18

Как работать со структурами?

Объявление:

Book b; // здесь выделяется память!
Book b1 = { "А.С. Пушкин",
            "Полтава", 1998, 223 };

Заполнение полей:

strcpy ( b.author, "А.С. Пушкин" );
strcpy ( b.title,  "Полтава" );
b.year = 1998;
b.pages = 223;

Ввод полей с клавиатуры:

printf ( "Автор " );
gets ( b.author );
printf ( "Название книги " );
gets ( b.title );
printf ( "Год издания, кол-во страниц " );
scanf ( "%d%d", &b.year, &b.pages );

alt: Копирование структур По элементам:

description:
19

Копирование структур

По элементам:

Book b1, b2;
...   // здесь вводим b1
strcpy ( b2.author, b1.author );
strcpy ( b2.title, b1.title );
b2.year = b1.year;
b2.pages = b1.pages;

Задача: скопировать структуру b1 в b2.

Копирование «бит в бит»:

#include <mem.h>
...

memcpy ( &b2, &b1, sizeof(Book) );

или просто так:

b2 = b1;

куда

откуда

сколько байт

alt: Массивы структур Объявление: Book

description:
20

Массивы структур

Объявление:

Book B[10];

Обращение к полям:

for ( i = 0; i < 10; i ++ )
  B[i].year = 2008;

B[0]           ...          B[9]

author

title

year

pages

Запись в двоичный файл:

Чтение из двоичного файла:

FILE *f;
f = fopen("input.dat", "wb" );

fwrite ( B, sizeof(Book), 10, f );

f = fopen("input.dat", "rb" );
n = fread ( B, sizeof(Book), 10, f );
printf ( "Прочитано %d структур", n );

адрес массива

размер блока

сколько блоков

указатель на файл

Book

write binary

alt: Пример программы Задача: в файле books

description:
21

Пример программы

Задача: в файле books.dat записаны данные о книгах в виде массива структур типа Book (не более 100). Установить для всех 2008 год издания и записать обратно в тот же файл.

#include <stdio.h>
struct Book { … };
void main()
{
  Book B[100];
  int i, n;
  FILE *f;
  f = fopen ( "books.dat", "rb" );
  n = fread ( B, sizeof(Book), 100, f );
  fclose(f);
  for ( i = 0; i < n; i ++ ) B[i].year = 2008;
  fp = fopen("books.dat", "wb" );
  fwrite ( B, sizeof(Book), n, f );
  fclose ( f );
}

struct Book { … };

f = fopen ( "books.dat", "rb" );
n = fread ( B, sizeof(Book), 100, f );
fclose ( f );

fp = fopen("books.dat", "wb" );
fwrite ( B, sizeof(Book), n, f );
fclose ( f );

полное описание структуры

чтение массива (≤ 100 структур), размер записывается в переменную n

запись массива (n структур)

alt: Выделение памяти под структуру

description:
22

Выделение памяти под структуру

Book *p;
p = new Book;
printf ( "Автор " );
gets (  p->author  );
printf ( "Название книги " );
gets ( p->title );
printf ( "Количество страниц " );
scanf ( "%d", &p->pages );
p->year = 2008;
...
delete p;

p = new Book;

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

p->author

delete p;

освободить память

alt: Динамические массивы структур

description:
23

Динамические массивы структур

 Book *B;
 int 	n;
 printf ( "Сколько у вас книг? " );
 scanf ( "%d", &n );
 B = new Book[n];
 ...  // здесь заполняем массив B
 for ( i = 0; i < n; i++ )
   printf ( "%s. %s. %d.\n",
          B[i].author, B[i].title,
          B[i].year);
 delete B;

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

B = new Book[n];

Book *B;

delete B;

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

выделяем память

освобождаем память

alt: Сортировка массива структур Ключ (ключевое поле) – это поле, по которому сортируются структуры

description:
24

Сортировка массива структур

Ключ (ключевое поле) – это поле, по которому сортируются структуры.
Проблема: как избежать копирования структур при сортировке?
Решение: использовать вспомогательный массив указателей, при сортировке переставлять указатели.

5

1

3

2

4

5

1

3

2

4

p[0]

p[1]

p[2]

p[3]

p[4]

p[4]

p[0]

p[2]

p[1]

p[3]

До
сортировки:

После
сортировки:

Вывод результата:

for ( i = 0; i < 5; i ++ )
  printf("%d %s", p[i]->year, p[i]->title);

p[i]

p[i]

alt: Реализация в программе const N = 10;

description:
25

Реализация в программе

const N = 10;
Book B[N];
Book *p[N], *temp;
int i, j;
...	// здесь заполняем структуры
for ( i = 0; i < N; i++ )
  p[i] = &B[i];
for ( i = 0; i < n-1; i++ )
  for ( j = n-2; j >= i; j-- )
    if ( p[j+1]->year
year ) {
	temp = p[j];
	p[j] = p[j+1];
	p[j+1] = temp;
	}
for ( i = 0; i < 5; i ++ )
  printf("%d %s", p[i]->year, p[i]->title);

Book *p[N], *temp;

for ( i = 0; i < N; i++ )
  p[i] = &B[i];

for ( i = 0; i < n-1; i++ )
  for ( j = n-2; j >= i; j-- )
    if ( p[j+1]->year
year ) {
	temp = p[j];
	p[j] = p[j+1];
	p[j+1] = temp;
	}

вспомогательные указатели

начальная расстановка указателей

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

alt: Тема 4. Списки Динамические структуры данных (язык

description:
Тема 4. Списки

Динамические структуры данных(язык Си)

alt: Динамические структуры данных Строение: набор узлов, объединенных с помощью ссылок

description:
27

Динамические структуры данных

Строение: набор узлов, объединенных с помощью ссылок.
Как устроен узел:

данные

ссылки на другие узлы

Типы структур:

списки

деревья

графы

односвязный

двунаправленный (двусвязный)

циклические списки (кольца)

alt: Когда нужны списки? Задача (алфавитно-частотный словарь)

description:
28

Когда нужны списки?

Задача (алфавитно-частотный словарь).  В файле записан текст.       Нужно записать в другой файл в столбик все слова,        встречающиеся в тексте, в алфавитном порядке, и количество     повторений для каждого слова.
Проблемы:
количество слов заранее неизвестно (статический массив);
количество слов определяется только в конце работы (динамический массив).
Решение – список.
Алгоритм:
создать список;
если слова в файле закончились, то стоп.
прочитать слово и искать его в списке;
если слово найдено – увеличить счетчик повторений, иначе добавить слово в список;
перейти к шагу 2.

alt: Что такое список: пустая структура – это список; список – это начальный узел ( голова ) и связанный с ним список

description:
29

Что такое список:
пустая структура – это список;
список – это начальный узел (голова) и связанный с ним список.

Списки: новые типы данных

Структура узла:

struct Node {
  char word[40];  // слово
  int	 count;     // счетчик повторений
  Node *next;     // ссылка на следующий элемент
  };

typedef Node *PNode;

Указатель на эту структуру:

Адрес начала списка:

PNode Head = NULL;

alt: Что нужно уметь делать со списком?

description:
30

Что нужно уметь делать со списком?

Создать новый узел.
Добавить узел:
в начало списка;
в конец списка;
после заданного узла;
до заданного узла.
Искать нужный узел в списке.
Удалить узел.

alt: Создание узла PNode CreateNode ( char

description:
31

Создание узла

PNode CreateNode ( char NewWord[] )
{
  PNode NewNode = new Node;
  strcpy(NewNode->word, NewWord);
  NewNode->count = 1;
  NewNode->next = NULL;
  return NewNode;
}

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

возвращает адрес созданного узла

новое слово

alt: Добавление узла в начало списка 1)

description:
32

Добавление узла в начало списка

1) Установить ссылку нового узла на голову списка:

NewNode->next = Head;

2) Установить новый узел как голову списка:

Head = NewNode;

void AddFirst (PNode &  Head, PNode NewNode)
{
  NewNode->next = Head;
  Head = NewNode;
}

&

адрес головы меняется

alt: Добавление узла после заданного 1)

description:
33

Добавление узла после заданного

1) Установить ссылку нового узла на узел, следующий за p:

NewNode->next = p->next;

2) Установить ссылку узла p на новый узел:

p->next = NewNode;

void AddAfter (PNode p, PNode NewNode)
{
   NewNode->next = p->next;
   p->next = NewNode;
}

alt: Задача: сделать что-нибудь хорошее с каждым элементом списка

description:
34

Задача:
    сделать что-нибудь хорошее с каждым элементом списка.

Алгоритм:
установить вспомогательный указатель q на голову списка;
если указатель q  равен NULL (дошли до конца списка), то стоп;
выполнить действие над узлом с адресом q ;
перейти к следующему узлу, q->next.

Проход по списку

...
PNode q = Head;       // начали с головы
while ( q != NULL ) { // пока не дошли до конца
  ...                 // делаем что-то хорошее с q
  q = q->next;        // переходим к следующему узлу
  }
...

alt: Добавление узла в конец списка

description:
35

Добавление узла в конец списка

Задача:  добавить новый узел в конец списка.
Алгоритм:
найти последний узел q, такой что q->next  равен NULL;
добавить узел после узла с адресом q  (процедура AddAfter).
Особый случай: добавление в пустой список.

void AddLast ( PNode &Head, PNode NewNode )
{
PNode q = Head;
if ( Head == NULL ) {
   AddFirst( Head, NewNode );
   return;
   }
while ( q->next ) q = q->next;
AddAfter ( q, NewNode );
}

особый случай – добавление в пустой список

ищем последний узел

добавить узел после узла q

alt: Проблема: нужно знать адрес предыдущего узла, а идти назад нельзя!

description:
36

Проблема:     нужно знать адрес предыдущего узла, а идти назад нельзя!
Решение: найти предыдущий узел q (проход с начала списка).

Добавление узла перед заданным

void AddBefore ( PNode & Head, PNode p, PNode NewNode )
{
PNode q = Head;
if ( Head == p ) {
   AddFirst ( Head, NewNode );
   return;
   }
while ( q && q->next != p ) q = q->next;
if ( q ) AddAfter(q, NewNode);
}

особый случай – добавление в начало списка

ищем узел, следующий за которым – узел p

добавить узел после узла q

alt: Добавление узла перед заданным (II)

description:
37

Добавление узла перед заданным (II)

Задача: вставить узел перед заданным без поиска предыдущего.
Алгоритм:
поменять местами данные нового узла и узла p;

установить ссылку узла p на NewNode.

void AddBefore2 ( PNode p, PNode NewNode )
{
  Node temp;
  temp = *p; *p = *NewNode;
  *NewNode = temp;
  p->next = NewNode;
}

alt: Поиск слова в списке Задача: найти в списке заданное слово или определить, что его нет

description:
38

Поиск слова в списке

Задача: найти в списке заданное слово или определить, что его нет.
Функция Find:
вход:    слово (символьная строка);
выход: адрес узла, содержащего это слово или NULL.
Алгоритм: проход по списку.

PNode Find ( PNode Head, char NewWord[] )
{
  PNode q = Head;
  while (q && strcmp(q->word, NewWord))
    q = q->next;
  return q;
}

ищем это слово

результат – адрес узла

while ( q && strcmp ( q->word, NewWord) )
  q = q->next;

пока не дошли до конца списка и слово не равно заданному

alt: Куда вставить новое слово? Задача: найти узел, перед которым нужно вставить, заданное слово, так чтобы в списке сохранился алфавитный порядок слов

description:
39

Куда вставить новое слово?

Задача: найти узел, перед которым нужно вставить, заданное слово, так чтобы в списке сохранился алфавитный порядок слов.
Функция FindPlace:
вход:    слово (символьная строка);
выход: адрес узла, перед которым нужно вставить это слово или         NULL, если слово нужно вставить в конец списка.

PNode FindPlace ( PNode Head, char NewWord[] )
{
  PNode q = Head;
  while ( q  &&  strcmp(NewWord, q->word) > 0 )
    q = q->next;
  return q;
}

> 0

слово NewWord стоит по алфавиту до q->word

alt: Удаление узла void DeleteNode (

description:
40

Удаление узла

void DeleteNode ( PNode &Head, PNode p )
{
PNode q = Head;
if ( Head == p )
   Head = p->next;
else {
   while ( q  &&  q->next != p )
     q = q->next;
   if ( q == NULL ) return;
   q->next = p->next;
   }
delete p;
}

while ( q  &&  q->next != p )
  q = q->next;

if ( Head == p )
   Head = p->next;

Проблема: нужно знать адрес предыдущего узла q.

особый случай: удаляем первый узел

ищем предыдущий узел, такой что q->next == p

delete p;

освобождение памяти

alt: Алфавитно-частотный словарь Алгоритм: открыть файл на чтение; прочитать слово: если файл закончился ( n!=1 ), то перейти к шагу 7; если слово найдено, увеличить счетчик…

description:
41

Алфавитно-частотный словарь

Алгоритм:
открыть файл на чтение;

прочитать слово:

если файл закончился (n!=1), то перейти к шагу 7;
если слово найдено, увеличить счетчик (поле count);
если слова нет в списке, то
создать новый узел, заполнить поля (CreateNode);
найти узел, перед которым нужно вставить слово (FindPlace);
добавить узел (AddBefore);
перейти к шагу 2;
вывести список слов, используя проход по списку.

char word[80];
...
n = fscanf ( in, "%s", word );

FILE *in;
in = fopen ( "input.dat", "r" );

read, чтение

вводится только одно слово (до пробела)!

alt: Двусвязные списки Структура узла: struct

description:
42

Двусвязные списки

Структура узла:

struct Node {
  char word[40];  // слово
  int	 count;     // счетчик повторений
  Node *next;     // ссылка на следующий элемент
  Node *prev;     // ссылка на предыдущий элемент
  };

typedef Node *PNode;

Указатель на эту структуру:

Адреса «головы» и «хвоста»:

PNode Head = NULL;
PNode Tail = NULL;

alt: Задания «4»: «Собрать» из этих функций программу для построения алфавитно-частотного словаря

description:
43

Задания

«4»: «Собрать» из этих функций программу для построения алфавитно-частотного словаря. В конце файла вывести общее количество разных слов (количество элементов списка).
«5»: То же самое, но использовать двусвязные списки.
«6»: То же самое, что и на «5», но вывести список слов в порядке убывания частоты, то есть, сначала те слова, которые встречаются чаще всего.

alt: Тема 5. Стеки, очереди, деки Динамические структуры данных (язык

description:
Тема 5. Стеки, очереди, деки

Динамические структуры данных(язык Си)

alt: Стек Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца ( вершины стека )

description:
45

Стек

Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца (вершины стека). Stack = кипа, куча, стопка (англ.)
LIFO = Last In – First Out
«Кто последним вошел, тот первым вышел».
Операции со стеком:
добавить элемент на вершину (Push = втолкнуть);
снять элемент с вершины(Pop = вылететь со звуком).

alt: Пример задачи Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [] , {} и ()

description:
46

Пример задачи

Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры:
        [()]{}   ][    [({)]}
Упрощенная задача: то же самое, но с одним видом скобок.
Решение: счетчик вложенности скобок. Последовательность правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным.

alt: Решение задачи со скобками Алгоритм: в начале стек пуст; в цикле просматриваем все символы строки по порядку; если очередной символ – открывающая скобка, заносим ее…

description:
47

Решение задачи со скобками

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

[   (   (   )   )   ]   {   }

alt: Реализация стека (массив) Структура-стек: const

description:
48

Реализация стека (массив)

Структура-стек:

const MAXSIZE = 100;
struct Stack {
   char data[MAXSIZE]; // стек на 100 символов
   int  size;	     // число элементов
   };

Добавление элемента:

int Push ( Stack &S, char x )
{
if ( S.size == MAXSIZE ) return 0;
S.data[S.size] = x;
S.size ++;
return 1;
}

ошибка: переполнение стека

добавить элемент

нет ошибки

alt: Реализация стека (массив) char

description:
49

Реализация стека (массив)

char Pop ( Stack &S )
{
if ( S.size == 0 ) return char(255);
S.size --;
return S.data[S.size];
}

Снятие элемента с вершины:

Пусто	й или нет?

int isEmpty ( Stack &S )
{
if ( S.size == 0 )
     return 1;
else return 0;
}

ошибка: стек пуст

int isEmpty ( Stack &S )
{
return (S.size == 0);
}

description:
50

Программа

void main()
{
  char br1[3] = { '(', '[', '{' };
  char br2[3] = { ')', ']', '}' };
  char s[80], upper;
  int i, k, error = 0;
  Stack S;
  S.size = 0;
  printf("Введите выражение со скобками > ");
  gets ( s );
  ...  // здесь будет основной цикл обработки
  if ( ! error && (S.size == 0) )
       printf("\nВыpажение пpавильное\n");
  else printf("\nВыpажение непpавильное\n");
}

открывающие скобки

закрывающие скобки

то, что сняли со стека

признак ошибки

alt: Обработка строки (основной цикл) for ( i = 0; i < strlen(s); i++ ) { for ( k = 0; k < 3; k++ )…

description:
51

Обработка строки (основной цикл)

for ( i = 0; i < strlen(s); i++ )
  {
  for ( k = 0; k < 3; k++ )
    {
    if ( s[i] == br1[k] )  // если открывающая скобка
      {
      Push ( S, s[i] ); // втолкнуть в стек
      break;
      }
    if ( s[i] == br2[k] ) // если закрывающая скобка
      {
      upper = Pop ( S );  // снять верхний элемент
      if ( upper != br1[k] ) error = 1;
      break;
      }
    }
  if ( error ) break;
  }

цикл по всем символам строки s

цикл по всем видам скобок

ошибка: стек пуст или не та скобка

была ошибка: дальше нет смысла проверять

alt: Реализация стека (список) Добавление элемента:

description:
52

Реализация стека (список)

Добавление элемента:

Структура узла:

struct Node {
	char data;
      Node *next;
      };
typedef Node *PNode;

void Push (PNode &Head, char x)
{
   PNode NewNode = new Node;
   NewNode->data = x;
   NewNode->next = Head;
   Head = NewNode;
}

alt: Реализация стека (список) Снятие элемента с вершины: char

description:
53

Реализация стека (список)

Снятие элемента с вершины:

char Pop (PNode &Head) {
  char x;
  PNode q = Head;
  if ( Head == NULL ) return char(255);
  x = Head->data;
  Head = Head->next;
  delete q;
  return x;
}

Изменения в основной программе:

Stack S;
S.size = 0;
...
if ( ! error && (S.size == 0) )
     printf("\nВыpажение пpавильное\n");
else printf("\nВыpажение непpавильное \n");

PNode S = NULL;

(S == NULL)

стек пуст

alt: Вычисление арифметических выражений a b + c d + 1 - /

description:
54

Вычисление арифметических выражений

a b + c d + 1 - /

Как вычислять автоматически:

Инфиксная запись
(знак операции между операндами)

(a + b) / (c + d – 1)

необходимы скобки!

Постфиксная запись (знак операции после операндов)

польская нотация,
Jan Łukasiewicz (1920)

скобки не нужны, можно однозначно вычислить!

Префиксная запись (знак операции до операндов)

/ + a b - + c d 1

обратная польская нотация,
F. L. Bauer and E. W. Dijkstra

a + b

a + b

c + d

c + d

c + d  -  1

c + d  -  1

description:
55

Запишите в постфиксной форме

(32*6-5)*(2*3+4)/(3+7*2)

(2*4+3*5)*(2*3+18/3*2)*(12-3)

(4-2*3)*(3-12/3/4)*(24-3*12)

alt: Вычисление выражений Постфиксная форма: a b + c d + 1 - /

description:
56

Вычисление выражений

Постфиксная форма:

a b  +  c   d   +   1   -   /

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

a

b

a

a+b

c

a+b

d

c

a+b

c+d

a+b

1

c+d

a+b

c+d-1

a+b

X

X =

alt: Системный стек ( Windows – 1 Мб )

description:
57

Системный стек (Windows – 1 Мб)

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

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

alt: Очередь Очередь – это линейная структура данных, в которой добавление элементов возможно только с одного конца ( конца очереди ), а удаление элементов – только…

description:
58

Очередь

Очередь – это линейная структура данных, в которой добавление элементов возможно только с одного конца (конца очереди), а удаление элементов – только с другого конца (начала очереди).
FIFO = First In – First Out
«Кто первым вошел, тот первым вышел».
Операции с очередью:
добавить элемент в конец очереди (PushTail = втолкнуть в конец);
удалить элемент с начала очереди (Pop).

alt: Реализация очереди (массив) самый простой способ нужно заранее выделить массив; при выборке из очереди нужно сдвигать все элементы

description:
59

Реализация очереди (массив)

самый простой способ

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

alt: Реализация очереди (кольцевой массив)

description:
60

Реализация очереди (кольцевой массив)

alt: Реализация очереди (кольцевой массив)

description:
61

Реализация очереди (кольцевой массив)

В очереди 1 элемент:

Очередь пуста:

Очередь полна:

Head == Tail + 1

размер массива

Head == Tail + 2

Head == Tail

alt: Реализация очереди (кольцевой массив) const

description:
62

Реализация очереди (кольцевой массив)

const MAXSIZE = 100;
struct Queue {
   int data[MAXSIZE];
   int head, tail;
   };

Структура данных:

Добавление в очередь:

int PushTail ( Queue &Q, int x )
{
   if ( Q.head == (Q.tail+2) % MAXSIZE )       return 0;
   Q.tail = (Q.tail + 1) % MAXSIZE;
   Q.data[Q.tail] = x;
   return 1;
}

замкнуть в кольцо

% MAXSIZE

очередь полна, не добавить

удачно добавили

alt: Реализация очереди (кольцевой массив)

description:
63

Реализация очереди (кольцевой массив)

Выборка из очереди:

int Pop ( Queue &Q )
{
   int temp;
   if ( Q.head == (Q.tail + 1) % MAXSIZE )
     return 32767;
   temp = Q.data[Q.head];
   Q.head = (Q.head + 1) % MAXSIZE;
   return temp;
}

очередь пуста

взять первый элемент

удалить его из очереди

alt: Реализация очереди (списки) struct

description:
64

Реализация очереди (списки)

struct Node {
   int  data;
   Node *next;
   };
typedef Node *PNode;

struct Queue {
   PNode Head, Tail;
   };

Структура узла:

Тип данных «очередь»:

alt: Реализация очереди (списки) void

description:
65

Реализация очереди (списки)

void PushTail ( Queue &Q, int x )
{
   PNode NewNode;
   NewNode = new Node;
   NewNode->data = x;
   NewNode->next = NULL;
   if ( Q.Tail )
        Q.Tail->next = NewNode;
   Q.Tail = NewNode;
   if ( Q.Head == NULL )         Q.Head = Q.Tail;
}

Добавление элемента:

создаем новый узел

если в списке уже что-то было, добавляем в конец

если в списке ничего не было, …

alt: Реализация очереди (списки) int

description:
66

Реализация очереди (списки)

int Pop ( Queue &Q )
{
   PNode top = Q.Head;
   int x;
   if ( top == NULL )
      return 32767;
   x = top->data;
   Q.Head = top->next;
   if ( Q.Head == NULL )
        Q.Tail = NULL;
   delete top;
   return x;
}

Выборка элемента:

если список пуст, …

запомнили первый элемент

если в списке ничего не осталось, …

освободить память

alt: Дек Дек ( deque = d ouble e nded que ue , очередь с двумя концами) – это линейная структура данных, в которой добавление и…

description:
67

Дек

Дек (deque = double ended queue, очередь с двумя концами) – это линейная структура данных, в которой добавление и удаление элементов возможно с обоих концов.

Операции с деком:
добавление элемента в начало (Push);
удаление элемента с начала (Pop);
добавление элемента в конец (PushTail);
удаление элемента с конца (PopTail).

Реализация:
кольцевой массив;
двусвязный список.

alt: Задания «4»: В файле input.dat находится список чисел (или слов)

description:
68

Задания

«4»: В файле input.dat находится список чисел (или слов). Переписать его в файл output.dat в обратном порядке.
«5»: Составить программу, которая вычисляет значение арифметического выражения, записанного в постфиксной форме, с помощью стека. Выражение правильное, допускаются только однозначные числа и знаки +, -, *, /.
«6»: То же самое, что и на «5», но допускаются многозначные числа.

alt: Тема 6. Деревья Динамические структуры данных (язык

description:
Тема 6. Деревья

Динамические структуры данных(язык Си)

alt: 70 Деревья

description:
70

Деревья

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

description:
71

Деревья

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

корень

Какие структуры – не деревья?

alt: Деревья Предок узла x – это узел, из которого существует путь по стрелкам в узел x

description:
72

Деревья

Предок узла x – это узел, из которого существует путь по стрелкам в узел x.
Потомок узла x – это узел, в который существует путь по стрелкам из узла x.
Родитель узла x – это узел, из которого существует дуга непосредственно в узел x.

Сын узла x – это узел, в который существует дуга непосредственно из узла x.
Брат узла x (sibling) – это узел, у которого тот же родитель, что и у узла x.
Высота дерева – это наибольшее расстояние от корня до листа (количество дуг).

alt: Дерево – рекурсивная структура данных

description:
73

Дерево – рекурсивная структура данных

Рекурсивное определение:
Пустая структура – это дерево.
Дерево – это корень и несколько связанных с ним деревьев.

Двоичное (бинарное) дерево – это дерево, в котором каждый узел имеет не более двух сыновей.

Пустая структура – это двоичное дерево.
Двоичное дерево – это корень и два связанных с ним двоичных дерева (левое и правое поддеревья).

alt: Двоичные деревья Структура узла: struct

description:
74

Двоичные деревья

Структура узла:

struct Node {
  int  data;          // полезные данные
  Node *left, *right; // ссылки на левого                       // и правого сыновей
  };
typedef Node *PNode;

Применение:
поиск данных в специально построенных деревьях(базы данных);
сортировка данных;
вычисление арифметических выражений;
кодирование (метод Хаффмана).

alt: Двоичные деревья поиска Слева от каждого узла находятся узлы с меньшими ключами, а справа – с бóльшими

description:
75

Двоичные деревья поиска

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

Ключ – это характеристика узла, по которой выполняется поиск (чаще всего – одно из полей структуры).

Как искать ключ, равный x:
если дерево пустое, ключ не найден;
если ключ узла равен x, то стоп.
если ключ узла меньше x, то искать x в левом поддереве;
если ключ узла больше x, то искать x в правом поддереве.

alt: Двоичные деревья поиска Поиск в массиве (N элементов):

description:
76

Двоичные деревья поиска

Поиск в массиве (N элементов):

При каждом сравнении отбрасывается 1 элемент.
Число сравнений – N.

Поиск по дереву (N элементов):

При каждом сравнении отбрасывается половина оставшихся элементов.
Число сравнений ~ log2N.

быстрый поиск

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

description:
77

Реализация алгоритма поиска

//---------------------------------------
// Функция Search – поиск по дереву
// Вход: Tree - адрес корня,
//         x  - что ищем
// Выход: адрес узла или NULL (не нашли)
//---------------------------------------
PNode Search (PNode Tree, int x)
{
if ( ! Tree ) return NULL;
if ( x == Tree->data )
     return Tree;
if ( x < Tree->data )
  return Search(Tree->left, x);
else
  return Search(Tree->right, x);
}

дерево пустое: ключ не нашли…

нашли, возвращаем адрес корня

искать в левом поддереве

искать в правом поддереве

description:
78

Как построить дерево поиска?

//---------------------------------------------
// Функция AddToTree – добавить элемент к дереву
// Вход: Tree - адрес корня,
//         x  - что добавляем
//----------------------------------------------
void AddToTree (PNode &Tree, int x)
{
if ( ! Tree ) {
   Tree = new Node;
   Tree->data = x;
   Tree->left = NULL;
   Tree->right = NULL;
   return;
   }
if ( x < Tree->data )
     AddToTree ( Tree->left, x );
else AddToTree ( Tree->right, x );
}

дерево пустое: создаем новый узел (корень)

адрес корня может измениться

добавляем к левому или правому поддереву

alt: Обход дерева Обход дерева – это перечисление всех узлов в определенном порядке

description:
79

Обход дерева

Обход дерева – это перечисление всех узлов в определенном порядке.

Обход ЛКП («левый – корень – правый»):

125

98

76

45

59

30

16

Обход ПКЛ («правый – корень – левый»):

Обход КЛП («корень – левый – правый»):

Обход ЛПК («левый – правый – корень»):

description:
80

Обход дерева – реализация

//---------------------------------------------
// Функция LKP – обход дерева в порядке ЛКП
//               (левый – корень – правый)
// Вход: Tree - адрес корня
//----------------------------------------------
void LKP( PNode Tree )
{
if ( ! Tree ) return;
LKP ( Tree->left );
printf ( "%d ", Tree->data );
LKP ( Tree->right );
}

обход этой ветки закончен

обход левого поддерева

вывод данных корня

обход правого поддерева

alt: Разбор арифметических выражений a b + c d + 1 - /

description:
81

Разбор арифметических выражений

a b + c d + 1 - /

Как вычислять автоматически:

Инфиксная запись, обход ЛКП
(знак операции между операндами)

(a + b) / (c + d – 1)

необходимы скобки!

Постфиксная запись, ЛПК (знак операции после операндов)

a +  b / c  +  d  – 1

польская нотация,
Jan Łukasiewicz (1920)

скобки не нужны, можно однозначно вычислить!

Префиксная запись, КЛП (знак операции до операндов)

/ + a b - + c d 1

обратная польская нотация,
F. L. Bauer and E. W. Dijkstra

description:
82

Вычисление выражений

Постфиксная форма:

a b  +  c   d   +   1   -   /

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

a

b

a

a+b

c

a+b

d

c

a+b

c+d

a+b

1

c+d

a+b

c+d-1

a+b

X

X =

alt: Вычисление выражений Задача: в символьной строке записано правильное арифметическое выражение, которое может содержать только однозначные числа и знаки операций +-*\

description:
83

Вычисление выражений

Задача: в символьной строке записано правильное арифметическое выражение, которое может содержать только однозначные числа и знаки операций +-*\. Вычислить это выражение.

Алгоритм:
ввести строку;
построить дерево;
вычислить выражение по дереву.

Ограничения:
ошибки не обрабатываем;
многозначные числа не разрешены;
дробные числа не разрешены;
скобки не разрешены.

alt: Построение дерева Алгоритм: если first=last (остался один символ – число), то создать новый узел и записать в него этот элемент; иначе

description:
84

Построение дерева

Алгоритм:
если first=last (остался один символ – число), то создать новый узел и записать в него этот элемент; иначе...
среди элементов от first до last включительно найти последнюю операцию (элемент с номером k);
создать новый узел (корень) и записать в него знак операции;
рекурсивно применить этот алгоритм два раза:
построить левое поддерево, разобрав выражение из элементов массива с номерами от first до k-1;
построить правое поддерево, разобрав выражение из элементов массива с номерами от k+1 до last.

5

+

7

*

6

-

3

*

2

first

last

k

k+1

k-1

alt: Как найти последнюю операцию? Порядок выполнения операций умножение и деление; сложение и вычитание

description:
85

Как найти последнюю операцию?

Порядок выполнения операций
умножение и деление;
сложение и вычитание.

5

+

7

*

6

-

3

*

2

Приоритет (старшинство) – число, определяющее последовательность выполнения операций: раньше выполняются операции с большим приоритетом:
умножение и деление (приоритет 2);
сложение и вычитание (приоритет 1).

description:
86

Приоритет операции

//--------------------------------------------
// Функция Priority – приоритет операции
// Вход:  символ операции
// Выход: приоритет или 100, если не операция
//--------------------------------------------
int Priority ( char c )
{
  switch ( c ) {
    case '+': case '-':       return 1;
    case '*': case '/':       return 2;
    }
  return 100;
}

сложение и вычитание: приоритет 1

умножение и деление: приоритет 2

это вообще не операция

description:
87

Номер последней операции

//--------------------------------------------
// Функция LastOperation – номер последней операции
// Вход:  строка, номера первого и последнего//        символов рассматриваемой части
// Выход: номер символа - последней операции
//--------------------------------------------
int LastOperation ( char Expr[], int first, int last )
{
  int MinPrt, i, k, prt;
  MinPrt = 100;
  for( i = first; i <= last; i++ ) {
    prt = Priority ( Expr[i] );
    if ( prt <= MinPrt ) {
      MinPrt = prt;
      k = i;
      }
    }
  return k;
}

проверяем все символы

вернуть номер символа

нашли операцию с минимальным приоритетом

alt: Построение дерева Структура узла struct

description:
88

Построение дерева

Структура узла

struct Node {
  char data;
  Node *left, *right;
  };
typedef Node *PNode;

Создание узла для числа (без потомков)

PNode NumberNode ( char c )
{
  PNode Tree = new Node;
  Tree->data = c;
  Tree->left = NULL;
  Tree->right = NULL;
  return Tree;
}

возвращает адрес созданного узла

один символ, число

description:
89

Построение дерева

//--------------------------------------------
// Функция MakeTree – построение дерева
// Вход:  строка, номера первого и последнего//        символов рассматриваемой части
// Выход: адрес построенного дерева
//--------------------------------------------
PNode MakeTree ( char Expr[], int first, int last )
{
 PNode Tree;
 int k;
 if ( first == last )
   return NumberNode ( Expr[first] );
 k = LastOperation ( Expr, first, last );
 Tree = new Node;
 Tree->data  = Expr[k];
 Tree->left  = MakeTree ( Expr, first, k-1 );
 Tree->right = MakeTree ( Expr, k+1, last );
 return Tree;
}

осталось только число

новый узел: операция

description:
90

Вычисление выражения по дереву

//--------------------------------------------
// Функция CalcTree – вычисление по дереву
// Вход:  адрес дерева
// Выход: значение выражения
//--------------------------------------------
int CalcTree (PNode Tree)
{
 int num1, num2;
 if ( ! Tree->left ) return Tree->data - '0';
 num1 = CalcTree( Tree->left);
 num2 = CalcTree(Tree->right);
 switch ( Tree->data ) {
   case '+': return  num1+num2;
   case '-': return  num1-num2;
   case '*': return  num1*num2;
   case '/': return  num1/num2;
   }
 return 32767;
}

вернуть число, если это лист

вычисляем операнды (поддеревья)

выполняем операцию

некорректная операция

description:
91

Основная программа

//--------------------------------------------
// Основная программа: ввод и вычисление
// выражения с помощью дерева
//--------------------------------------------
void main()
{
  char s[80];
  PNode Tree;
  printf ( "Введите выражение > " );
  gets(s);
  Tree = MakeTree ( s, 0, strlen(s)-1 );
  printf ( "= %d \n", CalcTree ( Tree ) );
  getch();
}

alt: Дерево игры Задача. Перед двумя игроками лежат две кучки камней, в первой из которых 3, а во второй – 2 камня

description:
92

Дерево игры

Задача. Перед двумя игроками лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней.
       Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу.
       Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16.
       Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок?

description:
93

Дерево игры

3, 2

игрок 1

3, 6

27, 2

3, 18

3, 3

4, 2

12, 2

4, 6

5, 2

4, 3

9, 3

4, 3

36, 2

4, 18

15, 2

27, 3

игрок 1

игрок 2

игрок 2

9, 2

4, 3

4, 3

ключевой ход

выиграл игрок 1

alt: Задания «4»: «Собрать» программу для вычисления правильного арифметического выражения, включающего только однозначные числа и знаки операций +, -, * , /

description:
94

Задания

«4»: «Собрать» программу для вычисления правильного арифметического выражения, включающего только однозначные числа и знаки операций +, -, * , /.
«5»: То же самое, но допускаются также многозначные числа и скобки.
«6»: То же самое, что и на «5», но с обработкой ошибок (должно выводиться сообщение).

alt: Тема 7. Графы Динамические структуры данных (язык

description:
Тема 7. Графы

Динамические структуры данных(язык Си)

alt: Определения Граф – это набор вершин (узлов) и соединяющих их ребер (дуг)

description:
96

Определения

Граф – это набор вершин (узлов) и соединяющих их ребер (дуг).

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

Да, без циклов!

alt: Определения Связный граф – это граф, в котором существует цепь между каждой парой вершин

description:
97

Определения

Связный граф – это граф, в котором существует цепь между каждой парой вершин.
k-cвязный граф – это граф, который можно разбить на k связных частей.

Полный граф – это граф, в котором проведены все возможные ребра (n вершин → n(n-1)/2 ребер).

alt: Описание графа Матрица смежности – это матрица, элемент

description:
98

Описание графа

Матрица смежности – это матрица, элемент M[i][j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет.

0

1

0

1

0

1

0

1

0

1

1

0

0

1

2

3

4

0

1

2

3

4

0

1

0

1

1

0

1

2

3

4

0

1

2

3

4

Список смежности

1

2

3

0

3

4

1

4

1

3

0

1

2

3

4

1

2

3

3

4

4

0

1

2

3

4

alt: Матрица и список смежности 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0…

description:
99

Матрица и список смежности

0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

alt: Построения графа по матрице смежности 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 2 3…

description:
100

Построения графа по матрице смежности

0

1

0

1

1

0

1

0

0

1

0

1

1

0

1

0

0

1

2

3

4

0

1

2

3

4

0

1

1

0

1

0

1

0

1

0

0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

alt: Как обнаружить цепи и циклы? Задача: определить, существует ли цепь длины k из вершины i в вершину j (или цикл длиной k из вершины i…

description:
101

Как обнаружить цепи и циклы?

Задача: определить, существует ли цепь длины k из вершины i в вершину j (или цикл длиной k из вершины i в нее саму).

M2[i][j]=1, если  M[i][0]=1 и  M[0][j]=1

или

M[i][1]=1 и  M[1][j]=1

или

M[i][2]=1 и  M[2][j]=1

строка i

логическое умножение

столбец j

логическое сложение

0

1

0

1

0

0

1

0

1

1

0

0

1

2

3

0

1

2

3

M =

или

M[i][3]=1 и  M[3][j]=1

alt: Как обнаружить цепи и циклы? M2 =

description:
102

Как обнаружить цепи и циклы?

M2 = M  M

Логическое умножение матрицы на себя:

матрица путей длины 2

0

1

0

1

0

0

1

0

1

1

0

M2 =



0

1

0

1

0

0

1

0

1

1

0

=

0

1

0

1

1

0

1

0

0

1

0

0

1

2

3

0

1

2

3

M2[2][0] = 0·0 + 1·1 + 0·0 + 1·1 = 1

маршрут 2-1-0

маршрут 2-3-0

alt: Как обнаружить цепи и циклы? M3 =

description:
103

Как обнаружить цепи и циклы?

M3 = M2  M

Матрица путей длины 3:

0

1

0

1

0

0

1

0

1

1

0

M3 =



=

1

0

0

1

0

1

1

0

1

0

1

0

1

2

3

0

1

2

3

0

1

0

1

1

0

1

0

0

1

0

на главной диагонали – циклы!

0

1

0

1

0

0

1

0

1

1

0

M4 =



=

0

1

0

1

0

0

1

0

1

1

0

0

1

2

3

0

1

2

3

1

0

0

1

0

1

1

0

1

0

1

alt: Весовая матрица Весовая матрица – это матрица, элемент

description:
104

Весовая матрица

Весовая матрица – это матрица, элемент W[i][j] которой равен весу ребра из вершины i в вершину j (если оно есть), или равен ∞, если такого ребра нет.

0

7

3

5

∞

7

0

∞

4

8

3

∞

0

∞

5

4

∞

0

6

∞

8

6

0

0

1

2

3

4

0

1

2

3

4

0

7

3

5

∞

∞

0

∞

4

8

3

∞

0

∞

5

0

6

∞

8

∞

0

0

1

2

3

4

0

1

2

3

4

alt: Задача Прима-Краскала Задача: соединить

description:
105

Задача Прима-Краскала

Задача: соединить N городов телефонной сетью так, чтобы длина телефонных линий была минимальная.

Та же задача: дан связный граф с N вершинами, веса ребер заданы весовой матрицей W. Нужно найти набор ребер, соединяющий все вершины графа (остовное дерево) и имеющий наименьший вес.

0

7

3

5

∞

7

0

∞

4

8

3

∞

0

∞

5

4

∞

0

6

∞

8

6

0

0

1

2

3

4

0

1

2

3

4

alt: Жадный алгоритм Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее в данный момент

description:
106

Жадный алгоритм

Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее в данный момент.

Шаг в задаче Прима-Краскала – это выбор еще невыбранного ребра и добавление его к решению.

alt: Реализация алгоритма Прима-Краскала

description:
107

Реализация алгоритма Прима-Краскала

Проблема: как проверить, что 1) ребро не выбрано, и 2) ребро не образует цикла с выбранными ребрами.
Решение: присвоить каждой вершине свой цвет и перекрашивать вершины при добавлении ребра.

2

1

3

4

Алгоритм:
покрасить все вершины в разные цвета;
сделать N-1 раз в цикле:
выбрать ребро (i,j) минимальной длины из всех ребер, соединяющих вершины разного цвета;
перекрасить все вершины, имеющие цвет j, в цвет i.
вывести найденные ребра.

3

alt: Реализация алгоритма Прима-Краскала

description:
108

Реализация алгоритма Прима-Краскала

Структура «ребро»:

struct rebro {
  int i, j;    // номера вершин
  };

const	N = 5;
void main()
{
int W[N][N], Color[N], i, j,
    k, min, col_i, col_j;
rebro Reb[N-1];
...	// здесь надо ввести матрицу W
for ( i = 0; i < N; i ++ ) // раскрасить вершины
   Color[i] = i;
...	// основной алгоритм – заполнение массива Reb
...	// вывести найденные ребра (массив Reb)
}

Основная программа:

весовая матрица

цвета вершин

alt: Реализация алгоритма Прима-Краскала for ( k = 0; k <

description:
109

Реализация алгоритма Прима-Краскала

for ( k = 0; k < N-1; k ++ ) {
  min = 30000; // большое число
  for ( i = 0; i < N-1; i ++ )
    for ( j = i+1; j < N; j ++ )
	if ( Color[i] != Color[j] &&            W[i][j] < min ) {
  	  min = W[i][j];
	  Reb[k].i = i;
        Reb[k].j = j;
        col_i = Color[i];
        col_j = Color[j];
        }
  for ( i = 0; i < N; i ++ )
    if ( Color[i] == col_j ) Color[i] = col_i;
  }

Основной алгоритм:

нужно выбрать N-1 ребро

цикл по всем парам вершин

учитываем только пары с разным цветом вершин

запоминаем ребро и цвета вершин

перекрашиваем  вершины цвета col_j

alt: Сложность алгоритма Основной цикл:

description:
110

Сложность алгоритма

Основной цикл:

O(N3)

for ( k = 0; k < N-1; k ++ ) {
  ...
  for ( i = 0; i < N-1; i ++ )
    for ( j = i+1; j < N; j ++ )
	...
  }

три вложенных цикла, в каждом число шагов <=N

растет не быстрее, чем N3

Требуемая память:

int W[N][N], Color[N];
rebro Reb[N-1];

O(N2)

Количество операций:

alt: Кратчайшие пути (алгоритм Дейкстры)

description:
111

Кратчайшие пути (алгоритм Дейкстры)

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

Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных.

присвоить всем вершинам метку ∞;
среди нерассмотренных вершин найти вершину j с наименьшей меткой;
для каждой необработанной вершины i: если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние;
если остались необработанны вершины, перейти к шагу 2;
метка = минимальное расстояние.

Алгоритм Дейкстры (E.W. Dijkstra, 1959)

alt: 112 Алгоритм Дейкстры

description:
112

Алгоритм Дейкстры

alt: Реализация алгоритма Дейкстры Массивы: массив a , такой что a[i]=1 , если вершина уже рассмотрена, и a[i]=0 , если нет

description:
113

Реализация алгоритма Дейкстры

Массивы:
массив a, такой что a[i]=1, если вершина уже рассмотрена, и a[i]=0, если нет.
массив b, такой что b[i] – длина текущего кратчайшего пути из заданной вершины x в вершину i;
массив c, такой что c[i] – номер вершины, из которой нужно идти в вершину i в текущем кратчайшем пути.
Инициализация:
заполнить массив a нулями (вершины не обработаны);
записать в b[i] значение W[x][i];
заполнить массив c значением x;
записать a[x]=1.

1

0

0

7

9

∞

14

a

b

c

0

1

2

3

4

5

alt: Реализация алгоритма Дейкстры Основной цикл : если все вершины рассмотрены, то стоп

description:
114

Реализация алгоритма Дейкстры

Основной цикл:
если все вершины рассмотрены, то стоп.
среди всех нерассмотренных вершин (a[i]=0) найти вершину j, для которой b[i] – минимальное;
записать a[j]=1;
для всех вершин k: если путь в вершину k через вершину j короче, чем найденный ранее кратчайший путь, запомнить его: записать b[k]=b[j]+W[j][k] и c[k]=j.

1

0

0

7

9

22

∞

14

1

0

a

b

c

0

1

2

3

4

5

Шаг 1:

alt: Реализация алгоритма Дейкстры 1 0 0 7 9 20 ∞ 11 2 0 2 a b c 0 1 2 3 4 5

description:
115

Реализация алгоритма Дейкстры

1

0

0

7

9

20

∞

11

2

0

2

a

b

c

0

1

2

3

4

5

Шаг 2:

1

0

1

0

7

9

20

11

2

5

2

a

b

c

0

1

2

3

4

5

Шаг 3:

alt: Как вывести маршрут? 1 0 7 9 20 11 2 5 2 a b c 0 1 2 3 4 5

description:
116

Как вывести маршрут?

1

0

7

9

20

11

2

5

2

a

b

c

0

1

2

3

4

5

Результат работа алгоритма Дейкстры:

длины путей

Маршрут из вершины 0 в вершину 4:

4

0

5

2

5

2

0

Сложность алгоритма Дейкстры:

O(N2)

два вложенных цикла по N шагов

Вывод маршрута в вершину i (использование массива c):
установить z=i;
пока c[i]!=x присвоить z=c[z] и вывести z.

alt: Алгоритм Флойда-Уоршелла Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение

description:
117

Алгоритм Флойда-Уоршелла

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

for ( k = 0; k < N; k ++ )
  for ( i = 0; i < N; i ++ )
    for ( j = 0; j < N; j ++ )
      if ( W[i][j]  >  W[i][k] + W[k][j] )
           W[i][j] = W[i][k] + W[k][j];

Если из вершины i в вершину j короче ехать через вершину k, мы едем через вершину k!

alt: Алгоритм Флойда-Уоршелла Версия с запоминанием маршрута: for ( i = 0; i <

description:
118

Алгоритм Флойда-Уоршелла

Версия с запоминанием маршрута:

for ( i = 0; i < N; i ++ )
  for ( j = 0; j < N; j ++ )
    c[i][j] = i;
...
for ( k = 0; k < N; k ++ )
  for ( i = 0; i < N; i ++ )
    for ( j = 0; j < N; j ++ )
      if ( W[i][j]  >  W[i][k] + W[k][j] )
        {
        W[i][j] = W[i][k] + W[k][j];
        c[i][j] = c[k][j];
        }

i–ая строка строится так же, как массив c в алгоритме Дейкстры

в конце цикла c[i][j] – предпоследняя вершина в кратчайшем маршруте из вершины i в вершину j

c[i][j] = c[k][j];

O(N3)

alt: Задача коммивояжера Задача коммивояжера

description:
119

Задача коммивояжера

Задача коммивояжера. Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по разу в неизвестном порядке города 2,3,...N, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Точные методы:
простой перебор;
метод ветвей и границ;
метод Литтла;
…
Приближенные методы:
метод случайных перестановок (Matlab);
генетические алгоритмы;
метод муравьиных колоний;
…

большое время счета для больших N

O(N!)

не гарантируется оптимальное решение

alt: Другие классические задачи Задача на минимум суммы

description:
120

Другие классические задачи

Задача на минимум суммы. Имеется N населенных пунктов, в каждом из которых живет pi школьников (i=1,...,N). Надо разместить школу в одном из них так, чтобы общее расстояние, проходимое всеми учениками по дороге в школу, было минимальным.
Задача о наибольшем потоке. Есть система труб, которые имеют соединения в N узлах. Один узел S является источником, еще один – стоком T. Известны пропускные способности каждой трубы. Надо найти наибольший поток от источника к стоку.
Задача о наибольшем паросочетании. Есть M мужчин и N женщин. Каждый мужчина указывает несколько (от 0 до N) женщин, на которых он согласен жениться. Каждая женщина указывает несколько мужчин (от 0 до M), за которых она согласна выйти замуж. Требуется заключить наибольшее количество моногамных браков.

title: Си_ДинСтруктурыДанных.ppt


file_name: 3кл step 4.pptx

alt: Continents (континенты) Учитель английского языка:

description:
Continents (континенты)Учитель английского языка: Прус Анна Дмитриевна. МБОУ СОШ №4 г. Ханты-Мансийск.

Методическое пособие к учебнику «Rainbow English» 3 класс
Unit 7 Animals Step 4

alt: Hello, children! Здравствуйте, дети!

description:
 Hello, children!Здравствуйте, дети! How are you?Как у вас дела?
Let’s start!
 Начинаем наш урок.
Classwork

description:
The 17th of April

Откройте учебник английского языка на стр. 42 упр. 3-Прочитайте предложения и выберете только те, которые звучат правдоподобно.(Устно)

alt: стр. 43 упр. 4- (Письменно)

description: стр. 43 упр. 4- (Письменно)

description:
 стр. 43 упр.5-Послушай, как диктор произносит названия континентов и словосочетания с ними. Постарайтесь выучить новые слова и запишите их в словарик. (Аудио 139 к заданию 5).(Устно)

*(Чтобы прослушать аудио, нужно зайти в интернет, в поиске набрать  Rainbow English 3 класс 2 часть слушать аудио онлайн. Появится самый первый сайт rosuchebnik.ru, заходите на этот сайт выбираете стр. 43 аудиозапись № 139 к заданию 5).

alt: Прочитайте внимательно правило

description: стр. 44 Прочитайте внимательно правило.

alt: стр. 44-45 упр.7 (устно)

description: стр. 44-45 упр.7 (устно)

alt: Hometask (Домашнее задание): Стр

description:
Hometask (Домашнее задание):

Стр. 46 упр. 2 (письменно)

alt: Goodbye! До свидания! GOOD LUCK!

description:
Goodbye!
До свидания!

GOOD  LUCK!
Желаю удачи!

intro: Continents (континенты)


file_name: История возникновения календарей.pptx

alt: Выполнили: ученицы 6 «Б» класса

description:
Выполнили:
ученицы 6 «Б» класса
Полетаева Екатерина и
Коршунова Ульяна

История возникновения календарей

description:
Гипотеза:
Календарь прошлого отличается от современного календаря.
Цель:
Доказать, что календарь прошлого отличается от современного.
Задача:
Рассказать историю возникновения календаря. Провести опрос. Сравнить календарь прошлого и современный календарь и календари разных стран. Сделать вывод.

description:
Что такое календарь?

Календарь — это система счисления больших промежутков времени, основанная на периодичности движения небесных тел: Солнца — в солнечных календарях, Луны — в лунных календарях и одновременно Солнца и Луны в лунно-солнечных календарях.
Также календарём называется список дней года с разделением на недели и месяцы и обозначением праздников и периодическое справочное издание с последовательным перечнем дней, недель, месяцев данного года, а также другими сведениями различного характера.

alt: Опрос на тему: «Что такое календарь?»

description: Опрос на тему: «Что такое календарь?»

description:
Как возник календарь

При измерении промежутков времени прибегли к периодическим изменениям, происходящим в окружающей среде. То есть смена времени суток и смена времени года. Смена дня и ночи, помогла людям создать единицу времени – сутки. Благодаря смене сезонов появилась единица счета – тропический год, то есть период времени, когда солнцестояние достигает наибольшей величины, а затем идет на уменьшение. Кроме того обратили внимание на то, что происходит смена фаз Луны, происходящая в течение синодического месяца.  То есть имелось в виду, что каждый месяц происходит сближение Луны и Солнца, а иногда Луна закрывает Солнце и происходит его  временное затмение.
  Естественно при создании календаря не обошлось без проблем, это было вызвано с тем, что протяженность суток, тропический год и синодический месяц  несопоставимы друг с другом.

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

солнечный календарь,
лунный,
лунно-солнечный.

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

alt: Трудность составления точного календаря

description:
Трудность составления точного календаря

Астрономический, или солнечный, год продолжается 365 суток 5 часов 48 минут 46 секунд. Поэтому и нет целого числа суток, вот откуда возникает сложность в составлении календаря, который должен вести правильный отсчет времени.

description:
Разновидности календарей

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

description: Древнеримский календарь начинался с 1 марта и содержал 304 дня, которые делились на 10 равных частей. Он постоянно реформировался, и в итоге начальной точкой стало 1 января. Также были добавлены еще два месяца.

description: Юлий Цезарь, наблюдая за природными явлениями, выявил в них определенную периодичность. Так появился юлианский календарь, который был рассчитан с математической точностью. Он состоял из 365, 25 суток. Именно Цезарь ввел понятие «високосный год». Его протяженность увеличивалась ровно на одни сутки. Наблюдение за движением Солнца позволило избежать неточностей и появления лишних дней в году.

alt: Григорианский календарь во времена папы

description: Григорианский календарь во времена папы Римского Григория XIII был введен новый стиль летоисчисления. Основной его целью было закрепление даты весеннего равноденствия, которая постоянно смещалась. Именно 21 марта день равнялся ночи, и это максимально приближено к тропическому году, где разница составляет лишь 26 секунд. Чтобы этот промежуток равнялся суткам, потребовалось бы около 3300 лет. Такой невероятной точностью обладает григорианский календарь. Начиная с 1918 года в России был утвержден новый стиль и введен григорианский календарь, опережающий старый на 13 дней. Именно поэтому многие люди празднуют Старый Новый год, который как раз приходился бы на 13 января.

alt: Календарь на Руси На Руси, начиная с

description:
Календарь на Руси

На Руси, начиная с X века, Новый год отмечали 1 марта, когда по библейскому преданию Бог сотворил мир.
 В 1492 году, в соответствии с церковной традицией, начало года в России перенесли на 1 сентября, и отмечали так более 200 лет. Месяцы имели чисто славянские названия, происхождение которых было связано с явлениями природы. Годы считали от сотворения мира.

description: 19 декабря 7208 года Петр I подписал указ о реформе календаря. Календарь оставался юлианским, как и до реформы, принятым Русью из Византии вместе с крещением. Вводилось новое начало года — 1 января и христианское летоисчисление «от Рождества Христова». В указе царя предписывалось: «День после 31 декабря 7208 года от сотворения мира (православная церковь считает датой сотворения мира — 1 сентября 5508 лет до Р. X.) считать 1 января 1700 года от Рождества Христова. Указ также предписывал отмечать это событие особенно торжественно. Счет лет от Рождества Христова принят большинством государств мира.

description:
Современный календарь

После октябрьского переворота и в нашей стране 14 февраля 1918 года был введен так называемый новый стиль (григорианский).
Не забыт и Юлианский календарь, так называемый «старый стиль». Ежегодно в январе мы вспоминаем о нём, когда отмечаем «старый» Новый год.

description:
Календари разных стран мира

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

Какой год
в разных календарях мира наступил
в 2018 году?

alt: Согласно буддийскому календарю , который начинает свой отсчет от 543 года до н

description:
Согласно буддийскому календарю, который начинает свой отсчет от 543 года до н. э., в 2018 на дворе стоит 2561 год. Этот календарь берет свое начало с года смерти основателя и главного философа буддизма Сиддхартхи Гаутамы. Такое летоисчисление используют в Таиланде, Лаосе, Камбодже и Мьянме.
Согласно еврейскому календарю, в 2018 наступил 5778 год. Календарь берет начало с даты первого новолуния, которое произошло за год до сотворения мира — 3761 год до н. э. В Израиле григорианский календарь используется наряду с еврейским.

alt: Согласно солнечному зороастрийскому календарю , в 2018 на дворе стоит 1387 год

description: Согласно солнечному зороастрийскому календарю, в 2018 на дворе стоит 1387 год. В этом календаре существует 12 месяцев по 30 дней и не существует недель. Зороастризм считается одной из древнейших религий, которая была распространена на территории Средней и Малой Азии. Зороастрийский календарь ведет отчет от 632 года н. э., когда на трон государства Сасанидов взошел шах Йездигерда III. Этим календарем пользуются в оставшихся общинах последователей зороастризма в Индии, Иране и Азербайджане.

description:
Наряду с григорианским в Индии действует единый национальный календарь Индии. Его приняли в 1957 году, а летоисчисление он ведет от 78 года н. э., когда правитель династии Сатавахана, Гаутамипутра Сатакарни, остановил нашествие иранских племен на юг Индии. В этом календаре продолжительность года равняется длине тропического года, то есть 365 дней 5 часов 48 минут 46 секунд. Согласно этому календарю, в 2018 идет 1939 год.
По исламскому календарю в 2018 наступил 1439 год. Этот календарь ведет летоисчисление от 16 июля 622 года н. э., когда пророк Мухаммед и первые мусульмане переселились из Мекки в Медину. Это лунный календарь, в нем 12 лунных месяцев содержат приблизительно 354 дня. По исламскому календарю некоторые мусульманские
     страны определяют даты
     религиозных праздников.

alt: В Корейской Народно-Демократической

description:
В Корейской Народно-Демократической Республике по календарю чучхе в 2018 наступил 107 год. Летоисчисление ведется от 1912 года, когда на свет появился будущий основатель государства и первый правитель Ким Ир Сен.
На эфиопском календаре в 2018 начался 2010 год. Летоисчисление ведется от 29 августа 8 года н. э. по юлианскому календарю, когда, согласно утверждениям александрийского монаха Аниана, архангел Гавриил принес Деве Марии благую весть о скором рождении Спасителя. Эфиопским календарем используются Эритрейская православная, католическая и Евангелистская церкви страны.

description:
По китайскому календарю в 2018 на дворе стоит 35-й год 34-го цикла. Этот 60-летний календарь был введен императором Хуан-ди в 2637 году до н. э. Его используют в Китае для вычисления дат традиционных праздников.
Согласно японскому календарю, в 2018 наступил 29-й год эры Хэйсэй. В обиход его ввели в 1989 году, когда на трон взошел и ныне здравствующий император Акихито.

description:
Вывод

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

title: Исследовательская работа " История возникновения календарей"