假设我们有一组讲座，并预设了开始和结束时间。假设讲座一旦开始就会持续到结束为止、两个讲座不能同时进行、一个讲座可以在另一个讲座结束时开始，请设计一个贪婪算法能够在一个演讲厅里安排尽可能多的讲座。假设讲座[tex=0.429x1.214]adIpAOtu2Zm0WIyZC7drnQ==[/tex]的开始时间为[tex=0.786x1.071]3YamWgG8PBtTEWeMXui9+g==[/tex](这里[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]是指开始)，结束时间为[tex=0.786x1.071]7tqE5ZceH5PZa3J1RF9rtw==[/tex](这里[tex=0.5x0.786]WKYr2kz69xrVCyPvbyVG1w==[/tex]是指结束)。

2022-06-01

假设我们有一组讲座，并预设了开始和结束时间。假设讲座一旦开始就会持续到结束为止、两个讲座不能同时进行、一个讲座可以在另一个讲座结束时开始，请设计一个贪婪算法能够在一个演讲厅里安排尽可能多的讲座。假设讲座[tex=0.429x1.214]adIpAOtu2Zm0WIyZC7drnQ==[/tex]的开始时间为[tex=0.786x1.071]3YamWgG8PBtTEWeMXui9+g==[/tex](这里[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]是指开始)，结束时间为[tex=0.786x1.071]7tqE5ZceH5PZa3J1RF9rtw==[/tex](这里[tex=0.5x0.786]WKYr2kz69xrVCyPvbyVG1w==[/tex]是指结束)。

答案：

解：要采用贪婪算法来安排最多的讲座，即一个最优调度，我们需要确定在每一步如何选择增加哪个讲座。有很多准则可以用来在每一步选择一个讲座，这里我们选择那些与已选讲座没有重叠的讲座。比如，我们可以以最早开始时间为序来增加讲座，也可以以最短讲座时间为序来增加讲座，也可以以最早结束时间为序来增加讲座，或者可以用其他的准则。我们选择来考虑这些可能的准则。假设我们增加那个与已选讲座相容的讲座中开始时间最早的讲座。我们可以构造一个反例来证明这样的算法并非总是产生最优调度。例如，假定有三个讲座:第一个讲座上午8点开始中午12点结束，第二个讲座上午9点开始上午10点结束，而第三个讲座上午11点开始中午12点结束。我们首先选择第一个讲座，因为它开始得最早。但是一旦我们选择了第一个讲座，就不能选第二个或第三个讲座了，因为它们和第一个讲座有重叠。故该贪婪算法只选了一个讲座。这不是最优的，因为我们可以安排第二个和第三个讲座，这两个没有重叠。现在假设我们增加那个与已选讲座相容的讲座中持续时间最短的讲座。我们依然可以找到一个反例来证明这样的算法并非总是产生最优调度。为此，假定有三个讲座：第一个讲座上午8点开始上午9点15分结束，第二个讲座上午9点开始上午10点结束，而第三个讲座上午9点45分开始上午11点结束。我们选择第二个讲座，因为它是最短的只需要一小时。一旦我们选择了第二个讲座，就不能选第一个或第三个讲座了，因为没有一个和第二个讲座是不重叠的。故该贪婪算法只选了一个讲座。可是有可能选择两个讲座的，第一个和第三个讲座，这两个没有重叠。然后，可以证明如果我们在每一步选择那个与已选讲座相容的讲座中结束时间最早的讲座，我们就能安排最多的讲座。

举一反三

内容

0
6个顶点11条边的所有非同构的连通的简单非平面图有[tex=2.143x2.429]iP+B62/T05A6ZTM0eeaWiQ==[/tex]个，其中有[tex=2.143x2.429]ndZSw3zT0QTOVLVdoUto1Q==[/tex]个含子图[tex=1.786x1.286]J+vVZa2YaMpc6mJBbqVvWw==[/tex]，有[tex=2.143x2.429]lmhx48evnQMhi03NovPXig==[/tex]个含与[tex=1.214x1.214]kFXZ1uR8GjycbJx+Ts2kyQ==[/tex]同胚的子图。供选择的答案[tex=3.071x1.214]3KinXFh3SXhZ7nIe1y9KEV6aadxhhJWeEy6Dij1iObdMUZkY6ZA5J2dVVjPSuhEf[/tex]：(1) 1 ;(2) 2 ;(3) 3 ; (4) 4 ;(5) 5 ;(6) 6 ; (7) 7 ; (8) 8 。
1
学生辅导中心办了一系列学习方法的讲座。为评估这个系列讲座的效果。随机抽取了25个参加讲座的学生，调查了他们系列讲座开始前那个学期的[tex=2.214x1.0]0bF9yuj5cBfCVx3LHI5YCg==[/tex]和系列讲座结束后那个学期的[tex=2.214x1.0]0bF9yuj5cBfCVx3LHI5YCg==[/tex],从差异均值分布看，这25个学生提高了[tex=8.143x1.214]RZAF1mPCluevq0toctuxTg==[/tex]用以上数据来对系列讲座提高[tex=2.214x1.0]0bF9yuj5cBfCVx3LHI5YCg==[/tex]的效应进行估计。做点估计和[tex=1.857x1.143]6ct+iwoR4UNC8as2/Ebayw==[/tex]的区间估计。
2
从供选择的答案中选出填入叙述中的方框内的正确答案计算非同构的根树的个数(1) 2 个顶点非同构的根树有 [tex=2.143x2.429]rVbjoKgaBYChmT2nPEBA4Q==[/tex] 个(2) 3 个顶点非同构的根树有 [tex=2.143x2.429]ndZSw3zT0QTOVLVdoUto1Q==[/tex] 个(3) 4 个顶点非同构的根树有 [tex=2.143x2.429]lmhx48evnQMhi03NovPXig==[/tex] 个(4) 5 个顶点非同构的根树有 [tex=2.214x2.429]ZPUE0nZuXRHoore7NT++rQ==[/tex] 个供选择的答案[tex=6.071x1.286]GZbiT2P8T8KVyVUEWQpYyjIiVTkGekbnZrmhPI/Gp54=[/tex]：① 1; ② 2; ③ 3; ④ 4; ⑤ 5; ⑥ 6; ⑦ 7; ⑧ 8; ⑨ 9; ⑩ 10
3
证明:如果秩为[tex=0.5x0.786]U5O66aolbR1y5vuKrQbXNA==[/tex]的向量组可以由它的[tex=0.5x0.786]U5O66aolbR1y5vuKrQbXNA==[/tex]个向量线性表出，则这[tex=0.5x0.786]U5O66aolbR1y5vuKrQbXNA==[/tex]个向量构成这向量组的一个极大线性无关组.
4
证明：任意一个秩为[tex=0.5x0.786]U5O66aolbR1y5vuKrQbXNA==[/tex]的矩阵都可以表为[tex=0.5x0.786]U5O66aolbR1y5vuKrQbXNA==[/tex]个秩为1的矩阵之和。