Дискретные структуры это: матан для айтишников / Хабр

Предмет Дискретные структуры

Программа изучения нормативной учебной дисциплины «Дискретные структуры» составлена в соответствии с образовательно-профессиональной программой подготовки бакалавров направления «Программная инженерия».

Цель курса:

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

— повысить математическую и алгоритмическую культуру студентов;

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

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

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

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

Курс «Дискретные структуры» является логическим продолжением курса «Дискретная математика».

Задачи курса:

— ознакомить студентов с основами теории дискретных структур;

— выработать навыки решения задач теории дискретных структур;

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

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

В результате изучения учебной дисциплины студент должен:

— Знать:

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

— Уметь:

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

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

— проектировать элементы математического и лингвистического обеспечения вычислительных систем;

— проектировать человеко-машинный интерфейс информационных систем;

— разработка семантических порталов знаний;

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

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

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

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

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

— владеть навыками решения основных задач теории дискретных структур.

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

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

Программа учебной дисциплины состоит из таких содержательных модулей.

1. Простейшие методы доказательства.

2. Дискретные структуры и принятия решений.

3. Вычислительная сложность.

4. Модели представления знаний и методы вывода.

5. Элементарная теория чисел.

Если Вы изучаете курс «Дискретные структуры» и Вам необходима помощь в подготовке контрольных и других видов работ обращайтесь в компанию ИЦ «KURSOVIKS».

ДИСКРЕТНАЯ МАТЕМАТИКА • Большая российская энциклопедия

ДИСКРЕ́ТНАЯ МАТЕМА́ТИКА, раз­дел ма­те­ма­ти­ки, изу­чаю­щий свой­ст­ва дис­крет­ных струк­тур, ко­то­рые воз­ни­ка­ют как в са­мой ма­те­ма­ти­ке, так и в её при­ло­же­ни­ях. При этом дис­крет­ны­ми струк­ту­ра­ми на­зы­ва­ют­ся объ­ек­ты, для ко­то­рых важ­ней­шие ха­рак­те­ри­сти­ки при­ни­ма­ют ко­неч­ное или счёт­ное чи­сло зна­че­ний. К чис­лу та­ких струк­тур от­но­сят­ся, напр., ко­неч­ные груп­пы, ко­неч­ные гра­фы, не­ко­то­рые ма­те­ма­тич. мо­де­ли пре­об­ра­зо­ва­те­лей ин­фор­ма­ции, ко­неч­ные ав­то­ма­ты, Тью­рин­га ма­ши­ны. Это при­ме­ры струк­тур фи­нит­но­го (ко­неч­но­го) ха­рак­те­ра. Часть Д. м., изу­чаю­щая их, ино­гда на­зы­ва­ет­ся ко­неч­ной ма­те­ма­ти­кой. По­ми­мо фи­нит­ных струк­тур, Д. м. изу­ча­ет так­же дис­крет­ные бес­ко­неч­ные струк­ту­ры (напр., бес­ко­неч­ные ал­геб­ра­ич. сис­те­мы, бес­ко­неч­ные гра­фы, бес­ко­неч­ные ав­то­ма­ты).

Предмет и методы дискретной математики

