Структуры данных и алгоритмы (1021739), страница 99
Текст из файла (страница 99)
УПРАВЛЕНИЕ ПАМЯТЬЮа) первый подходящий;б) самый подходящий.12.2. Рассмотрим следующий вариант динамической памяти, в котором "чистые"участки обозначают используемую память, а участки, помеченные буквами, —неиспользуемую, т.е. пустую.О100200300500Укажите последовательности запросов, которые можно удовлетворить, еслииспользовать стратегииа) первого подходящего, но не самого подходящего;б) самого подходящего, но не первого подходящего.*12.3. Допустим, что используется экспоненциальный метод близнецов с размерамиблоков 1, 2, 4, 8 и 16 в динамической памяти размером 16. Если поступает запрос на блок размером п при 1 < п < 16, то необходимо выделить блок разме1ром 2', где 2'" < п < 2'. Неиспользуемую часть блока (если таковая имеется)нельзя использовать для удовлетворения любого другого запроса.
Если нуженблок размером 2' при i < 4 и такого свободного блока в динамической памяти+1нет, то сначала находится блок размером 2' и расщепляется на две равные+1части. Если блока размером 2' также нет, тогда сначала находится и расщеп+2ляется свободный блок размером 2' , и т.д.
Если оказывается, что необходимсвободный блок размером 32, то следует признать, что удовлетворить поступивший запрос не удалось. В данном упражнении предполагается, что нельзяобъединять смежные свободные блоки в динамической памяти.Существуют последовательности запросов а ь а2, ... , а„, сумма которых меньше 16,причем последний запрос в таких последовательностях удовлетворить невозможно. Рассмотрим, например, последовательность 5, 5, 5.
Первый запрос приводит к расщеплению начального блока размером 16 на две части размером 8,причем одна из них используется для удовлетворения поступившего запроса.Оставшийся свободный блок размером 8 удовлетворяет второй запрос, но дляудовлетворения третьего запроса свободного пространства уже нет.Найдите последовательность а1( a2, ...
, ап целых чисел (необязательно одинаковых) из интервала от 1 до 16, сумма которых по возможности минимальна, но если эту последовательность рассматривать как последовательность запросов на блоки размеров а\, а^, ... , ап, то последний запрос удовлетворить невозможно. Поясните, почему эту последовательность запросовневозможно удовлетворить, а любую последовательность, сумма которойокажется меньше, можно.12.4. Рассмотрим задачу уплотнения памяти для блоков одинакового размера. Допустим, каждый блок состоит из поля данных и поля указателя.
Допустимтакже, что уже помечены все используемые в настоящее время блоки. Пустьэти блоки находятся в области памяти, расположенной между адресами а и Ь.Необходимо поменять местоположение всех блоков, занятых данными, так,чтобы они занимали непрерывный участок памяти, начиная с адреса а.
Перемещая блок, следует помнить, что необходимо скорректировать поле указателялюбого блока, указывающее на перемещаемый блок. Разработайте алгоритмуплотнения таких блоков.12.5. Рассмотрим массив размера п. Разработайте алгоритм циклического сдвигапротив часовой стрелки всех элементов в таком массиве на k позиций, используя только фиксированную дополнительную память, объем которой независит от k и п. Совет. Проанализируйте, ~что произойдет, если переставитьв обратном порядке первые k элементов, последние п - k элементов и, наконец, весь массив.УПРАЖНЕНИЯ36712.6. Разработайте алгоритм замены вложенной строки символов у, принадлежащейстроке хуг, на другую вложенную строку у', используя для этого как можноменьшее количество дополнительной памяти.
Какова временная сложность(время выполнения) этого алгоритма и сколько для него необходимо памяти?12.7. Напишите программу получения копии заданного списка. Какова временнаясложность этого алгоритма и сколько для него необходимо памяти?12.8. Напишите,программу, которая проверяла бы идентичность двух списков.Какова временная сложность этого алгоритма и сколько для него необходимо памяти?12.9. Реализуйте алгоритм Морриса для уплотнения динамической памяти (см.раздел 12.6).* 12.10. Разработайте схему выделения памяти применительно к ситуации, когда память выделяется и освобождается блоками длиной 1 и 2. Перечислите преимущества и недостатки такого алгоритма.Библиографические примечанияЭффективное управление памятью — центральная проблема, которую решаютразработчики многих языков программирования, в том числе Snobol [30], Lisp [74],APL [56] и SETL [98].
В [80] и [86] обсуждают методы управления памятью в контексте компиляции языков программирования.Выделение памяти по методу близнецов было впервые описано в [62]. Методблизнецов с числами Фибоначчи рассмотрен в работе [48].Изящный алгоритм маркировки, предназначенный для использования в процедуре чистки памяти, был разработан Питером Дойчем (Peter Deutsch) [25], а такжеШорром и Уэйтом (Schorr and Waite) [97]. Схема уплотнения динамической памяти,изложенная в разделе 12.6, заимствована из статьи [77].В работах [90] и [91] анализирует объем памяти, требующийся для работы алгоритмов динамического выделения памяти.
В [92] представлен алгоритм ограниченного рабочего пространства (bounded workspace algorithm) для копирования циклических структур. Решение упражнения 12.5 можно найти в [32].368ГЛАВА 12. УПРАВЛЕНИЕ ПАМЯТЬЮСписок литературы1. Адельсон-Вельский Г. М., Ландис Е. М. (1962). Один алгоритм организации информации. Докл. АН СССР, 146, с. 263-266.2. Aho, А. V., М. R. Garey, and J.
D. Ullman (1972). The transitive reduction of adirected graph, SIAM J. Computing 1:2, pp. 131-137.3. Aho, A. V., J. E. Hopcroft, and J. D. Ullman (1974). The Design and Analysis ofComputer Algorithms, Addison-Wesley, Reading, Mass. (Русский перевод: Ахо А.,Хоркрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М., "Мир", 1979.)4.
Aho, А. V., and N. J. A. Sloane (1973). Some doubly exponential sequences,Fibonacci Quarterly, 11:4, pp. 429-437.5. Aho, A. V., and J. D. Ullman (1977). Principles of Compiler Design, AddisonWesley, Reading, Mass.6. Bayer, R., and E. M. McCreight (1972). Organization and maintenance of largeordered indices, Acta Informatica 1:3, pp. 173-189.7. Bellman, R. E. (1957). Dynamic Programming, Princeton University Press,Princeton, N. J. (Русский перевод: Беллман Р. Динамическое программирование. — М., ИЛ, 1960.)8. Bentley, J. L.
(1982). Writing Efficient Programs, Prentice-Hall, Englewood Cliffs, N. J.9. Bentley, J. L., D. Haken, and J. B. Saxe (1978). A general method for solvingdivide-and-conquer recurrences, CMU-CS-78-154, Dept. of CS, Carnegie-MellonUniv., Pittsburg, Pa.10. Berge, C. (1957). Two theorems in graph theory, Proc. National Academy ofSciences 43, pp. 842-844.11.
Berge, C. (1958). The Theory of Graphs and its Applications, Wiley, N. Y. (Русскийперевод: Берж С. Теория графов и ее применение. — М., ИЛ, 1962.)12. Birtwistle, G. М., O.-J. Dahl, В. Myhrhaug, and К. Nygaard (1973). SIMULABegin, Auerbach Press, Philadelphia, Pa.13. Blum, M., R. W. Floyd, V. R. Pratt, R. L. Rivest, and R. E. Tarjan (1972). Timebounds for selection, J. Computer and System Sciences 7:4, pp. 448-461.14. Boruvka, 0. (1926).
On a minimal problem, Prace Moraske Pridovedecke Spolecnosti3:3, pp. 37-58.15. Brooks, F. P. (1974). The Mythical Man Month, Addison-Wesley, Reading, Mass.16. Carter, J. L., and M. N. Wegman (1977). Universal classes of hash functions, Proc.Ninth Annual ACM Symp. on Theory of Computing, pp. 106-112.17. Cheriton, D., and R. E. Tarjan (1976). Finding minimum spanning trees, SIAM J.Computing 5:4, pp. 724-742.18. Cocke, J., and F. E. Allen (1976). A program data flow analysis procedure, Comm.ACM 19:3, pp.
137-147.19. Coffman, E. G. (ed.) (1976). Computer and Job Shop Scheduling Theory, John Wileyand Sons, New York.20. Comer, D. (1979). The ubiquitous B-tree, Computing Surveys 11, pp. 121-137.21. Cooley, J. M., and J. W. Tukey (1965). An algorithm for the machine calculation ofcomplex Fourier series, Math. Сотр. 19, pp. 297-301.22. DBTG (1971). CODASYL Data Base Task Group April 1971 Report, ACM, New York.M23. Demers, A., and J.
Donahue (1979). Revised report on RUSSELL, TR79-389, Dept.of Computer Science, Cornell Univ., Ithaca, N. Y.24. Deo, N. (1975). Graph Theory with Applications to Engineering and ComputerScience, Prentice-Hall, Englewood Cliffs, N. J.25. Deutsch, L. P., and D. G. Bobrow (1966). An efficient incremental automaticgarbage collector, Comm.
ACM 9:9, pp. 522-526.26. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs,Numerische Mathematik 1, pp. 269-271.27. Edmonds, J. (1965). Paths, trees, and flowers, Canadian J. Math 17, pp. 449-467.28. Even, S. (1980). Graph Algorithms, Computer Science Press, Rockville, Md.29. Even, S., and O.
Kariv (1975). An O(n2'5) algorithm for maximum matching ingeneral graphs, Proc. IEEE Sixteenth Annual Symp. on Foundations of ComputerScience, pp. 100-112.30. Farber, D., R. E. Griswold, and I. Polonsky (1964). SNOBOL, a string manipulationlanguage, J.ACM 11:1, pp. 21-30.31. Fischer, M. J. (1972). Efficiency of equivalence algorithms, in Complexity ofComputer Computations (R. E.
Miller and J. W. Thatcher, eds.), pp. 153-168.32. Fletcher, W., and R. Silver (1966). Algorithm 284: interchange of two blocks ofdata, Comm. ACM 9:5, p. 326.33. Floyd, R. W. (1962). Algorithm 97: shortest path, Comm. ACM 5:6, p. 345.34. Floyd, R. W. (1964). Algorithm 245: treesort 3, Comm. ACM 7:12, p. 701.35.
Floyd, R. W., and A. Smith (1973). A linear time two-tape merge, Inf. Processingletters 2:5, pp. 123-126.36. Ford, L. R., and S. M. Johnson (1959). A tournament problem, Amer. Math.Monthly 66, pp. 387-389.37. Frazer, W. D., and A. C. McKellar (1970). Samplesort: a sampling approach tominimal tree storage sorting, J. ACM 17:3, pp. 496-507.38. Fredkin, E. (I960).
Trie memory, Comm. ACM 3:9, pp. 490-499.39. Friend, E. H. (1956). Sorting on electronic computer systems, J. ACM 3:2, pp. 134-168.40. Fuchs, H., Z. M. Kedem, and S. P. Uselton (1977). Optimal surface reconstructionusing planar contours, Comm. ACM 20:10, pp. 693-702.41. Garey, M.
R., and D. S. Johnson (1979). Computers and Intractability: a Guide tothe Theory of NF'-Completeness, Freeman, San Francisco. (Русский перевод: ГэриM., Джонсон Д.С. Вычислительные машины и трудноразрешимые задачи. — М.,"Мир", 1982.)42. Geschke, С. M., J. H. Morris, Jr., and E. H. Satterthwaite (1977).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
