Бахарев Ю.П. \ Продвинутая информатика для школьников

 

Embed or link this publication

Description

Продвинутая информатика для школьников

Popular Pages


p. 1



[close]

p. 2

VIXRI.RU 2015 Каждый хочет, чтобы его информировали честно, беспристрастно, правдиво — и в полном соответствии с его взглядами. Гилберт Честертон Логика есть анатомия мышления. Джон Локк Логика — это нравственность мысли и речи. Ян Лукасевич Логика — это искусство ошибаться с полной достоверностью. Джозеф Вуд Кратч ЧЕТЫРЕ ЗАКОНА ТЕОРИИ ИНФОРМАЦИИ: 1. Информация, которая у вас есть, не та, которую вам хотелось бы получить. 2. Информация, которую вам хотелось бы получить, не та, которая вам на самом деле нужна. 3. Информация, которая вам на самом деле нужна, вам недоступна. 4. Информация, которая в принципе вам доступна, стоит больше, чем вы можете за нее заплатить. Парень, который изобрел первое колесо, был идиотом, но парень, который изобрел остальные три, был гением. Сид Сизар Знания бывают двоякого рода: либо мы что-нибудь знаем, либо мы знаем, где найти сведения об этом. Сэмюэл Джонсон Мудр тот, кто овладел искусством размышления, познал себя и научился обращению с людьми, но отвергает звание мудреца и не лезет к другим с назиданиями, ведь глупее непрошеной мудрости нет ничего на земле. Генри Питер Брум Мудрость часто влечет за собой одиночество. Мудрецу хорошо одному, в своем собственном обществе, наедине со своими помыслами, однако истинный мудрец не отворачивается от людей, вращаясь в самой гуще жизни, хоть его счастье и заключено в покое. В мире людей порой, чтобы мудро поступить, придется поневоле притвориться глупым человеком, однако тот, кто слишком злоупотребляет этим способом, сам рано или поздно превращается в глупца. Все дело в том, что это легкий путь решения проблем, а без сложной работы со временем ум, потускнев, увядает. Педагоги не могут успешно кого-то учить, если в это же время усердно не учатся сами. Правильно говорят, что, если человек талантлив, то талант у него многогранен. Однако он должен еще суметь развить в себе все эти дарования, отшлифовать свои способности и правильно воспользоваться ими с пользой для себя и для людей, но удается это далеко не всем и уж во всяком случае не сразу. Старайся знать все о чем-нибудь и что-нибудь обо всем. Никто не знает достаточно; слишком много знают слишком многие. Мария Эбнер-Эшенбах Бахарев Ю.П. Продвинутая информатика для школьников Страница 2

[close]

p. 3

VIXRI.RU 2015 Бахарев Ю.П. Продвинутая информатика для школьников Страница 3

[close]

p. 4

VIXRI.RU 2015 Сергей Павлович Королёв – ученый, основоположник практической космонавтики, выдающийся конструктор и организатор работ по созданию ракетно-космической техники в СССР. Он по праву считается первопроходцем многих основных направлений развития отечественного ракетного вооружения и ракетно-космической техники, обеспечивших стратегический паритет и сделавших наше государство передовой ракетно-космической державой. За выдающийся вклад в оборону Родины и в развитие практической космонавтики академик С. П. Королёв дважды удостоен звания Героя Социалистического Труда, в 1956 и 1961 годах, ему присуждена Ленинская премия в 1957 году и золотая медаль имени К. Э. Циолковского. Сергей Павлович Королёв родился 12 января 1907 года в Ж итомире в семье преподавателя русской словесности Павла Яковлевича Королёва и Марии Николаевны Москаленко. Ему было около трех лет, когда родители развелись. По решению матери, маленького Сережу отправили в Нежин к бабушке Марии Матвеевне и дедушке Николаю Яковлевичу Москаленко. В 1915 году Сергей поступил в подготовительные классы гимназии в Киеве, в 1917 году – пошел в первый класс гимназии в Одессе, куда переехали мать, Мария Николаевна, и отчим, Бахарев Ю.П. Продвинутая информатика для школьников Страница 4

[close]

p. 5