Зна­чит. часть клас­сич. ма­те­ма­ти­ки за­ни­ма­ет­ся изу­че­ни­ем свойств объ­ек­тов не­пре­рыв­но­го ха­рак­те­ра. Ис­поль­зо­ва­ние дис­крет­ной или не­пре­рыв­ной мо­де­ли изу­чае­мо­го объ­ек­та свя­за­но как с са­мим объ­ек­том, так и с тем, ка­кие за­да­чи ста­вит пе­ред со­бой ис­сле­до­ва­тель. Са­мо де­ле­ние ма­те­ма­ти­ки на Д. м. и ма­те­ма­ти­ку, за­ни­маю­щую­ся не­пре­рыв­ны­ми мо­де­ля­ми, в зна­чит. ме­ре ус­лов­но, по­сколь­ку, с од­ной сто­ро­ны, про­ис­хо­дит об­мен идея­ми и ме­то­да­ми ме­ж­ду ни­ми, а с дру­гой – час­то воз­ни­ка­ет не­об­хо­ди­мость ис­сле­до­ва­ния мо­де­лей, об­ла­­даю­щих как дис­крет­ны­ми, так и не­пре­рыв­ны­ми свой­ст­ва­ми од­но­вре­мен­но. В ма­те­ма­ти­ке су­ще­ст­ву­ют раз­де­лы, ис­поль­зую­щие сред­ст­ва Д. м. для изу­че­ния не­пре­рыв­ных мо­де­лей (напр., ал­геб­раи­че­ская гео­мет­рия), и на­обо­рот, час­то ме­то­ды, раз­ви­тые для ана­ли­за не­пре­рыв­ных мо­де­лей, ис­поль­зу­ют­ся при изу­че­нии дис­крет­ных струк­тур (напр., асим­пто­ти­че­ские ме­то­ды в тео­рии чи­сел, в пе­ре­чис­ли­тель­ных за­да­чах ком­би­на­то­ри­ки). Од­на­ко спе­ци­фи­ка мн. раз­де­лов Д. м. свя­за­на с не­об­хо­ди­мо­стью от­ка­за от та­ких фун­дам. по­ня­тий клас­сич. ма­те­ма­ти­ки, как пре­дел и не­пре­рыв­ность, в свя­зи с чем для мн. за­дач Д. м. не­ко­то­рые ме­то­ды клас­сич. ма­те­ма­ти­ки ока­зы­ва­ют­ся не­при­ме­ни­мы­ми.

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

Исторический очерк

Эле­мен­ты Д. м. воз­ник­ли в глу­бо­кой древ­но­сти; раз­ви­ва­ясь па­рал­лель­но с др. раз­де­ла­ми ма­те­ма­ти­ки, они яв­ля­лись их со­став­ной ча­стью. Ти­пич­ны­ми бы­ли за­да­чи, свя­зан­ные со свой­ст­ва­ми це­лых чи­сел, позд­нее эти за­да­чи при­ве­ли к соз­да­нию тео­рии чи­сел. При­ме­ры та­ких за­дач: оты­ска­ние ал­го­рит­мов сло­же­ния и ум­но­же­ния на­ту­раль­ных чи­сел у древ­них егип­тян, во­про­сы де­ли­мо­сти на­ту­раль­ных чи­сел и за­да­чи сум­ми­ро­ва­ния в пи­фа­го­рей­ской шко­ле, а в бо­лее позд­нее вре­мя – воп­ро­сы, свя­зан­ные с раз­ре­ши­мо­стью урав­не­ний в це­лых чис­лах. Этот этап раз­ви­тия Д. м. свя­зан с име­на­ми Дио­фан­та, Евли­да, Пифа­го­ра­ и Эрато­сфе­на­. В 17–18 вв., в осн. в свя­зи с иг­ро­вы­ми за­да­ча­ми, поя­ви­лись эле­мен­ты ком­би­на­тор­но­го ана­ли­за и дис­крет­ной тео­рии ве­ро­ят­но­стей, а в свя­зи с об­щи­ми про­бле­ма­ми тео­рии чи­сел, ал­геб­ры и гео­мет­рии в 18–19 вв. воз­ник­ли та­кие важ­ней­шие по­ня­тия ал­геб­ры, как груп­па, по­ле, коль­цо, оп­ре­де­лив­шие даль­ней­шее раз­ви­тие и со­дер­жа­ние ал­геб­ры и имев­шие, по су­ще­ст­ву, дис­крет­ную при­ро­ду. На про­тя­же­нии 17–19 вв. раз­ви­тие Д. м. свя­за­но с име­на­ми Н. Абеля­, Э. Варин­га­, У. Гамиль­то­на­, Э. Га­луа, А. Кэли­, Ж. Лаг­ран­жа, А. Лежан­дра­, П. Фер­ма, Л. Эйле­ра­. В 19–20 вв. стрем­ле­ние к стро­го­сти ма­те­ма­тич. рас­су­ж­де­ний и ана­лиз ме­то­дов ма­те­ма­ти­ки при­ве­ли к вы­де­ле­нию ещё од­но­го раз­де­ла – ма­те­ма­тич. ло­ги­ки. В это вре­мя проб­ле­ма­ми Д. м. за­ни­ма­лись Л. Брау­эр, Дж. Буль, Н. Винер­, К. Гёдель­, Д. Гиль­берт, А. Чёрч, К. Шеннон­. В со­з­да­нии рос. шко­лы Д. м. участ­во­ва­ли И. М. Вино­гра­дов­, А. Н. Колмо­го­ров­, О. Б. Лупа­нов­ и С. В. Яблон­ский­.

