Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Другие методич. материалы / Учебно-исследовательская работа по информатике и математике на тему Круги Эйлера и теория графов в решении задач по математике и информатике"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Информатика

Учебно-исследовательская работа по информатике и математике на тему Круги Эйлера и теория графов в решении задач по математике и информатике"

Выбранный для просмотра документ Приложение 1.docx

библиотека
материалов

Приложение 1

Решение задач, применяя круги Эйлера


Рассмотрим несколько задач, которые могут быть решены с применением кругов Эйлера на уроках математики или информатики.

Задачи


1. В классе 25 учащихся. Из них 5 человек не умеют играть ни в шашки, ни в шахматы. 18 учащихся умеют играть в шашки, 20 — в шахматы. Сколько учащихся класса играют и в шашки, и в шахматы?


2. Каждый из 35 пятиклассников является читателем, по крайней мере, одной из двух библиотек: школьной и районной. Из них 25 учащихся берут книги в школьной библиотеке, 20 — в районной. Сколько из пятиклассников:

а) не являются читателями школьной библиотеки;

б) не являются читателями районной библиотеки;

в) являются читателями только школьной библиотеки;

г) являются читателями только районной библиотеки;

д) являются читателями обеих библиотек?


3. Каждый ученик в классе изучает либо английский, либо французский язык, либо оба этих языка. Английский язык изучают 25 человек, французский — 27 человек, а тот и другой —18 человек. Сколько всего учеников в классе?


4. На листе бумаги начертили круг площадью 78 см2 и квадрат площадью 55 см2. Площадь пересечения круга и квадрата равна 30 см2. Не занятая кругом и квадратом часть листа имеет площадь 150 см2. Найдите площадь листа.

5. В детском саду 52 ребенка. Каждый из них любит либо пирожное, либо мороженое, либо и то, и другое. Половина детей любит пирожное, а 20 человек — пирожное и мороженое. Сколько детей любит мороженое?


6. В ученической производственной бригаде 86 старшеклассников. 8 из них не умеют работать ни на тракторе, ни на комбайне. 54 ученика хорошо овладели трактором, 62 — комбайном. Сколько человек из этой бригады могут работать и на тракторе, и на комбайне?


7. В классе 36 учеников. Многие из них посещают кружки: физический (14 человек), математический (18 человек), химический (10 человек). Кроме того, известно, что 2 человека посещают все три кружка; из тех, кто посещает два кружка, 8 человек занимаются в математическом и физическом кружках, 5 — в математическом и химическом, 3 — в физическом и химическом. Сколько человек не посещают никаких кружков?


8. 100 шестиклассников нашей школы участвовали в опросе, в ходе которого выяснялось, какие компьютерные игры им нравятся больше: симуляторы, квесты или стратегии. В результате 20 опрошенных назвали симуляторы, 28 — квесты, 12 — стратегии. Выяснилось, что 13 школьников отдают одинаковое предпочтение симуляторам и квестам, 6 учеников — симуляторам и стратегиям, 4 ученика — квестам и стратегиям, а 9 ребят совершенно равнодушны к названным компьютерным играм. Некоторые из школьников ответили, что одинаково увлекаются и симуляторами, и квестами, и стратегиями. Сколько таких ребят?


9. В классе 25 учащихся. Из них 5 человек не умеют играть ни в шашки, ни в шахматы. 18 учащихся умеют играть в шашки, 20 – в шахматы. Сколько учащихся класса играют и в шашки, и в шахматы?

10. Каждый из 35 пятиклассников является читателем по крайней мере одной из двух библиотек: школьной и районной. Из них 25 учащихся берут книги в школьной библиотеке, 20 - в районной. Сколько из пятиклассников: а) не являются читателями школьной библиотеки;

б) не являются читателями районной библиотеки;

в) являются читателями только школьной библиотеки;

г) являются читателями только районной библиотеки;

д) являются читателями обеих библиотек?


11. В одном множестве 40 элементов, а в другом 30. Сколько элементов может быть в их:

а) пересечении;

б) объединении?


12. Каждый ученик в классе изучает либо английский, либо французский язык, либо оба этих языка. Английский язык изучают 25 человек, французский – 27 человек, а тот и другой – 18 человек. Сколько всего учеников в классе?


13. Некоторые ребята из нашего класса любят ходить в кино. Известно, что 15 ребят смотрели фильм «Обитаемый остров», 11 человек – фильм «Стиляги», из них 6 смотрели и «Обитаемый остров», и «Стиляги». Сколько человек смотрели только фильм «Стиляги»?


14. Из 90 туристов, отправляющихся в путешествие, немецким языком владеют 30 человек, английским – 28, французским – 42. Английским и немецким одновременно владеют 8 человек, английским и французским -10 , немецким и французским – 5, всеми тремя языками – 3. Сколько туристов не влвдеют ни одним языком?


15. В ясельной группе 11 деток любят манную кашу, 13 – гречневую и

7 малышей – перловую. Четверо любят и манную, и гречневую 3 – манную и перловую, 6- гречневую и перловую, а двое любят все три вида каши.

Сколько детей в этой группе, если в ней нет ни одного ребёнка, вовсе не любящего кашу?


16. В городе живёт многодетная семья. 7 детей любят капусту, 6 – морковь, 5 – горох, 4 – капусту и морковь, 3 – капусту и горох, 2 – морковь и горох, 1 – и капусту, и морковь, и горох. Сколько детей было в семье?


17. В детском лагере отдыхало 70 ребят. Из них 20 занимаются в драмкружке, 32 поют в хоре, 22 увлекаются спортом. В драмкружке 10 ребят из хора, в хоре 6 спортсменов, в драмкружке 8 спортсменов, а 3 спортсмена посещают и драмкружок, и хор. Сколько ребят не поют в хоре, не увлекаются спортом и не занимаются в драмкружке? Сколько ребят заняты спортом?


18. Из сотрудников фирмы 16 побывали во Франции, 10 – в Италии, 6 – в Англии. В Англии и Италии – пятеро, в Англии и Франции – 6, во всех трёх странах – 5 сотрудников. Сколько человек посетили и Италию, и Францию, если всего в фирме работает 19 человек, и каждый их них побывал хотя бы в одной из названных стран?


19. Домашние любимцы. У всех моих подруг есть домашние питомцы. Шестеро из них любят и держат кошек, а пятеро - собак. И только у двоих есть и те и другте. Угадайте, сколько у меня подруг?


20. Библиотеки. В классе 30 учеников. Все они являются читателями школьной и районной библиотек. Из них 20 ребят берут книги в школьной библиотеке, 15 - в районной. Сколько учеников не являются читателями школьной библиотеки?

21. Любимые мультфильмы. Среди школьников пятого класса проводилось анкетирование по любимым мультфильмам. Самыми популярными оказались три мультфильма: "Белоснежка и семь гномов", "Винни Пух", "Микки Маус". Всего в классе 28 человек. "Белоснежку и семь гномов" выбрали 16 учеников, среди которых трое назвали еще "Микки Маус", шестеро - "Винни Пух", а один написал все три мультфильма. Мультфильм "Микки Маус" назвали 9 ребят, среди которых пятеро выбрали по два мультфильма. Сколько человек выбрали мультфильм "Винни Пух"?