VIXRI.RU 2015 Георгий Михайлович Баланин. Еще в школьные годы Сергей отличался исключительными способностями и неукротимой тягой к новой тогда авиационной технике. В 1921 году Королёв познакомился с летчиками Одесского гидроотряда и активно участвовал в авиационной общественной жизни: с 16 лет как лектор по ликвидации авиабезграмотности, а с 17 лет — как автор проекта безмоторного самолета К-5, официально защищенного перед компетентной комиссией и рекомендованного к постройке. В гимназии учился недолго – ее закрыли, потом были четыре месяца единой трудовой школы. Далее получал образование дома – его мать и отчим были учителями, а отчим помимо педагогического имел инженерное образование. В 1923 году Сергей вступил в Общество друзей воздушного флота (ОДВФ), сконструировал свой первый безмоторный планер. В 1924 году окончил Одесскую строительную профессиональную школу, а уже 1 июня этого же года подал просьбу о зачислении в Академию воздушного флота. Решение вопроса затянулось, и он поступил в Киевский политехнический институт на авиационное отделение, затем перевелся в Московское высшее техническое училище имени Н. Э. Баумана (МВТУ). Будучи еще студентом, Сергей Королёв в мае 1927 года посетил международную выставку межпланетных аппаратов, где впервые познакомился с работами Ф. А. Цандера и брошюрой К. Э. Циолковского «Исследование мировых пространств реактивными приборами». Книги, чертежи, схемы, кустарные модели – все, что демонстрировалось на выставке, задело сознание юноши. С этого времени он стал более пристально относиться к ракетам и полетам в космос. Производственную практику студент выпускного курса МВТУ проходил в конструкторском бюро А. Н. Туполева при Центральном аэрогидродинамическом институте (ЦАГИ). В это время он уже работал на авиационном заводе в Филях. Одновременно готовил дипломный проект, решив сконструировать легкомоторный двухместный самолет СК-4, выжав из него все возможное. За время учебы в МВТУ Королёв уже получил известность как молодой способный авиаконструктор и опытный планерист. Спроектированные и построенные им летательные аппараты: планеры «Коктебель», «Красная Звезда» и легкий самолет СК-4, предназначенный для достижения рекордной дальности полета, — показали незаурядные способности Королёва как авиационно-Сергей Павло вич Корол Ёв 1907– 1966 го конструктора. Нагрузка на квадратный метр у планера «Красная Звезда» была большей, чем у «Коктебеля», – 22,5 кг. Данные аппараты были настолько необычными, что ставилась под сомнение возможность самого парения в воздухе. Однако именно на нем впервые в истории авиации летчик-испытатель В. А. Степанченок, опытный летчик-планерист, в свободном полете совершил знаменитую петлю Нестерова. Королёв на состязаниях не присутствовал, его неожиданно свалил тяжелый тиф. В результате осложнения появились сильные головные боли. После болезни организм оказался настолько ослабленным, что пришлось на несколько месяцев оставить работу. Но едва стало легче, Сергей с увлечением принялся за труд К. Э. Циолковского «Реактивный аэроплан». Сергея Королёва по-прежнему интересовала авиация, но стремление найти средства летать выше, быстрее, дальше вплотную подвели его к мысли заняться исследованием возможностей реактивного движения. Он был согласен с К. Э. Циолковским: «За эрой аэропланов винтовых должна следовать эра аэропланов реактивных, или аэропланов стратосферы». Он окончил в 1929 году МВТУ, получив специальность инженера-аэромеханика, и одновременно в Московской школе летчиковпланеристов получил свидетельство пилота. В сентябре 1931 года С. П. Королёв и талантливый энтузиаст в области ракетных двигателей Ф. А. Цандер добиваются с помощью центрального совета Общества содействия обороне, авиационному и химическому строительству (Осоавиахим) создания в Москве общественной организации – Группы изучения реактивного движения (ГИРД). Клуб энтузиастов стал Бахарев Ю.П. Продвинутая информатика для школьников Страница 5

[close]

p. 6

