Викиконспекты - Вклад участника [ru]

LAN - особенности топологии

2016-12-12T11:47:09Z

Baba beda: /* LAN */ интервики в WAN

==Введение==
===LAN===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в несколько километров (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. 
Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). 
'''Основные характеристики LAN''':
* высокая скорость передачи данных
* большая пропускная способность
* низкий уровень ошибок передачи
* использование качественных и хорошо защищенных линий связи (с ростом числа компьютеров стоимость может значительно увеличиться, поэтому LAN обычно содержат до нескольких десятков узлов)
* эффективный механизм управления обменом по сети
* заранее ограниченное количество компьютеров 
[[WAN - особенности, принципы построения сетей | WAN]], в отличие от LAN, рассчитаны на неограниченное число абонентов, соответственно при конфигурации сети могут быть использованы не слишком качественные каналы связи, отсюда повышение числа ошибок и снижение пропускной способности. В [[WAN - особенности, принципы построения сетей | WAN]] скорость передачи данных может быть значительно ниже, а механизм управления обменом не может быть достаточно эффективным, так как заранее не известно количество подключенных компьютеров. В целом, в [[WAN - особенности, принципы построения сетей | WAN]] гораздо важнее не качество связи, а сам факт ее существования.

===Топология сети===
'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif|right]]
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограничение длины кабеля и количества рабочих станций, связанное с затуханием сигнала
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif|right]]
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена одним или двумя кабелями с центральным элементом, тип которого зависит от типа данной звезды. В топологии '''активная звезда''' центральным элементом является компьютер, по мощности значительно превыщающий периферийные. В топологии '''пассивная звезда''' в центре находится '''концентратор''' или '''хаб'''. Концентратор обеспечивает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. Пассивная звезда распространена гораздо шире, чем активная. 
Данные от передающей станции отправляются через центральную всем остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
Одним из способов расширения данной сети является замена периферийного компьютера на центральный, к которому в последствие могут быть подключены новые периферийные. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов и кабелей, так как каждый кабель соединяет только узел с хабом
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля
* ограничение числа узлов, связанное с пропускной способностью хаба 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet. 
Так как данные передаются от каждого компьютера к каждому, физическая топология "звезда" соответствует логической топологии "шина".

===Кольцо===
[[Файл:Topologies-ring.gif|right]]
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* простота подключения нового узла (за исключением того, что необходимо останавливать всю сеть на время подключения)
* низкий расход кабеля
* простота настройки и конфигурации
* утойчивость к перегрузкам и большим потокам информации
* малое количество коллизий
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации. Например, станции соединяются двумя параллельными линиями связи, передающими информацию в противоположных направлениях. Так увеличивается скорость передачи и устойчивость сети.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif|right]]
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов 
Логическая топология данной сети - классическая шина.

===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif|right]]
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов 
Логическая топология данной сети - классическое кольцо.
[[Категория:Компьютерные сети]]
=Источники=
* [https://en.wikipedia.org/wiki/Network_topology Network topology]
* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D0%B0%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%8F Сетевая топология]
* [http://www.firewall.cx/networking-topics/general-networking/103-network-topologies.html LAN Network Topologies]
* [http://www.intuit.ru/studies/courses/57/57/lecture/1672?page=1 Определение локальных сетей и их топология]
* [https://en.wikipedia.org/wiki/Local_area_network Local area network]

LAN - особенности топологии

2016-12-12T11:43:23Z

Baba beda: /* LAN */ добавлено краткое сравнение с WAN

==Введение==
===LAN===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в несколько километров (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. 
Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). 
'''Основные характеристики LAN''':
* высокая скорость передачи данных
* большая пропускная способность
* низкий уровень ошибок передачи
* использование качественных и хорошо защищенных линий связи (с ростом числа компьютеров стоимость может значительно увеличиться, поэтому LAN обычно содержат до нескольких десятков узлов)
* эффективный механизм управления обменом по сети
* заранее ограниченное количество компьютеров 
WAN, в отличие от LAN, рассчитаны на неограниченное число абонентов, соответственно при конфигурации сети могут быть использованы не слишком качественные каналы связи, отсюда повышение числа ошибок и снижение пропускной способности. В WAN скорость передачи данных может быть значительно ниже, а механизм управления обменом не может быть достаточно эффективным, так как заранее не известно количество подключенных компьютеров. В целом, в WAN гораздо важнее не качество связи, а сам факт ее существования.

===Топология сети===
'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif|right]]
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограничение длины кабеля и количества рабочих станций, связанное с затуханием сигнала
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif|right]]
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена одним или двумя кабелями с центральным элементом, тип которого зависит от типа данной звезды. В топологии '''активная звезда''' центральным элементом является компьютер, по мощности значительно превыщающий периферийные. В топологии '''пассивная звезда''' в центре находится '''концентратор''' или '''хаб'''. Концентратор обеспечивает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. Пассивная звезда распространена гораздо шире, чем активная. 
Данные от передающей станции отправляются через центральную всем остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
Одним из способов расширения данной сети является замена периферийного компьютера на центральный, к которому в последствие могут быть подключены новые периферийные. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов и кабелей, так как каждый кабель соединяет только узел с хабом
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля
* ограничение числа узлов, связанное с пропускной способностью хаба 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet. 
Так как данные передаются от каждого компьютера к каждому, физическая топология "звезда" соответствует логической топологии "шина".

===Кольцо===
[[Файл:Topologies-ring.gif|right]]
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* простота подключения нового узла (за исключением того, что необходимо останавливать всю сеть на время подключения)
* низкий расход кабеля
* простота настройки и конфигурации
* утойчивость к перегрузкам и большим потокам информации
* малое количество коллизий
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации. Например, станции соединяются двумя параллельными линиями связи, передающими информацию в противоположных направлениях. Так увеличивается скорость передачи и устойчивость сети.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif|right]]
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов 
Логическая топология данной сети - классическая шина.