22. Хобби. Из 24 учеников 5 класса музыкальную школу посещают 10 человек, художественную школу - 8 человек, спортивную школу - 12 человек, музыкальную и художественную школу- 3, художественную и спортивную школу - 2, музыкальную и спортивную школу - 2, все три школы посещает 1 человек. Сколько учеников посещают только одну школу? Сколько учащихся ни в чем себя не развивают?


23. О головоломках. На полке стояло 26 различных математических игр - головоломок. В 4 из них поиграл и Гриша, и Саша. Игорь попробовал проиграть 7 игр, которых не касались ни Гриша, ни Саша, и две головоломки, в которые играл Гриша. Всего Гриша играл в 11 математических игр - головоломок. Во сколько головоломок сыграл Саша?


24. Спорт для всех. В классе 38 человек. Из них 16 играют в баскетбол, 17 - в хоккей, 18 - в футбол. Увлекаются двумя видами спорта - баскетболом и хоккеем - четверо, баскетболом и футболом - трое, футболом и хоккеем - пятеро. Трое не увлекаются ни баскетболом, ни хоккеем, ни футболом. Сколько ребят увлекаются одновременно тремя видами спорта? Сколько ребят увлекается лишь одним из этих видов спорта?


25. Спортивный класс. В классе 35 учеников. 24 из них играют в футбол, 18 - в волейбол, 12 - в баскетбол. 10 учеников одновременно играют в футбол и волейбол, 8 - в футбол и баскетбол, а 5 - в волейбол и баскетбол. Сколько учеников играют и в футбол, и в волейбол, и в баскетбол одновременно?


26. Часть жителей нашего города умеет говорить только по-русски, часть – только по-башкирски и часть умеет говорить на обоих языках. По-башкирски говорят 85%, по-русски 75%. Сколько процентов жителей говорят на обоих языках?


27. Все мои подруги выращивают в своих квартирах какие-нибудь растения. Шестеро из них разводят кактусы, а пятеро — фиалки. И только у двоих есть и кактусы и фиалки. Угадайте, сколько у меня подруг?


28. В футбольной команде «Спартак» 30 игроков, среди них 18 нападающих. 11 полузащитников, 17 защитников и вратари. Известно, что трое могут быть нападающими и защитниками, 10 защитниками и полузащитниками, 6 нападающими и защитниками, а 1 и нападающим, и защитником, и полузащитником. Вратари не заменимы. Сколько в команде «Спартак» вратарей?


29. В классе 30 человек. 20 из них каждый день пользуются метро, 15 — автобусом, 23 — троллейбусом, 10 — и метро, и троллейбусом, 12 — и метро, и автобусом, 9 — и троллейбусом, и автобусом. Сколько человек ежедневно пользуются всеми тремя видами транспорта?


30. В восьмом классе учится 40 человек. Каждый из них изучает не менее одного иностранного языка: английский, немецкий, французский. 34 человека изучают хотя бы один из двух языков: английский, немецкий. 25 человек — хотя бы один из языков: немецкий, французский. 6 человек только немецкий. Одновременно два языка — английский и немецкий — изучают на 3 человека больше, чем французский и немецкий языки. Сколько человек изучает каждый из языков и сколько изучает одновременно каждую пару языков?


31. В магазине побывало 65 человек. Известно, что они купили 35 холодильников, 36 микроволновок, 37 телевизоров. 20 из них купили и

холодильник и микроволновку, 19 - и микроволновку, и телевизор, 15-холодильник и телевизор, а все три покупки совершили три человека. Был ли среди них посетитель, не купивший ничего?


32. В футбольной команде «Спартак» 30 игроков: 18 нападающих, 11 полузащитников, 17 защитников. Вратари. 3 могут быть нападающими и защитниками, 10 защитниками и полузащитниками, 6 нападающими и защитниками 1 и нападающим, и защитником, и полузащитником.

Вратари не заменимы. Сколько в команде «Спартак» вратарей?


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

Сколько детей было в этой семье?


34. Среди школьников шестого класса проводилось анкетирование по любимым мультфильмам. Самыми популярными оказались три мультфильма: «Белоснежка и семь гномов», «Губка Боб Квадратные Штаны», «Волк и теленок». Всего в классе 38 человек. «Белоснежку и семь гномов» выбрали 21 ученик, среди которых трое назвали еще «Волк и теленок», шестеро – «Губка Боб Квадратные Штаны», а один написал все три мультфильма. Мультфильм «Волк и теленок» назвали 13 ребят, среди которых пятеро выбрали сразу два мультфильма. Сколько человек выбрали мультфильм «Губка Боб Квадратные Штаны»?


35. В магазин «Мир музыки» пришло 35 покупателей. Из них 20 человек купили новый диск певицы Максим, 11 – диск Земфиры, 10 человек не купили ни одного диска. Сколько человек купили диски и Максим, и Земфиры?


36. На полке стояло 26 волшебных книг по заклинаниям, все они были прочитаны. Из них 4 прочитал и Гарри Поттер, и Рон. Гермиона прочитала 7 книг, которых не читали ни Гарри Поттер, ни Рон, и две книги, которые читал Гарри Поттер. Всего Гарри Поттер прочитал 11 книг. Сколько книг прочитал только Рон?


37. В пионерском лагере 70 ребят. Из них 27 занимаются в драмкружке, 32 поют в хоре, 22 увлекаются спортом. В драмкружке 10 ребят из хора, в хоре 6 спортсменов, в драмкружке 8 спортсменов; 3 спортсмена посещают и драмкружок и хор. Сколько ребят не поют, не увлекаются спортом, не занимаются в драмкружке? Сколько ребят заняты только спортом?


38. Из 100 ребят, отправляющихся в детский оздоровительный лагерь, кататься на сноуборде умеют 30 ребят, на скейтборде – 28, на роликах – 42. На скейтборде и на сноуборде умеют кататься 8 ребят, на скейтборде и на роликах – 10, на сноуборде и на роликах – 5, а на всех трех – 3. Сколько ребят не умеют кататься ни на сноуборде, ни на скейтборде, ни на роликах?


39. Сколько учащихся в 10 А классе, если 8 из них посещают только факультатив по физике, 10- только по математике, 4 –оба
факультатива, и «бездельников» нет
.

40. Задача №18 из демо-версии ГИА 2013

В таблице приведены запросы к поисковому серверу. Для каждого запроса указан его код – соответствующая буква от А до Г. Расположите коды запросов слева направо в порядке убывания количества страниц, которые найдет поисковый сервер по каждому запросу.

Код

Запрос

А

(Муха & Денежка) | Самовар

Б

Муха & Денежка & Базар & Самовар

В

Муха | Денежка | Самовар

Г

Муха & Денежка & Самовар



41. Задача В12 из демо-версии ЕГЭ-2013.

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Запрос

Найдено страниц (в тысяч)

Фрегат | Эсминец

3400

Фрегат & Эсминец

900

Фрегат

2100

Какое количество страниц (в тысячах) будет найдено по запросуЭсминец?

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.


