Методология и средства разработки алгоритмов решения задач анализа и синтеза структур программного обеспечения и устройств вычислительной техники
Диссертация
При использовании в качестве базовой абстракции языка понятия «граф» появляется возможность многоуровневого преобразования описания алгоритмов: в операциях над графами, в операциях над множествами, в операциях над структурами данных с использованием универсального языка программирования и, наконец, в машинных командах над внутренними представлениями данных. Для каждого уровня описания существуют… Читать ещё >
Список литературы
- Алгоритмы и программы решения задач на графах и сетях / М.И. Не-чипуренко, В. К. Попков, С. М. Майнагашев и др. Новосибирск: Наука. Сиб. отделение, 1990. -515 с.
- Асанов М.О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ Регулярная и хаотическая динамика, 2001.-288 с.
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции: Пер. с англ. М.: Мир, 1978. — Т. 1.-611 с.
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции: Пер. с англ. M.: Мир, 1978. — Т. 2. — 487 с.
- Ахо A.B., Хопкрофт Д., Ульман Д. Д. Построение и анализ вычислительных алгоритмов: Пер. с англ. М.: Мир, 1978. — 536 с.
- Ахо A.B., Хопкрофт Д., Ульман Д. Д. Структуры данных и алгоритмы: Пер. с англ. М.: Издательский дом Вильяме, 2001. — 384 с.
- Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вища школа, 1981. — 168 с.
- Вениаминов Е.М., Ефимова Е. А. Элементы универсальной алгебры и ее приложений в информатике. М.: Научный мир, 2004. -168 с.
- Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Саратов: Изд-во Саратовского ун-та, 1983. — 120 с.
- П.Вирт Н. Алгоритмы+структуры данных=программы: Пер. с англ. -М.: Мир, 1985.-406 с.
- Глушков В.М. Теория автоматов и формальные преобразования микропрограмм // Кибернетика. 1965. — № 5 (6). — С. 1−10.
- Глушков В.М., Цейтлин Г. Е., Ющенко E.JI. Алгебра. Языки. Программирование. Киев: Наукова думка, 1978. — 389 с.
- Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов: Пер. с англ. -М.: Мир, 1981.-368 с.
- Грис. Д. Конструирование компиляторов для цифровых вычислительных машин: Пер. с англ. -М.: Мир, 1975. 544 с.
- Дал У., Дейкстра Э., Хоор К. Структурное программирование: Пер. с англ. М.: Мир, 1975. — 248 с.
- Евстигнеев В.А. Применение теории графов в программировании / Под ред. А. П. Ершова. М.: Наука. Гл. ред. физ.-мат. лит., 1985. — 352 с.
- Ершов А.П. Операторные алгоритмы. III (Об операторных схемах Янова) // Проблемы кибернетики (М.). 1968. — Вып. 20. — С. 25−43.
- Ершов А. П. Описание основных конструкций программирования // Проблемы кибернетики (М.). 1962. — Вып. 8. — С. 12−31.
- Ершов А.П. Современное состояние теории схем программ // Проблемы кибернетики (М.). 1973. — Вып. 27 (4). — С. 87−111.
- Зыков A.A. О некоторых свойствах линейных комплексов // Математический сборник. 1949. — Вып. 2 (24). — С. 163−188.
- Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. М.: Лаборатория Базовых Знаний, 2002. — 288 с.
- Иванова Г. С. Математические модели структур данных // Информационные технологии. 2006. — № 9. — С. 44−52.
- Иванова Г. С. Модели объектов задач структурного синтеза // Наука и образование. Инженерное образование: Эл. науч. издание. 2006. — № 12. (Номер гос. регистрации 420 600 025 053.)
- Иванова Г. С. Нумерация вершин управляющего графа для решения задачи его структуризации // Информационные технологии. 2005. — № 12. -С, 48−56.
- Иванова Г. С. Основы программирования: Учебник для вузов. М.: Изд-во МГТУ им. Н. Э. Баумана, 2004. — 416 с.
- Иванова Г. С. Способы представления структурных моделей // Наука и образование. Инженерное образование: Эл. науч. издание. 2007. — № 1. (Номер гос. регистрации 42 070 0025X003.)
- Иванова Г. С. Технология программирования: Учебник для вузов. -М.: Изд-во МГТУ им. Н. Э. Баумана, 2003. 320 с.
- Иванова Г. С. Формальная постановка задачи структуризации алгоритмов // Вестник Московского государственного технического университета им. Н. Э. Баумана. Приборостроение. 2005. — № 3(60). — С. 64−73.
- Иванова Г. С., Бакулина М. А. Автоматизация процесса разработки алгоритмов решения задач структурного синтеза на графах // Тез. докл. Международной научно-технической конференции М., 2003. — С. 166−167.
- Иванова Г. С., Домосканов A.A. Оптимизация управления динамическим распределением оперативной памяти. // Современные информационные технологии: Сб. докл. и сооб. Межвузовской юбилейной научно-технической конференции.-М., 2001. С. 6−13.
- Иванова Г. С., Ничушкина Т. Н. Проектирование синхронных интерфейсов интерактивных программных систем. // Научный вестник МГТУ ГА. Информатика. Прикладная математика. 2002. — № 55. — С. 33−37.
- Иванова Г. С., Ничушкина Т. Н., Пугачев Е. К. Объектно-ориентированное программирование: Учебник для вузов. М.: Изд-во МГТУ им. Н. Э. Баумана, 2003. — 366 с.
- Иванова Г. С., Тихонов Ю. В. Введение в МПролог: Практическое пособие для программистов. М.: Изд-во МГТУ, 1990. — 152 с.
- Калужнин JI.A. Что такое математическая логика? М.: Наука. Гл. ред. физ.-мат. лит., 1964. — 150 с.
- Касперски К. Техника оптимизации программ. Эффективное использование памяти. СПб.: БХВ — Петербург, 2003. — 464 с.
- Касьянов В.Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ — Петербург, 2003. — 1104 с.
- Касьянов В.Н. Оптимизирующие преобразования программ. М.: Наука. Гл. ред. физ.-мат. лит., 1988. — 336 с.
- Компаниец Р. П., Маньков Е. В., Филатов Н. Е. Системное программирование. Основы построения трансляторов: Уч. пособие. СПб.: Корона принт, 2000. — 256 с.
- Кнут Д. Искусство программирования для ЭВМ: Пер. с англ. 2-е изд. — М.: Издательский дом Вильяме, 2001. -Т.1 — 720 с.
- Кнут Д. Искусство программирования для ЭВМ: Пер. с англ. 2-е изд. — М.: Издательский дом Вильяме, 2001. — Т. 3. — 823 с.
- Компаниец Р.И., Маньков Е. В., Филатов Н. Е. Системное программирование. Основы построения трансляторов. СПб.: Корона принт, 2000. — 320 с.
- Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. — 960 с.
- Котов В.Е. Введение в теорию схем программ. Новосибирск: Наука, 1978.-256 с.
- Котов В.Е., Сабельфельд В. К. Теория схем программ. М.: Наука. Гл. ред. физ.-мат. лит., 1991. -248 с.
- Кофман А. Введение в прикладную комбинаторику. М.: Мир, 1981. -480 с.
- Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-427 с.
- Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. — 480 с.
- Лавров С.С. Программирование. Математические основы, средства, теория, — СПб.: БХВ-Петербург, 2001. 320 с.
- Липский В. Комбинаторика для программистов: Пер. с польск. М.: Мир, 1988.-213 с.
- Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов и др. М.: Наука, Гл. ред. физ.-мат. лит., 1990. — 384 с.
- Майерс Г. Надежность программного обеспечения: Пер. с англ. М.: Мир, 1980.-360 с.
- Мартынюк В.В. Об изменении порядка выполнения операторов в операторной схеме // ЦВТ и программирование. М.: Советское радио, 1967. -Вып. 2. — С. 67−72.
- Макконнелл Дж. Основы современных алгоритмов: Пер. с англ. М.: Техносфера, 2004. — 368 с.
- Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука. Гл. ред. физ.-мат. лит., 1971. — 416 с.
- Мелихов А.Н., Берштейн Л. С. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов-на-Дону: Из-во Ростовского униве-ситета, 1981. — 112 с.
- Мелихов А.Н., Берштейн Л. С., Курейчик В. М. Применение графов для проектирования дисретных устройств. М.: Наука, 1974. — 303 с.
- Мину М. Математическое программирование. Теория и алгоритмы. -М.: Наука, 1990.-488 с.
- Многоуровневое структурное проектирование программ: Теоретические основы, инструментарий / Е. Л. Ющенко, Г. Е. Цейтлин, В. П. Грицай и др. -М.: Финансы и статистика, 1989. 208 с.
- Морозов К.К., Одиноков В. Г., Курейчик A.M. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. М.: Радио и связь, 1983.-280 с.
- Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001.-304 с.
- Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов. М.: Изд-во МГТУ им. Н. Э. Баумана. — 2000. — 360 с.
- Овчинников В.А. Автоматизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: Учеб. для вузов. М.: Изд-во МГТУ им. Н. Э. Баумана, 2001. — 288 с.
- Овчинников В.А., Иванова Г. С. Информационно-логическая модель алгоритма // Вестник Московского государственного технического университета им. Н. Э. Баумана. Приборостроение. 2005. -№ 2(59). — С. 109−121.
- Овчинников В.А., Иванова Г. С. Проектно-исследовательская система решения задач структурного синтеза // Тез. докл. научно-технической конференции. М., 2000.-С. 41.
- Овчинников В.А., Иванова Г. С. Способы снижения вычислительной сложности реализации операций над множествами // Научный вестник МГТУ ГА. Информатика. Прикладная математика. 2002. — № 55. — С. 38−42.
- Овчинников В.А., Николаев К. В., Попов А. Ю. Исследование вычислительной сложности алгоритмов двоичной свертки схем ЭВМ // Вестник
- Московского государственного технического университета. Приборостроение. 1997. — № 2. — С. 113−120.
- Оре О. Теория графов. М.: Наука, 1980. — 336 с.
- Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. -М.: Мир, 1985. 512 с.
- Пасхавер И.С., Яблочник А. Л. Общая теория статистики / Под ред. М. М. Юзбашева. М.: Финансы и статистика, 1983. — 432 с.
- Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под ред. А. Матросова. СПб.: Питер, 2002. — 688 с.
- Попов А.Ю. Модели и алгоритмы автоматизированной декомпозиции схем ЭВМ: Дисс.. канд. техн. наук. М., 2004. — 136 с.
- Проектирование высокопроизводительного процессора обработки графов / С. М. Абрамов, A.B. Кондратьева, В. А. Роганов и др. // Информационные технологии. 2001. — № 3. — С. 7−10.
- Райли Д. Абстракция и структуры данных: Пер. с англ. М.: Мир, 1993.-752 с.
- Савельев А.Я., Овчинников В. А. Конструирование ЭВМ и систем: Учебник для вузов. М.: Высшая школа, 1989. — 312 с.
- Седжвик Р. Фундаментальные алгоритмы на С: Пер. с англ. СПб, ООО ДиаСофт, 2003. — 1136 с.
- Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики: Учебник для вузов. М. — Новосибирск: ИНФРА-М — Изд-во НГТУ, 2002.-280 с.
- Татт У. Теория графов: Пер. с англ. М.: Мир, 1988. — 424 с.
- Теоретические основы проектирования компиляторов / Ф. Льюис, Р. Розенкранц, Р. Стиринз: Пер. с англ. -М.: Мир, 1979. 654 с.
- Успенский В.А., Семенов А. Л. Теория алгоритмов: основные открытия и приложения. М.: Наука. Гл. ред. физ.-мат. лит., 1987. — 288 с.
- Харрари Ф. Теория графов: Пер. с англ. М.: Едиториал УРСС, 2003.-296 с.
- Хидитниеми С., Гудман С. Введение в разработку и анализ вычислительных алгоритмов: Пер. с англ. М. Мир, 1981 г. — 366 с.
- Цейтлин Г. Е. Формальные аспекты структурного программирования с GOTO // Программирование. 1984. — № 1. — С. 3−16.
- Цейтлин Г. Е. Формальная трансформация структурированных алгоритмов сортировки // Программирование. 1985. — № 2. — С. 88−100.
- Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики (М.).- 1958. -Вып. 1.-С. 75−109.
- Ashcroft Е., Manna Z. The translation of GOTO Programs to WHILE Programs // Proc. IFIP Congress 71- Lubljana (Yugoslavia), August 23−28 1971. -Amsterdam, 1972. -V. 1. P. 250−255.
- Baker B.S. An algorithm for structuring flowfraphs // J. of the ACM. -1977.-V. 24 ,№ i.p. 98−120.
- Behm C., Jacopini G. Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules // Comm. of ACM. 1966. — V. 9, № 5. — P. 366 371.
- Caldwell A., Kahng A., Markov I. Improved Algorithms for Hypergraph В? partitioning // Proc. Asia and South Pacific Design Automation Conf. Tokyo (Japan), 2000.-P. 661−666.
- Cifuentes C. A structuring Algorithm for Decompilation // Proceedings of the XIX Conf. Latinoamericana de Informatica. Buenos Aries (Argentina), 1993. -P. 267−276.
- Chang C-C., Cong J., Xie M. Optimality and Scalability of Existing Placement Algorithms // Proc. Asia and South Pacific Design Automation Conf. -Tokyo (Japan), 2003. P. 621−627.
- Coorer D.C. Behm and Jacopini’s reduction of flow charts // Comm. ACM. 1967. — V. 10, № 8. — P. 463−473.
- Dutt S., Deng W. VLSI Circuit Partitioning by Cluster-Removel Using Interactive Improvement Techniques // Proc. IEEE International Conf. on Computer-Aided Design. San Jose (USA), 1996. — P. 194−200.
- Earnest C.P., Balke K.G., Anderson J. Analysis of graphs by ordering of nodes // J. ACM. 1972. — Vol. 19, № 1. — P. 23−42.
- Erosa A.M., Henron L.J. Taming Control Flow: A structured Approach to Elimination GOTO Statements // Proc. IEEE International Conf. on Computer Languages. Toulouse (France), 1994. — P. 229−240.
- Flajolet Ph., Salvy B., Zimmermen P. Automatic Average-Case Analysis of Algorithms // Theoretical Computer Science. 1991. — Feb. — P. 37−109.
- Hauck S., Bordello G. An Evaluation of Bipartitioning Techniques // IEEE Transactions of Competer-Aided Design. 1997. — V.16, № 8. — P. 849 866.
- Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // J. of Parallel and Distributed Computing. 1998. — № 48 (1). — P. 96 129.
- Kosaraju S.R. Analysis of Structured Programs // J. Computer and System Sci. 1974. — V.9, № 2(3). — P. 232−255.
- Knuth D.E., Floyd R.W. Notes on avoiding GOTO statements // Inform. Processing Letters. 1971. — № 1. — P. 23−31.
- Ledgard H.K., Marcotty M.A. Genealogy of Control Structures // Communications ACM. 1975,-V. 18, № 11.-P. 629−639.
- Martin J.L. Generalized structured programming // AFIPS Conf. Proc. -Chicago, 1974,-V. 43.-P. 665−669.411
- Mills H.D. Mathematical foundation for structured programming // IBM Tech. Rep. 1972. — V. FSC-72−6012. — P. 34.
- Peter R. Graph schemata and Recursive Functionalb // Dialectica. -1958.-V.12, — P. 373−388.
- Peterson W.W., Kasami T., Tokura N. On the capabilities of the WHILE, REPEAT, and EXIT statements // Comm. ACM. 1973. — V. 16, № 8. -P. 503−512.
- Programming With Sets: An Introduction to SETL / Jacob T. Schwartz, R.B.K. Dewar, E. Dubinsky and etc. New York, 1986. — 127 pp.
- Ramshaw L. Eliminating goto’s while preserving program structure // J. ACM. 1988. — V. 35, № 4. — P. 893−920.
- Vitter J., Flajolet Ph. Average-Case Analyse of Algorithms and Data Structure // Handbook of Handbook of theoretical computer science: algorithms and complexity. 1991. — Vol. A. — P. 431 -524.
- Williams M.H. Generating structured flow diagrams: the nature of un-structuredness // Computer. 1977. — V. 20, № 1. — P.45−50.
- Williams M.H., Chen G. Restructuring Pascal programs containing goto statements// The Computer Journal. 1985. — V. 28, № 2. — P. 134−137.
- Yang X., Choi B., Sarrafzadeh M. Routability Driven White Space Allocation for Fixed-Diie Standart-Cell Placement // Proc. International Symposium on Physical Design. Del Mar (USA), 2002. — P. 42−49.- СРЕДСТВА и СИСТЕМЫ АВТОМАТИЗАЦИИ
- Закрытое акционерное общество «РТСофт»
- Ген.директор «РТСофт» д.т.н. Синенко О.В.1. АКТо внедрении результатов диссертационной работы к.т.н. доцента кафедры «Компьютерные системы и сети» МГТУ им. Н. Э. Баумана Ивановой Г. С.
- Зам.Генерального директора по проектному бизнесу Л^д С. А. Андрианов ifeim
- Технический Директор ББ АИУС Куцевич H.A.1. Ко4--!xSs-ож1. РБК СОФТ
- Адрес: 117 393, Москва, уя. Профсоюзная, 78- Е-лиі!- in! o:@t!A.o!iiu- Телефон:(095)363−1111- фаю: (951 363−1125- www.fDcsoH.ru
- Основные теоретические результаты диссертационной работы Ивановой Г. С. использованы при разработке математической модели адаптивного Интернет-сайта, как новой оригинальной составляющей, реально
- Лингвистические средства реализации и анализа алгоритмов, разработанные в диссертационной работе Ивановой Г. С., включены в проект очередной версии системы управления контентом RBC Contents 5,01.
- На базе системы управления контентом RBC Contents предыдущих версий компанией РБК СОФТ реализовано более 600 сайтов, из которых не менее 20 кольца сайтов.
- Ожидаемый экономический эффект от внедрения положений диссертационной работы Ивановой Г. С. может составить не мене 200 000 рублей на один адаптивный Интернет-сайт.
- Данный акт не может служить основанием для финансовых претензии. используемой в проектах РБК СОФТ, модели кольца сайтов.
- Генеральный директор ЗАО «РБ.КХОФТ"1. А.В. Кузовкинл
- Практическое применение разработанной системы позволило на 30−40% сократить время разработки алгоритмического и программного обеспечения блока обработки сигналов и управления многофункциональной РДС и блока управления бортового Фурье-спектрометра,
- Начальник отдела НИИ ИСУ МГТУ им. Н. Э. Баумана, к.т.н., Ст. научный сотрудник
- A.C. Романовский С. Ю. Чухров
- МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ имени Н. Э. Баумана
- Факультет Информатика и системы управления
- J07005, Москва, 2-я Бауманская ул., 5 Телекс 417 661, Для телеграмм- Москва, ГРАЧ Гед. (095) 267−65−37 Факс (095) 267−79−851. УТВЕРЖДАЮ»
- Руководитель НУК ИСУ — К4ГТУ -ще Г1. В. А. Матвеев 2007 г. 1. АКТоб использовании результатов диссертационной работы к.т.н. доцента кафедры «Компьютерные системы и сети» МГ’ТУ им. Н. Э. Баумана Ивановой Г'.С,
- Практическое применение указанных методик и средств позволило существенно повысить уровень подготовки студентов в области разработки программного обеспечения и средств автоматизации проектирования.
- Заведующий кафедрой «Компьютерные системы и сети» д.т.п. профессор -------«» В.В. Сюзев
- Заместитель заведующего кафедрой по учебной работе 7к.т.н. доцент /^Гу^----.^-- А.М. Губарь