===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif|right]]
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов 
Логическая топология данной сети - классическое кольцо.
[[Категория:Компьютерные сети]]
=Источники=
* [https://en.wikipedia.org/wiki/Network_topology Network topology]
* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D0%B0%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%8F Сетевая топология]
* [http://www.firewall.cx/networking-topics/general-networking/103-network-topologies.html LAN Network Topologies]
* [http://www.intuit.ru/studies/courses/57/57/lecture/1672?page=1 Определение локальных сетей и их топология]
* [https://en.wikipedia.org/wiki/Local_area_network Local area network]

LAN - особенности топологии

2016-12-12T00:27:59Z

Baba beda: добавлены источники

==Введение==
===LAN===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в несколько километров (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. 
Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). 
'''Основные характеристики LAN''':
* высокая скорость передачи данных
* большая пропускная способность
* низкий уровень ошибок передачи
* использование качественных и хорошо защищенных линий связи (с ростом числа компьютеров стоимость может значительно увеличиться, поэтому LAN обычно содержат до нескольких десятков узлов)
* эффективный механизм управления обменом по сети
* заранее ограниченное количество компьютеров
===Топология сети===
'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif|right]]
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограничение длины кабеля и количества рабочих станций, связанное с затуханием сигнала
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif|right]]
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена одним или двумя кабелями с центральным элементом, тип которого зависит от типа данной звезды. В топологии '''активная звезда''' центральным элементом является компьютер, по мощности значительно превыщающий периферийные. В топологии '''пассивная звезда''' в центре находится '''концентратор''' или '''хаб'''. Концентратор обеспечивает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. Пассивная звезда распространена гораздо шире, чем активная. 
Данные от передающей станции отправляются через центральную всем остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
Одним из способов расширения данной сети является замена периферийного компьютера на центральный, к которому в последствие могут быть подключены новые периферийные. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов и кабелей, так как каждый кабель соединяет только узел с хабом
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля
* ограничение числа узлов, связанное с пропускной способностью хаба 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet. 
Так как данные передаются от каждого компьютера к каждому, физическая топология "звезда" соответствует логической топологии "шина".

===Кольцо===
[[Файл:Topologies-ring.gif|right]]
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* простота подключения нового узла (за исключением того, что необходимо останавливать всю сеть на время подключения)
* низкий расход кабеля
* простота настройки и конфигурации
* утойчивость к перегрузкам и большим потокам информации
* малое количество коллизий
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации. Например, станции соединяются двумя параллельными линиями связи, передающими информацию в противоположных направлениях. Так увеличивается скорость передачи и устойчивость сети.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif|right]]
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов 
Логическая топология данной сети - классическая шина.

