|
||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[21]
4-2 Недостающее число Массив А[1. .га] содержит все целые числа от 0 до га, кроме одного. Чтобы найти пропущенное число, можно отмечать во вспомогательном массиве В [О . .га] все числа, встречающиеся в А, и затем посмотреть, какое число не отмечено (всё вместе требует времени О (га)). При этом использование элемента массива А в качестве индекса считается элементарной операцией. Наложим такое дополнительное ограничение на доступ к массиву А: за одно действие мы можем посмотреть заданный бит заданного элемента массива А. Покажите, что и при таких ограничениях мы можем найти пропущенное число за время О (га). 4-3 Время передачи параметров В этой книге мы предполагаем, что передача параметров занимает постоянное время, даже если передаваемый параметр - массив. В большинстве языков программирования это так и есть, поскольку передаётся не сам массив, а указатель на него. Но возможны и другие варианты. Сравним три способа передачи массивов в качестве параметров: 1.Массив передается как указатель за время 0(1). 2.Массив копируется за время Q(N), где N - размер массива. 3.В процедуру передаётся только та часть массива, которая будет в ней использоваться. При этом требуется время 0(g - р + 1), если передаётся участок А\р. .q]. а.Рассмотрим рекурсивный алгоритм двоичного поиска числа в упорядоченном массиве (упр. 1.3-5). Каково будет время его работы при каждом из указанных способов передачи параметра? (Аргументами рекурсивной процедуры являются искомый элемент и массив, в котором осуществляется поиск.) б.Проведите такой анализ для алгоритма Merge-Sort из раздела 1.3.1. 4-4 Ещё несколько рекуррентных соотношений Укажите возможно более точные асимптотические верхние и нижние оценки для Т(п) в каждом из указанных ниже примеров. Предполагается, что Т(п) - константа при га 8. а. Т(п) = ЗГ(га/2) + га lgra. Задачи к главе 4 73 б.Т(п) = ЗТ(га/3 + 5) + га/2. в.ТЫ) = 2Г(та/2) + га/lgra. г.Г(га) = Г(га - 1) + 1/га. д.Г(га) = Г(га - 1) + lg га. е.Г(га) = у/гаГ(у/га) + га. 4-5 Переход от степеней к произвольным аргументам Пусть мы получили оценку для ТЫ) ПРИ всех га, являющихся степенями некоторого целого Ь. Как распространить её на произвольные га? а.Пусть ТЫ) и h(n) - монотонно возрастающие функции, определённые для произвольных положительных аргументов (не обязательно целых), причём ТЫ) h(n) Для всех га, являющихся степенями целого числа Ь > 1. Пусть известно, кроме того, что h «растёт достаточно медленно»: h(n) = 0(h(n/b)) Докажите, что ТЫ) = 0(h(n)). б.Пусть для функции Г выполнено соотношение ТЫ) = аТ(п/Ь) + f(n) ПРИ п > гао! пусть а 1, 6 > 1 и /(га) монотонно возрастает. Пусть ТЫ) монотонно возрастает при га гао, и при этом Г(гао) аТ(по/Ь) +/Ыо) Докажите, что ТЫ) монотонно возрастает. в.Упростите доказательство теоремы 4.1 для случая монотонной и «достаточно медленно растущей» функции /(га). Воспользуйтесь леммой 4.4. 4-6 Числа Фибоначчи Числа Фибоначчи определяются соотношением (2.13). Здесь мы рассмотрим некоторые их свойства. Для этого определим производящую функцию (generating function), определяемую как формальный степенной ряд (formal power series) оо Т = £ Ftzl = 0 + z + z2 + 2z3 + 3z4 + 5z5 + 8z6 + 13/ + ... 8 = 0 а.Покажите, что T(z) = z ~\~ zT(z) + z2T(z). б.Покажите, что Tlz) 1/1 1 - z - г2 (1 - <z) (1 - (pz) д/5 \ 1 - <£z 1 - (/5,2 где 1 + V5 ¥> == 1,61803... и £= 1 ~ = -0,61803... Глава 4 Гекуррентные соотношения в. Покажите, что оо n*) = i-rW-?)z% 8 = 0 V5V г.Докажите, что Fi при i > 0 равно ближайшему к <р>1 /\/Ъ целому числу. (Указание: \ф\ < 1.) д.Докажите, что -F8+2 <~рг для всех г 0. 4-7 Тестирование микросхем Имеется га одинаковых микросхем, способных проверять друг друга; некоторые из них исправны, некоторые - нет. Для проверки пара микросхем вставляется в специальную плату, после чего каждая из них сообщает о состоянии соседа. Исправная микросхема при этом никогда не ошибается, а неисправная может дать любой ответ. Ответ АОтвет ВРезультат В исправнаА исправнаобе хорошие или обе плохие В исправнаА неисправнахотя бы одна неисправна В неисправнаА исправнахотя бы одна неисправна В неисправнаА неисправнахотя бы одна неисправна а.Покажите, что если больше половины микросхем плохие, то попарное тестирование не позволит узнать наверняка, какие именно микросхемы плохи (они смогут нас обмануть). б.Пусть нужно найти хотя бы одну хорошую микросхему из га штук, из которых больше половины исправных. Покажите, что достаточно [га/2] попарных тестов, чтобы свести задачу к аналогичной задаче половинного размера. в.Пусть исправно больше половины микросхем. Покажите, что можно найти все хорошие микросхемы за О (га) попарных тестов. (Воспользуйтесь рекуррентным соотношением.) [Эту задачу можно переформулировать в иных терминах: имеется га одинаковых на вид предметов, но на самом деле они относятся к нескольким категориям. Есть прибор, который по двум предметам проверяет, одинаковы ли они. Известно, что предметы некоторой категории составляют большинство. Надо найти представитель этого большинства за О (га) сравнений. Помимо рекуррентного решения, эта задача имеет простое итеративное решение. Заведём коробку, в которой будем накапливать одинаковые предметы, а также урну, куда можно выкидывать предметы. Перекладываем непросмотренные элементы в коробку или урну, поддерживая такое свойство: среди невыкинутых искомые составляют большинство.] |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||||||||||||||||||