VIXRI.RU 2015 тем центром, куда стекались все интересующиеся ракетной техникой. Руководителем ее был назначен Ф. А. Цандер, сыгравший важную роль в разработке теоретических и практических вопросов космоплавания. Технический совет новой организации возглавил С. П. Королёв. Возраст сотрудников, за небольшим исключением, не превышал 25 лет. Размещался клуб ГИРД в заброшенном подвале в доме 19 на Садово -Спасской улице. Мысль о создании реактивных двигателей волновала в те годы многие умы и за пределами СССР. Но первый, основной толчок дал Константин Эдуардович Циолковский, именно ему принадлежит идея рождения реактивного двигателя, работающего на жидком топливе. В 1920-х годах работы в этом направлении также велись немецким ученым Германом Обертом, американским профессором Робертом Годдардом и др. В апреле 1932 года ГИРД становится по существу государственной научно-конструкторской лабораторией по разработке ракетных летательных аппаратов, в которой создаются и первые отечественные жидкостные баллистические ракеты (БР) ГИРД-09 (конструкции М. К. Тихонравова) и ГИРД-Х (конструкции Ф. А. Цандера). В 1933 году сбылась наконец мечта энтузиастов ракетного дела о создании единого ракетного центра. Отсекая все бюрократические препоны, личным приказом по Реввоенсовету М. Н. Тухачевского, с глубоким пониманием относившегося к принципиально новым работам, ГИРД и ленинградская Газодинамическая лаборатория (ГДЛ) были объединены в Реактивный научно исследовательский институт (РНИИ). Начальником института был назначен И. Т. Клеймёнов (начальник ГДЛ), а его заместителем по научной работе – С. П. Королёв. Ему присвоили должностное звание дивизионного инженера (по современному табелю о рангах – звание генерал-лейтенанта технических войск). Высокое звание в 26 лет. В это же время С. П. Королёв и М. К. Тихонравов были удостоены высшей награды оборонного общества – знака «За активную оборонную работу». В 1934 году вышла в свет первая печатная работа С. П. Королёва «Ракетный полет в стратосфере». «Ракета является очень серьезным оружием», – предупреждал автор в своей работе. Экземпляр книги Сергей Павлович послал К. Э. Циолковскому. Вскоре в Осоавиахим пришло письмо от Циолковского с отзывом на труд Королёва: «Книга разумная, содержательная и полезная». Ученый лишь сетовал, что автор не сообщил своего адреса и лишил его возможности лично поблагодарить за книгу. В том же 1934 году из за расхождения во взглядах со своим руководством на перспективы развития ракетной техники Королёв переходит на должность руководителя отдела ракетных летательных аппаратов, где ему как начальнику отдела в 1936 году удалось довести до испытаний крылатые ракеты: зенитную 217 с пороховым ракетным двигателем и дальнобойную 212 с жидкостным ракетным двигателем. Также им был разработан ряд успешных проектов, в том числе проекты управляемой крылатой ракеты (летавшей в 1939 году) и ракетоплана РП-318- 1 с ракетным двигателем. В 1937 году Сергей Павлович участвовал в испытаниях ракетоплана с двигателем ОРМ-65 конструкции В. П. Глушко. Постепенно создалась серьезная научно-техническая база для энтузиастов ракетного дела. Но в это же время стал складываться и культ личности Сталина. Чувствовалось и приближение войны. Внимание многих ученых все более сосредотачивалось на вопросах обороны. Приходилось откладывать в сторону многие чисто научные замыслы. Королёв мечтал вплотную заняться ракетопланом, но задуманному тогда не суждено было осуществиться. Не все шло гладко во вновь созданном институте. Выявились разногласия относительно первостепенных задач Ракетного института между И. Т. Клеймёновым и С. П. Королёвым, в результате которых последнего сместили на рядовую должность старшего инженера. Осенью 1937 года волна репрессий и произвола, захлестнувшая страну, докатилась и до РНИИ. Среди других «военных заговорщиков» был расстрелян М. Н. Тухачевский. Началась Бахарев Ю.П. Продвинутая информатика для школьников Страница 6

[close]

p. 7