===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif|right]]
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов 
Логическая топология данной сети - классическое кольцо.
[[Категория:Компьютерные сети]]
=Источники=
* [https://en.wikipedia.org/wiki/Network_topology Network topology]
* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D0%B0%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%8F Сетевая топология]
* [http://www.firewall.cx/networking-topics/general-networking/103-network-topologies.html LAN Network Topologies]
* [http://www.intuit.ru/studies/courses/57/57/lecture/1672?page=1 Определение локальных сетей и их топология]
* [https://en.wikipedia.org/wiki/Local_area_network Local area network]

LAN - особенности топологии

2016-12-11T23:54:42Z

Baba beda: /* Звезда-Кольцо */ логический аналог

==Введение==
===LAN===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в несколько километров (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. 
Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). 
'''Основные характеристики LAN''':
* высокая скорость передачи данных
* большая пропускная способность
* низкий уровень ошибок передачи
* использование качественных и хорошо защищенных линий связи (с ростом числа компьютеров стоимость может значительно увеличиться, поэтому LAN обычно содержат до нескольких десятков узлов)
* эффективный механизм управления обменом по сети
* заранее ограниченное количество компьютеров
===Топология сети===
'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif|right]]
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограничение длины кабеля и количества рабочих станций, связанное с затуханием сигнала
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif|right]]
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена одним или двумя кабелями с центральным элементом, тип которого зависит от типа данной звезды. В топологии '''активная звезда''' центральным элементом является компьютер, по мощности значительно превыщающий периферийные. В топологии '''пассивная звезда''' в центре находится '''концентратор''' или '''хаб'''. Концентратор обеспечивает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. Пассивная звезда распространена гораздо шире, чем активная. 
Данные от передающей станции отправляются через центральную всем остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
Одним из способов расширения данной сети является замена периферийного компьютера на центральный, к которому в последствие могут быть подключены новые периферийные. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов и кабелей, так как каждый кабель соединяет только узел с хабом
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля
* ограничение числа узлов, связанное с пропускной способностью хаба 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet. 
Так как данные передаются от каждого компьютера к каждому, физическая топология "звезда" соответствует логической топологии "шина".

===Кольцо===
[[Файл:Topologies-ring.gif|right]]
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* простота подключения нового узла (за исключением того, что необходимо останавливать всю сеть на время подключения)
* низкий расход кабеля
* простота настройки и конфигурации
* утойчивость к перегрузкам и большим потокам информации
* малое количество коллизий
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации. Например, станции соединяются двумя параллельными линиями связи, передающими информацию в противоположных направлениях. Так увеличивается скорость передачи и устойчивость сети.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif|right]]
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов 
Логическая топология данной сети - классическая шина.

===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif|right]]
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов 
Логическая топология данной сети - классическое кольцо.
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T23:54:08Z

Baba beda: /* Звезда-Шина */ логический аналог

==Введение==
===LAN===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в несколько километров (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. 
Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). 
'''Основные характеристики LAN''':
* высокая скорость передачи данных
* большая пропускная способность
* низкий уровень ошибок передачи
* использование качественных и хорошо защищенных линий связи (с ростом числа компьютеров стоимость может значительно увеличиться, поэтому LAN обычно содержат до нескольких десятков узлов)
* эффективный механизм управления обменом по сети
* заранее ограниченное количество компьютеров
===Топология сети===
'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif|right]]
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограничение длины кабеля и количества рабочих станций, связанное с затуханием сигнала
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif|right]]
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена одним или двумя кабелями с центральным элементом, тип которого зависит от типа данной звезды. В топологии '''активная звезда''' центральным элементом является компьютер, по мощности значительно превыщающий периферийные. В топологии '''пассивная звезда''' в центре находится '''концентратор''' или '''хаб'''. Концентратор обеспечивает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. Пассивная звезда распространена гораздо шире, чем активная. 
Данные от передающей станции отправляются через центральную всем остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
Одним из способов расширения данной сети является замена периферийного компьютера на центральный, к которому в последствие могут быть подключены новые периферийные. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов и кабелей, так как каждый кабель соединяет только узел с хабом
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля
* ограничение числа узлов, связанное с пропускной способностью хаба 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet. 
Так как данные передаются от каждого компьютера к каждому, физическая топология "звезда" соответствует логической топологии "шина".