Современные задачи дискретной математики

В 20 в. раз­ви­тие Д. м. оп­ре­де­ля­лось гл. обр. за­про­са­ми прак­ти­ки. Воз­ник­ла но­вая нау­ка – ки­бер­не­ти­ка и её тео­ре­тич. часть – ма­те­ма­тич. ки­бер­не­ти­ка, изу­чаю­щая ма­те­ма­тич. ме­то­да­ми раз­но­об­раз­ные про­бле­мы, ко­то­рые ста­вит пе­ред ки­бер­не­ти­кой прак­тич. дея­тель­ность че­ло­ве­ка. Ма­те­ма­тич. ки­бер­не­ти­ка яв­ля­ет­ся по­став­щи­ком идей и за­дач Д. м. Так, при­клад­ные во­про­сы, тре­бую­щие боль­ших вы­чис­ле­ний, сти­му­ли­ро­ва­ли по­яв­ле­ние и раз­ви­тие чис­лен­ных ме­то­дов ре­ше­ния за­дач, что при­ве­ло к соз­да­нию вы­чис­ли­тель­ной ма­те­ма­ти­ки. Ана­лиз по­ня­тий «вы­чис­ли­мость» и «ал­го­ритм» при­вёл к соз­да­нию тео­рии ал­го­рит­мов. За­да­чи хра­не­ния, об­ра­бот­ки и пе­ре­да­чи ин­фор­ма­ции спо­соб­ст­во­ва­ли воз­ник­но­ве­нию ин­фор­ма­ции тео­рии, тео­рии ко­ди­ро­ва­ния и тео­ре­тич. крип­то­гра­фии. Эко­но­мич. за­да­чи, за­да­чи элек­тро­тех­ни­ки, рав­но как и внут­рен­ние про­бле­мы ма­те­ма­ти­ки, по­тре­бо­ва­ли раз­ви­тия тео­рии гра­фов. За­да­чи опи­са­ния ра­бо­ты и кон­ст­руи­ро­ва­ния слож­ных управ­ляю­щих сис­тем со­ста­ви­ли пред­мет тео­рии управ­ляю­щих сис­тем и тео­рии ав­то­ма­тов.

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

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

Дискретная математика — это… Что такое Дискретная математика?

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

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

Разделы дискретной математики

Примечания

Литература

• Андерсон Джеймс. Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8
• Белоусов А. И., Ткачев С. Б. Дискретная математика. Серия: Математика в техническом университете. Изд-во: МГТУ им. Н. Э. Баумана, 2001.- 744 с. ISBN 5-7038-1769-2, 5-7038-1270-4
• Виленкин Н. Я. Комбинаторика. — М., 1969.
• Ерусалимский Я. М. Дискретная математика. — М., 2000.
• Иванов Б. Н. Дискретная математика. Алгоритмы и программы. Издательство: Физматлит, 2007. — 408 с. ISBN 978-5-9221-0787-7
• Капитонова Ю. В., Кривой С. Л., Летичевский А. А., Луцкий Г. М. Лекции по дискретной математике. — СПб.: БХВ-Петербург, 2004. — С. 624. — ISBN 5-94157-546-7
• Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. — М., 1963. — С. 486.
• МЭС (1995), — М., БРЭ.
• Новиков Ф.А. Дискретная математика для программистов. — 2-е изд. — СПб.: «Питер», 2005. — С. 364. — ISBN 5-94723-741-5
• Редькин Н. П. Дискретная математика. Издательство: Лань, 2006. — 96 с. ISBN 5-8114-0522-7

• Романовский И. В. Дискретный анализ. — 4-е изд. — СПб.: Невский Диалект; БХВ-Петербург, 2008. — С. 336.
• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1979. — С. 272.

См. также

Ссылки

Дискретный — это… Что такое Дискретный?

ДИСКРЕТНЫЙ АНАЛИЗ — это… Что такое ДИСКРЕТНЫЙ АНАЛИЗ?

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

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

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