VIXRI.RU 2015 чистка ближнего и дальнего их окружения. Был арестован и помещен за тюремную решетку начальник Центрального конструкторского бюро (ЦКБ-29), специально созданного народным комиссариатом, А. Н. Туполев. В этом закрытом ЦКБ оказался не по своей воле не только 614 личность в истории Туполев, но и арестованные по навету «враги народа» – знаменитые в авиационном мире конструкторы В. М. Мясищев, В. М. Петляков, Р. Л. Бартини и др. В Москве, на улице Радио, для них переоборудовали в тюрьму семиэтажное здание ЦАГИ, выделив комнаты для жилья и конструкторской работы. Специалисты здесь работали не за страх, а за совесть, понимая – дело их необходимо стране, и свято веря, что скоро разберутся и убедятся в их невиновности. В июне 1938 года Королёв был необоснованно репрессирован и осужден на 10 лет. Вначале он был выслан на Колыму. За пересмотр приговора ходатайствовали прославленные летчики В. С. Гризодубова и М. М. Громов, авиаконструктор А. Н. Туполев, также находившийся в заключении в это время. Но решающее значение в этом деле сыграло назначение наркомом внутренних дел Л. П. Берии, который, чтобы снять народную напряженность, приступил к частичному пересмотру дел. В их числе оказалось и дело Королёва, который 13 июня 1939 года был возвращен в Москву. Но еще год пребывания в Бутырской тюрьме оказался напрасным – Королёв снова был признан виновным и осужден на восемь лет в исправительных трудовых лагерях. Казалось, этого удара Королёв не вынесет, но несгибаемая воля и вера в собственную правоту взяли верх. После долгих размышлений он решает обратиться лично к И. В. Сталину. В этом письме Сергей Павлович ставил акцент не на личном положении, а на интересах страны, ее обороны, на которую он работал не покладая рук и не щадя себя. Видимо, он был все-таки услышан. В 1940 году, после пересмотра дела, С. П. Королёва перевели с Колымы к А. Н. Туполеву в Московское конструкторское бюро при НКВД, где репрессированные авиационные специалисты принимали активное участие в создании бомбардировщиков Пе-2 и Ту-2 и где он также инициативно разрабатывал проекты управляемой аэроторпеды и нового варианта ракетного перехватчика. Это послужило причиной для перевода С. П. Королёва в 1942 году в другое КБ тюремного типа – ОКБ16 при Казанском авиазаводе №16, где под руководством В. П. Глушко велись работы над ракетными двигателями новых типов с целью применения их в авиации. Здесь С. П. Королёв со свойственным ему энтузиазмом отдается идее практического использования ракетных двигателей для усовершенствования авиации: сокращения длины разбега самолета при взлете и повышения скоростных и динамических характеристик воздушного судна во время боя. Работая в ОКБ заместителем главного конструктора двигателей, занимается проблемой оснащения серийных боевых самолетов жидкостными ракетными ускорителями. Параллельно с конструированием ракетного ускорителя Сергей Павлович стремился воплотить в жизнь свою давнюю идею создания ракетоплана, оснащенного реактивным двигателем. Там родился проект самолета-перехватчика РП с реактивным двигателем РД-1, изложенный в работе «Введение к вопросу о самолете-перехватчике РП с реактивным двигателем РД-1». В 1943 году Королёв испытывал сконструированный ракетный ускоритель в наземных и полетных условиях на самолете Пе-2. В 1944 году Королёв написал работы «Объяснительная записка к эскизному проекту специальной модификации самолетаистребителя «Лавочкин 5ВИ» со вспомогательными реактивными двигателями РД-1 и РД-3», «Крылатые ракеты» (краткий обзор работ, проводившихся в РНИИ в 1932–1938 годах). В том же году он обратился в военные инстанции страны с проектом программы разработки боевых ракетных систем. 27 июля 1944 года на заседании Президиума Верховного Совета СССР принято постановление о его досрочном освобождении, после чего он еще год работает в Казани. В августе 1945 года Сергей Павлович вернулся в Москву. В сентябре он отбыл в Германию в качестве специалиста Бахарев Ю.П. Продвинутая информатика для школьников Страница 7

[close]

p. 8

VIXRI.RU 2015 технической комиссии по изучению трофейной ракетной техники. 13 мая 1946 года было принято решение о создании в СССР отрасли по разработке и производству ракетного вооружения с жидкостными ракетными двигателями. В августе 1946 года С. П. Королёв начал работать в подмосковном Калининграде (затем переименованном в 1996 году в Королёв), где был назначен главным конструктором баллистических ракет дальнего действия и начальником отдела №3 НИИ-88 по их разработке. Также предусматривалось объединение всех групп советских инженеров, изучающих с 1945 года в Германии немецкое ракетное вооружение Фау-2, в единый научноисследовательский институт «Нордхаузен», директором которого был назначен генералмайор Л. М. Гайдуков, а главным инженерно-техническим руководителем – С. П. Королёв. Первой задачей, поставленной перед С. П. Королёвым как главным конструктором и всеми организациями, занимающимися ракетным вооружением, было создание аналога ракеты Фау-2 из отечественных материалов. В Германии Сергей Павлович не только изучает немецкую ракету Фау-2, но и проектирует более совершенную баллистическую ракету с дальностью полета до 600 км. 18 октября 1947 года на полигоне Капустин Яр состоялся старт первого образца баллистической ракеты. В 1948 году С. П. Королёв занимается совершенствованием высотных геофизических ракет, созданных на базе военных, читает курс лекций по ракетной технике в МВТУ имени Н. Э. Баумана. Занимаясь боевыми баллистическими ракетами, он стремился к главной цели – покорению космического пространства и космическим полетам человека. В 1949 году Сергей Павлович еще совместно с учеными АН СССР начал исследования с использованием модификаций ракеты Р-1А, запуская их на высоты до 100 км, а затем с помощью более мощных ракет Р-2 и Р-5 на высоты 200 и 500 км соответственно. Целью этих полетов было изучение параметров ближнего космического пространства, солнечных и галактических излучений, магнитного поля Земли, поведения высокоразвитых животных в косми-615 С ергей П авлович К орол ё в ческих условиях (невесомости, перегрузок, больших вибраций и акустических нагрузок), а также отработка средств жизнеобеспечения и возвращение животных на Землю из космоса. Было произведено около 70 таких пусков, заложивших серьезную основу для штурма космоса человеком. В 1953 году Сергей Павлович Королёв принят в члены КПСС. В том же году избран членом-корреспондентом АН СССР. В 1955 году С. П. Королёв, М. В. Келдыш и М. К. Тихонравов обратились к Правительству Советского Союза с предложением о выведении в космос при помощи ракеты Р-7 искусственного спутника Земли. Правительство поддержало эту инициативу. В августе 1956 года ОКБ-1 вышло из состава НИИ-88 и стало самостоятельной организацией, главным конструктором и директором которой назначен С. П. Королёв. За заслуги перед Отечеством Сергей Павлович Королёв в 1956 году удостаивается звания Героя Социалистического Труда – за разработку новых образцов боевых ракет. 4 октября 1957 года запущен на околоземную орбиту первый в истории человечества искусственный спутник Земли. Его полет имеет ошеломляющий успех и создает нашей стране высокий международный авторитет. А в конце 1957 года уже начался завершающий этап подготовки к запуску второго искусственного спутника Земли. Он весил в шесть раз больше первого, на его борту разместилась кабина для собаки по кличке Лайка. От успеха второго запуска зависело, быть в ближайшее время пилотируемому полету в космос или нет. Утром 3 ноября 1957 года состоялся старт второго спутника. Наблюдения за Лайкой продолжались семь суток. Из этого полета Лайка на Землю не вернулась, но ученые получили весьма ценные данные о воздействии невесомости на живой организм. Королёв умел смотреть далеко вперед. Еще до старта первого искусственного спутника под его руководством шла разработка проектов межпланетных станций, спутников народно-хозяйственного назначения, Бахарев Ю.П. Продвинутая информатика для школьников Страница 8