===Кольцо===
[[Файл:Topologies-ring.gif|right]]
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* простота подключения нового узла (за исключением того, что необходимо останавливать всю сеть на время подключения)
* низкий расход кабеля
* простота настройки и конфигурации
* утойчивость к перегрузкам и большим потокам информации
* малое количество коллизий
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации. Например, станции соединяются двумя параллельными линиями связи, передающими информацию в противоположных направлениях. Так увеличивается скорость передачи и устойчивость сети.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif|right]]
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов 
Логическая топология данной сети - классическая шина.

===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif|right]]
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T23:51:30Z

Baba beda: /* Кольцо */ уточнения и пример расширения

==Введение==
===LAN===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в несколько километров (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. 
Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). 
'''Основные характеристики LAN''':
* высокая скорость передачи данных
* большая пропускная способность
* низкий уровень ошибок передачи
* использование качественных и хорошо защищенных линий связи (с ростом числа компьютеров стоимость может значительно увеличиться, поэтому LAN обычно содержат до нескольких десятков узлов)
* эффективный механизм управления обменом по сети
* заранее ограниченное количество компьютеров
===Топология сети===
'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif|right]]
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограничение длины кабеля и количества рабочих станций, связанное с затуханием сигнала
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif|right]]
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена одним или двумя кабелями с центральным элементом, тип которого зависит от типа данной звезды. В топологии '''активная звезда''' центральным элементом является компьютер, по мощности значительно превыщающий периферийные. В топологии '''пассивная звезда''' в центре находится '''концентратор''' или '''хаб'''. Концентратор обеспечивает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. Пассивная звезда распространена гораздо шире, чем активная. 
Данные от передающей станции отправляются через центральную всем остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
Одним из способов расширения данной сети является замена периферийного компьютера на центральный, к которому в последствие могут быть подключены новые периферийные. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов и кабелей, так как каждый кабель соединяет только узел с хабом
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля
* ограничение числа узлов, связанное с пропускной способностью хаба 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet. 
Так как данные передаются от каждого компьютера к каждому, физическая топология "звезда" соответствует логической топологии "шина".

===Кольцо===
[[Файл:Topologies-ring.gif|right]]
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* простота подключения нового узла (за исключением того, что необходимо останавливать всю сеть на время подключения)
* низкий расход кабеля
* простота настройки и конфигурации
* утойчивость к перегрузкам и большим потокам информации
* малое количество коллизий
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации. Например, станции соединяются двумя параллельными линиями связи, передающими информацию в противоположных направлениях. Так увеличивается скорость передачи и устойчивость сети.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif|right]]
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif|right]]
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T23:45:34Z

Baba beda: /* Звезда */ добавлена информация про активную и пассивную звезду

==Введение==
===LAN===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в несколько километров (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. 
Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). 
'''Основные характеристики LAN''':
* высокая скорость передачи данных
* большая пропускная способность
* низкий уровень ошибок передачи
* использование качественных и хорошо защищенных линий связи (с ростом числа компьютеров стоимость может значительно увеличиться, поэтому LAN обычно содержат до нескольких десятков узлов)
* эффективный механизм управления обменом по сети
* заранее ограниченное количество компьютеров
===Топология сети===
'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif|right]]
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограничение длины кабеля и количества рабочих станций, связанное с затуханием сигнала
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif|right]]
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена одним или двумя кабелями с центральным элементом, тип которого зависит от типа данной звезды. В топологии '''активная звезда''' центральным элементом является компьютер, по мощности значительно превыщающий периферийные. В топологии '''пассивная звезда''' в центре находится '''концентратор''' или '''хаб'''. Концентратор обеспечивает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. Пассивная звезда распространена гораздо шире, чем активная. 
Данные от передающей станции отправляются через центральную всем остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
Одним из способов расширения данной сети является замена периферийного компьютера на центральный, к которому в последствие могут быть подключены новые периферийные. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов и кабелей, так как каждый кабель соединяет только узел с хабом
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля
* ограничение числа узлов, связанное с пропускной способностью хаба 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet. 
Так как данные передаются от каждого компьютера к каждому, физическая топология "звезда" соответствует логической топологии "шина".

===Кольцо===
[[Файл:Topologies-ring.gif|right]]
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* низкий расход кабеля
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif|right]]
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif|right]]
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T23:28:01Z

Baba beda: все картинки вправо

