×

Loading...

事实上这个问题有个隐形的属性几乎没有书讲过,那就是多余的resource从代数的角度来说必须是等于 a= (p -sup[acuirable resource]) mod p, 且a>=50% useable resource.

我当年读研时候具体研究过这个问题。

即能拿满的resource状态下,其剩余resource在哲学家modulus状态下必须超过一半的acquirable resource才行,且resource 数不能是maximum acquirable的倍数。举个糖炒栗子:

7个哲学家,7个筷子,acquirable resource是2, 那么最大 sup[acquirable resource]其实是 6个筷子, 那么7(p)-6=1 mod 7, 且 1=50% * 2(筷子能工作的数)。

也就是说如果resource和需求者,从代数上不符合这个式子的时候,resource分配反而是很容易的,举个例子,如果是8个哲学家,8个筷子,那么每次间隔拿筷子2个,根本不用semaphore,recursive decision就可以,因为这个时候8(p)-8=0 mod 8, 因为和2是4倍偶数关系(resource数 8 是acquirable (2)的4倍)。

这个问题有一个极值讨论的问题,就是什么状态下,resource调度是个recursive最深问题,我记得当时做过一个模公式,有一个sup极值的状态的。并且还有很多特例的,比如3个时候,反而不需要深度recursive分配resource,所有拿起的等待即可,我记得好像有个公式是如果gcd(p(3),2)=1的时候是这个状态。

这个问题的深入讨论非常复杂。

Sign in and Reply Report

Replies, comments and Discussions:

  • 工作学习 / 学科技术 / 离散数学和线性代数这两门课我是逃课过来的,现在一点印象没有了,哪位好心人给我补补课做IT没这俩门课我损失了什么?
    • 对大腕们来说一定是缺之不可,对我们这样的小混混就没有那么重要。我们连因式分解都不会,不一样吃IT饭,炒股读财报,数数蜡烛线?
      • 那你和我是站在台下听讲的。
        • 你比我段位高,是站在台下听讲的。我是猫在讲台背后反着听的,所以全不得要领
    • 当然有损失了!上这门课有年轻漂亮的美眉,你失去了搭讪聊天和发展的机会
      • 这个回答跟离散也不沾边啊
    • 损失了40万?
      • step by step please
    • 损失了吹牛的资格,我们讨论离散数学是怎么离散的你可能插不上嘴呀
      • 你起个头,看我能不能接上。会不会在实际工作中把这些知识不知不觉的补上了
        • 好吧,讨论一下现在码工经常要用的Dining philosophers problem,你怎么理解的,我招人的时候一般都会问
          • hold 叉子是 exclusive lock,
            先到先得,而且有queue排队等待。得到一个叉子的Lock 后再等下一个叉子的lock,用完放下 (release lock). 后台有进程监视deadlock 杀掉其中一个,这是数据库的解决方案。五个哲学家是个例可以有更优化的算法。我这么理解对吗?另外这跟离散数学有关系吗
            • 有很多种方法,对于问题的最优算法用到了Mathematical logic,Combinatorics,Graph Theory,间接用到Game Theory
              • 我好奇那些靠刷 leecode进大厂拿40w的考不考这个。
            • 事实上这个问题有个隐形的属性几乎没有书讲过,那就是多余的resource从代数的角度来说必须是等于 a= (p -sup[acuirable resource]) mod p, 且a>=50% useable resource. +1

              我当年读研时候具体研究过这个问题。

              即能拿满的resource状态下,其剩余resource在哲学家modulus状态下必须超过一半的acquirable resource才行,且resource 数不能是maximum acquirable的倍数。举个糖炒栗子:

              7个哲学家,7个筷子,acquirable resource是2, 那么最大 sup[acquirable resource]其实是 6个筷子, 那么7(p)-6=1 mod 7, 且 1=50% * 2(筷子能工作的数)。

              也就是说如果resource和需求者,从代数上不符合这个式子的时候,resource分配反而是很容易的,举个例子,如果是8个哲学家,8个筷子,那么每次间隔拿筷子2个,根本不用semaphore,recursive decision就可以,因为这个时候8(p)-8=0 mod 8, 因为和2是4倍偶数关系(resource数 8 是acquirable (2)的4倍)。

              这个问题有一个极值讨论的问题,就是什么状态下,resource调度是个recursive最深问题,我记得当时做过一个模公式,有一个sup极值的状态的。并且还有很多特例的,比如3个时候,反而不需要深度recursive分配resource,所有拿起的等待即可,我记得好像有个公式是如果gcd(p(3),2)=1的时候是这个状态。

              这个问题的深入讨论非常复杂。

              • 钦佩你的学术专研精神 +1
    • 如果你从事的是一般的应用开发,而不是理论研究或开创性的具有一定深度的系统软件开发,尤其是不涉及数据库或密码方面的研究开发,那大概率啥也没损失....多了解一些现成的算法包/子程序的使用即可
    • 你损失什么我不清楚,反正我班女生让我晚上去她家帮她补习离散数学,她爸妈出差不在家,一个人害怕,我摇摇头说我没时间明天还要考英语呢。 +1
      • 三果想XB损失了几个亿!
    • 同样是IT,别人一只眼睛上班,一只眼睛发贴回贴,你得等到五点半下班才能发帖,别人都吃饭去了。这就是区别。
      • I can complete the work in 4 hours, but I choose to deep dive to give more value to the company.
    • 这两门课都很重要
    • 建议在你的RESUME中老老实实写明 “离散数学和线性代数这两门课我是逃课过来的”,
      • 很好!老板见了这简历指令HR必须招进来,可以安插到公司监事会,这样的诚实员工不会随便欺骗老板,用着放心.....
    • 那你肯定没上后面的矢量分析,没事,你的损失就是少掉了几根头发
      • 哈哈,少掉头发算是损失,那多掉头发是得益what?
      • 矢量分析目前美加大学基本全都放到微分几何,微分流形的课程里顺带讲的。并不单独分一门学科,没有必要。 +1
        • how about "gradient, divergence, curl"?
          • 微分流形里一并讲完的。作为张量的一些应用来讲,比如grad其实就是多元微分的jacobian matrix而已,当然大部分grad都只在R^n->R,而div是每个标准张量作用于张量标准字函数的偏导之和,相当于说取偏导之和。 +1
            • 有道理。空间<——>场,紧密相联
    • 离散数学这个狗屁课,前几堂课我觉得是小菜一碟,然后就再也没听明白过 +1
      • 学完判断复杂的if else 就够了,其他的也用不上
    • 现代理解3d空间运算还是很重要的,游戏编程,那些3d坐标的换算,我还是专门回去把矩阵计算复习了一遍才勉强看懂
        • 欧几里德空间不需要很强想象力,有一般生活常识想学都应该学得进去