Д. а. представляет собой важное направление в математике, имеющее характерные для него предмет исследования, методы и задачи, специфика к-рых обусловлена, в первую очередь, необходимостью отказа в Д. а. от основополагающих понятий классич. математики — предела и непрерывности — и (в связи с этим) тем, что для многих задач Д. а. сильные средства классич. математики оказываются, как правило, мало приемлемыми. Наряду с выделением Д. а. путем указания его предмета, методов и задач можно также охарактеризовать Д. а. посредством перечисления подразделов, составляющих его. К ним, в первую очередь, относятся комбинаторный анализ, графов теория, теория кодирования и декодирования, теория функциональных систем и нек-рые другие. Часто под термином «Д. а.» (в предположении, что его предмет исчерпывается конечными структурами) понимается именно совокупность перечисленных дисциплин. За счет расширения понимания его круга вопросов возможно и более широкое толкование Д. а. С этой точки зрения, к Д. а. могут быть отнесены также как целые разделы математики, напр, математич. логика, так и части таких разделов, как теория чисел, алгебра, вычислительная математика, теория вероятностей и некоторые другие, в к-рых изучаемый объект носит дискретный характер.

Элементы Д. а. возникли в глубокой древности и, развиваясь, параллельно с другими разделами математики, в значительной мере являлись их составной частью. Типичными для того периода были задачи, связанные со свойствами целых чисел, приведшие затем к созданию теории чисел. Позже, в основном в связи с игровыми задачами, появились элементы комбинаторного анализа и дискретной теории вероятностей, а в связи с общими проблемами теории чисел, алгебры и геометрии возникли важнейшие понятия алгебры такие, как группа, поле, кольцо и др., определившие развитие и содержание алгебры на много лет вперед и имевшие по существу дискретную природу. Стремление к строгости математич. рассуждений и анализ рабочего инструмента математики — логики — привели к выделению еще одного важного раздела математики — математич. логики. Однако наибольшего развития Д. а. достиг в связи с появлением кибернетики и ее теоретич. части — математич. кибернетики. Математич. кибернетика, непосредственно изучающая с позиций математики самые разнообразные проблемы, к-рые ставит перед кибернетикой практика, является важным поставщиком идей и задач для Д. а., вызывая в нем целые новые направления. Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление сильных численных методов решения задач, оформившихся затем в вычислительную математику, а анализ понятий вычислимости и алгоритма привел к появлению важного раздела математич. логики — алгоритмов теории. Растущий поток информации и связанные с ним задачи хранения, обработки и передачи информации привели к возникновению теории кодирования; экономич. задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов; задачи конструирования и описания работы сложных управляющих систем привели к теории функциональных систем и т. д. В то же время математич. кибернетика использует результаты Д. а. при решении своих задач. Наряду с отмеченными, Д. а. обладает рядом и других особенностей. Так, вместе с задачами типа существования, имеющими общематематич. характер, важное место в Д. а. занимают задачи, связанные с алгоритмич. разрешимостью и построением конкретных решающих алгоритмов, что характерно именно для Д. а. Особенностью Д. а. является и то, что он по существу первым столкнулся с необходимостью глубокого исследования так наз. дискретных многоэкстремальных задач, часто возникающих в математич. кибернетике. Соответствующие методы классич. математики для поиска экстремумов, существенно использующие гладкость функций, в этих случаях оказываются мало эффективными. Типичными задачами такого рода в Д. а. являются, напр., задачи об отыскании в нек-ром смысле оптимальных стратегий в шахматной партии при ограниченном числе ходов, а также важный вопрос математич. кибернетики о построении минимальных дизъюнктивных нормальных форм для булевых функций, т. е. так наз. проблема булевых функций минимизации. Особенностью Д. а., связанной уже с задачами для конечных структур, является и то, что для многих из этих задач, как правило, существует алгоритм решения, в то время как в классич. математике полное решение задачи часто возможно лишь при весьма жестких ограничениях. Примером такого алгоритма может служить алгоритм просмотра всех возможных вариантов, т. е. алгоритм типа «полного перебора». К числу задач указанного вида можно отнести, напр., упомянутые задачи о стратегиях в шахматной партии, о минимизации булевых функций и др. Вместо с тем решения типа «полного перебора» очень трудоемки и практически мало приемлемы, в связи с чем возникает ряд новых задач, связанных с условиями, ограничивающими перебор и приводящими к сведению индивидуальных задач, характеризующихся конкретными значениями параметров, к массовой проблеме, характеризующейся бесконечным множеством значений параметров; возникают задачи наложения ограничений на средства решения, естественных для этого класса задач, и др. Постановка такого рода вопросов и разработка методик осуществляется на конкретных моделях, доставляемых различными разделами математики, напр, на моделях минимизации булевых функций н синтеза управляющих систем из математич. кибернетики.