42. В классе 36 человек. Ученики этого класса посещают математический, физический и химический кружки, причем математический кружок посещают 18 человек, физический - 14 человек, химический - 10. Кроме того, известно, что 2 человека посещают все три кружка, 8 человек - и математический и физический, 5 и математический и химический, 3 - и физический и химический. Сколько учеников класса не посещают никаких кружков?


43. После зимних каникул классный руководитель спросил, кто из ребят ходил в театр, кино или цирк. Оказалось, что из 36 учеников класса двое не были ни в кино. ни в театре, ни в цирке. В кино побывало 25 человек, в театре - 11, в цирке 17 человек; и в кино, и в театре - 6; и в кино и в цирке - 10; и в театре и в цирке - 4. Сколько человек побывало и в кино, и в театре, и в цирке?


44. На листе бумаги начертили круг площадью 78 hello_html_m1cc31f1a.gif и квадрат площадью 55hello_html_m1cc31f1a.gif. Площадь пересечения круга и квадрата равна 30 hello_html_m1cc31f1a.gif. Не занятая кругом и квадратом часть листа имеет площадь 150 hello_html_m1cc31f1a.gif. Найдите площадь листа.


45. В бригаде полеводов 25 человек. Среди них 20 человек моложе 30 лет и 15 человек старше 20 лет. Может ли так быть?


46. Сколько в классе учащихся, если известно, что лыжным спортом увлекаются 28 человек, отличников в классе – 12, причем отличников-спортсменов, увлекающихся лыжами, - 10?

47. 37 школьников из ученической производственной бригады изъявили желание летом работать на уборке зерновых. Каждый из них имеет права для работы на тракторе или на комбайне, а некоторые могут работать и на тракторе, и на комбайне. Сколько школьников могут работать и на тракторе. И на комбайне, если известно. Что трактором овладели 23 человека, а комбайном – 31 человек?


48. В ученической производственной бригаде 86 старшеклассников, 8 из них не умеют работать ни на тракторе.ю ни на комбайне. 54 ученика хорошо овладели трактором. 62 – комбайном. Сколько человек из этой бригады могут работать и на тракторе. И на комбайне?


49. В классе 35 учеников. Каждый из которых любит футбол. волейбол или баскетбол. А некоторые – два или даже три из этих видов спорта. 24 ученика любят футбол, 18 – волейбол, 12 – баскетбол. При этом 10 учеников одновременно любят футбол и волейбол, 8 – футбол и баскетбол. А 5 – волейбол и баскетбол. Сколько учеников этого класса любят все три вида спорта?


50. В классе 36 учеников. из них посещают кружки: физический (14 человек), математический (18 человек), химический (10 человек). Кроме того, известно. Что 2 человека посещают все три кружка; из тех, кто посещает два кружка, 8 человек занимаются в математическом и физическом кружках, 5 – в математическом и химическом, 3 – в физическом и химическом. Сколько человек не посещают никаких кружков?


51. 100 шестиклассников нашей школы участвовали в опросе, в ходе которого выяснилось, какие компьютерные игры им нравятся больше: симуляторы, квесты или стратегии. В результате 20 опрошенных назвали симуляторы, 28 – квесты, 12 – стратегии. Выяснилось, что 13 школьников отдают одинаковое предпочтение симуляторам и квестам, 6 учеников – симуляторам и стратегиям. 4 ученика – квестам и стратегиям, а 9 ребят совершенно равнодушны к названным компьютерным играм. Некоторые из школьников ответили, что одинаково увлекаются и симуляторами, и квестами, и стратегиями. Сколько таких ребят?

52. Изобразить с помощью кругов Эйлера отношения между понятиями:

  • Четырехугольник

  • Трапеция

  • Параллелограмм



53. Изобразить с помощью кругов Эйлера отношения между понятиями:

  • Параллелограмм

  • Ромб

  • Прямоугольник

  • Квадрат


54. Изобразить с помощью кругов Эйлера отношения между понятиями:

  • Натуральные числа

  • Целые числа

  • Рациональные числа

  • Действительные числа


55. Тождественны ли следующие понятия? Изобразите их с помощью кругов Эйлера.

«Луна», «Спутник Земли».

56. Подберите понятия, отношения между которыми можно изобразить кругами Эйлера.

hello_html_2ef85282.png


57. Изобразите при помощи кругов Эйлера отношения между объемами понятий a и b, если: 1) а – «треугольник», b – «прямоугольный треугольник»; 2) а – «прямая», b – «отрезок»; 3) а – «равнобедренный треугольник», b – «тупоугольный треугольник».


58. А – множество натуральных чисел, меньших 20, а В, С и D – его подмножества, причем В состоит из чисел, кратных 3, С – из чисел, кратных 4, D – из четных чисел. Какие числа являются элементами множеств:

1) (А В) С; 2) А (В С ); 3) А (В С );

4) (А В) С; 5) А В С; 6) А (В С ).



59. Х – множество двузначных чисел, Y – множество четных чисел, Р – множество чисел, кратных 4. Каковы характеристические свойства элементов множеств А = Х Y Р и В = (Х Y) Р? Изобразите множества Х , Y, Р, А и В при помощи кругов Эйлера. Назовите три числа, принадлежащие множеству А, и три числа, принадлежащие множеству В.



60. Найдите пересечение множеств А и В, если:

A = {a, b, c, d, e, f}; B = {b, e, f, k, l};


61. В группе из 100 туристов 70 человек знают английский язык, 45 знают французский язык и 23 человека знают оба языка. Сколько туристов в группе не знают ни английского, ни французского языка?























Ответы

Овал: ВОвал: А1.

А – шахматы 25-5=20 – чел. умеют играть

В – шашки 20+18-20=18 – чел играют и в шашки, и в шахматы

2. Ш – множество посетителей школьной библиотеки

Р – множество посетителей районной библиотеки

25+20-35=10


http://pandia.ru/text/78/128/images/image013_34.gif

 

а) 10;

б) 15;

в) 15;

г)10;

Овал: А 7http://pandia.ru/text/78/128/images/image015_29.gifОвал: 18 Ф 9д) 10.

3. 34. А – английский, Ф – французский

25-18=7 – только английский

27-18=9 – только французский

7+18+9=34 – чел. в классе

4. 253. Sкр=78; Sкв=55; Sсумм=150; Sлиста=78+55-30+150=253

http://pandia.ru/text/78/128/images/image017_10.jpg


http://pandia.ru/text/78/128/images/image018_24.gif

 

5. 46. П – пирожное, М – мороженое

52-26-20=6 – детей любят пирожноеhttp://pandia.ru/text/78/128/images/image019_25.gif

 




6. 38. Т – трактор, К – комбайн

54+62-(86-8)=38 – умеют работать и на тракторе и на комбайне

http://pandia.ru/text/78/128/images/image020_18.gif7. Способ 1. Выясним, сколько ребят посещают только математический кружок: 18-8-5-2 = 3; только физический: 14-8-3-2 = 1; только химический: 10-5-3-2 = 0. Таким образом, три кружка посещают 2 ученика; два кружка — 16 учеников (8 + 3 + 5); один кружок — 4 ученика (3 + 1 + 0). Всего посещают кружки 2 + 16 + 4 = 22 ученика. Следовательно, кружки не посещают 36 - 22 = 14 ученика.

