|
Реферат: USB-порт. Flash-Память (Программирование)
О г л а в л е н и е:
Спецификация USB……………………………………………………………………………………3
Создатели……………………………………………………………………………………………….3
Работа USB……………………………………………………………………………………………..3
Виды периферийного оборудования, которые поддерживает USB………………………………...4
Программное обеспечение, которое нужно для работы USB……………………………………….4
Значение USB для поставщиков систем и периферии………………………………………………4
Применение USB при наличие двух систем, например ноутбука и настольного
компьютера…..5
Возможность увеличения длины соединения устройств через шину USB до 50-200
метров (например, используя оптоволокно)………………………………………………………………….6
Разница между соединителями серии "A" и "B"…………………………………………………….6
Разница между основным хабом и обычным с точки зрения аппаратной реализации
и программного обеспечения……………………………………………………………………………7
Технология USB 2.0……………………………………………………………………………………7
Флэш-память……………………………………………………………………………………………25
Compact Flash…………………………………………………………………………………………...26
SmartMedia………………………………………………………………...……………………………27
MultiMediaCard…………………………………………………………………………………………27
Secure Digital……………………………………………………………………………………………28
Memory Stick……………………………………………………………………………………………28
Считыватели……………………………………………………………………………………………29
Внешние считыватели …………………………………………………………………………………29
Внутренние считыватели………………………………………………………………………………30
Считыватели – переходники………………………………………………………………….30
Список использованных материалов………………………………………………………...31
Спецификация USB.
Спецификация периферийной шины USB разработана лидерами компьютерной и
телекоммуникационной промышленности -- Compaq, DEC, IBM, Intel, Microsoft,
NEC и Northern Telecom -- для подключения компьютерной периферии вне
корпуса машины по стандарту plug'n'play, в результате отпадает
необходимость в установке дополнительных плат в слоты расширения и
переконфигурировании системы. Персональные компьютеры, имеющие шину USB,
позволяют подключать периферийные устройства и осуществляют их
автоматическое конфигурирование, как только устройство физически будет
присоединено к машине, и при этом нет необходимость перезагружать или
выключать компьютер, а так же запускать программы установки и
конфигурирования. Шина USB позволяет одновременно подключать
последовательно до 127 устройств, таких, как мониторы или клавиатуры,
выполняющие роль дополнительно подключенных компонентов, или хабов (т.е.
устройство, через которое подключается еще несколько).
Создатели.
USB была разработана группой из семи компаний, которые видели необходимость
во взаимодействии для обеспечения дальнейшего роста и развития расцветающей
индустрии интегрированных компьютеров и телефонии. Эти семь компаний,
продвигающие USB, следующие: Compaq, Digital Equipment Corp, IBM PC Co.,
Intel, Microsoft, NEC и Northern Telecom.
Работа USB.
USB определяет, добавлено устройство или отключено, благодаря своей
разумности, обеспечиваемой основной системой. Шина автоматически
определяет, какой системный ресурс, включая программный драйвер и
пропускную способность, нужен каждому периферийному устройству и делает
этот ресурс доступным без вмешательства пользователя. Владельцы
компьютеров, оснащенных шиной USB имеют возможность переключать совместимые
периферийные устройства, так же просто, как они вкручивают новую лампочку в
лампу.
Виды периферийного оборудования, которые поддерживает USB.
Вы знаете эти устройства: телефоны, модемы, клавиатуры, мыши, устройства
чтения CD ROM, джойстики, ленточные и дисковые накопители, сканеры и
принтеры, MP3-плееры и флаш-драйвы. Скорость прокачки в 480 мегабит/секунду
позволяет подключать через USB все современное поколение периферийных
устройств, включая аппаратуру для обработки видео данных формата MPEG-2,
перчатки для управления виртуальными объектами и дигитайзеры. Также, с
ожиданием большого роста в области интеграции компьютеров и телефонии, шина
USB может выступать в качестве интерфейса для подключения устройств
Цифровой сети с интегрированными услугами (ISDN) и цифровых устройств
Private Branch eXchange (PBX), позволяющих подключать большое количество
телефонов к небольшому количеству линий связи.
Программное обеспечение, которое нужно для работы USB.
Операционная система Windows 95 (начиная с версии OSR 2.1, выпущенной 29
октября 1996г.) поставляется уже со встроенными драйверами, которые
позволяет Вашему персональному компьютеру распознавать USB периферию. В
результате, Вам не нужно покупать или инсталлировать дополнительное
программное обеспеченье для каждого нового периферийного устройства. Тем не
менее, вместе с новой USB периферией вы получите дискету с новыми
драйверами. Однако, не все так радужно - например, корректную работу
принтера с интерфейсом USB способна обеспечить только OC Windows 98 и выше.
Значение USB для поставщиков систем и периферии.
Совместимость USB строится на основе технологически целостной и открытой
спецификации, которая удовлетворяет потребностям потребителей в легко
расширяемых компьютерах. В свою очередь, для поставщиков и реселлеров
компьютеров, периферии и программного обеспечения, совместимость USB
принесет прибыль, за счет использования новых методов маркетинга:
. "Готовая платформа" позволяет логично связать аппаратное и
программное обеспечение для совместной поставки покупателю.
. USB может снизить риск возможной несовместимости периферийного и
программного обеспечения, поставляемого с компьютерами, за счет
поставки готовых систем по ключ, которые удовлетворяют
требованиям специализированных рыночных ниш.
. USB-совместимая периферия может предложить частным и
корпоративным покупателям больший выбор оборудования, без страха
снижения функциональных возможностей аппаратных средств.
. Реселлеры получают большую гибкость в подборе аппаратуры и
готовых систем, для стимуляции покупательского спроса, за счет
возможности комбинирования комплектов поставляемой периферии,
без опасений, что что-то с чем-то не будет работать в паре.
. USB может обеспечить поставщикам периферии дополнительную
выгоду, за счет поставки нового оборудования для систем,
использующих технологию MMX™.
. USB может помочь поставщикам снизить их затраты на разработки,
что в свою очередь позволит им устанавливать новые, более
конкурентоспособные, цены.
Применение USB при наличие двух систем, например ноутбука и настольного
компьютера.
Применение маленького адаптера, который будет определен в качестве
устройства для каждой USB системы, которая входит в соединение. Два USB
контроллера периферии с общим буфером памяти будет наиболее оптимальным
решением, стоимость которого не должна превысить $50. Корпус адаптера может
выглядеть, как маленькая капля в середине кабеля или, может быть, небольшое
утолщение, расположенное на одном из его концов. Кабель, подобный
описанному, сможет выполнять так же и функции хаба, всего лишь за небольшую
дополнительную плату, а это уже гораздо более ценный продукт.
Возможность увеличения длины соединения устройств через шину USB до 50-200
метров (например, используя оптоволокно).
Периферийный интерфейс USB предназначен для настольных систем, а расстояние
в 200 метров, похоже, соответствует очень большему столу. Многие компании,
входящие в сообщество внедрения USB, уже долгое время обсуждают проблему
применения шины на больших расстояниях и думают о создании продуктов,
которые позволили бы сделать это возможным. Устройство расширения выглядит
как два хаба для шины USB, однако использует другие протоколы (например,
для оптоволокна) между точками соединения кабеля. На каждом конце
электрический сигнал в USB должен быть транслирован в или из сигнала для
длинных расстояний. Для того, что бы все это стало возможным, необходимо
решить вопросы, связанные с протоколом передачи пакетов данных и временными
задержками, которые должны быть совместимы и соответствовать спецификации
USB.
Разница между соединителями серии "A" и "B".
Коннекторы серии "A" разработаны для всех устройств USB, и являются
разъемом для периферии и гнездом для персонального компьютера. В
большинстве случаев, кабель USB должен быть встроен в периферийное
устройство. Это снижает стоимость соединителей, избавляет от
несовместимости, возможной в случае разного сопротивления кабелей, и
упрощает действия пользователей по подключению. Однако в некоторых случаях
встроенный кабель нельзя использовать. Хорошим примером могут служить очень
большие и тяжелые устройства, плохо сочетатающиеся с тонким кабелем,
который нельзя удалить, а так же устройства, подключаемые только изредка,
которые интенсивно используются, когда не являются подключенными. Для таких
случаев и были созданы коннекторы серии "B". Две серии коннекторов
различаются внешне, это сделано для предотвращения соединений, которые бы
могли нарушить топологию архитектуры USB.
Разница между основным хабом и обычным с точки зрения аппаратной реализации
и программного обеспечения.
Все хабы совершенно одинаковы с точки зрения программного обеспечения
(кроме разницы, как устройств имеющих питание и нет). Основной хаб (или
корневой), это просто первый хаб, обнаруженный при нумерации. Во многих
реализациях основной хаб может быть интегрирован в ту же микросхему, что и
основной контроллер, это позволяет снизить стоимость.
Технология USB 2.0
Следующий год, по прогнозам аналитиков, должен стать переломным в пользу
нового (относительно) USB 2.0. А ведь многие еще и с первым-то незнакомы.
Скорости с которой производители "компьютерных железяк" разрождаются новыми
творениями можно только удивляться.
Бедняжка пользователь в таком огромном потоке высокотехнологичных устройств
часто теряется, и многие технологии остаются за гранью его внимания. Так
вот и шина USB, какой бы новой многим она ни казалась, - технология в
возрасте. Десятилетний юбилей не за горами. Жизнь ее началась в далеком
1995 году, когда многие компании, стремясь следовать провозглашенному
принципу Plug'n'Play стремились создать нечто, позволяющее сделать
процедуру добавления новых устройств в систему настолько простой, насколько
это вообще возможно, да и к тому же универсальное, пригодное для большого
числа разного вида устройств. Эта идея объединила лидеров компьютерной и
телекоммуникационной промышленности в лицах Compaq, DEC, IBM, Intel,
Microsoft, NEC и Northern Telecom. Мы же простые пользователи, с трепетом
ожидали окончания разработок.
Ведь если новая технология действительно будет работать, то это позволит
забыть о проблеме постоянной нехватки коммуникационных портов, с которой в
те годы благодаря значительно увеличившейся доступности периферии многим
уже довелось столкнуться.
Что ж. Их мучения не прошли даром. И хотя поначалу внедрение шло с очень
большим скрипом, сегодня сотни миллионов компьютеров по всему миру оснащены
шиной USB, а периферийных устройств с этим интерфейсов всех не перечесть:
от мышек и клавиатур до жестких дисков, приводов для записи CD и DVD и др.
Причиной скрипа при внедрении был замкнутый круг: естественно, что новая
шина должна была поддерживаться операционной системой, а Windows 95 этим
похвастаться не могла. Microsoft не горела желанием работать не пойми для
чего - устройства с USB интерфейсом можно было пересчитать едва ли не на
пальцах, а в производители аппаратного обеспечения в свою очередь не хотели
делать устройства для не поддерживающейся популярной ОС шины.
Выход обновлений OSR2.1 не сильно изменил ситуацию, так как сделано все
было в нем через пень-колоду (кстати, а в NT системах она так и не
появилась. до Windows 2000). Основная поддержка была со стороны компаний
производителей систем и системных компонентов - для них это было источником
прибыли (по данным аналитиков Dataquest объем продаж систем с USB должен
был составить в 1997 году 30 млн штук и в 1998 все продаваемые компьютеры
должны были быть оснащены этой шиной (возможно так и было, но не у нас:-
))), и, потом, товарищи верили, что взойдет она, звезда пленительного
счастья.
Пусть не сегодня, завтра, но взойдет. Так и случилось. Переломным моментом
в истории USB стал выход Windows 98: появилась поддержка, начался выпуск
устройств, и технология начала свое существование не только у
разработчиков, но и у пользователей, кстати, многие из которых относят
появление именно к этому моменту.
Сегодня USB - это очень популярная универсальная последовательная шина.
Предназначена для легкого подключения различного вида устройств это
клавиатуры, мыши, джойстики, колонки, модемы, мобильные телефоны,
ленточные, дисковые, оптические и магнитооптические накопители, флэш-диски,
сканеры и принтеры, дигитайзеры, словом все, что подключается к ПК. Также,
с ожиданием большого роста в области интеграции компьютеров и телефонии,
шина USB может выступать в качестве интерфейса для подключения устройств
цифровой сети с интегрированными услугами (ISDN) и цифровых устройств
Private Branch eXchange (PBX).
Пропускной способности в 480 Мбит/с в версии 2.0 достаточно для
удовлетворения потребностей всех этих применений в полной мере. Добавление
устройств больше не сопряжено с установкой дополнительных адаптеров,
выполнением сложного конфигурирования, ручным инсталлированием
дополнительного программного обеспечения: система автоматически определяет,
какой ресурс, включая программный драйвер и пропускную способность, нужен
каждому периферийному устройству и делает этот ресурс доступным без
вмешательства пользователя. Популярная периферия сегодня доступна в
вариантах с USB гораздо чаще, чем с другими.
Существовавшей раньше разницы в цене в 10-15-20 долларов (автор помнит как
5 лет назад приобретая сканер переплачивал 20 долларов за USB модель) и
заоблачных цен на внешние USB-контроллеры нет, более того, уже давно USB-
контроллеры интегрируются в чипсеты материнских плат, и пользователь
получает их в свое распоряжение практический задаром. USB вышел в массы и
нужно констатировать тот факт, что COM LPT и PS/2 порты медленно умирают.
Что ж. Давно пора была избавиться от многочисленных пережитков прошлого.
Это та красивая внешняя сторона, которой USB обращена к пользователю.
Наверное многие слышали о том что USB шина позволяет подключать до 127
устройств. И в тоже время на задней стенке обычно находится 2 или 4 порта.
И у многих наверняка возник вопрос - нас обманули, на нас сэкономили
(меньше портов - дешевле система. Хотя… 127 портов разместить на задней
панели… Даже представить сложно) или что-то еще. Оказывается дело все в
том, что шина USB позволяет многоуровневое каскадирование. Наглядно это
объясняет следующий рисунок:
[pic]
Так мы выходим на первую архитектурную особенность шины USB: ее логическая
топология - многоуровневая звезда.
[pic]
Самым верхним уровнем является корневой концентратор, который обычно
совмещается с USB контроллером. Если функции контроллера понятны, то
концентратор - устройство для периферийных интерфейсов не привычное. В
данном случае его функция такая же, что и концентраторов сетей передачи
данных - добавление новых портов для подключения большего числа устройств.
Ничего большего, чем просто разветвитель.
К корневому концентратору могут быть подключены либо устройства, либо еще
концентраторы, для увеличения числа доступных портов. Допускается
организация до пяти уровней. Концентратор может быть выполнен в виде
отдельного устройства, либо быть встроенным в какое-то другое. С этой точки
зрения устройства подключаемые к USB можно подразделить на функциональные
устройства, т.е. те которые выполняют какую-то конкретную функцию и не
берут на себя никаких дополнительных задач (например, мыши) устройства-
концентраторы в чистом виде выполняющие только функцию только разветвления,
и совмещенные (комбинированные) устройства, т.е. имеющие в своем составе
концентратор, расширяющие набор портов и позволяющие подключать другие
устройства (в качестве наиболее часто встречающихся примеров можно назвать
мониторы, позволяющие по USB осуществлять настройку параметров, и обычно
имеющих еще несколько дополнительные порты, для подключения других
устройств или клавиатуры, с разъемами для подключения мышей).
Обратите внимание, на то, что на пятом уровне комбинированное устройство
использоваться не может. Кроме того отдельно стоит упомянуть о хосте,
являющемся скорее программно-аппаратным комплексом, нежели просто
устройством. Физическая топология шины - звезда
[pic]
Это объясняется тем, что каждый концентратор обеспечивает прозрачно для
хоста соединение с устройством.
А отношения клиентского программного обеспечения и USB устройств вообще
сказка. В отличие от привычных старых интерфейсов, где взаимодействие можно
было (и нужно) осуществлять обращаясь к устройству по конкретным физическим
адресам памяти и портам ввода вывода, USB предоставляет для взаимодействия
программный интерфейс и только его, позволяя клиентскому ПО существовать в
отрыве от конкретного подключенного к шине устройства и его конфигурации.
Для клиентской программы USB - это лишь набор функций.
Все классы устройств уже были упомянуты. Теперь можно о каждом поговорить
немного подробнее.
Хост. Как уже было сказано ранее, программно-аппаратный комплекс.
В обязанности хоста входит:
. Слежение за подключением и отключением устройств
. Организация управляющих потоков между USB-устройством и хостом.
. Организация потоков данных между USB-устройством и хостом
. Контроль состояния устроств и ведение статистики активности
. Снабжение подключенных устройств электропитанием
Аппаратной частью является хост контроллер - посредник между хостом и
устройствами на шине.
Программные функции (перечисление устройств и их конфигурирование,
управление энергопотреблением, процессами передачи, устройствами на шине и
самой шиной) возложены на операционную систему. Первой популярной
операционной системой, в которой поддержка USB реализована была в полном
объеме стала Windows 98 Second Edition. Некоторые устройства могут быть
работоспособными и под более ранними версиями (98 без SE, и изредка 95), но
далеко не все и не всегда.
Концентратор (хаб). Позволяет множественные подключения к одному порту,
создавая дополнительные порты. Каждый хаб имеет один восходящий порт,
предназначенный для подключения к имеющемуся в наличии свободному порту, и
несколько нисходящих, к которым могут быть подключены или снова
концентраторы, или конечные устройства, либо совмещенные устройства.
[pic]
Хаб должен следить за подключением и отключением устройств, уведомляя хост
об изменениях, управлять питанием портов. В концентраторе стандарта USB 2.0
можно выделить 3 функциональных блока: контроллер, повторитель, транслятор
транзакций. Контроллер отвечает за соединения с хостом. Понятие повторитель
в USB несколько отличается от принятого в сетях передачи данных. Его
обязанность - соединять входной и какой-то нужный из выходных портов.
Транслятор транзакций появился лишь в USB 2.0 и нужен, как всегда, из
соображений совместимости с предыдущими версиями. Вкратце его суть в том,
что бы обеспечивать максимальную скорость соединения с хостом. Подключенное
к высокоскоростному (USB 2.0) порту старое медленное (USB 1.1) устройство
съедало бы значительную часть времени, а следовательно и полезной
пропускной способности шины, ведя обмен с хостом на низкой скорости (почему
так происходит мы выясним позже при рассмотрении механизма обмена данными
хост-устройство). Как метод борьбы транслятор транзакций буферизирует
поступающий с медленного порта кадр, а затем на максимальной скорости
передает его хосту, или же буферизирует получаемый на максимальной скорости
кадр от хоста, передавая его затем устройству на меньшей, приемлемой для
него скорости. Помимо разветвления и трансляции транзакций хаб должен
осуществлять конфигурирование портов и слежение за корректным
функционированием подключенных к ним устройств. Нужно сказать также, что
при использовании старых и новых концентраторов вместе возможно создание
неоптимальных с точки зрения производительности конфигураций. Для того что
бы избежать создания узких мест в своей цепи, подключайте низкоскоростные
устройства к низкоскоростным хабам, которые в свою очередь делайте
последними уровнями ветвления и не подключайте их в середину
высокоскоростной цепочки.
Функциональное устройство. С точки зрения USB, устройство - это набор
конечных точек с которыми возможен обмен данными. Число и функции точек
зависят от устройства и выполняемых им функций, и определяются при
производстве. В обязательном порядке присутствует точка с номером 0 - для
контроля состояния устройства и управления им. До осуществления
конфигурирования устройства через точку 0 остальные каналы не доступны.
Каждая конечная точка устройства описывается следующими параметрами:
. Частотой обращения к шине и требованиями к задержкам
. Необходимой полосой пропускания
. Номером конечной точки
. Требованиями к обработке ошибок
. Максимальным размером кадра который может быть принят или послан.
. Типом поддерживаемой передачи данных
. Направлением осуществления передачи между конечной точной и хостом.
Для низкоскоростных (low-speed) устройств возможно существование до двух
дополнительных точек; для full-speed устройств их число ограничивается лишь
возможностями протокола и может достигать 15-ти для ввода и 15-ти для
вывода.
Вообще конечная точка - это конец логического канала данных между хостом и
устройством. В свою очередь канал - это логическое соединение между хостом
и устройством. Так как конечных точек у устройства предусматривается
несколько, то это означает, что обмен данными между хост-контроллером и
устройством на шине может проихсодить по нескольким каналам, так называемый
многоканальный режим. Полоса пропускания шины делиться между всеми
установленными каналами. В распоряжение шина USB может предоставить каналы
следующих типов:
. Каналы сообщений. Являются двунаправленными каналами и служат, не
трудно сообразить, для передачи сообщений, имеющих строго определенный
в спецификации формат, необходимый для обеспечения надежной
идентификации и передачи команд. Возникает канал при отсылке хостом
запроса в устройства, и управляет передачей только хост. Каналы
сообщений используется для передач только управляющего типа (что такое
смотрим ниже).
. Потоковые каналы. Являются однонаправленными. В отличие от четко
определенных сообщений не имеют определенного закрепленного в
стандарте формата, что означает возможность передачи данных любого
вида. Эти передачи могут контролироваться не только хостом, но и
устройством. Используется для передач данных типа прерывание,
групповая пересылка, изохронная (смотрим ниже). В спецификации в
зависимости от типа передаваемых данных, предъявляемых требований к
скорости обработки, задержки доставки и т.п. определены следующие типы
передач.
. Управляющие передачи. Используются для конфигурирования устройств во
время подключения и выполнения других специфических функций над
устройством, включая организацию новых каналов.
. Прерывания. Используются для спонтанных, но гарантированных передач с
гарантированными скоростями и задержками. Используются обычно для
передачи введенных данных от клавиатуры или сведений об изменении
положения указателя мыши, в устройствах обратной связи, и.т.д
. Групповая пересылка. Используется для гарантированной передачи данных
больших объемов без предьявленных требований к скоростям и задержкам.
Занимает под себя всю свободную пропускную способность шины. В любой
момент доступная полоса может быть урезана при необходимости
осуществления передач других видов с более высоким приоритетом, или
добавлена, при освобождении другими устройствами. Обычно такие
передачи используется между принтерами, сканерами, накопителями и др.
. Изохронная передачи. Используются для потоковых передач данных в
реальном времени. Резервируют определенную полосу пропускания шины,
гарантируют определенные величины задержек доставки, но не гарантируют
доставку (в случае обнаружения ошибки повторной передачи не
происходит. Передачи этого вида используются для передачи аудио и
видео трафика.
Обмен данными может осуществляться в трех скоростных режимах:
. Low Speed. Низкоскоростной режим. Скорость передачи составляет 1.5
Мбит/с.
. Full Speed. Полноскоростной режим. Скорость передачи 12 Мбит/с.
. High Speed. Высокоскоростной режим. Появился лишь в спецификации 2.0.
Скорость передачи 480 Мбит/с.
Информация по шине передается пакетами. Всего их определено 4 вида:
. Маркерные пакеты.
o In - информируют USB устройство, что хост хочет читать данные из
устройства
o Out - информирует USB устройство, что хост хочет передавать
данные в устройство
o Setup - используются для обозначения начала управляющего типа
передачи данных
o SOF - пакеты начала кадра (Start of Frame Packets)
. Пакеты данных.
o Существуют два типа пакетов данных - DATA0, DATA1 , каждый из
которых способен содержать до 1024 байтов данных. У
высокоскоростных устройств для пакетов данных определены два
других PID-a: DATA2 и MDATA.
. Пакеты подтверждения.
o ACK - подтверждение того, что пакет был успешно принят
o NAK - информирует, что устройство в данный момент не может
принимать либо отправлять данные. А в Interrupt транзакциях
сообщает хосту, что устройство не имеет новых данных для
передачи.
o STALL - указывает, что устройство неспособно передавать или
получать данные и требуется вмешательство хоста.
. Специальные.
o PRE - предшествует низкоскоростной передаче данных.
Устройства на шине USB делятся на ведущие и ведомые. Фактически, ведущих
устройств на шине может быть только одно, и таковым является хост. Все
передачи данных инициируются хостом в соответствии определенной временной
программой. Функциональные устройства сами не могут инициировать передачу,
а лишь отвечают на запросы хоста. Обмен данными возможен только между
хостом и устройством, и не возможен на прямую между устройствами
подключенными к шине (это означает, что в принципе в первую очередь USB -
это шина вывода. Позже мы поймем почему). Транзакции на USB шине состоят из
двух-трех актов: посылки пакета маркера, определяющего, что будет следовать
дальше (тип транзакции, адрес устройства и его конечную точку), пакета
данных (опционально), и пакета статуса транзакции (для подтверждения
нормального выполнения операции или сообщения об ошибке).
Мы не станем опускаться в рассмотрении до уровня кадров и микрокадров, так
как это совсем не помешает понять нам общие принципы работа шина.
Физические каналы связи организуются концентраторами и соединительными
проводами. С концентраторами мы уже почти разобрались ранее. Провод
использующийся для подключения USB устройств представляет собой
экранированную витую пару. Для высокоскоростных устройств предъявляются
высокие требования к ее качеству. Низкоскоростные к этому элементу
физического интерфейса относятся не критично, и без проблемно могут
функционировать на неэкранированном невитом проводе. Всего в USB кабеле
используется 4 проводов.
[pic]
Два для передачи сигнала и два для подачи напряжения. Для подключения
устройств предназначены соединители двух типов: типа "A" и типа "B". Как
мне кажется создание двух различных видов коннекторов было необходимо для
того, что бы избежать излишней путаницы при подключении устройств и
защититься от дурака, лишив его возможности подключить что-либо не так.
Кроме того, они характеризуются различным усилием необходимым для вставки и
силой удержания в разьеме.
Коннекторы типа "А" используются для подключения к компьютеру, обеспечивают
жесткое и надежное крепление и не предназначены для частого
подключения/отсоединения.
[pic]
Соединители же типа "B", наоборот, нужны в тех местах, где существует
необходимость частого подключения/отключения, и применяются они со стороны
периферии.
[pic]
В живую они вот так смотрятся.
[pic]
Кроме того в новой версии USB определен коннектор miniUSB типа "B".
[pic]
Он предназначен для применения на малогабаритных устройствах типа мобильных
телефонов, фотоаппаратов, плееров, где нет возможности разместить
стандартный полноразмерный разъем. (По совершенно непонятным для меня
причинам, с доступностью кабелей miniUSB ситуация обстоит не лучшим
образом: и хотя это очень распространенный в последнее время тип
подключения, достать его зачастую очень проблемно, а если и возможно, то за
него просят порой 10-20$, при том что с обычной вилкой типа "B" можно
приобрести на каждом углу за 1$. Это и собственное наблюдение, и опыт
общения с людьми в разных городах и странах) От мелкой периферии, типа
клавиатур, мышек, где размещение соединительных разъемов неудобно да и
вообще глупо, кабель может вообще не отсоединятся. Конструктивно разъемы
задуманы так, что сначала происходит соединение шины питания, потом шины
данных.
По подписям D+ и D- на схеме кабеля должно быть вы уже догадались, что USB
использует дифференциальную передачу (впрочем, каждый порт помимо
дифференциального приемника имеет еще и линейные для каждого сигнала),
добавлю еще что применяется потенциальное кодирование по методу NRZI (Non
Return to Zero Invert to ones, без возвращения к нулю с инверсией для
единиц) и битстаффинг для улучшения самосинхронизирующихся свойств потока.
Это в общем. Глубже мы не станем вдаваться. Совершенно ни к чему.
Подключаемые устройства, потребляющие небольшой ток, могут быть запитаны от
шины USB. Максимальный ток, который может обеспечить шина равен 500 мА. Это
ток, доступный всем устройствам на шине, а не, как приходит некоторым в
голову, на каждое из 127 возможных устройств (при этом на стадии
подключения и конфигурирования потребляемый ток не должен превышать 100 мА,
в противном случае устройство просто не будет инициировано). Для увеличения
доступной мощности питания на шине, концентраторы могут оснащаться своим
собственным блоком питания, однако такое решение не популярно.
Теперь, обладая необходимым минимумом сведений об шине USB, устройствах
протоколах и пр. можно попробовать в общих чертах разобраться с тем как же
все это работает.
Итак, к шине подключено новое устройство. Наверняка вы задавались вопросом,
каким образом происходит обнаружение. Ответ прост: обнаружение устройства,
а также и его скоростной режим определяется по скачку напряжения, который
имеет место быть при включении на шине данных. Этот скачок создается
подключением резистора к напряжению 3.3 В. Для низкоскоростных устройств
этот резистор подключается к шине D-, для полно- и высокоскоростных - к
шине D+. Обычно тот резистор делается программно управляемым для того, что
бы после обнаружения устройства его можно было отключить и сбалансировать
линию. Итак, новое устройство подключено и обнаружено.
Конфигурирование осуществляется через конечную точку с номером 0 (для
любопытных можно сказать, что обмен информацией в этот момент происходит в
полноскоростном режиме!). Загружаются необходимые драйверы. Устройство
готово к работе.
Обмен данными. Случай первый: передача от хоста к устройству. В принципе,
никакой сложности нет. Как только такая необходимость возникла, хост может
инициировать передачу. Для этого он посылает устройству пакет out (в знак
того, что данные будет передавать он), затем посылает сами данные, а затем
принимает пакет ACK, подтверждающий, что данные устройством получены без
ошибок (если это не изохронный тип передачи, для которого подтверждение не
передается).
Обмен данными. Случай второй: от устройства к хосту. У устройства возникла
необходимость передать данные. НО! Оно не может никаким образом дать знать
об этом хосту. Таких средств в USB просто не предусмотрено. Для того, что
бы выполнить такую передачу, хост должен обратиться у устройству с
вопросом, не имеет ли оно желание чего-либо ему сказать (послав пакет in).
В ответ на что устройство вышлет ему имеющиеся данные и дождется получения
подтверждения (снова же, если ведется не изохронная передача).
Соответственно, если хост не обратиться с таким вопросом, то данные никогда
не будут переданы.
Обмен управляющей информацией. В принципе имеет ту же логику, но
используется передача типа управление и канал сообщений и специальные
пакеты.
Во время простоев в энергосберегающих целях устройства переводятся в
состояние suspend (и выход из этого состояния, передача информации о
пробуждении - единственный случай, когда устройство может стать инициатором
транзакции). Вообще состояний в которых может пребывать устройство гораздо
больше, но это основное из того, что нам было необходимо знать для
формирования общего представления о принципах работы.
Флэш-память
Следует признать тот факт, что цифровые технологии все шире входят в
нашу жизнь. За последние пять лет появилось множество различных МРЗ-
плееров, камер, карманных компьютеров и другой цифровой аппаратуры. А все
это стало возможным благодаря созданию компактных и мощных процессоров.
Однако при покупке какого-либо устройства, помещающегося в кармане, не
стоит ориентироваться лишь на процессорную мощность, поскольку в списке
приоритетов она стоит далеко не на первом месте.
При выборе портативных устройств самое важное, на мой взгляд - время
автономной работы при разумных массе и размерах элемента питания. Во многом
это от памяти, которая определяет объем сохраненного материала, и,
продолжительность работы без подзарядки аккумуляторов. Возможность хранения
информации в карманных устройствах ограничивается скромными энергоресурсами
Память, обычно используемая в ОЗУ компьютеров, требует постоянной подачи
напряжения. Дисковые накопители могут сохранять информацию и без
непрерывной подачи электричества, зато при записи и считывании данных
тратят его за троих. Хорошим выходом оказалась флэш-память, не
разряжающаяся самопроизвольно. Носители на ее основе называются
твердотельными, поскольку не имеют движущихся частей. К сожалению, флэш-
память - дорогое удовольствие: средняя стоимость ее мегабайта составляет 2
доллара[1], что в восемь раз выше, чем у SDRAM, не говоря уж о жестких
дисках. А вот отсутствие движущихся частей повышает надежность флэш-памяти:
стандартные рабочие перегрузки равняются 15 g, а кратковременные могут
достигать 2000 g, т. е. теоретически карта должна превосходно работать при
максимально возможных космических перегрузках, и выдержать падения с
трёхметровой высоты. Причем в таких условиях гарантируется функционирование
карты до 100 лет.
Многие производители вычислительной техники видят память будущего
исключительно твердотелой. Следствием этого стало практически одновременное
появление на рынке комплектующих нескольких стандартов флэш-памяти.
Compact Flash
Этот стандарт был предложен в 1994 г. компанией SanDisk, а в 1995 г.
его стала продвигать ассоциация CFA, созданная такими крупными компаниями,
как Hewlett-Packard, Hitachi, IBM, Motorola и др. Сейчас в нее входят уже
более 165 фирм.
Модули памяти Compact Flash (CF) представляют собой модификацию PC-
карт. Правда, они меньше по объему и имеют всего 50 контактов вместо 68, но
их можно подключать в разъемы PCMCIA через пассивный переходник без
дополнительного ПО. Устройства CF делятся на два типа, внешне различающихся
толщиной. Размеры CF типа I - 36,4x42,8x3,3 мм, a CF типа II имеют ту же
площадь, но их толщина больше - 5 мм. Карты типа II несовместимы с
разъемами типа I, тогда как для карт типа I подходят порты обоих видов.
Для работы модули CF используют напряжение 3,3 или 5 В и ток до 100 мА.
В итоге, по утверждению производителей, они потребляют в 20 раз меньше
энергии, нежели стандартные жесткие диски, так что не нужно часто заменять
батарейки.
Максимальная емкость карт типа I составляет 256 Мбайт (у компаний PQI и
Delkin), а карт типа II - 512 Мбайт (у фирмы SiliconTech).Причём цена
экспоненциально зависит от размера модуля. Например, SiliconTech за свою
полугигабайтную микросхему типа II требует 1608 долл., а наиболее выгодные
по критерию "доллар за мегабайт" 128- и 256-Мбайтные карты стоят от 205 и
420 долл. соответственно. Память типа I дороже, чем типа II, так как у нее
то же число микросхем надо вмещать в меньший объем.
Стандарт Compact Flash уже довольно давно представлен на рынке, поэтому
при покупке камеры, работающей с картами CF, можно не сомневаться, что
удастся найти совместимый по памяти МРЗ-плеер и не придется иметь дело с
картами разных видов. Для совмещения карты данного типа с ноутбуком
достаточно купить за 10 долл. переходник для разъема PCMCIA.
SmartMedia
Стандарт SmartMedia, или SSFDC был разработан в 1995 г. компанией
Toshiba, а его продвижением занимается организация SSFDC Forum, в рядах
которой немало известных компаний. SSFDC (Solid State Floppy Disk Card)
можно перевести как "твердотельная дискета". Следует отметить, что многие
производители делают флэш-карты сразу трех основных типов: Compact Flash,
SmartMedia и MultiMediaCard.
В отличие от Compact Flash, карты SmartMedia (SM) не снабжены
встроенным контроллером, что, по замыслу создателей, должно снижать их
стоимость. Кроме того, SM имеют меньшие размеры (37x45x1,76 мм) и массу (до
2 г). По популярности SM спорят с CF, а вместе с ним оба этих стандарта
охватывают более половины рынка флэш-карт.
Рабочие напряжения у SM такие же, как и у CF, но обычно используется
3,3 В. Максимальная емкость карт, объявленная производителями, в частности
компаниями ЕМТЕС и Delkin, составляет 128 Мбайт, и стоит около 250 долл..
Из-за отсутствия внутреннего контроллера для работы с этими картами
невозможно применить пассивный переходник, а считыватели для них стоят
около 50 долл. SM обычно используются в цифровых камерах и МРЗ-плеерах, а
вот в КПК - практически никогда.
MultiMediaCard
Этот стандарт предложили в 1997 г. компании Infineon Technologies
(подразделение Siemens) и SanDisk, а продвигает его ассоциация ММСА,
состоящая из 80 компаний (Infineon, Nokia, Ericsson, Hitachi, SanDisk,
Motorola и др.).
Карты ММС еще меньше, чем рассмотренные выше, - 32x24x1,4 мм, да и
весят они всего 1,5 г. Поэтому и предназначены в основном для
ультрапортативных устройств, особенно актуальны они в КПК, сотовых
телефонах и электронных записных книжках.
Эти модули памяти работают при напряжениях 3,3 или 2,7 В и токе до 35
мА, что и обусловливает низкое энергопотребление.
Максимальная емкость ММС, представленных на Российском рынке,
составляет 64 Мбайт, и стоит около 130 долл. Этот же объем оказался
наиболее выгодным по соотношению "доллар за мегабайт".
Сейчас стандарт ММС уже достаточно популярен, и примером тому может
служить его поддержка КПК Cassiopea EM-500
Secure Digital
Компания Matsushita Electronic (известная под торговой маркой
Panasonic) вместе с SanDisk и Toshiba разработали стандарт, в котором учли
последние веяния времени. Чтобы предотвратить несанкционированное
копирование, носители Secure Digital (SD) снабжены средствами защиты от
незаконного копирования.
Размеры карт - 32x24x2,1 мм. Разъемы для них совместимы с модулями ММС.
Пока стандарт только начал завоевывать рынок, но производители обещают уже
в этом году довести емкость карт SD до 256 Мбайт.
Уже анонсирован выпуск в формате SD модемов и других периферийных
устройств. А возможность защиты авторских прав позволила продавцам
выпустить в продажу книги и песни на этих носителях.
Memory Stick
Некогда Sony заставила компьютерную индустрию выбрать в качестве
сменных носителей свои 3,5-дюймовые флоппи-дисководы, а теперь она решила
позаботиться о своих позициях и на аудиорынке, для чего разработала новый
стандарт флэш-карт Memory Stick
(MS). Эти 10-контактные устройства . размерами 21,5x50x2,8 мм и массой
4 г стали опорой цифровой империи Sony, которая устанавливает их в свои
цифровые плееры, фотоаппараты и видеокамеры, также игрушки и другие
устройства.
В апреле этого (2001) года была выпущена новая, 128-Мбайт модель MS
стоимостью 249 долл. Также существует разновидность MS MagicGate (с защитой
от несанкционированного копирования), предназначенная для плееров. В
настоящее время стандарт Memory Stick поддерживается почти исключительно
устройствами производства концерна Sony. Из-за такой не универсальности они
и не получили широкого распространения.
Считыватели
Для быстрого и удобного обмена информацией между флэш-картами и
компьютером используются считыватели. Они различаются способом и
интерфейсом подключения к ПК, а также скоростными характеристиками.
Внешние считыватели
Эти устройства могут подключаться через USB, LPT, и FireWire(IEEE1394)
интерфейсы. Они отличаются друг от друга только скоростными показателями.
Скорость самого медленного из них – подключаемого через параллельный порт,
может достигать 0,34Мбайт/с – при записи, и 0,62Мбайт/с – при чтение
данных. У моделей с универсальным последовательным портом эти показатели
составляют 0,46 и 0,77Мбайт/с. А вот FireWire считыватель оставил далеко
позади всех своих конкурентов. Устройства с данным интерфейсом способны
“запоминать” информацию на скорости до 0,7Мбайт/с, и выдавать её в три раза
быстрее - 2,1Мбайт/с. Также большим плюсом является способность некоторых
моделей работать ни с одним, а с несколькими стандартами флэш-памяти.
Внутренние считыватели
Подобные устройства вставляются в 3,5-дюймовый отсек системного блока,
и подключаются к ATA интерфейсу. К достоинствам считывателей данного класса
относятся высокая скорость(0,52 Мбайт/с и 1Мбайт/с) и отсутствие
посторонних устройств на столе. А к недостаткам – то он занимает отсек
системного блока, и IDE канал.
Считыватели - переходники
Этот класс устройств позволяет подключить флэш-карту к компьютеру через
дисковод. При этом используется переходник внешне похожий на 3,5-дюймовую
дискету(или PC-карту для ноутбуков). Карта памяти вставляется в адаптер,
который впоследствии размещается в дисководе. Использование PCMCIA-
адаптеров даёт неплохие результаты, скорость передачи достигает 1Мбайт/с. А
при использовании флоппи-дисковода она недотягивает и до отметки 36
Кбайт/с. И это при том что FDD(FlashPath)-адаптер стоит дороже любого
другого считывателя.
Список использованных материалов:
1. http://ixbt.stack.net
2. http://developer.intel.com/design/iio/
3. http://www.usb.org/
4. http://www.skipstone.com/
5. http://www.sel.sony.com/SEL/consumer/camcorder/dcr_vx1000.html
6. http://www.ti.com/sc/docs/msp/1394/1394.htm
7. http://developers.intel.com/technology/agp
8. http://www.mka.ru/?p=41229
9. http://www.3dnews.ru/storage/usb-2
-----------------------
[1] -Здесь и далее цены приведены на лето 2001 года.
Реферат на тему: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Введение 8
Целевая аудитория 10
Глава 1. Основные понятия 15
Что такое алгоритмы? 15
Анализ скорости выполнения алгоритмов 16
Пространство — время 17
Оценка с точностью до порядка 17
Поиск сложных частей алгоритма 19
Сложность рекурсивных алгоритмов 20
Многократная рекурсия 21
Косвенная рекурсия 22
Требования рекурсивных алгоритмов к объему памяти 22
Наихудший и усредненный случай 23
Часто встречающиеся функции оценки порядка сложности 24
Логарифмы 25
Реальные условия — насколько быстро? 25
Обращение к файлу подкачки 26
Псевдоуказатели, ссылки на объекты и коллекции 27
Резюме 29
Глава 2. Списки 30
Знакомство со списками 31
Простые списки 31
Коллекции 32
Список переменного размера 33
Класс SimpleList 36
Неупорядоченные списки 37
Связные списки 41
Добавление элементов к связному списку 43
Удаление элементов из связного списка 44
Уничтожение связного списка 44
Сигнальные метки 45
Инкапсуляция связных списков 46
Доступ к ячейкам 47
Разновидности связных списков 49
Циклические связные списки 49
Проблема циклических ссылок 50
Двусвязные списки 50
Потоки 53
Другие связные структуры 56
Псевдоуказатели 56
Резюме 59
Глава 3. Стеки и очереди 60
Стеки 60
Множественные стеки 62
Очереди 63
Циклические очереди 65
Очереди на основе связных списков 69
Применение коллекций в качестве очередей 70
Приоритетные очереди 70
Многопоточные очереди 72
Резюме 74
Глава 4. Массивы 75
Треугольные массивы 75
Диагональные элементы 77
Нерегулярные массивы 78
Прямая звезда 78
Нерегулярные связные списки 79
Разреженные массивы 80
Индексирование массива 82
Очень разреженные массивы 85
Резюме 86
Глава 5. Рекурсия 86
Что такое рекурсия? 87
Рекурсивное вычисление факториалов 88
Анализ времени выполнения программы 89
Рекурсивное вычисление наибольшего общего делителя 90
Анализ времени выполнения программы 91
Рекурсивное вычисление чисел Фибоначчи 92
Анализ времени выполнения программы 93
Рекурсивное построение кривых Гильберта 94
Анализ времени выполнения программы 96
Рекурсивное построение кривых Серпинского 98
Анализ времени выполнения программы 100
Опасности рекурсии 101
Бесконечная рекурсия 101
Потери памяти 102
Необоснованное применение рекурсии 103
Когда нужно использовать рекурсию 104
Хвостовая рекурсия 105
Нерекурсивное вычисление чисел Фибоначчи 107
Устранение рекурсии в общем случае 110
Нерекурсивное построение кривых Гильберта 114
Нерекурсивное построение кривых Серпинского 117
Резюме 121
Глава 6. Деревья 121
Определения 122
Представления деревьев 123
Полные узлы 123
Списки потомков 124
Представление нумерацией связей 126
Полные деревья 129
Обход дерева 130
Упорядоченные деревья 135
Добавление элементов 135
Удаление элементов 136
Обход упорядоченных деревьев 139
Деревья со ссылками 141
Работа с деревьями со ссылками 144
Квадродеревья 145
Изменение MAX_PER_NODE 151
Использование псевдоуказателей в квадродеревьях 151
Восьмеричные деревья 152
Резюме 152
Глава 7. Сбалансированные деревья 153
Сбалансированность дерева 153
АВЛ-деревья 154
Удаление узла из АВЛ-дерева 161
Б-деревья 166
Производительность Б-деревьев 167
Вставка элементов в Б-дерево 167
Удаление элементов из Б-дерева 168
Разновидности Б-деревьев 169
Улучшение производительности Б-деревьев 171
Балансировка для устранения разбиения блоков 171
Вопросы, связанные с обращением к диску 173
База данных на основе Б+дерева 176
Резюме 179
Глава 8. Деревья решений 179
Поиск в деревьях игры 180
Минимаксный поиск 181
Улучшение поиска в дереве игры 185
Поиск в других деревьях решений 187
Метод ветвей и границ 187
Эвристики 191
Другие сложные задачи 207
Задача о выполнимости 207
Задача о разбиении 208
Задача поиска Гамильтонова пути 209
Задача коммивояжера 210
Задача о пожарных депо 211
Краткая характеристика сложных задач 212
Резюме 212
Глава 9. Сортировка 213
Общие соображения 213
Таблицы указателей 213
Объединение и сжатие ключей 215
Примеры программ 217
Сортировка выбором 219
Рандомизация 220
Сортировка вставкой 221
Вставка в связных списках 222
Пузырьковая сортировка 224
Быстрая сортировка 227
Сортировка слиянием 232
Пирамидальная сортировка 234
Пирамиды 235
Приоритетные очереди 237
Алгоритм пирамидальной сортировки 240
Сортировка подсчетом 241
Блочная сортировка 242
Блочная сортировка с применением связного списка 243
Блочная сортировка на основе массива 245
Резюме 248
Глава 10. Поиск 248
Примеры программ 249
Поиск методом полного перебора 249
Поиск в упорядоченных списках 250
Поиск в связных списках 251
Двоичный поиск 253
Интерполяционный поиск 255
Строковые данные 259
Следящий поиск 260
Интерполяционный следящий поиск 261
Резюме 262
Глава 11. Хеширование 263
Связывание 265
Преимущества и недостатки связывания 266
Блоки 268
Хранение хеш-таблиц на диске 270
Связывание блоков 274
Удаление элементов 275
Преимущества и недостатки применения блоков 277
Открытая адресация 277
Линейная проверка 278
Квадратичная проверка 284
Псевдослучайная проверка 286
Удаление элементов 289
Резюме 291
Глава 12. Сетевые алгоритмы 292
Определения 292
Представления сети 293
Оперирование узлами и связями 295
Обходы сети 296
Наименьшие остовные деревья 298
Кратчайший маршрут 302
Установка меток 304
Коррекция меток 308
Другие задачи поиска кратчайшего маршрута 311
Применения метода поиска кратчайшего маршрута 316
Максимальный поток 319
Приложения максимального потока 325
Резюме 327
Глава 13. Объектно-ориентированные методы 327
Преимущества ООП 328
Инкапсуляция 328
Полиморфизм 330
Наследование и повторное использование 333
Парадигмы ООП 335
Управляющие объекты 335
Контролирующий объект 336
Итератор 337
Дружественный класс 338
Интерфейс 340
Фасад 340
Порождающий объект 340
Единственный объект 341
Преобразование в последовательную форму 341
Парадигма Модель/Вид/Контроллер. 344
Резюме 346
Требования к аппаратному обеспечению 346
Выполнение программ примеров 346
programmer@newmail.ru
Далее следует «текст», который любой уважающий себя программист должен
прочесть хотя бы один раз. (Это наше субъективное мнение)
Введение
Программирование под Windows всегда было нелегкой задачей. Интерфейс
прикладного программирования (Application Programming Interface) Windows
предоставляет в распоряжение программиста набор мощных, но не всегда
безопасных инструментов для разработки приложений. Можно сравнить его с
бульдозером, при помощи которого удается добиться поразительных
результатов, но без соответствующих навыков и осторожности, скорее всего,
дело закончится только разрушениями и убытками.
Эта картина изменилась с появлением Visual Basic. Используя визуальный
интерфейс, Visual Basic позволяет быстро и легко разрабатывать законченные
приложения. При помощи Visual Basic можно разрабатывать и тестировать
сложные приложения без прямого использования функций API. Избавляя
программиста от проблем с API, Visual Basic позволяет сконцентрироваться на
деталях приложения.
Хотя Visual Basic и облегчает разработку пользовательского интерфейса,
задача написания кода для реакции на входные воздействия, обработки их, и
представления результатов ложится на плечи программиста. Здесь начинается
применение алгоритмов.
Алгоритмы представляют собой формальные инструкции для выполнения сложных
задач на компьютере. Например, алгоритм сортировки может определять, как
найти конкретную запись в базе из 10 миллионов записей. В зависимости от
класса используемых алгоритмов искомые данные могут быть найдены за
секунды, часы или вообще не найдены.
В этом материале обсуждаются алгоритмы на Visual Basic и содержится большое
число мощных алгоритмов, полностью написанных на этом языке. В ней также
анализируются методы обращения со структурами данных, такими, как списки,
стеки, очереди и деревья, и алгоритмы для выполнения типичных задач, таких
как сортировка, поиск и хэширование.
Для того чтобы успешно применять эти алгоритмы, недостаточно их просто
скопировать в свою программу. Необходимо кроме этого понимать, как
различные алгоритмы ведут себя в разных ситуациях, что в конечном итоге и
будет определять выбор наиболее подходящего алгоритма.
В этом материале поведение алгоритмов в типичном и наихудшем случаях
описано доступным языком. Это позволит понять, чего вы вправе ожидать от
того или иного алгоритма и распознать, в каких условиях встречается
наихудший случай, и в соответствии с этим переписать или поменять алгоритм.
Даже самый лучший алгоритм не поможет в решении задачи, если применять его
неправильно.
=============xi
Все алгоритмы также представлены в виде исходных текстов на Visual Basic,
которые вы можете использовать в своих программах без каких-либо изменений.
Они демонстрируют использование алгоритмов в программах, а также важные
характерные особенности работы самих алгоритмов.
Что дают вам эти знания
После ознакомления с данным материалом и примерами вы получите:
1. Понятие об алгоритмах. После прочтения данного материала и выполнения
примеров программ, вы сможете применять сложные алгоритмы в своих
проектах на Visual Basic и критически оценивать другие алгоритмы,
написанные вами или кем-либо еще.
2. Большую подборку исходных текстов, которые вы сможете легко добавить к
вашим программам. Используя код, содержащийся в примерах, вы сможете
легко добавлять мощные алгоритмы к вашим приложениям.
3. Готовые примеры программ дадут вам возможность протестировать алгоритмы.
Вы можете использовать эти примеры и модифицировать их для углубленного
изучения алгоритмов и понимания их работы, или использовать их как основу
для разработки собственных приложений.
Целевая аудитория
В этом материале обсуждаются углубленные вопросы программирования на Visual
Basic. Они не предназначена для обучения программированию на этом языке.
Если вы хорошо разбираетесь в основах программирования на Visual Basic, вы
сможете сконцентрировать внимание на алгоритмах вместо того, чтобы
застревать на деталях языка.
В этом материале изложены важные концепции программирования, которые могут
быть с успехом применены для решения новых задач. Приведенные алгоритмы
используют мощные программные методы, такие как рекурсия, разбиение на
части, динамическое распределение памяти и сетевые структуры данных,
которые вы можете применять для решения своих конкретных задач.
Даже если вы еще не овладели в полной мере программированием на Visual
Basic, вы сможете скомпилировать примеры программ и сравнить
производительность различных алгоритмов. Более того, вы сможете выбрать
удовлетворяющие вашим требованиям алгоритмы и добавить их к вашим проектам
на Visual Basic.
Совместимость с разными версиями Visual Basic
Выбор наилучшего алгоритма определяется не особенностями версии языка
программирования, а фундаментальными принципами программирования.
=================xii
Некоторые новые понятия, такие как ссылки на объекты, классы и коллекции,
которые были впервые введены в 4-й версии Visual Basic, облегчают
понимание, разработку и отладку некоторых алгоритмов. Классы могут
заключать некоторые алгоритмы в хорошо продуманных модулях, которые легко
вставить в программу. Хотя для того, чтобы применять эти алгоритмы,
необязательно разбираться в новых понятиях языка, эти новые возможности
предоставляют слишком большие преимущества, чтобы ими можно было
пренебречь.
Поэтому примеры алгоритмов в этом материале написаны для использования в 4-
й и 5-й версиях Visual. Если вы откроете их в 5-й версии Visual Basic,
среда разработки предложит вам сохранить их в формате 5-й версии, но
никаких изменений в код вносить не придется. Все алгоритмы были
протестированы в обеих версиях.
Эти программы демонстрируют использование алгоритмов без применения
объектно-ориентированного подхода. Ссылки и коллекции облегчают
программирование, но их применение может приводить к некоторому замедлению
работы программ по сравнению со старыми версиями.
Тем не менее, игнорирование классов, объектов и коллекций привело бы к
упущению многих действительно мощных свойств. Их использование позволяет
достичь нового уровня модульности, разработки и повторного использования
кода. Их, безусловно, необходимо иметь в виду, по крайней мере, на
начальных этапах разработки. В дальнейшем, если возникнут проблемы с
производительностью, вы сможете модифицировать код, используя более быстрые
низкоуровневые методы.
Языки программирования зачастую развиваются в сторону усложнения, но редко
в противоположном направлении. Замечательным примером этого является
наличие оператора goto в языке C. Это неудобный оператор, потенциальный
источник ошибок, который почти не используется большинством программистов
на C, но он по-прежнему остается в синтаксисе языка с 1970 года. Он даже
был включен в C++ и позднее в Java, хотя создание нового языка было хорошим
предлогом избавиться от него.
Так и новые версии Visual Basic будут продолжать вводить новые свойства в
язык, но маловероятно, что из них будут исключены строительные блоки,
использованные при применении алгоритмов, описанных в данном материале.
Независимо от того, что будет добавлено в 6-й, 7-й или 8-й версии Visual
Basic, классы, массивы и определяемые пользователем типы данных останутся в
языке. Большая часть, а может и все алгоритмы из приведенных ниже, будут
выполняться без изменений в течение еще многих лет.
Обзор глав
В 1 главе рассматриваются понятия, которые вы должны понимать до того, как
приступить к анализу сложных алгоритмов. В ней изложены методы, которые
потребуются для теоретического анализа вычислительной сложности алгоритмов.
Некоторые алгоритмы с высокой теоретической производительностью на практике
дают не очень хорошие результаты, поэтому в этой главе также затрагиваются
практические соображения, например обращение к файлу подкачки и
сравнивается использование коллекций и массивов.
Во 2 главе показано, как образуются различные виды списков с использованием
массивов, объектов, и псевдоуказателей. Эти структуры данных можно с
успехом применять во многих программах, и они используются в следующих
главах
В 3 главе описаны два особых типа списков: стеки и очереди. Эти структуры
данных используются во многих алгоритмах, включая некоторые алгоритмы,
описанные в последующих главах. В конце главы приведена модель очереди на
регистрацию в аэропорту.
В 5 главе обсуждается мощный инструмент — рекурсия. Рекурсия может быть
также запутанной и приводить к проблемам. В 5 главе объясняется, в каких
случаях следует применять рекурсию и показывает, как можно от нее
избавиться, если это необходимо.
В 6 главе используются многие из ранее описанных приемов, такие как
рекурсия и связные списки, для изучения более сложной темы — деревьев. Эта
глава также охватывает различные представления деревьев, такие как деревья
с полными узлами (fat node) и представление в виде нумерацией связей
(forward star). В ней также описаны некоторые важные алгоритмы работы с
деревьями, таки как обход вершин дерева.
В 7 главе затронута более сложная тема. Сбалансированные деревья обладают
особыми свойствами, которые позволяют им оставаться уравновешенными и
эффективными. Алгоритмы сбалансированных деревьев удивительно просто
описываются, но их достаточно трудно реализовать программно. В этой главе
используется одна из наиболее мощных структур подобного типа — Б+дерево
(B+Tree) для создания сложной базы данных.
В 8 главе обсуждаются задачи, которые можно описать как поиск ответов в
дереве решений. Даже для небольших з | |