==Введение==
===LAN===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в несколько километров (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. 
Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). 
'''Основные характеристики LAN''':
* высокая скорость передачи данных
* большая пропускная способность
* низкий уровень ошибок передачи
* использование качественных и хорошо защищенных линий связи (с ростом числа компьютеров стоимость может значительно увеличиться, поэтому LAN обычно содержат до нескольких десятков узлов)
* эффективный механизм управления обменом по сети
* заранее ограниченное количество компьютеров
===Топология сети===
'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif|right]]
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограничение длины кабеля и количества рабочих станций, связанное с затуханием сигнала
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif|right]]
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена кабелем с '''концентратором''' или '''хабом'''. Концентратор обеспечиает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. 
Данные от передающей станции отправляются через хаб все остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet.
===Кольцо===
[[Файл:Topologies-ring.gif|right]]
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* низкий расход кабеля
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif|right]]
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif|right]]
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T23:24:24Z

Baba beda: /* Шина */ уточнение к недостатку

==Введение==
===LAN===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в несколько километров (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. 
Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). 
'''Основные характеристики LAN''':
* высокая скорость передачи данных
* большая пропускная способность
* низкий уровень ошибок передачи
* использование качественных и хорошо защищенных линий связи (с ростом числа компьютеров стоимость может значительно увеличиться, поэтому LAN обычно содержат до нескольких десятков узлов)
* эффективный механизм управления обменом по сети
* заранее ограниченное количество компьютеров
===Топология сети===
'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif]] 
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограничение длины кабеля и количества рабочих станций, связанное с затуханием сигнала
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif]] 
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена кабелем с '''концентратором''' или '''хабом'''. Концентратор обеспечиает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. 
Данные от передающей станции отправляются через хаб все остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet.
===Кольцо===
[[Файл:Topologies-ring.gif]] 
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* низкий расход кабеля
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif]] 
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif]] 
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T23:20:23Z

Baba beda: /* Введение */ добавлены характеристики LAN

==Введение==
===LAN===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в несколько километров (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. 
Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). 
'''Основные характеристики LAN''':
* высокая скорость передачи данных
* большая пропускная способность
* низкий уровень ошибок передачи
* использование качественных и хорошо защищенных линий связи (с ростом числа компьютеров стоимость может значительно увеличиться, поэтому LAN обычно содержат до нескольких десятков узлов)
* эффективный механизм управления обменом по сети
* заранее ограниченное количество компьютеров
===Топология сети===
'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif]] 
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограниченная длина кабеля и количество рабочих станций
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif]] 
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена кабелем с '''концентратором''' или '''хабом'''. Концентратор обеспечиает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. 
Данные от передающей станции отправляются через хаб все остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet.
===Кольцо===
[[Файл:Topologies-ring.gif]] 
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* низкий расход кабеля
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif]] 
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif]] 
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T23:12:10Z

Baba beda: /* Смешанные */ краткое описание смешанных топологий

==Введение==
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в 1-2 километра (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. Так, например, существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры).

'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif]] 
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограниченная длина кабеля и количество рабочих станций
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif]] 
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена кабелем с '''концентратором''' или '''хабом'''. Концентратор обеспечиает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. 
Данные от передающей станции отправляются через хаб все остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet.
===Кольцо===
[[Файл:Topologies-ring.gif]] 
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* низкий расход кабеля
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации.

==Смешанные==
Смешанной называется топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произовльно связанные фрагменты (подсети), имеющие типовую топологию.
===Звезда-Шина===
[[Файл:Topologies-hybrid-star-bus.gif]] 
Данная топология также называется "дерево". 
Как следует из названия, сеть, построенная по данной топологии, состоит из нескольких подсетей с топологией "звезда", соединенных единой шиной. 
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
===Звезда-Кольцо===
[[Файл:Topologies-hybrid-star-ring.gif]] 
Хабы нескольких подсетей с топологией "звезда" соединены единым кабелем в кольцо. При использовании метода передачи токена, все компьютеры в такой топологии имеют равные шансы отправить данные.
'''Преимущества''':
* простота расширения
* простота поиска обрывов и неисправностей
* устойчивость к неисправностям отдельных компьютеров
* высокая пропускная способность
'''Недостатки''':
* неустойчивость к неисправности шины и хабов
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T22:46:33Z

Baba beda: /* Шина */

==Введение==
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в 1-2 километра (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. Так, например, существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры).

'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif]] 
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограниченная длина кабеля и количество рабочих станций
* низкая производительность, обусловленная разделением канала между всеми абонентами
* большое количество коллизий пакетов 
На текущий момент данная топология применяется крайне редко.