Способ 2. Представим множества учащихся, посещающих математический, физический и химический кружки, в виде кругов, вырезанных из плотной бумаги. Будем считать, что площадь каждого из этих кругов равна числу учащихся, посещающих соответствующий кружок. Наложим круги друг на друга так, чтобы было понятно, что есть учащиеся, посещающие один, два или три кружка. Вычислим площадь получившейся плоской фигуры: 14 + 18 + 10 - (8 + 5 + 3) - 2 - 2 = 22 — это и есть число учеников, посещающих кружки. Следовательно, кружки не посещают 36 - 22 = 14 учеников.

8. Пусть X — искомое число учеников, увлекающихся всеми видами компьютерных игр. Тогда: 20 + 28 + 12 + 13 + 6 + 4 + 9 + Х = 100, Х = 6.








Выбранный для просмотра документ Приложение 2.docx

библиотека
материалов

Приложение 2


1.  Задача о Кенигсбергских мостах. На рисунке представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена (показано, что решение не существует) Эйлером в 1736 году.

http://pandia.ru/text/78/128/images/image030_6.jpg


2.  Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году. (рис. 11).

http://pandia.ru/text/78/128/images/image031_8.gif


3 Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом. С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.http://pandia.ru/text/78/128/images/image033_9.gif






4. Задачи Дьюдени.

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

2. М-р Робинсон живет в Лос-Анджелесе.

3. Кондуктор живет в Омахе.

4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.

5. Пассажир – однофамилец кондуктора живет в Чикаго.

6. Кондуктор и один из пассажиров, известный специалист по математической физике, хотя в одну церковь.

7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.

Как фамилия машиниста?

Здесь 1-5 – номера ходов, в скобках – номера пунктов задачи, на основании которых сделаны ходы (выводы). Далее следует из п.7, что кочегар не Смит, следовательно, Смит-машинист.


5. Катя, Маша и Ира играют с мячом. Каждая из них должна по одному разу бросить мяч в сторону каждой подруги. Сколько раз каждая из девочек должна бросать мяч? Сколько всего раз будет подбрасываться мяч? Определите, сколько раз будет подбрасываться мяч, если в игре примут участие: четверо детей; пятеро детей.


6. Любители музыки

В клубе «Отдых» познакомились 3 любителя клубной музыки видов техно, хаус, рейв. Один говорит: «Вы какую музыку больше любите? Я техно люблю!». Другой ответил, что любит хаус, а третий сказал, что не любит ни техно, ни хаус, но зато обожает рейв. Интересно то, что все они были в банданах и рубашках черного, белого и желтого цветов, но цвет банданы и рубашки совпадал только у любителя техно. А у любителя хаус ни рубашка, ни бандана не были белыми. А любитель рейв был в желтой рубашке. Определите цвет рубашек и бандан каждого из любителей клубной музыки.
Решение Заметим, что по условию задачи цвет банданы и рубашки совпадал только у любителя техно. А так как у любителя хаус ни рубашка ни бандана не были белыми и любитель рейв был в желтой рубашке, то делаем вывод, что любитель техно может быть в рубашке и бандане только белого цвета.

  1. Футбол

Четыре футбольных команды: итальянская команда «Милан», испанская – «Реал», российская – «Зенит», английская – «Челси» встретились в групповом этапе лиги чемпионов по футболу. Их тренировали тренеры из этих же четырех стран: итальянец Антонио, испанец Родриго, русский Николай, англичанин Марк. Известно, что национальность у всех четырех тренеров не совпадала с национальностью команд. Требуется определить тренера каждой команды, если известно: а) Зенит не тренируется у Марка и Антонио, б) Милан обещал никогда не брать Марка главным тренером.


8. Три поросёнка

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

  1. Соревнование по фехтованию

Атос, Портос и Арамис в соревновании по фехтованию заняли три первых места. Какое место занял каждый из них, если Портос занял не второе и не третье место, а Арамис – не третье?

  1. "Виа Гра"

В группе «Виа Гра» поют три девушки: блондинка, рыжая и брюнетка. В клипе «Бриллианты» девушки одеты в белое, красное и черное платья. Интересно, - заметила брюнетка, - что цвета наших с вами волос не соответствуют нашим платьям. - А ведь верно, но мне подошло бы твое платье, - подтвердила девушка в белом платье. В какое платье была одета каждая из девушек?


  1. Катя, Маша и Ира играют с мячом. Каждая из них должна по одному разу бросить мяч в сторону каждой подруги. Сколько раз каждая из девочек должна бросать мяч? Сколько всего раз будет подбрасываться мяч? Определите. Сколько раз будет подбрасываться мяч, если в игре примут участие: четверо детей; пятеро детей.


  1. Даны три фасада и две крыши, имеющие одинаковую форму, но раскрашенную в различные цвета: фасады – в желтый, синий и красный цвета, а крыши – в синий и красные цвета. Какие домики можно построить? Сколько всего комбинаций?

  2. Даны три одинаковых по форме фасада домика: синий, желтый и красный – и три крыши: синяя. Желтая и красная. Какие домики можно построить? Сколько всего комбинаций?

  3. Рисунки на флажках могут иметь вид круга, квадрата. Треугольника или звезды, причем их можно раскрасить в зеленый или красный цвет. Сколько всего может быть разных флажков?

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

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


  1. Сколькими способами можно рассадить в ряд на стулья трех учеников? Выписать все возможные случаи.


  1. Сколькими способами могут четыре (пять) человек стать в ряд?


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


  1. Слог называется открытым, если он начинается с согласной буквы, а заканчивается гласной. Сколько открытых двухбуквенных слогов можно написать, используя буквы «а», «б», «в», «г», «е», «и», «о»? выпишите эти слоги.


  1. Из Акулово в Рыбницу ведут три дороги, а из Рыбницы в Китово – четыре дороги. Сколькими способами можно проехать из Акулово в Китово через Рыбницу?


  1. Сколько различных вариантов костюмов из блузки и юбки можно составить, если имеется 4 блузки и 4 юбки?


  1. Записать все возможные двузначные числа, используя цифры 7 и 4.

  2. Когда Петя идет в школу, он иногда встречает одного или нескольких своих приятелей: Васю, Леню, Толю. Перечислите все возможные случаи, которые при этом могут быть.


  1. Миша запланировал купить: карандаш, линейку, блокнот и тетрадь. Сегодня он купил только два разных предмета. Что мог купить Миша, если считать, что в магазине были все нужные ему учебные принадлежности?


  1. Сколько существует двузначных чисел, в записи которых отсутствует цифра 0?


  1. Четыре человека обменялись рукопожатиями. Сколько было всего рукопожатий?


  1. Записать все возможные трехзначные числа, которые можно составить из цифр 1 и 2.


  1. Записать все возможные двузначные числа, при записи которых используются цифры 2, 8 и 5.


  1. Записать все возможные четные трехзначные числа, которые можно составить из цифр 1 и 2.


  1. Сколько существует различных двухзначных чисел, все цифры которых нечетные?


  1. Сколько трехзначных чисел можно составить из цифр 1, 2, 4, 6, если никакую цифру не использовать более одного раза? Сколько среди этих чисел будет четных? Сколько нечетных?

  2. Какие трехзначные числа можно записать с помощью цифр 3, 7 и 1 при условии, что в записи числа не должно быть одинаковых цифр? Сколько таких чисел?


  1. В автомашине пять мест. Сколькими способами пять человек могут усесться в эту машину, если занять место водителя могут только двое из них?


  1. В классе 5 одноместных парт. Сколькими способами можно рассадить на них двух (трех) вновь прибывших школьников?


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


  1. Вспомните басню И. Крылова «Квартет»:

Проказница Мартышка,

Осел,

Козел

Да косолапый Мишка

Затеяли сыграть Квартет.

…………………..

Ударили в смычки. Дерут, а толку нет.

«Стой, братцы, стой! – кричит Мартышка. –

Погодите!

Как музыке идти? Ведь вы не так

сидите».

Сколькими различными способами могут попытаться сесть эти музыканты? Может ли это улучшить качество их игры?


  1. Мальчиков и девочек рассаживают в ряд на подряд расположенные места, причем мальчики садятся на нечетные места, а девочки на четные. Сколькими способами можно это сделать, если: а) на 6 мест рассаживают 3 мальчиков и 3 девочек; б) на 10 мест рассаживают 5 мальчиков и 5 девочек?


  1. Пусть номер автомобиля составляется из двух букв, за которыми следуют две цифры, например АВ-53. Сколько разных номеров можно составить, если использовать 5 букв и 6 цифр?



  1. Номер автомобиля состоит из трех букв и четырех цифр. Сколько существует различных автомобильных номеров (три буквы берутся из 29 букв русского алфавита)?



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



  1. Пусть вам нужно было сходить в библиотеку, сберегательный банк, на почту и отдать в ремонт ботинки. Для того чтобы выбрать кратчайший маршрут, необходимо рассмотреть все возможные варианты. Сколько существует вариантов пути. Если библиотека, сберегательная касса, почта и сапожная мастерская расположены далеко друг от друга?



  1. Имеется пять кубиков, которые отличаются друг от друга только цветом: 2 красных, 1 белый и 2 черных. Есть два ящика А и Б, причем в А помещается 2 кубика, а в Б – 3. Сколькими различными способами можно разместить эти кубики в ящиках А и Б?



  1. Игра. Сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причем за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку.



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

  1. иди сейчас по правой тропинке;

  2. на следующей развилке не выбирай правую тропинку;

  3. на третьей развилке не ходи по левой тропинке.

Пролетавший мимо голубь шепнул Ивану-царевичу, что только один совет ворона верный и что обязательно надо пройти по тропинкам разных направлений. Наш герой выполнил задание и попал в волшебный сад. Каким маршрутом он воспользовался?



  1. Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором – любая гласная, если первая буква гласная, и любая согласная. На третьем месте – одна из бусин C, D, E, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?


  1. Сколько существует трехзначных чисел, все цифры которых различны?








Выбранный для просмотра документ Круги Эйлера и теория графов в решении задач.docx

библиотека
материалов

hello_html_m4bf8e84b.gifhello_html_m565d3158.gifhello_html_m748dd20f.gifhello_html_20a2087d.gifhello_html_m55724b3b.gifhello_html_m68358c37.gifhello_html_m7bbb4246.gifhello_html_261d4994.gifhello_html_m5d55d885.gifhello_html_m2c6729a6.gifhello_html_m1615fea1.gifhello_html_5d2e5047.gifhello_html_702454f.gifМуниципальное общеобразовательное учреждение

средняя общеобразовательная школа № 29

Тракторозаводского района г. Волгограда


Городской конкурс

«Я и Земля»

имени В.И.Вернадского

секция «Информатика и

вычислительная техника,

информационные технологии»


Учебно-исследовательская работа


Круги Эйлера и теория графов в решении задач

школьной математики и информатики


Выполнили: ученицы 8 класса

Лихачева Анна

Зиярова Алина

Доан Тхи Тхань

Руководители:

учитель информатики

Скачкова Зинаида Ивановна







Волгоград, 2014

Содержание

Введение…………………………………………………………………………...3

Актуальность………..………………………………………..…………………...3

Задачи……………………………………………………….……………………..3

Цель исследования….…………………………………………………………….3

Методы исследования…………………………………………………………….3

Апробация работы………………………………………………………………...3

Гипотеза исследования……………………………………………………….......4

Предмет исследования………………...……………………………………….....4

Круги Эйлера

Исторические сведения……………………………………………………4

Теоретические основы кругов Эйлера………………………………….5

Задачи, при решении которых используются круги Эйлера……………9

Графы

Исторические сведения…………………………………………………..13

Теория графов……………………………………………………………13

Решение задач, используя графы………………………………………...20

Заключение………………………………………………………………….........24

Литература…………………………………………………….…………………25

Приложение 1

Приложение 2










Введение

«Всё наше достоинство заключено в мысли.

Не пространство, не время, которое мы не можем заполнить,

возвышает нас, а именно она, наша мысль.

Будем же учиться - хорошо мыслить».

Б. Паскаль

Основной задачей школы является не подача детям большого объёма знаний, а обучение учащихся самим добывать знания, умению перерабатывать эти знания и применять их в каждодневной жизни. Увлечение математикой и информатикой, часто начинается с размышления над какой-то задачей. Поставленные задачи может решить ученик, обладающий не только умением хорошо и много работать, но и ученик с развитым логическим мышлением. В связи с этим во многие школьные предметы вложены различного типа задачи, которые и развивают у детей логическое мышление. Решая эти задачи, мы применяем различные приёмы решения. Одни из приёмов решения – это использование кругов Эйлера и граф.

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

Действительно, такого практикума нет, а он необходим.

Цель исследования: изучение материала, применяемого на уроках математики и информатики, где используются круги Эйлера и теория графов, как один из приемов решения задач.

Задачи исследования:

1. Изучить теоретические основы понятий: «Круги Эйлера», «Графы».

2. Решение задач школьного курса вышеназванными методами.

3. Составить подборку материала для использования учениками и учителями на уроках математики и информатики кругов Эйлера и графов.

Гипотеза исследования: применение кругов Эйлера и графов повышают результативность и наглядность при решении задач?

Предмет исследования: понятия: «Круги Эйлера», «Графы», задачи школьного курса математики и информатики.


Круги Эйлера

Исторические сведения

Леонард Эйлер - один из величайших математиков. Родился он в Швейцарии, много лет жил и работал в Петербурге, поэтому его можно считать русским ученым. За свою жизнь он написал более 800 работ по математике, физике, оптике, баллистике, кораблестроению, теории музыки.hello_html_4e3502b7.png

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

Эйлер писал тогда, что «круги очень подходят для того, чтобы облегчить наши размышления».

При решении целого ряда задач Леонард Эйлер использовал идею изображения множеств с помощью кругов и они получили название «круги Эйлера».

Типы кругов Эйлера:

hello_html_30d5b3f.pnghello_html_3b06db67.png






hello_html_m78e429f3.pnghello_html_383ddc44.png





Теоретические основы о кругах Эйлера