[close]

p. 9

VIXRI.RU 2015 пилотируемых кораблей. 15 февраля 1958 года Королёву был представлен проект летательного аппарата, состоящего из двух отсеков: приборно-агрегатного и кабины для пилота. Но проблемы возникали одна за другой. Главной из всех задач стала разработка способа возвращения корабля из космоса на Землю. Дискуссии, споры, взаимоисключающие суждения, идеи, фантастические проекты, непонимание – все это Королёв нес на своих плечах, сводил воедино, отбирал оптимальный вариант. Только благодаря всестороннему знанию предмета, напористости и убежденности, его несгибаемой воле Сергей Павлович смог выдержать все трудности работы и добиться желаемых результатов в столь короткие сроки. Под контролем Королёва в 1959 году запускаются автоматические межпланетные станции «Луна-1, -2, -3». Третья по счету лунная станция передала фотоснимки обратной, невидимой стороны Луны. С. П. Королёв начинает разработку более совершенного лунного аппарата для его мягкой посадки на поверхность Луны, фотографирования и передачи на Землю лунной панорамы. 12 апреля 1961 года С. П. Королёв снова одерживает победу, имеющую мировое значение. Создав первый пилотируемый космический корабль «Восток», он реализует первый орбитальный полет человека – гражданина СССР Юрия Алексеевича Гагарина в космическом пространстве. Корабль с человеком на борту совершил один виток вокруг планеты и успешно возвратился на Землю. Далее следует череда запусков: 6 августа 1961 года Г. С. Титовым на корабле «Восток-2» был совершен второй космический полет, который длился сутки; с 11 по 12 августа 1962 года состоялся совместный полет космических кораблей «Восток-3» и «Восток-4», пилотируемых космонавтами А. Н. Николаевым и П. Р. Поповичем; между космонавтами была установлена прямая радиосвязь; с 14 по 16 июня 1963 года – совместный полет космонавтов В. Ф. Быковского и В. В. Терешковой на кораблях «Восток-5» и «Восток6»; с 12 по 13 октября 1964 года в космос летит экипаж из трех человек по околоземной орбите на более сложном космическом корабле «Восход»; 18 марта 1965 года во время полета на корабле «Восход-2» с экипажем из двух человек космонавт А. А. Леонов в скафандре совершает первый в мире выход в открытый космос, через шлюзовую камеру. Развивая программу пилотируемых околоземных полетов, Сергей Павлович начал реализовывать свои идеи о разработке пилотируемой долговременной орбитальной станции. Ее прообразом явился принципиально новый, более совершенный, чем предыдущие, космический корабль «Союз», проект которого он утвердил. Параллельно с развитием пилотируемой космонавтики велись работы над спутниками научного, народно-хозяйственного и оборонного назначения. Сергей Королёв был генератором многих неординарных идей и прародителем выдающихся конструкторских коллективов, работающих в области ракетно-космической техники, его вклад в развитие отечественной и мировой пилотируемой космонавтики является решающим. Можно только удивляться многогранности таланта Сергея Павловича, его неиссякаемой творческой энергии. Он является первопроходцем во многих основных направлениях развития отечественного ракетного вооружения и ракетно-космической техники. Трудно себе даже представить, какого уровня достигли бы мы в этой сфере, если бы преждевременная смерть Сергея Павловича не прервала творческий полет его мыслей. Сергей Павлович Королёв скончался на 60-м году жизни 14 января 1966 года. Урна с его прахом установлена на Красной площади в кремлевской стене. В 1966 году, менее чем через месяц после кончины С. П. Королёва, на поверхность Луны совершил мягкую посадку космический аппарат – последняя его работа по программе изучения Луны. Бахарев Ю.П. Продвинутая информатика для школьников Страница 9