===Звезда===
[[Файл:Topologies-star.gif]] 
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена кабелем с '''концентратором''' или '''хабом'''. Концентратор обеспечиает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. 
Данные от передающей станции отправляются через хаб все остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet.
===Кольцо===
[[Файл:Topologies-ring.gif]] 
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* низкий расход кабеля
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации.

==Смешанные==
===Звезда-Шина===
===Звезда-Кольцо===
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T22:42:33Z

Baba beda: /* Кольцо */ добавлена основная информация

==Введение==
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в 1-2 километра (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. Так, например, существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры).

'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

=Топологии=
==Полносвязные==
[[Файл:Topologies-mesh.gif|right]]
Полносвязной называется сеть, где каждый компьютер непосредственно связан со всеми остальными. Такая конфигурация очень громоздка и неэффективна, так как каждый компьютер должен иметь большое количество коммуникационных портов, достаточное для связи со всеми остальными. Но плюсом такой сети является устойчивость к поломке отдельных компонентов: сеть не перестанет функционировать из-за неисправности одного компьютера.

==Неполносвязные==
Существует несколько различных неполносвязных топологий. При конфигурации LAN в основном используются следующие: шина (bus), звезда/хаб (star/hub), кольцо (ring). В неполносвязных топологиях передача данных может осуществляться не напрямую между компьютерами, а через дополнительные узлы.
===Шина===
[[Файл:Topologies-bus.gif]] 
В данной топологии все рабочие стации подсоединены к общему кабелю (называемому '''магистраль''' или шина). Данные, сгенерированные на одном из компьютеров, отправляются через шину во все остальные. Чтобы сигнал не отражался обратно, на концах шины должны стоять специальные '''терминаторы''', поглощающие сигнал. 
'''Преимущества''':
* низкий расход кабеля
* устойчивость сети к неисправностям отдельных узлов
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля
* ограниченная длина кабеля и количество рабочих станций
* низкая производительность, обусловленная разделением канала между всеми абонентами 
На текущий момент данная топология применяется крайне редко.
===Звезда===
[[Файл:Topologies-star.gif]] 
В сети, построенной согласно топологии "звезда", каждая рабочая станция соединена кабелем с '''концентратором''' или '''хабом'''. Концентратор обеспечиает параллельное соединение компьютеров и, таким образом, все компьютеры, подключенные к сети, могут общаться друг с другом. 
Данные от передающей станции отправляются через хаб все остальным компьютерам, но принимаются они только теми станциями, которым они предназначались. 
'''Преимущества''':
* простота подключения нового узла
* возможность централизованного управления
* устойчивость сети к неисправностям отдельных узлов
'''Недостатки''':
* неустойчивость сети к неисправности хаба
* высокий расход кабеля 
Данная топология - одна из самых используемых в домашних и офисных сетях. Применяется в LAN с архитектурой 10Base-T Ethernet.
===Кольцо===
[[Файл:Topologies-ring.gif]] 
В данной топологии компьютеры соединены кабелем в единое кольцо: выход одного компьютера связан с входом следующего. В отличие от топологии "шина" здесь нет необходимости в терминаторах, так как сигнал идет всегда в одну сторону по кругу. Данные, отправленные одной станцией, пройдут через все другие, но будут приняты только той станцией, которой они предназначались. При этом каждый промежуточный компьютер на этом пути будет выступать усилителем сигнала. 
Метод, используемый для передачи данных в кольце, называется '''передачей токена'''. Токен - специальная последовательность бит, содержащая контрольную информацию. Станция, обладающая в данный момент токеном, может посылать данные. 
'''Преимущества''':
* низкий расход кабеля
* простота настройки и конфигурации
'''Недостатки''':
* неустойчивость сети к неисправности кабеля и неисправности рабочих станций 
Данная топология редко используется в чистом виде из-за своей ненадежности, на практике применяются ее различные модификации.

==Смешанные==
===Звезда-Шина===
===Звезда-Кольцо===
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T22:24:56Z

Baba beda: /* Топологии */ добавлены шина и звезда

Файл:Topologies-ring.gif

2016-12-11T22:24:39Z

Baba beda: загружена новая версия «Файл:Topologies-ring.gif»

Файл:Topologies-ring.gif

2016-12-11T22:24:13Z

Baba beda:

Файл:Topologies-star.gif

2016-12-11T22:14:30Z

Baba beda:

Файл:Topologies-mesh.gif

2016-12-11T21:39:26Z

Baba beda:

Файл:Topologies-hybrid-star-ring.gif

2016-12-11T21:25:53Z

Baba beda:

Файл:Topologies-hybrid-star-bus.gif

2016-12-11T21:24:36Z

Baba beda:

Файл:Topologies-bus.gif

2016-12-11T21:16:02Z

Baba beda: загружена новая версия «Файл:Topologies-bus.gif»

Файл:Topologies-bus.gif

2016-12-11T21:15:15Z

Baba beda:

LAN - особенности топологии

2016-12-11T21:05:48Z

Baba beda: минорное изменение заголовков

LAN - особенности топологии

2016-12-11T21:05:01Z

Baba beda: добавлен подраздел

===Введение===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в 1-2 километра (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. Так, например, существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры).

'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

===Топологии===
[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T21:04:20Z

Baba beda: /* Введение */ подробнее про физическую и логическую топологии

=== Введение ===
'''Local Area Network (LAN)''' - компьютерная сеть, сосредоточенная на относительно небольшой территории, ограниченной радиусом обычно в 1-2 километра (например: дом, школа, лаборатория, офис). В общем случае локальная сеть представляет собой коммуникационную систему, принадлежащую одной организации. Так, например, существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры).

'''Топология сети''' описывает конфигурацию компонентов сети и их связи. Топологическая структура сети делится на две основные категории: физическую и логическую.

* '''Физическая топология''' описывает: схему прокладки кабеля, расположение узлов и взаимосвязи между ними. Физическая топология сети определяется возможностями устройств доступа, желаемым уровнем контроля и толерантности к ошибками, а так же стоимостью всех необходимых материалов. а логическая - движение сигнала между узлами в рамках заданной физической топологии.

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

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

[[Категория:Компьютерные сети]]

LAN - особенности топологии

2016-12-11T20:34:58Z

Baba beda: базовые определения

Компьютерные сети

2016-12-11T19:38:33Z

Baba beda: /* Блок 3 */ добавлена новая тема "LAN"

=Блок 1=
* [[Коммутация на канальном уровне]]
* [[Сети с общей средой передачи данных (подуровень MAC, протоколы)]]
* [[Физическое кодирование]]
* [[Канальный уровень]]
* [[Физический уровень]]
* [[Ethernet]]
* [[Bluetooth]]
* [[Виртуальные локальные сети]]
* [[Протоколы стандарта 802.11]]
* [[Data link layer - LLC]]
* [[Data link layer - Flow control]]
* [[Data link layer - MAC - Aloha, CSMA]]

=Блок 2=
* [[Сетевой уровень]]
* [[Мультикаст. Мультикаст маршрутизация]]
* [[IP]]
* [[Управляющие протоколы Internet]]
* [[Протоколы внешнего и внутреннего шлюза]]
* [[IPv6]]
* [[Транспортный уровень]]
* [[Протоколы транспортного уровня (TCP, UDP, SCTP)]]

=Блок 3=
* [[DHCP]]
* [[Служба DNS. Пространство имен в Internet]]
* [[Служба электронной почты]]
* [[WWW. HTTP. Основы и развитие]]
* [[FTP. Telnet. SSH]]
* [[Авторизация. Аутентификация. Аудит. Radius. Diameter]]
* [[Шифрование]]
* [[SSL/TLS]]
* [[TLS. IPsec. Основы, отличия. IPv6 и шифрование]]
* [[Протоколы аутентификации]]
* [[Firewall. Концепция, примеры]]
* [[SIP. Телефония поверх IP]]
* [[Одноранговые сети]]
* [[Сетевые атаки. Классификация, описания]]
* [[Мультимедиа поверх IP. RTSP]]
* [[NAT]]
* [[LTE и WiFi]]
* [[WAN - особенности, принципы построения сетей]]
* [[Wireless networks - WAN]]
* [[LAN - особенности топологии]]

Сложностные классы

2016-03-17T20:42:06Z

Baba beda: /* Определения */ пофиксила определение НМТ

В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д.

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> {{---}} класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \leqslant f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, в которой существует пара "ленточный символ - состояние", для которой существует 2 и более команд.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]