Эйлеровы круги (круги Эйлера) — принятый в логике способ моделирования, наглядного изображения отношений между объемами понятий с помощью кругов, предложенный знаменитым математиком Л. Эйлером (1707–1783). Обозначение отношений между объемами понятий посредством кругов было применено еще представителем афинской неоплатоновской школы — Филопоном (VI в.), написавшим комментарии на «Первую Аналитику» Аристотеля. Условно принято, что круг наглядно изображает объем одного какого-нибудь понятия. Объем же понятия отображает совокупность предметов того или иного класса предметов. Поэтому каждый предмет класса предметов можно изобразить посредством точки, помещенной внутри круга, как это показано на рисунке.

Отношения между понятиями

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

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

Группа предметов, составляющая вид данного класса предметов, изображается в виде меньшего круга, нарисованного внутри большего круга, как это сделано на рисунке.



А

В

Рассмотрим два понятия – «квадрат» и «прямоугольник». Объем понятия «прямоугольник» больше объема понятия «квадрат», так как все квадраты – тоже прямоугольники. Отношения между понятиями удобно представлять кругами. Объем понятия А – «прямоугольник», а объем понятия В – «квадрат».



В



А



Когда же ни один предмет, отображенный в объеме понятия A, не может одновременно отображаться в объеме понятия B, то в таком случае отношение между объемами понятий изображается посредством двух кругов, нарисованных один вне другого. Ни одна точка, лежащая на поверхности одного круга, не может оказаться на поверхности другого круга.

Такое именно отношение существует, например, между понятиями «тупоугольный треугольник» и «остроугольный треугольник». В объеме понятия «тупоугольный треугольник» не отображается ни один остроугольный треугольник, а в объеме понятия «остроугольный треугольник» не отображается ни один тупоугольный треугольник.

Отношение «тождество»

А=В

Отношения между равнозначащими понятиями, объемы которых совпадают, отображаются наглядно посредством одного круга, на поверхности которого написаны две буквы, обозначающие два понятия, имеющие один и тот же объем.

Если объемы понятий совпадают (объем одного понятия равен объему другого), то отношение между этими понятиями называют тождеством.

Отношение «пересечение»

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

В

А

Пересечением называют отношение между понятиями, объемы которых совпадают частично, то есть содержат общие элементы. Пусть А – «электронное письмо», В – «письмо на русском языке». В пересечении двух кругов попадают все электронные письма на русском языке.

Отношение «подчинение»

А





В

Подчинением называют отношение между понятиями, когда объем одного из них полностью входит в объем другого понятия, но не исчерпывает его. Пусть понятие А – «клавиатура», понятие В – «устройство ввода», тогда клавиатура является устройством ввода.

Отношение «соподчинение»

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

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





F

D

B

E

C

А

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

Это применимо к понятиям: «дом», «сарай», «ангар», «театр», подчиненных понятию «постройка»; к понятиям: «муха», «комар», «бабочка», «жук», «пчела», подчиненных понятию «насекомое» и т. д.

Отношение «противоположность»

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

В

С

А

Слова, выражающие противоположные понятия, называются антонимами. Например, понятие А – «компьютер с маленькой памятью», понятие В – «компьютер с большой памятью». Объемы этих понятий разделены объемом некоторого третьего понятия, например, - «компьютер со средней памятью». hello_html_m7cf309ce.png



Отношение «противоречие»

Между противоположными понятиями возможно третье, среднее, так как они не исчерпывают полностью объема родового понятия. Такое именно отношение существует между понятиями «легкий» и «тяжелый». Они исключают друг друга. Нельзя об одном и том же предмете, взятом в одно и то же время и в одном и том же отношении, сказать, что он и легкий, и тяжелый. Но между данными понятиями есть среднее, третье: предметы бывают не только легкого и тяжелого веса, но также и среднего веса.

Когда же между понятиями существует противоречащее отношение, тогда отношение между объемами понятий изображается иначе: круг делится на две части так: А — родовое понятие, B и не-B (обозначается как B) — противоречащие понятия. Противоречащие понятия, исключают друг друга и входят в один и тот же род, что можно выразить такой схемой:

Понятие А – «новый компььютер», тогда другое понятие, находящееся с ним в отношении противоречия, нужно обозначить не-А («неновый компьютер»). Круг, выражающий это отношение, делится на две части: третьего понятия между ними нет.hello_html_m5001ea4d.png


Задачи, при решении которых, используются круги Эйлера

Ну а как же круги Эйлера помогают при решении задач? Для ответа возьмем несколько задач:

1. Часть жителей нашего города умеет говорить только по-русски, часть – только по-башкирски и часть умеет говорить на обоих языках. По-башкирски говорят 85%, по-русски 75%. Сколько процентов жителей говорят на обоих языках?

Решение. Составим схему.

В кружке под буквой «Б» обозначим жителей, говорящих по-башкирски, под буквой «Р» - по-русски. В общей части кружков обозначим жителей, говорящих на обоих языках. Теперь от всех жителей (100%) отнимем кружок «Б» (85%), получим жителей, говорящих только по-русски (15%). А теперь от всех, говорящих по-русски (75%), отнимем эти 15%. Получим говорящих на обоих языках (60%).hello_html_1d1fe48e.png

2. Все мои подруги выращивают в своих квартирах какие-нибудь растения. Шестеро из них разводят кактусы, а пятеро — фиалки. И только у двоих есть и кактусы и фиалки. Угадайте, сколько у меня подруг?hello_html_m2b29b326.png

Решение. Обратимся к кругам Эйлера.hello_html_7b7973fd.png

Изобразим два круга, так как у нас два вида цветов. В одном будем фиксировать владелиц кактусов, в другом — фиалок. Поскольку у некоторых подруг есть и те, и другие цветы, то круги нарисуем так, чтобы у них была общая часть. В этой общей части ставим цифру 2 так как кактусы и фиалки у двоих. В оставшейся части «кактусового» круга ставим цифру 4 (6 − 2 = 4). В свободной части «фиалкового» круга ставим цифру 3 (5 − 2 = 3). А теперь рисунок сам подсказывает, что всего у меня 4 + 2 + 3 = 9 подруг.

3. В футбольной команде «Спартак» 30 игроков, среди них 18 нападающих. 11 полузащитников, 17 защитников и вратари. Известно, что трое могут быть нападающими и защитниками, 10 защитниками и полузащитниками, 6 нападающими и защитниками, а 1 и нападающим, и защитником, и полузащитником. Вратари не заменимы. Сколько в команде «Спартак» вратарей?

Решение. 18+11+17-3-10-6+1=28 (игроков) на этой диаграмме. Но в команде всего 30 футболистов. Значит вратарей будет 30-28=2. Ответ: 2 вратаря.

4. В классе 30 человек. 20 из них каждый день пользуются метро, 15 — автобусом, 23 — троллейбусом, 10 — и метро, и троллейбусом, 12 — и метро, и автобусом, 9 — и троллейбусом, и автобусом. Сколько человек ежедневно пользуются всеми тремя видами транспорта?

Решение. 1 способ. Для решения опять воспользуемся кругами Эйлера: Пусть х человек пользуется всеми тремя видами транспорта. Тогда пользуются только метро и троллейбусом — (10 − х) человек, только автобусом и троллейбусом — (9 − х) человек, только метро и автобусом — (12 − х) человек. Найдем, сколько человек пользуется одним только метро: 20 − (12 − х) − (10 − х) − х = х − 2hello_html_m5213a91a.png

