{"id":290,"date":"2013-06-20T16:54:34","date_gmt":"2013-06-20T15:54:34","guid":{"rendered":"http:\/\/iww.inria.fr\/colloquium\/?p=290"},"modified":"2015-12-29T15:46:11","modified_gmt":"2015-12-29T14:46:11","slug":"jeffrey-shallit-the-frobenius-problem-and-its-generalizations","status":"publish","type":"post","link":"https:\/\/iww.inria.fr\/colloquium\/fr\/jeffrey-shallit-the-frobenius-problem-and-its-generalizations\/","title":{"rendered":"Jeffrey Shallit &#8211; The Frobenius Problem and Its Generalizations"},"content":{"rendered":"<h4>June 20, 2013<\/h4>\n<div id=\"attachment_293\" style=\"width: 152px\" class=\"wp-caption alignright\"><a href=\"http:\/\/iww.inria.fr\/colloquium\/files\/2015\/12\/shallit_jeffrey.jpg\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-293\" class=\" wp-image-293\" src=\"http:\/\/iww.inria.fr\/colloquium\/files\/2015\/12\/shallit_jeffrey.jpg\" alt=\"Jeffrey Shallit, David Cheriton School of Computer Science, Faculty of Math,  University of Waterloo.  Portrait by Chris Hughes\" width=\"142\" height=\"199\" srcset=\"https:\/\/iww.inria.fr\/colloquium\/files\/2015\/12\/shallit_jeffrey.jpg 154w, https:\/\/iww.inria.fr\/colloquium\/files\/2015\/12\/shallit_jeffrey-107x150.jpg 107w\" sizes=\"auto, (max-width: 142px) 100vw, 142px\" \/><\/a><p id=\"caption-attachment-293\" class=\"wp-caption-text\">Jeffrey Shallit, David Cheriton School of Computer Science, Faculty of Math, University of Waterloo.<br \/>Portrait by Chris Hughes<\/p><\/div>\n<p style=\"text-align: justify;\">The classical but oddly little-known Frobenius problem from number theory is the following: given a set of positive integers with greatest common divisor equal to 1, find the largest integer not representable as a non-negative integer linear combination of the set elements. This largest integer is called the Frobenius number. For example, the Frobenius number of 6, 9, and 20 is 43. In this talk I will survey some of the known results on this problem and its applications to computer science, and a new generalization of this problem to words (strings of symbols).<\/p>\n<p><em>Jeffrey Shallit (University of Waterloo, Canada)<\/em><\/p>\n<div style=\"position: relative; padding-bottom: 56.25%; padding-top: 10px; height: 0; overflow: hidden;\"><iframe loading=\"lazy\" style=\"position: absolute; top: 0; left: 0; width: 100%; height: 100%;\" src=\"https:\/\/www.canal-u.tv\/video\/inria\/embed.1\/the_frobenius_problem_and_its_generalizations.12691?width=100%&amp;height=100%\" width=\"550\" height=\"306\" frameborder=\"0\" scrolling=\"no\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/div>\n<p><a href=\"http:\/\/iww.inria.fr\/colloquium\/files\/2015\/12\/shallit.pdf\">Slides<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>June 20, 2013 The classical but oddly little-known Frobenius problem from number theory is the following: given a set of positive integers with greatest common divisor equal to 1, find the largest integer not representable as a non-negative integer linear combination of the set elements. This largest integer is called\u2026<\/p>\n<p> <a class=\"continue-reading-link\" href=\"https:\/\/iww.inria.fr\/colloquium\/fr\/jeffrey-shallit-the-frobenius-problem-and-its-generalizations\/\"><span>Continue reading<\/span><i class=\"crycon-right-dir\"><\/i><\/a> <\/p>\n","protected":false},"author":643,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,1],"tags":[89],"class_list":["post-290","post","type-post","status-publish","format-standard","hentry","category-12","category-tous","tag-shallit"],"_links":{"self":[{"href":"https:\/\/iww.inria.fr\/colloquium\/fr\/wp-json\/wp\/v2\/posts\/290","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/iww.inria.fr\/colloquium\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/iww.inria.fr\/colloquium\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/iww.inria.fr\/colloquium\/fr\/wp-json\/wp\/v2\/users\/643"}],"replies":[{"embeddable":true,"href":"https:\/\/iww.inria.fr\/colloquium\/fr\/wp-json\/wp\/v2\/comments?post=290"}],"version-history":[{"count":5,"href":"https:\/\/iww.inria.fr\/colloquium\/fr\/wp-json\/wp\/v2\/posts\/290\/revisions"}],"predecessor-version":[{"id":476,"href":"https:\/\/iww.inria.fr\/colloquium\/fr\/wp-json\/wp\/v2\/posts\/290\/revisions\/476"}],"wp:attachment":[{"href":"https:\/\/iww.inria.fr\/colloquium\/fr\/wp-json\/wp\/v2\/media?parent=290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/iww.inria.fr\/colloquium\/fr\/wp-json\/wp\/v2\/categories?post=290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/iww.inria.fr\/colloquium\/fr\/wp-json\/wp\/v2\/tags?post=290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}