Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Радиоэлектроника Радиоэлектроника

Алгоритмы трассировки

Брелок LED "Лампочка" классическая.
Брелок работает в двух автоматических режимах и горит в разных цветовых гаммах. Материал: металл, акрил. Для работы нужны 3 батарейки
131 руб
Раздел: Металлические брелоки
Ночник-проектор "Звездное небо и планеты", фиолетовый.
Оригинальный светильник - ночник - проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фонариков) 2) Три
330 руб
Раздел: Ночники
Наклейки для поощрения "Смайлики 2".
Набор для поощрения на самоклеящейся бумаге. Формат 95х160 мм.
19 руб
Раздел: Наклейки для оценивания, поощрения

МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ ВОСТОЧНОУКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СЕВЕРОДОНЕЦКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ РЕФЕРАТ на тему: "Алгоритмы трассировки " Руководитель: Исполнитель: А.Ф. Горбатюк В.Н. Руднев г. Северодонецк 2000 г Введение В настоящее время используются различные варианты волнового алгоритма, в частности, лучевой и маршрутные. Простейшим видом волнового алгоритма является волновой алгоритм нахождения кратчайшего пути без пересечения множества занятых и запрещенных элементов (участков печатной платы). Его целесообразно использовать при трассировке соединений в одной плоскости, когда недопустимо выходить из пределов этой плоскости. Определяются начальная и конечная точки и моделируется распространение волны от конечной точки к начальной в направлении волны. Недостатком этого алгоритма является то, что он мало пригоден для трассировки многослойных печатных плат, проводники прокладываются по краям платы, значительное число длинных параллельных проводников являются причиной большой взаимоиндуктивности. Более совершенным волновым алгоритмом является волновой алгоритм прокладки пути с минимальным числом пересечения. В этом случае число пересечений ранее проложенных трасс должно быть минимальным. Для преодоления недостатка этого алгоритма, при котором трассы стремятся к одной из границ платы и прижимаются друг к другу, был предложен алгоритм для проведения пути, минимально приближающихся к другим трассам. Основой алгоритма является условие, при котором элементы данного соединения должны иметь минимум соседних элементов, принадлежащих ранее проложенным трассам. Если одним из условий является требование регулярности соединений (один слой горизонтальные, другой – вертикальные и т.п.), то удобнее использовать волновой алгоритм прокладки пути с минимальным числом изменений направления, который позволяет минимизировать количество межслойных соединений. В отличие от волновых и лучевых алгоритмов, в которых на начальной стадии перебираются все возможные варианты трассы, в маршрутных алгоритмах прокладка трассы ведется сразу и по кратчайшему маршруту. Маршрутный алгоритм трассировки Каждый слой платы представлен в памяти ЭВМ булевой матрицей, элементы которой имеют значение 0, если соответствующий элемент свободен для прокладки пути, и имеют значение 1, если соответствующий элемент занят. Все элементы матрицы, которые принадлежат исходным препятствиям, задаются единичным значением. Алгоритм реализует следующие последовательно выполняемые этапы: 1) построение пути до встречи с препятствием; 2) обход препятствий; 3) минимизация построенного пути. Этап 1. Пусть требуется проложить путь между элементами da, булевой матрицы, описывающей модель платы. При отсутствии препятствий между элементами можно проложить конечное множество путей, имеющих минимальную длину в выбранной геометрии. Процесс построения Р-пути (Н-пути) сводится к тому, чтобы определить такую последовательность элементов L=, что любой элемент dk принадлежит Р-окрестности (Н-окрестности) элемента dk-1. Если будем рассматривать Н-окрестность, то вектор перехода Zk от элемента dk к элементу dк 1 возможен только в направлениях, параллельных координатным осям.