Аналогично получаем: х − 6 — только автобусом и х + 4 — только троллейбусом, так как всего 30 человек, составляем уравнение:

Х + (12 − х) + (9 − х) + (10 − х) + (х + 4) + (х − 2) + (х − 6) = 30. отсюда х = 3.

2 способ. А можно эту задачу решить задачу другим способом:

20+15+23-10-12-9+х=30, 27+х=30, х=3.

5. В восьмом классе учится 40 человек. Каждый из них изучает не менее одного иностранного языка: английский, немецкий, французский. 34 человека изучают хотя бы один из двух языков: английский, немецкий. 25 человек — хотя бы один из языков: немецкий, французский. 6 человек только немецкий. Одновременно два языка — английский и немецкий — изучают на 3 человека больше, чем французский и немецкий языки. Сколько человек изучает каждый из языков и сколько изучает одновременно каждую пару языков?

Решение

хотя бы 1

А + Н = 34

Ф + Н = 25

Н = 6

А + Н = на 3 человека >, чем Ф + Н = х одновр. одновр. 34 – х – 36х + х + 3 + 6 + х +25 – х – 6 – х – 3 = 40hello_html_m463e67e8.png

2х = 40 – 34 + 3 – 25

2х = –10 х = 5

Ф + Н = 5 человек.

А + Н = 8 человек.

А = 34 – 8 – 6 – 5 =15 человек.

Н = 6 человек.

Ф =25 – 5 – 6 –8 = 6 человек.

Всего 40 человек.

6. В магазине побывало 65 человек. Известно, что они купили 35 холодильников, 36 микроволновок, 37 телевизоров. 20 из них купили и холодильник и микроволновку, 19 - и микроволновку, и телевизор, 15-холодильник и телевизор, а все три покупки совершили три человека. Был ли среди них посетитель, не купивший ничего?hello_html_m3f7c74d9.png

Решение:

Купили только холодильники: 35-(20-3)-(15-3)-3=4.

Купили только микроволновки: 36-(20-3)-(19-3)-3=0.

Купили только телевизоры: 37-(15-3)-(19-3)-3=6.

Тогда всего покупателей было: 4+17+3+16+12+6=58. 65-58=7 посетителей магазина не купили ничего.

О графах

Исторические сведения

Теория графов - возникло в конце XVIII веке и в настоящее время превратилось в весьма мощный и непрерывно развивающийся математический инструмент.

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

Теория графов

Основные понятия

Если объекты некоторой системы изобразить вершинами, а связи между ними – линиями, то мы получим информационную модель рассматриваемой системы в форме графа. Граф состоит из вершин, связанных линиями – ребрами. Первое из основных понятий теории графов - это понятие вершины. В теории графов оно принимается в качестве первичного и не определяется. Его нетрудно представить себе на собственном интуитивном уровне. Обычно вершины графа наглядно изображаются в виде окружностей, овалов, прямоугольников, точек и другими фигурами. Хотя бы одна вершина должна обязательно присутствовать в каждом графе.

IMG00358

Другое основное понятие теории графов - дуги. Обычно дуги представляют собой отрезки прямых или кривых, соединяющих вершины. Каждый из двух концов дуги должен совпадать с какой-нибудь вершиной. Случай, когда оба конца дуги совпадают с одной и той же вершиной, не исключается. Например, IMG00362


- допустимые изображения дуг,



IMG00363

- недопустимые:

 

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

На рисунке с помощью взвешенного графа изображены дороги между пятью населенными пунктами A, B, C, D, E; веса ребер – протяженность дорог в километрах.

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

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

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

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

Всякая иерархическая система может быть представлена с помощью дерева. У дерева выделяется одна главная вершина, называемая его корнем. Каждая вершина дерева (кроме корня) имеет только одного предка, обозначенный им объект входит в один класс высшего уровня. Любая вершина дерева может порождать несколько потомков – вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один-ко-многим». Вершины, не имеющие порождённых вершин. Называются листьями.

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

Дуги могут быть однонаправленными, при этом каждая дуга имеет только одно направление, или двунаправленными.

В большинстве применений можно без потери смысла заменить ненаправленную дугу на двунаправленную, а двунаправленную - на две однонаправленных дуги. IMG00364

Как правило, граф либо сразу строится таким образом, чтобы все дуги имели одинаковую характеристику направленности (например, все - однонаправленные), либо приводится к такому виду путем преобразований. Если дуга AB - направленная, то это значит, что из двух ее концов один (A) считается началом, а второй (B) - концом. В этом случае говорят, что начало дуги AB есть вершина A, а конец - вершина B, если дуга направлена от A к B, или что - дуга AB исходит из вершины A и входит.IMG00365

Две вершины графа, соединенные какой-либо дугой (иногда, независимо от ориентации дуги) называют смежными вершинами.

Важным понятием при исследовании графов является понятие пути. Путь A1,A2,...An определяется как конечная последовательность (кортеж) вершин A1,A2,...An и дуг A1, 2,A2 ,3,...,An-1, n последовательно соединяющих эти вершины.

Важным понятием в теории графов является понятие связности. Если для любых двух вершин графа существует хотя бы один соединяющий их путь - граф называется связным.

Например, если изобразить в виде графа систему кровообращения человека, где вершины соответствуют внутренним органам, а дуги - кровеносным капиллярам, то такой граф, очевидно, является связным. Можно ли утверждать, что система кровообращения двух произвольных людей является несвязным графом? Очевидно, нет, поскольку в природе наблюдаются т. н. “сиамские близнецы”.

Связность может быть не только качественной характеристикой графа (связный/несвязный), но и количественной.

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

Иногда связность определяют как характеристику не каждой, а одной (произвольной) вершины. Тогда появляются определения типа: граф называется K-связным, если хотя бы одна его вершина связана с K других вершин.

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

Еще одна характеристика графа, исследуемая в ряде задач, часто называется мощностью графа. Эта характеристика определяется как количество дуг, связывающих две вершины. При этом дуги, имеющие встречное направление, часто рассматриваются раздельно.

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

Мощность, как и связность, может определяться как для каждой пары вершин графа, так и для некоторой (произвольной) пары.

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

Разновидности графов

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

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

Окраска

Окраска графов - весьма популярный способ модификации графов.

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

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

мозг



желудок





легкие





сердце






печень



конечности






Дольность

Иногда элементы объекта, моделируемые вершинами, имеют существенно различный характер. Или к реально существующим в объекте элементам в процессе формализации оказывается полезным добавить некоторые фиктивные элементы. В этом, и некоторых других случаях, вершины графа естественно разделить на классы (доли). Граф, содержащий вершины двух типов, называют двудольным и т. д. При этом в число ограничений графа вносятся правила, касающиеся взаимоотношений вершин разных типов. Например: “не существует дуги, которая бы соединяла вершины одного типа”. Одна из разновидностей графов такого рода называется “сеть Петри” (рис. 9) и имеет достаточно широкое распространение. Более подробно сети Петри будут рассмотрены в следующей статье этого цикла.