[close]

p. 10

VIXRI.RU 2015 СОДЕРЖАНИЕ 1. 2. 3. 4. 5. ОСНОВАНИЯ МАТЕМАТИКИ ДЛЯ ШКОЛЬНИКОВ Вводные понятия_5 Смысловое краткое содержание_32 Задачник с решением типовых задач_68 Вопросы для самопроверки_84 6. ЛОГИКА 7. ПРИНЦИПЫ (ОСНОВНЫЕ ЗАКОНЫ) И ЭЛЕМЕНТАРНЫЕ МЕТОДЫ МЫСЛИТЕЛЬНОЙ ДЕЯТЕЛЬНОСТИ_76 8. ЗАНИМАТЕЛЬНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА_201 9. ЭВМ для ШКОЛЬНИОВ_279 Бахарев Ю.П. Продвинутая информатика для школьников Страница 10

[close]

p. 11

VIXRI.RU 2015 I. 1. ОСНОВАНИЯ МАТЕМАТИКИ ДЛЯ ШКОЛЬНИКОВ ВВОДНЫЕ ПОНЯТИЯ 1.1 МНОЖЕСТВА Множества. Конечные и бесконечные множества. Способы задания множеств. Подмножества. Множество всех подмножеств данного множества. О числе кэлементных подмножеств n-элементного множества. Определение мощности множества всех подмножеств конечного множества (с использованием формулы бинома Ньютона). Универсальное множество. Понятие алгебры. Алгебра множеств. Понятия алгебраических и кардинальных операций. Алгебраические операции над множествами. Законы алгебры множеств. Двойственность в алгебре множеств. Уравнения и системы уравнений в алгебре множеств. Основные леммы, используемые при решении уравнений в алгебре множеств. Мощность множества. Понятие счетного множества и континуума. Канторовская диагональная процедура. Примеры счетных множеств. Доказательство счетности множества алгебраических чисел. Свойства счетных множеств. Необходимые и достаточные условия бесконечности множества. Примеры континуальных множеств. Теорема Кантора-Бернштейна. Доказательство существования иррациональных и трансцендентных чисел. Кардинальные операции над множествами. Прямое произведение множеств. Проекция множеств. 1.2 БИНАРНЫЕ ОТНОШЕНИЯ Бинарные отношения. Свойства бинарных отношений. Представления бинарных отношений в виде матриц, орграфов, верхнего и нижнего сечений. Операции над бинарными отношениями. Выражение свойств бинарных отношений через задающие их множества. Отношения порядка. Упорядоченные множества. Отношение эквивалентности. Классы эквивалентности. Системы различных представителей. Лексикографическое отношение порядка. Мажоранта и миноранта множеств. Максимум и минимум множеств. Точные грани множеств. Понятие графика. Функциональные, инъективные графики. Инверсия графика. Соответствия. Функциональные, инъективные, сюръективные и биективные соответствия. Общее понятие функции. Биективная функция. 1.3 АЛГЕБРА ВЫСКАЗЫВАНИЙ Высказывания. Операции над высказываниями. Формулы и функции алгебры логики. О числе функций алгебры логики от n переменных. Равносильные формулы. Законы алгебры логики. ДНФ и КНФ. Разложение функций алгебры логики по к переменным. СДНФ и СКНФ. Логические следствия. Проблема разрешимости в алгебре логики. Тавтологии и противоречия. Основные схемы доказательств: если x то y, доказательство от противного, доказательство построением цепочки импликаций, доказательство разбором случаев. Суперпозиция функций алгебры логики. Полные системы функций. Понятие базиса. Алгебра Жегалкина. Полином Жегалкина. Теорема Бахарев Ю.П. Продвинутая информатика для школьников Страница 11

[close]

p. 12