Для случая Р-окрестности вектор перехода может иметь диагональные направления. На каждом шаге построения пути направление вектора перехода Zk от элемента dk к элементу dк 1 определяется функциями sg (xb-xk), sg (yb-yk), где xb, yb - координаты элемента db пути, xk, yk - координаты элемента dk. Правило выбора направления построения пути до встречи с препятствием в наилучшем направлении приведено в таблице 1. Таблица 1. Функция Zk 0 1 2 3 4 5 6 7 sg (xb-xk) 1 1 0 -1 -1 -1 0 1 sg (yb-yk) 0 1 1 1 1 -1 -1 -1 Наименование направлений приведено на рисунке 1. 3 2 1 4 A 0 5 6 7 Рисунок 1. Наименование направлений вектора перемещения Zk. После каждого шага построения пути необходимо по вектору перехода Zk определить состояние очередного элемента dk (свободный или занятый) булево матрицы. Рассмотрим построение Н-пути. Для описания дискретного пространства, в котором строим путь, используем булеву матрицу С размером m( . Кроме того, для сокращения вычислений введем усеченную матрицу А размером m(l. Число строк в матрице А определяется шириной прокладываемого проводника в дискретах. При прокладке проводников шириной в один дискрет матрица А будет матрицой-строкой, только один элемент которой принимает единичное значение. Номер этого элемента определяется координатой xk анализируемого элемента dk. Состояние элементов описывается через булеву функцию , где ci,j – элемент матрицы С; ai - элемент матрицы-сторки А. Здесь через индекс j обозначается номер строки матрицы С, который определяется координатой yk элемента dk. Если V=1, то элемент dk занят, и построение пути прекращается. Дальнейшее построение осуществляется путем обхода препятствий, начиная с элемента dk-1, который будем называть элементом встречи с препятствием. При построении Р-пути распознавание состояния элемента выполняется в два этапа. На первом этапе определяем, принадлежит ли элемент dk какому-либо объекту, записанному в матрице С. Если элемент dk не принадлежит никакому объекту, то переходим к выполнению второго этапа, суть которого сводится к следующему: определяем состояние элементов, которые принадлежат одновременно Н- окрестностям элементов dk, dk-1. Таких элементов может быть только два, причем они расположены диагонально. Если оба элемента заняты, то построение пути из элемента dk-1 в dk запрещено. При построении пути в диагональных направлениях состояния элементов описывается булевой функцией , i=1, 3, 5, 7. (1) Булевы функции Vi, Vi-1, Vi 1 определяются при просмотреР-окрестности элемента dk. Если функция (1) равна нулю, то выбранный элемент свободный; в противном случае – занятый. Если очередной элемент dk булевой матрицы С, через который должен пройти путь занят, то из элемента dk-1, который назовем элементом встречи с препятствием (на рисунке 2 это элемент 1), начинается обход препятствия. Этап 2. Переход от элемента встречи с препятствием к следующему свободному элементу пути выполняются согласно правилу первого шага. Правило первого шага. Этап обхода препятствия начинается с элемента dk встречи с препятствием в направлении Zk, двоичный код которого определяется путем сложения кода предшествующего направления (Z’)k-1 с кодом 001 по модулю 8 при отрицательном направлении обхода препятствий, а при положительном обходе – с кодом 111.

Если выбранное направление запрещено, то принимаем первое возможное направление. При построении пути выполняется отрицательный (правый) и положительный (левый) обход всей группы препятствий, лежащих между конечными элементами пути. В этом случае у первого элемента встречи с препятствием путь разветвляется на два. По одному пути осуществляется обход препятствий справа, а по другому – слева. При построении Н-пути для обхода препятствий используется алгоритм Н-слежения, а при построении Р-пути – Р-слежение. При отрицательном направлении Р-слежения двоичный код приоритетного направления опреднляется соотношением . Если направление с высшим приоритетом запрещено, то выбирается первое возможное направление с низшим приоритетом. Определяемое соотношением , где – двоичный код чисел из последовательности 1, 2, ,8. Суммирование по модулю 8 выполняется при отрицательном направлении слежения, вычитание – при положительном. Важным моментом является определение элемента, в котором заканчивается обход препятствий и начинается построение пути в оптимальном направлении (по прямой к элементу db). Если в нужный момент не прекратить обход препятствий, то неизбежно зацикливание пути вокруг препятствий. Элемент пути, в котором прекращается обход препятствий, назовем элементом спуска. На рисунке 2 элементом спуска является элемент 19. Здесь приведен путь в лабиринте, построенный согласно этой методике от элемента da к элементу db. От элемента da до элемента 1, который является элементом встречи, выполняется построение пути согласно этапу 1. Обход препятствий начинается от элемента встречи 1 в отрицательном направлении (этап 2) и заканчивается элементом спуска 19. От элемента спуска 19 до конечного элемента пути выполняетсяэтап 1. Для определения элемента спуска пути предлагается следующий алгоритм: a) определяем двоичный код угла поворота вектора перехода относительно вектора Z’ из соотношения ; причем суммирование выполняется при отрицательном направлении обхода препятствий, вычитание – при положительном. b) В каждом элементе излома проверяем значение двоичного кода ak и направление построения пути в наилучшем направлении. Если ak(0 и направление обхода препятствий совпадает с наилучшим направлением построения пути, то элемент dk будет элементом спуска. В противном случае dk не является элементом спуска. Этап 3. Минимизация длинны пути сводится к построению выпуклого контура, описанного вокруг первоначального пути. Если нет возможности получить выпуклый контур из-за наличия препятствий, то строится сглаженный контур, т.е. контур, имеющий меньшую длину, чем первоначальный. Находим все элементы спуска первоначального пути и разбиваем его на отдельные участки, разграниченные элементами спуска. Последовательно минимизируем все участки пути. 1) Находим все элементы излома соответствующего участка пути, и если имеется не более одного излома, то он не подлежит минимизации если элементов излома два и более, то минимизация заключается в том, что строится новый путь Lн(da, dj) пути L(da, dj), где dj - элемент излома пути, самый близкий к конечному элементу.