Понятие дольности может быть применено не только к вершинам, но и к дугам.

IMG00374


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

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

Например, дана блок-схема алгоритма вычислений. На входе – любое целое число, на выходе – результат вычислений.C:\Users\миша\Desktop\Фото0104.jpg

Какое значение получится на выходе схемы, если на вход подать: а) число 3; б) число 1; в) число 25?


Решение задач, используя графы

1. Любители музыки

В клубе «Отдых» познакомились 3 любителя клубной музыки видов техно, хаус, рейв. Один говорит: «Вы какую музыку больше любите? Я техно люблю!». Другой ответил, что любит хаус, а третий сказал, что не любит ни техно, ни хаус, но зато обожает рейв. Интересно то, что все они были в банданах и рубашках черного, белого и желтого цветов, но цвет банданы и рубашки совпадал только у любителя техно. А у любителя хаус ни рубашка, ни бандана не были белыми. А любитель рейв был в желтой рубашке. Определите цвет рубашек и бандан каждого из любителей клубной музыки.
Решение Заметим, что по условию задачи цвет банданы и рубашки совпадал только у любителя техно. А так как у любителя хаус ни рубашка ни бандана не были белыми и любитель рейв был в желтой рубашке, то делаем вывод, что любитель техно может быть в рубашке и бандане только белого цвета.
Получаем граф:
3

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

Ответ. У любителя техно рубашка и бандана белого цвета; у любителя хаус черная рубашка и желтая бандана; у любителя рейв желтая рубашка и черная бандана.4

  1. Футбол

Четыре футбольных команды: итальянская команда «Милан», испанская – «Реал», российская – «Зенит», английская – «Челси» встретились в групповом этапе лиги чемпионов по футболу. Их тренировали тренеры из этих же четырех стран: итальянец Антонио, испанец Родриго, русский Николай, англичанин Марк. Известно, что национальность у всех четырех тренеров не совпадала с национальностью команд. Требуется определить тренера каждой команды, если известно:
а) Зенит не тренируется у Марка и Антонио.
б) Милан обещал никогда не брать Марка главным тренером.
Решение

Исходя из условий задачи, получаем следующий граф.

Сразу можем сделать вывод, что российская команда «Зенит» тренируется у испанца Родриго. Чертеж примет вид: 65


Теперь получили, что итальянская команда «Милан» тренируется у русского Николая. Внесем и эти изменения в чертеж, получим:

Приходим к выводу, что английская команда «Челси» тренируется у итальянца Антонио и испанская команда «Реал» тренируется у англичанина Марка.
Ответ. Российская команда «Зенит» тренируется у испанца Родриго; итальянская команда «Милан» тренируется у русского Николая; английская команда «Челси» тренируется у итальянца Антонио; испанская команда «Реал» тренируется у англичанина Марка.7

  1. Три поросёнка

Жили-были на свете три поросенка, три брата: Ниф-Ниф, Наф-Наф, Нуф-Нуф. Построили они три домика: соломенный, деревянный и кирпичный. Все три брата выращивали возле своих домиков цветы: розы, ромашки и тюльпаны. Известно, что Ниф-Ниф живет не в соломенном домике, а Наф-Наф – не в деревянном; возле соломенного домика растут не розы, а тот, у кого деревянный домик, выращивает ромашки. У Наф-Наф аллергия на тюльпаны, поэтому он не выращивает их. Узнайте, кто в каком домике живет и какие цветы выращивает.
Решение

Из условий задачи получаем граф: 8

Можно сделать вывод, что возле кирпичного домика растут розы, а возле соломенного – тюльпаны. А так как Наф-Наф живет не в деревянном домике, то он и не выращивает ромашки. А так как на тюльпаны у него аллергия, то он может выращивать только розы. Внесем эти данные в чертеж и получим:
Теперь стало ясно и то, что Ниф-Ниф живет в деревянном домике и выращивает ромашки. Методом исключения получаем, что Нуф-Нуф живет в соломенном домике и выращивает тюльпаны.
Ответ. Наф-Наф живет в кирпичном домике и выращивает розы; Ниф-Ниф живет в деревянном домике и выращивает ромашки; Нуф-Нуф живет в соломенном домике и выращивает тюльпаны.9


  1. Соревнование по фехтованию

Атос, Портос и Арамис в соревновании по фехтованию заняли три первых места. Какое место занял каждый из них, если Портос занял не второе и не третье место, а Арамис – не третье?
Решение
10

Учитывая условия задачи, сразу делаем вывод, что Портос занял первое место. Значит, Арамис занял второе место, и Атос – третье место. Решение задачи показано на чертеже:
Ответ. Арамис – второе место; Атос – третье место; Портос – первое место.

  1. "Виа Гра"

В группе «Виа Гра» поют три девушки: блондинка, рыжая и брюнетка. В клипе «Бриллианты» девушки одеты в белое, красное и черное платья. Интересно, - заметила брюнетка, - что цвета наших с вами волос не соответствуют нашим платьям.
- А ведь верно, но мне подошло бы твое платье, - подтвердила девушка в белом платье.
В какое платье была одета каждая из девушек?
Решение
Учитывая условия задачи, получаем следующий граф:
Используем правило: если какая-то точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с третьей точкой она должна быть соединена сплошной. Поэтому граф на рисунке будет выглядеть следующим образом:
hello_html_m2d371083.pnghello_html_m2d371083.png





Заключение

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

Данная исследовательская работа нашла применение на уроках математики и информатике в 3 «А», 6, 7-х классах школы № 29.

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

Таким образом, материалы работы показывают, что поставленные в ней задачи, сформированные выше во введении, полностью решены.












Литература

  1. http://ru.wikipedia.org/

  2. «Занимательные задачи по информатике» Л. Л. Босова, А. Ю. Босова, Москва, 2005

  3. «Сценарии школьных праздников» Е. Владимирова, Ростов-на-Дону, 2001

  4. Задачи для любознательных. Д. В.Климченко, М., Просвещение, 1992г,

  5. Внеклассная работа по математике, З. Н.Альхова, А. В.Макеева, Саратов, Лицей, 2002г

  6. Удивительный мир чисел. Б. А.Кордемский, А. А.Ахадов., М., Просвещение, 1986г.

  7. Алгебра: учебник для 9 класса. Ю. Н.Макарычев, Н. Г.Миндюк и др. под ред. С. А.Теляковского,- М.: Просвешение, 2008

  8. Математика: учебник для 5 класса. С. М.Никольский, М. К.Потапов и др.,- М.: Просвещение

  9. Занимательные задачи по информатике. Л.Л. Босова, А.Ю. Босова, Ю.Г. Коломенская., М.: БИНОМ. Лаборатория знаний, 2005

  10. Задачник-практикум в 2т. Том 1, Л.А. Залогова и др., М.: БИНОМ. Лаборатория знаний, 2009

  11. Информатика и ИКТ: учебник для 9 класса: в 2 ч. Ч. 1, Л.Л. Босова., М.: БИНОМ. Лаборатория знаний, 2012




Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Краткое описание документа:

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

Автор
Дата добавления 02.08.2015
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров4985
Номер материала ДA-000209
Получить свидетельство о публикации
Похожие материалы

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