VIXRI.RU 2015 Жегалкина. Замкнутые классы функций. Линейные функции. Монотонные функции. Теорема о монотонных функциях. Двойственность в алгебре высказываний. Самодвойственные функции . Функции не сохраняющие константы 0, 1. Теорема Поста о функциональной полноте. Смысловое содержание ДИСКРЕТНОЙ МАТЕМАТИКИ Формулы в математике были придуманы, как это не странно, чтобы облегчить занятия этой самой математикой. Школьники не могут в это поверить до сих пор. В древней, например, Индии хорошо обходились без формул: брали обезьяну, кувшин, банан, женщину и другие конкретные предметы… И, как сейчас говорят, конкретно строили логические выводы. И египтяне вместо формул, которые еще не были придуманы, высекали у себя в пустынях, красивые барельефы без малейшего представления о формулах. И арабы когда-то занимались математикой без формул — в стихотворной форме они ею занимались. Сладкозвучные поэмы писали про квадрат суммы… Но потом пошло-поехало… Виноват конкретно Пифагор, который сказал, что "ВСЕ ЕСТЬ ЧИСЛО"!… Большую неправду для математики трудно придумать и сегодня! Хотя к пифагоровым штанам претензий нет… Скроены они на века. Сегодня математику не любят многие. Подавляющее большинство мирного населения. Не любят прежде всего из-за формул. И правильно делают. Поскольку еще в школе несчастных предупредили, что математика — это формулы, так же как стихи — это рифмы. Не правда ли, очень удачно!? Каково же было мое удивление, когда, читая книги по основам (основаниям) математики, я там, практически, не обнаружил формул. Формулы, конечно, создают для математика великое облегчение, но это надо понять добровольно, а не подвергаться принудительной формулизации. Тут есть еще более коварное слово СЕМАНТИКА, что на человеческом языке означает обычно СМЫСЛ. Так вот, прежде всего со смыслом обычно и борется математика всеми доступными ей средствами, в том числе и формулами… Разумеется, во имя достижения ВЫСШЕГО СМЫСЛА. Как это всегда у нас бывает! Чем более «высшая" математика — тем меньше в ней СЕМАНТИКИ и больше СИНТАКСИСА. Синтаксис все в школе тоже проходили и он до сих пор мало кому доставляет радость!… В интернете, с момента его возникновения, много появляется очень умных людей, порой с законченным физмат образованием. Это хорошо, но иногда достает… поскольку от большого ума не все сохраняют способны судить «по законам жанра". Так что к ним отдельная просьба, не подозревать автора в попытке написать учебник по "основаниям математики“, или "монографию“. Раздел 1. МНОЖЕСТВА Что такое «множество» — ясно из самого слова без всякого определения. Тем более, что дать этому фундаментальному математическому понятию определение невозможно. И не пробуйте. Лучше потратить свою энергию на вечный двигатель или на что-то другое конкретное… Множеством может быть множество деревьев в лесу, множество студентов в университете или даже множество бедных родственников в Америке, которые могут выслать вам приглашение… Есть, конечно, специальная очень серьезная игра под названием "АКСИОМАТИЧЕСКАЯ теория множеств". Понять ее правила дано немногим, а найти практическое применение никому… Но это развлечение Бахарев Ю.П. Продвинутая информатика для школьников Страница 12

[close]

p. 13

VIXRI.RU 2015 для очень замкнутого круга любителей, коль скоро и сама эта теория очень замкнута. Множество состоит из элементов — деревьев, студентов, бедных родственников… При этом никакой роли не играет, рассматриваем ли мы тех же студентов в порядке алфавита или по успеваемости. Недопустимы только двойники или студенты, у которых отсутствуют отличительные свойства. Будьте хоть китайскими студентами, но должны друг от друга отличаться… Могут даже быть множества, состоящее из чисел. Но мы, как договорились, от математики вообще, и от чисел в частности, шарахаемся, как черт от ладана… Поэтому можно и без них. Или можно с ними. Или будем использовать только те числа, которые хорошо знакомы с детства… Однако мы не будем считать множеством «множество мыслей в голове». И не из-за их количества, а из-за того, что эти мысли-элементы невозможно четко разделить в общей каше, разложить по полочкам и разметить. Множество мыслей, разложенных по полочкам, в голове просто не поместится из-за устаревшего устройства типовой головы. Кстати, поскольку «множество» (set) в русском языке как бы намекает на «много». А понятие «много» (many) у каждого из нас свое, то, во избежания спора между русскоязычными, мы будем слово «множество» использовать для любого количества элементов, как и англоязычный Запад. Даже для одного элемента. Даже в случаях, когда в множестве нет ни одного элемента — такое множество называется пустым! Кроме понятия множества есть еще лишь одно исходное базовое понятие — и все. Остальное в этой теории производно. Так вот, второе базовое понятие — это ПРИНАДЛЕЖНОСТЬ, или «отношение принадлежности»: то есть «элемент принадлежит множеству». Тут, тем более, нечего определять, имея в виду что слово «принадлежит» в обыденной речи можно заменять, с учетом контекста, многими синонимами, вроде: — Та березка «находится» в этом лесу, — Сидоров «числится» в студентах, — Мистер X «входит» в число ваших бедных рязанских родственников. Примечание. Чтобы избежать синонимов, которые могут нас запутать, можно бы было ввести специальный маленький значок, напоминающий греческую букву эпсилон (ε). Но мы этого делать не будем, поскольку от этого значка до формул уже рукой подать… Важное предостережение. Вопросы, вроде: «Принадлежит ли студент Сидоров множеству лысеющих людей?» уводят нас в сторону от теории множеств и мы такие вопросы будем просто игнорировать, справедливо считая, что классическая теория множеств лысеющими просто не занимается, коль скоро нет обективных оценок лысости. А значит вопрос принадлежности — непринадлежности можно утрясти неформально, например за вознаграждение. Выход здесь очень простой. Сначала определиться четко с лысиной где-то в другом официальном месте, а потом привлекать теорию множеств. То есть предполагается, что мы всегда четко знаем, что принадлежит данному множеству, а что нет! Остальное считаем несуществующим вообще!!! Далее, если мы хотим сказать, что все березки (березка, не то что лысеющий человек — она и в Африке березка), находящиеся в данном лесу, принадлежат и всему лесному богатству нашей страны, а все студенты, которые числятся в университете, числятся и студентами России, то для сокращения фраз используются термины ПОДМНОЖЕСТВО или ВКЛЮЧЕНО. Здесь тоже могут быть очевидные синонимы. Но чтобы в них не запутаться и попросту не перепутать с «принадлежит», нужно помнить одну простую вещь: «принадлежит» относится к случаю, когда "ЭЛЕМЕНТ Бахарев Ю.П. Продвинутая информатика для школьников Страница 13