Лит.:[1] Яблонский С. В., Обзор некоторых результатов в области дискретной математики, «Информационные материалы», 1970, 5, с. 5 -15; [2] Кемеви Дж., Снелл Дж., Томпсон Дж., Введение в конечную математику, пер. с англ., 2 изд., М., 1965. См. сб. «Проблемы кибернетики» и «Дискретный анализ», ж. «Кибернетика».

В. Б. Кудрявцев.

Математическая энциклопедия. — М.: Советская энциклопедия.
И. М. Виноградов.
1977—1985.

Дискретность в биологии — это что такое? Примеры дискретности

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

Понятие дискретности

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

Важное свойство живых организмов

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

Дискретность и целостность в биологии

Такие свойства живых организмов, как дискретность и целостность, являются противоположными и в то же время взаимодополняющими понятиями, двумя сторонами одной медали. Дискретность в биологии — это что? Целостностью называют структурно-функциональное единство биосистем, обособленные составляющие которых представляют собой единое целое. Мир живой природы является целостным и дискретным одновременно. И с этими свойствами связаны различные уровни организации органики.

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

• молекулярно-генетический;
• организменный;
• популяционно-видовой;
• биогеоценотический.

Закон дискретности и непрерывности биологической информации

Согласно закону Моргана—Эфрусси деление на гены, хромосомы, молекулы, белки, а также отдельные рефлексы нервной деятельности выражают прерывность биологической информации. А ее целостность не сводится к простому сложению всех составляющих, так как информационное определение, развитие и функционирование живого организма являются сложными и многоступенчатыми процессами, которые осуществляются на генном, геномном и надгеномном уровнях. Что такое дискретность как общее свойство живого в биологии? На генном и молекулярном уровнях изучение этого вопроса стало возможным благодаря выдвижению хромосомной теории наследственности и выяснению природы ДНК.

Дополнительная возможность для эволюции

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

Общее свойство материи

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

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

Дискретная топология — это… Что такое Дискретная топология?



Дискретная топология

Дискре́тное простра́нство в общей топологии и смежных областях математики — это пространство, в котором все точки изолированы друг от друга в некотором смысле.

Определения

Тогда называется дискре́тной ме́трикой, а всё пространство называется дискре́тным метри́ческим простра́нством.

Замечание

Топология, индуцированная дискретной метрикой, является дискретной. Обратное, вообще говоря, неверно. Метрика, не являющаяся дискретной, может порождать дискретную топологию.

Примеры

Свойства

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

См. также

Wikimedia Foundation.
2010.

• Дискретное комплексное преобразование
• Дискретное метрическое пространство

Смотреть что такое «Дискретная топология» в других словарях:

• ДИСКРЕТНАЯ ТОПОЛОГИЯ — на множестве X топология, в к рой любое множество открыто (и потому любое множество замкнуто). Д. т. в решетке всех топологий на данном множестве есть наибольший элемент. Иногда термин Д. т. понимается несколько шире: топология, в к рой… …   Математическая энциклопедия

• Дискретная математика — Дискретная математика  область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях. К числу таких структур могут быть отнесены конечные группы, конечные графы, а… …   Википедия

• Топология — Не следует путать с топографией. У этого термина существуют и другие значения, см. Топология (значения). Лента Мёбиуса  поверхно …   Википедия

• Дискретная метрика — Дискретное пространство в общей топологии и смежных областях математики это пространство, в котором все точки изолированы друг от друга в некотором смысле. Содержание 1 Определения 2 Замечание 3 Примеры 4 Свойства …   Википедия

• Тривиальная топология — в общей топологии это топология, состоящая лишь из всего пространства и пустого множества. Логичнее, однако, называть эту топологию антидискретной, поскольку и дискретная, и антидискретная топологии обе довольно тривиальные в общеязыковом смысле… …   Википедия

• Дискетная топология — Курсив обозначает ссылку на этот словарь # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш …   Википедия

• Континуум (топология) — Курсив обозначает ссылку на этот словарь # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш …   Википедия

• Дифференциальная геометрия и топология — Дифференциальная геометрия и дифференциальная топология  два смежных раздела математики, которые изучают гладкие многообразия (обычно с дополнительными структурами). Эти два раздела математики почти неразделимы, при этом часто оба раздела… …   Википедия