== Источники информаии ==
* [http://ru.wikipedia.org/wiki/Класс_сложности Википедия | Класс сложности]
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.

[[Категория:Теория сложности|*]]
[[Категория:Детерминированные и недетерминированные вычисления, сложность по памяти и времени|*]]
[[Категория:Базовые определения|*]]

Сложностные классы

2016-03-17T20:30:47Z

Baba beda: more minor fixes

В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д.

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> {{---}} класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \leqslant f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]

== Источники информаии ==
* [http://ru.wikipedia.org/wiki/Класс_сложности Википедия | Класс сложности]
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.

[[Категория:Теория сложности|*]]
[[Категория:Детерминированные и недетерминированные вычисления, сложность по памяти и времени|*]]
[[Категория:Базовые определения|*]]

Сложностные классы

2016-03-17T20:27:06Z

Baba beda: a bit more fixing categories

В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д.

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> {{---}} класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]

== Источники ==
* [http://ru.wikipedia.org/wiki/Класс_сложности Википедия | Класс сложности]
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.

[[Категория:Теория сложности|*]]
[[Категория:Детерминированные и недетерминированные вычисления, сложность по памяти и времени|*]]
[[Категория:Базовые определения|*]]

Сложностные классы

2016-03-17T20:26:02Z

Baba beda: trying categories

В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д.

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> {{---}} класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]

== Источники ==
* [http://ru.wikipedia.org/wiki/Класс_сложности Википедия | Класс сложности]
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.

[[Категория: Теория сложности|*]]
[[Категория: Детерминированные и недетерминированные вычисления, сложность по памяти и времени|*]]
[[Категория: Базовые определения|*]]

Сложностные классы

2016-03-17T20:05:56Z

Baba beda: Вернула историю

В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д.

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> {{---}} класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]

== Источники ==
* [http://ru.wikipedia.org/wiki/Класс_сложности Википедия | Класс сложности]
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T22:32:44Z

Baba beda: /* Определения */

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> {{---}} класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]

== Источники ==
* [http://ru.wikipedia.org/wiki/Класс_сложности Википедия | Класс сложности]
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T22:32:07Z

Baba beda: /* Источники */

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> --- класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]

== Источники ==
* [http://ru.wikipedia.org/wiki/Класс_сложности Википедия | Класс сложности]
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T22:30:52Z

Baba beda: /* Источники */ добавлены пара источников

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> --- класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]

== Источники ==
* [https://ru.wikipedia.org/wiki/Класс_сложности Википедия | Класс сложности]
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T22:13:24Z

Baba beda: /* См. также */ 1.1.1.6 добавлены ссылки на другие статьи

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> --- класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
* [[Класс P]]
* [[Классы NP и Σ₁]]

== Литература и источники информации ==

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T22:10:01Z

Baba beda: добавлены разделы см. также и источники

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> --- класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
== Литература и источники информации ==

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T22:04:44Z

Baba beda: недетерминированная машина тьюринга -> НМТ

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> --- класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T21:58:27Z

Baba beda: 1.1.1.4 программы в определениях заменены на машины тьюринга

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> --- класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T21:35:12Z

Baba beda: 1.1.1.2 поправлен tex на переменных (теперь на всех)

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(p,x)</tex> — время работы программы <tex>p</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе <tex>p</tex> для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T21:34:22Z

Baba beda: 1.1.1.2 поправлен tex на переменных (пока не на всех, во втором определении при оборачивании x в tex все ломается)

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(p,x)</tex> — время работы программы <tex>p</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе <tex>p</tex> для выполнения на входе x.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T19:32:31Z

Baba beda: Отмена правки 52564 участника Baba beda (обсуждение)

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(p,x)</tex> — время работы программы р на входе х.
}}
{{Определение
|definition=
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе р для выполнения на входе х.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>). 
}}
{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>). 
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T19:28:22Z

Baba beda: 1.1.1.2 поправлен tex на переменных

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(p,x)</tex> — время работы программы <tex>р</tex> на входе <tex>х</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе <tex>р</tex> для выполнения на входе <tex>х</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>). 
}}
{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>). 
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

[[Категория: Теория сложности]]

Сложностные классы

2016-03-09T19:25:12Z

Baba beda: 1.1.1.1 убран пункт история

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(p,x)</tex> — время работы программы р на входе х.
}}
{{Определение
|definition=
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе р для выполнения на входе х.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>). 
}}
{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>). 
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

[[Категория: Теория сложности]]