# Brenda Baker

Brenda Sue Baker est une informaticienne américaine. Elle est connue pour la technique dite de Baker des algorithmes d'approximation sur les graphes planaires, pour ses premiers travaux concernant sur la détection de la duplication de code et pour ses recherches sur le problème de bin packing bidimensionnels.

## Biographie

Baker fait ses études de premier cycle au Radcliffe College. Elle obtient un doctorat à l'université Harvard en 1973 sous la direction de Ronald V. Book ; sa thèse, intitulée Tree Transductions and Families of Tree Languages, porte sur des sujets de théorie des automates et des langages formels. Elle est ensuite instructrice et chercheuse Vinton-Hayes à la division d'ingénierie et de physique appliquée d'université de Harvard, lectrice invitée au département de génie électrique et d'informatique de l'université de Californie à Berkeley et professeure assistante au département de l'informatique et des sciences de la communication à l'université du Michigan. Plus tard, et principalement, elle travaille aux Laboratoires Bell, et devient finalement membre émérite du personnel technique.
Baker a épousé un autre informaticien des Bell Labs, Eric Grosse, qui deviendra plus tard le vice-président de Google pour l'ingénierie de la sécurité et de la confidentialité. Leur fils, Roger Baker Grosse, est également chercheur en informatique$^,$.

## Recherche

Les travaux de recherche de Brenda Baker concernent principalement les algorithmes et les outils logiciels. Plus précisément, elle travaille alors sur des problèmes concernant le string matching, les algorithmes combinatoires et les algorithmes d'approximation pour des problèmes NP-difficiles.
Dans le domaine des outils logiciels, elle est conceptrice d'outils pour analyser et comparer le code source et les exécutables compilés. Ces outils incluent les logiciels Dup et Pdiff, qui comparent des régions du code source pour déterminer s'il y a des segments répétés, ainsi que Exediff, qui permet la création de petits correctifs pour les exécutables sans nécessiter l'accès au code source à partir duquel ils ont été compilés.

## Publications (sélection)

* (en) Brenda S. Baker et Ronald V. Book, « Reversal-bounded multi-pushdown machines », Conference Record of 13th Annual Symposium on Switching and Automata Theory, Institute of Electrical & Electronics Engineers (IEEE),‎ 1972, p. 207–211 (DOI 10.1109/SWAT.1972.21).
* (en) Brenda S. Baker, E. G., Jr. Coffman et Ronald L. Rivest, « Orthogonal packings in two dimensions », SIAM Journal on Computing, vol. 9, n$^o$ 4,‎ 1980, p. 846–855 (DOI 10.1137/0209064, MR 592771, CiteSeer$^x$ 10.1.1.309.8883).
* (en) Brenda S. Baker, Eric Grosse et Conor S. Rafferty, « Nonobtuse triangulation of polygons », Discrete and Computational Geometry, vol. 3, n$^o$ 2,‎ 1988, p. 147–168 (DOI 10.1007/BF02187904 , MR 920700).
* (en) Brenda S. Baker, « Approximation algorithms for NP-complete problems on planar graphs », Journal of the ACM, vol. 41, n$^o$ 1,‎ 1994, p. 153–180 (DOI 10.1145/174644.174650 , MR 1369197, S2CID 9706753).
* (en) Brenda S. Baker, « On finding duplication and near-duplication in large software systems », Proceedings of 2nd Working Conference on Reverse Engineering, Institute of Electrical & Electronics Engineers (IEEE),‎ 1995, p. 86–95 (ISBN 978-0-8186-7111-1, DOI 10.1109/wcre.1995.514697, S2CID 11446831, CiteSeer$^x$ 10.1.1.133.6440).
* (en) Brenda S. Baker et Udi Manber, « Deducing Similarities in Java Sources from Bytecodes », Proceedings of the USENIX Annual Technical Conference,‎ 1998, p. 179–190.