• Дифференциальные геометрия и топология — Дифференциальная геометрия и дифференциальная топология  два смежных раздела математики, которые изучают гладкие многообразия (обычно с дополнительными структурами). Эти два раздела математики почти неразделимы, при этом часто оба раздела… …   Википедия

• Дифференциальная топология — Дифференциальная геометрия и дифференциальная топология  два смежных раздела математики, которые изучают гладкие многообразия (обычно с дополнительными структурами). Эти два раздела математики почти неразделимы. Они находят множество применений в …   Википедия

CS202: Дискретные структуры | Saylor Academy

• Время: 44 часа

• Бесплатный сертификат

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

Понимание терминов «однократное членство» и «дискретное членство» важно, когда вы начинаете этот курс. «Однократное членство» относится к чему-то, что сгруппировано только в одном наборе, и к системам, которые могут одновременно находиться только в одном состоянии на одном и том же иерархическом уровне. Точно так же «дискретный» относится к тому, что индивидуально отдельное и отличное.Каждое из чего угодно может быть только в одном наборе или в одном состоянии одновременно. Это результат аристотелевской философии, согласно которой существует только два значения принадлежности: 0 или 1. Ответ — либо нет, либо да, ложь или истина, 0% членство или 100% членство, полностью в наборе или состоянии, или совсем нет. Нет оттенков серого. Это сильно отличается от нечеткой логики (из-за Лофти Заде), где что-то может быть членом любого набора или в любом состоянии в той или иной степени. Степень членства измеряется в процентах, и эти проценты складываются в 100%.Но даже в нечеткой логике (множественное членство, множественное состояние, недискретная логика) в конечном итоге приходит к четкому решению, нужно ли предпринять какое-то конкретное действие или нет. Для этого курса достаточно понять разницу между логикой с одним и несколькими состояниями.

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

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

.

Дискретные конструкции | Статья о дискретных структурах от The Free Dictionary

Обычно требуется много усилий, чтобы заставить молекулярные компоненты соединиться друг с другом и сформировать дискретные структуры, такие как кольца. Последовательные дискретные структуры, генерируемые последовательным алгоритмом из случайного ввода, составляют цепь Маркова, которая может демонстрировать долгосрочную зависимость от ее Первые несколько входных значений. Предварительные условия эквивалентны курсам бакалавриата по теории множеств, абстрактной алгебре или дискретным структурам, но текст содержит все остальные необходимые математические основы.Для аспирантов или студентов старших курсов математики, которые закончили начальный курс дискретной математики или теории графов, Браун (математика, Далхаузи У.) вводит ряд дискретных структур, с которыми большинство аспирантов в области комбинаторики редко сталкиваются. , изучение распространения волн и их применение в физически заранее определенных, по своей сути дискретных структурах (а не дискретных непрерывных структурах) приобретает все большее значение, поскольку эти типы структур / сетей предлагают широкий диапазон — e.g., синтез новых материалов — в рамках метаматериалов. В этой книге представлены методы решения задач счета и других задач, связанных с дискретными структурами. На примерах, задачах, теоремах и доказательствах Эриксон (математика, Государственный университет Трумэна) иллюстрирует связь дискретных структур с алгеброй, геометрией, теорией чисел и комбинаторикой и призван объединить исследовательские проекты ученых из России, Кыргызстана, Казахстана и других стран. Узбекистан через обмен опытом и передачу знаний молодым ученым.Международная школа-семинар состоит из нескольких разделов: инженерные сети, автоматизация производства, оптимизация дискретных структур, транспортных и других технических систем. Для этого потребуются глобальные силовые агрегаты и уникальные приложения и опции, общие электронные архитектуры и отличительные системы plug-and-play, и комбинируемые компоненты, которые можно комбинировать для создания дискретных структур. Существует некоторый прецедент для индуцированного вибрацией образования долгоживущих дискретных структур в материале, который обычно течет.Выявление иерархических дискретных структур в использовании пространства имеет первостепенное значение для дальнейшего структурирования пространства. Организационная структура гипоталамуса костистых зубов включает функциональные ядра в виде дискретных структур, распределенных вдоль продольной оси головного мозга в медиальной части. вентральная локализация.
.

NPTEL :: Computer Science and Engineering

9000OG3

000 PDF недоступен

000

0003

0003

170004 16

Закрытие

104 Отношения эквивалентности

0 9000 Pdf

Создание функций

000

000

000

PDF недоступен

04

04

.