[close]

p. 14

VIXRI.RU 2015 принадлежит МНОЖЕСТВУ", а «включено» — когда "МНОЖЕСТВО включено в МНОЖЕСТВО". Потому-то второй вариант для обозначения «включено» — «подмножество» — то есть какая-то часть множества. Множество студентов университета «включено» в множество студентов страны. То есть множество студентов университета «есть подмножество» множества студентов страны. Тем, кто не сломал при этом язык, ясно, что множество студентов страны «включено» во всемирное множество студентов. Можно продолжить эту цепочку включений, прихватив галактику. Но тогда следует, что множество студентов университета есть подмножество множества студентов галактики. Это свойство цепочек просто и строго (!) доказывается прямо на основании того, как мы определили отношение включения. У отношения включения есть ряд любопытных свойств. Не нами придуманных. Они могут быть обнаружены любым исследователем, если он «поиграет» с этим отношением. Например, можно сказать, что множество студентов группы ух-001 включено в множество студентов университета, поскольку такая группа в университете числится. То, что из группы отчислены все студенты, для математики никакой роли не играет. Поскольку, НЕТ ни одного студента, числящегося в этой группе, который бы не числился в университете. Такого рода рассуждения совершенно корректно можно применить к любым пустым множества и сделать обобщающий вывод, что пустое множество включено в любое множество, в том числе и в себя. Оцените математическую красоту фразы: любой элемент, принадлежащий множеству, не содержащему ни одного элемента, принадлежит и любому другому множеству, которое не содержит ни одного элемента. Чуть менее красива фраза: Любое множество является собственным подмножеством. Или то же самое, но более жестоко: любое множество включено само в себя. Действительно, группа ух-002 (в которой, вполне возможно, есть студенты) включена в группу ух-002, поскольку все студенты, которые в ней числятся по-прежнему числятся в ней, даже если ее название ух-002 упоминается несколько раз. Из последнего примера можно сделать важный вывод. Если два множества (возможно на первый взгляд различные, вроде множества чиновников и множества слуг народа) включены друг в друга, то эти множества равны — то есть состоят из одних и тех же элементов. Можно сказать чуть иначе: Если два множества являются подмножествами друг друга, то они состоят из одних и тех же элементов. А как же иначе?!… Правда, есть математики-диссиденты, которые это не признают. Но это скорее уже вопрос веры… другой математической конфессии… А теперь следует признать, что математики сродни той категории больных людей, которых называют «правдоискателями». Как правило искатели (социальной) правды правы. Но их правота или бессмысленна, или нереальна, а главное, никому кроме них не нужна… Так вот и в теории множеств часто можно найти правду, которая для посторонних людей может выглядеть, мягко выражаясь, странной и вредной. Например, студент Федоров не может быть подмножеством студентов университета, поскольку он сам не множество, а элемент. Поэтому он, как элемент, может быть лишь элементом множества студентов университета. А вот группа ух003, как множество студентов, есть полноправное подмножество множества студентов университета. Но группа ух-003 состоит всего лишь из одного неотчисленного студента. Того самого Федорова! Вот и получается, что сам Федоров не может быть подмножеством, но группа, состоящая из него одного, может. С другой стороны, если вдруг ректор решит рассматривать университет, как множество студенческих групп, то группа ух-003 станет элементом множества Бахарев Ю.П. Продвинутая информатика для школьников Страница 14

[close]

p. 15

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

[close]

Comments

no comments yet