Предложить способы улучшения алгоритма и программы. /Текст программы/ Задание 3 Есть ли смысл в следующем фрагменте программы? Есть ли ошибки? Пояснить. /Текст программы/ Задание 4 Сравнить два варианта программы: /Текст 1-го варианта/ /Текст 2-го варианта/ Задание 5 Разобраться в назначении и алгоритме программы. Выявить ошибки. Составить пример обращения к процедуре. Провести «разумную» трассировку. Определить эффективность и надежность программы в общепринятом смысле. Предложить способы улучшения алгоритма и программы. /Текст программы/ Работа по программам Au-pair («учись и работай») Под au-pair (в переводе с французского «в пару») подразумевается молодая девушка (в редких случаях молодой человек), которая должна будет выполнять роль гувернантки либо домработницы в европейских семьях. Иммиграционное законодательство некоторых стран Европы (Германия, Франция, Бельгия и др.) позволяют квалифицированным au-pair из Восточной Европы находиться в стране в течение 1 года. Au-pair пребывание не рассматривается как трудовая деятельность, а является межкультурной образовательной программой для содействия изучающим иностранные языки

1. Методы и алгоритмы компоновки, размещения и трассировки печатных плат

2. Алгоритм удаления циклов в графе вертикальных ограничений задачи трассировки многослойного канала

3. Реализация алгоритма обратной трассировки лучей для моделей с большим числом полигонов

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

5. Алгоритмы экономической (кадастровой) оценки городских земель и территориально-экономического зонирования

6. Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры
7. Информационные потоки в ЭВМ. Алгоритм работы процессора
8. Алгоритмы сортировки

9. Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных

10. Циклические алгоритмы

11. Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок схем на языке Turbo Pascal

12. Разработка системы задач (алгоритмы-программы) по дискретной математике

13. Применение метода частотных диаграмм к исследованиям устойчивости систем с логическими алгоритмами управления

14. Алгоритм компактного хранения и решения СЛАУ высокого порядка

15. Алгоритмы и протоколы маршрутизации

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

Папка для труда "Спортивное авто", 325х245 мм.
Размер: 325х245 мм. Материал: ткань.
322 руб
Раздел: Папки для труда
Машинка детская с полиуретановыми колесами "Бибикар спорт", красный.
Все еще не можете определиться, что подарить ребенку на торжество? Куклы и конструкторы уже негде складывать, а удивить малыша очень
2150 руб
Раздел: Каталки
Планшетик "Кто самый умный?".
Этот говорящий планшетик – прекрасный подарок для маленьких эрудитов! 200 умных вопросов, 20 игровых тем, 3 уровня – играй и узнавай много
445 руб
Раздел: Планшеты и компьютеры