Определение множества DM — это исследование дискретных структур. Фундаментальная дискретная структура, на которой построено большинство других дискретных структур, — это множества.

Презентация на тему: «Определение множества DM — это исследование дискретных структур. Фундаментальная дискретная структура, на которой построено большинство других дискретных структур, — это множества». — Стенограмма презентации:

1

Определение множества DM — это изучение дискретных структур.Фундаментальная дискретная структура, на которой построено большинство других дискретных структур, — это множества. Неупорядоченный набор объектов называется набором. Объекты в наборе также называются элементами или членами набора. Есть несколько способов описать набор. Один из способов — по возможности перечислить всех членов набора. У нас есть обозначение для перечисления элементов набора, заключенных в фигурные скобки и отделенных друг от друга запятой. Заглавные буквы используются для именования наборов. Примеры: –Множество всех гласных английского языка V = {a, e, i, o, u}.–Множество O всех нечетных натуральных чисел меньше 10, O = {1,3,5,7,9}. –Множество S всех натуральных чисел меньше 100, S = {1,2,3,… ..99}.

2

Обозначения наборов Хотя наборы обычно используются для группировки элементов с общими свойствами, ничто не мешает набору иметь явно несвязанные элементы. Например; V = {a, 2, Fred, New Jersey} — это набор, содержащий четыре элемента a, 2, Fred и New Jersey.Иногда фигурные скобки используются для описания множества без перечисления всех его элементов. В этом случае перечисляются только некоторые элементы, а затем используются многоточия, то есть (…), для обозначения общего шаблона элементов, которые включены в набор. Например; множество натуральных чисел меньше 100 можно обозначить как {1, 2, 3,…, 99}. Набор целых чисел может быть представлен как {0, 1, 2, 3,…}. Для набора элементов, которых бесконечно много как в порядке убывания, так и в порядке возрастания, эллипсы могут использоваться по обе стороны от нескольких перечисленных элементов.Например; множество всех целых чисел можно обозначить в виде множества Z = {…, -2, -1, 0, 1, 2,…}.

3

Нотация построителя множеств Нотация построителя множеств; это еще один способ описания множеств. Вместо того, чтобы перечислять, мы характеризуем все элементы в наборе, указывая свойство или свойства, которые они разделяют. Например; Множество O всех положительных нечетных целых чисел меньше десяти можно записать как O = {x | x — нечетное положительное целое число меньше десяти}.Обозначения Конструктора наборов становятся удобными при описании наборов, которые имеют бесконечно большие элементы и не могут быть перечислены. Например; множество всех действительных чисел можно обозначить как R = {x | x — действительное число}. Аналогично множество всех рациональных чисел можно представить как Q = {p / q | p  Z, q  Z  q ≠ 0}.

4

Равные множества Равные множества; Иногда математически важно утверждать, что два по-разному заданных набора объектов действительно являются одним и тем же набором или иначе.Таким образом, важно понимать, что означает равенство двух наборов. Два набора равны тогда и только тогда, когда они имеют одинаковые элементы. Например; set {1, 3, 5} и set {3, 5, 1} равны, так как имеют одинаковые элементы 1, 2 и 3. Примечание; что порядок, в котором перечислены элементы набора, не имеет значения. Также НЕ имеет значения, если элемент набора указан более одного раза. Например; два набора {1, 3, 3, 3, 5, 5, 5, 5} и {1, 3, 5} равны, поскольку имеют одинаковые элементы.

5

Диаграммы Венна Диаграммы Венна; предоставить другой способ графического представления наборов.На диаграммах Венна «Универсальный набор U», который содержит все рассматриваемые объекты, представлен прямоугольником. Внутри этого прямоугольника нарисованы круги, представляющие множества. Иногда точки также используются для обозначения определенного элемента набора. Например; чтобы нарисовать диаграмму Венна, представляющую V, набор гласных в английском алфавите, мы сначала рисуем прямоугольник, чтобы указать универсальный набор U, который представляет собой набор из 26 букв английского алфавита. Внутри этого прямоугольника мы рисуем круг, представляющий набор V ( набор гласных).Внутри этого круга мы обозначаем элементы V точками. Принято использовать заглавные буквы для обозначения множеств и строчные буквы для обозначения элементов множества.

6

Диаграмма Венна для набора гласных

.

No related posts.

Share :

Добавить комментарий Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Комментарий *

Имя *

Email *

Сайт