17. Методы размещения и трассировки печатных плат на примере модуля памяти

18. Трассировка печатной платы

19. Сравнительный анализ нейросетевых реализаций алгоритмов распознавания образов

20. Генетический алгоритм

21. Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод

22. Модель управления конфликтными потоками в классе алгоритмов
23. Методы и алгоритмы построения элементов систем статистического моделирования
24. Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости

25. Интуитивное понятие алгоритма и его свойств

26. Градиентный алгоритм для систем независимости с отрицательными весами

27. Место цифровой рентгенографии в современном алгоритме лучевой диагностики

28. Принципы и особенности составления лекарственных алгоритмов

29. Алгоритм иммуногематологического исследования женщин во время беременности

30. Алгоритмы выполнения манипуляций

31. Алгоритм развития для науки

32. Об алгоритмах самоорганизации в задаче синтеза информационных технологий обработки сигналов

Фоторамка "Poster black" (70х100 см).
Рамка настенная может располагаться как вертикально, так и горизонтально. Для фотографий размером: 70х100 см. Материал: пластик.
460 руб
Раздел: Размер 50x60 и более
Демонстрационные шахматы, магнитные.
Об этих шахматах говорит само их название. Они предназначены для шахматных школ, кружков или секций. Основное преимущество
2295 руб
Раздел: Шахматы
Фоторамка "Asti" (30х40 см).
Рамка для фото формата 30х40 см. Материал: дерево. Материалы, использованные в изготовлении рамок, обеспечивают высокое качество хранения
431 руб
Раздел: Размер 30x40

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

34. Системный подход и алгоритм управления подготовкой студентов к духовно-просветительской деятельности

35. Алгоритм создания сценария рекламного радиоролика

36. Составление алгоритма расчета расхода сырья верхних трикотажных изделий

37. Образ государства как алгоритм политического поведения

38. Типовой алгоритм составления бюджета
39. СППР фінансового аналізу на базі алгоритмів нечіткої логіки
40. Постановка и разработка алгоритма решения задачи Учёт основных средств

41. Алгоритм и программа

42. Ликвидация вертикальных конфликтов межсоединений в канале перед трассировкой

43. Исполнитель алгоритмов – человек

44. Трассировка в коммутационном блоке на основе генетических процедур

45. Формализация понятия алгоритма

46. Анализ алгоритма вируса

47. Алгоритмы выделения контуров

48. Конфигурирование програмного обеспечения алгоритмов IGRP, EIGRP на маршрутизаторе Cisco

Шарики, 50 шт.
Шарики из мягкого пластика. Диаметр: 6 см. Цвет представлен в ассортименте, без возможности выбора.
342 руб
Раздел: Шары для бассейна
Папка для труда, А4.
Формат листов: А4. Материал: картон, текстиль. Товар в ассортименте, без возможности выбора! На фото представлен не весь ассортимент товара!
366 руб
Раздел: Папки-портфели, папки с наполнением
Карандаши цветные "Lyra Groove Slim", 12 цветов + точилка.
Карандаши с эргономичным захватом по всей длине. Диаметр грифеля 3,3 мм! Точилка. Уникальные карандаши с канавками! Запатентовано! Научите
540 руб
Раздел: 7-12 цветов

49. Понятие алгоритма

50. Разработка алгоритмов и программных средств подсистемы документооборота системы управления содержанием информационного сервера

51. Алгоритм сжатия "Unbuffered RLE"

52. Алгоритм «рамо»

53. Модификация алгоритма определения клик графа с параметрической адаптацией

54. Методика и алгоритмы контроля работоспособности и диагностики сейсмометрических каналов
55. Варианты алгоритма возведения в степень: повышение точности и ускорение
56. Алгоритм нисходящего разбора. Нисходящие распознаватели

57. Сравнительные характеристики трёх наиболее эффективных алгоритмов рисования отрезка

58. Циклические алгоритмы

59. Разработка программы, реализующей алгоритм шифрования ГОСТ 28147-89

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

61. Генетический алгоритм

62. Методы и алгоритмы построения элементов систем статистического моделирования

63. Математическая логика и теория алгоритмов

64. Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод

Подставка для ножей AK-210ST "Alpenkok", 11x22 см.
Размеры: 11х22 см. Подставка для ножей мраморной расцветки с черным наполнением. Материал корпуса: пластик. Внутренняя часть:
673 руб
Раздел: Подставки для ножей
Колокольчик декоративный "Узор", 8x13 см.
Цвет: белый. Материал: фарфор. Размер: 8x13 см.
355 руб
Раздел: Миниатюры
Горшок надувной для дома и авто "Baby-Krug", розовый.
Невероятно удобный надувной горшок был разработан при непосредственном участии квалифицированных медицинских работников и технических
489 руб
Раздел: Горшки обычные

65. Алгоритм внедрения управленческого абсолюта

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

67. Алгоритм ситуационного анализа для разрешения конфликтных ситуаций

68. Общий алгоритм оценки эффективности рекламной кампании

69. Горные породы, алгоритмы их определения

70. Алгоритм и его свойства
71. Алгоритм криптографического преобразования в режиме простой замены
72. Алгоритм работы программы "Консультант Плюс"

73. Алгоритми сортування

74. Алгоритмічні мови програмування

75. Алгоритмы вокруг нас

76. Алгоритмы и организация данных

77. Алгоритмы на графах. Кратчайшие расстояния на графах

78. Алгоритмы параллельных процессов при исследовании устойчивости подкрепленных пологих оболочек

79. Алгоритмы поиска подстроки в строке

80. Алгоритмы сжатия данных

Подставка для колец "Слоник", арт. 62258.
Регулярно удалять пыль сухой, мягкой тканью. Материал: металл (сплав цинка с покрытием золотой краской), стекло. Товар не подлежит
365 руб
Раздел: Подставки для украшений
Бортик Polini Basic (цвет: белый).
Боковой бортик для подростковой кровати Polini Basic Монстрики и Polini Basic Джунгли 180х90см. Размер: 180х950х16 мм.
977 руб
Раздел: Бортики в детскую кроватку
Подушка "MediumSoft Стандарт", 70х70 см.
Подушка Medium Soft Стандарт "Файберсофт". Наволочка - 100 % микрофайбер. Наполнитель - силиконизированное волокно
389 руб
Раздел: Размер 70х70 см

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

82. Алгоритмы численного решения задач

83. Використання генетичних алгоритмів для складання розкладу

84. Интеллектуальные информационные технологии и системы: генетические алгоритмы

85. Компрессия информации и упорядочение дерева по алгоритму Виттера

86. Методические проблемы изучения алгоритмов работы с величинами
87. Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів
88. Принципы разработки алгоритмов и программ для решения прикладных задач

89. Программирование на Delphi с алгоритмами и кодами

90. Програмна реалізація криптографічного алгоритму RC5

91. Проектування керуючих автоматів Мура та Мілі за заданою граф-схемою алгоритму

92. Разработка алгоритма работы интеллектуальной информационной системы "Расчет меню"

93. Реализация генетических алгоритмов нейрокомпьютерами

94. Розробка алгоритму операційного автомату, синтез керуючого автомату з жорсткою логікою типу Мілі

95. Создание цифрового образовательного ресурса "Задачник по языку программирования. Циклические алгоритмы"

96. Стандартная библиотека на С++: алгоритм

Увлекательная настольная игра "Турбосчет Форсаж".
Продолжение самой "хитовой" игры "Турбосчет", еще больше карт с условиями, еще больше "прокачиваем" устный
392 руб
Раздел: Математика, цифры, счет
Настольная игра "Имаджинариум".
Каждый игрок выбирает себе слона и набор карточек для голосования того же цвета, что и слон. Карточек для голосования семь. Вам пригодится
1750 руб
Раздел: Карточные игры
Картриджи чернильные "Cartridge Quink", синие, 5 штук.
Картриджи подходят для всех перьевых ручек Parker. Картриджи с чернилами позволяют легко и просто заправить перьевую ручку, при этом не
309 руб
Раздел: Чернила, тушь, штемпель

97. Структуры и алгоритмы обработки данных

98. Формализация понятия "алгоритм"

99. Генетические алгоритмы


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.