稳定匹配问题
参考:经典算法问题——稳定匹配(Stable Matching)
Gale-Shapley Algorithms简称“GS 算法”,也称为延迟接受算法。是 Gale 和 Shapley 为了寻找一个稳定匹配而设计出的市场机制。运行时间在算法输入的大小上是线性的。根据其使用方式,它可以找到对匹配一侧的参与者或另一侧的参与者最佳的解决方案。
问题描述给出一个 $n$ 个男性的集合 $M$,和 $n$ 个女性的集合 $W$,其中:
每位男性根据对所有女性的心仪程度从高至低进行排名;
每位女性根据对所有男性的心仪程度从高至低进行排名。
根据以上条件,我们需要找到一个“稳定匹配”。
基本概念匹配 Matching匹配 $S$ 是一个包含有序数对 $m-w$ 的集合,其中 $m \in M$ 且$w \in W$,其中:
每个男性最多出现在一个数对中;
每个女性最多出现在一个数对中。
完美匹配 Perfect matching如果 $\left| S \right|=\left| M \right|=\left| W \right|=n$ 则匹配$S$是完美匹配,也就是说,男女数量相等且都 ...
COMPSCI 316: Lectrue 3
Lectrue 3
Understand computer security
Understand human aspect of security
Understand network security
Next, we can build on these three to understand cyber security
OSI 安全架构OSI 安全架构分为三大类,即安全攻击、安全机制和安全服务。
安全攻击(Security attack)安全攻击是指个人或实体企图获得未经授权的访问以破坏或损害系统、网络或设备的安全性。
被动攻击(Passive attack):试图从系统中学习或利用信息,但不影响系统资源。
窃听(Release of message content / disclosure):攻击者在两方不知情的情况下拦截和收听他们之间的通信。
流量分析(Traffic analysis):攻击者分析网络流量模式和元数据以收集有关系统、网络或设备的信息。入侵者无法读取消息,只能了解加密的模式和长度。可以使用多种技术执行流量分析,例如网络流量分析或协议分析。
主动攻 ...
1-计算机安全概述
参考书目:Computer Security: Principles and Practice, Fourth Edition, by William Stallings and Lawrie Brown. Pearson Higher Ed USA. ISBN 1292220635.
计算机安全的概念计算机安全(computer security)的定义保证信息系统资产的机密性、完整性以及可用性的措施和控制方法,其中资产包括硬件、软件、固件、以及要处理、存储和通信的信息
机密性、完整性和可用性一起被并称为 CIA 三元组
机密性(confidentiality)保持对信息访问和披露的限制,包括对个人隐私和专有信息保护的措施。机密性缺失是指非授权的信息披露
换言之机密性是指个人对资产的访问与披露具有控制能力,在未经许可或授权的情况下,他人无法访问相关数据。在现实中的实例就包括高校学生的教务系统,学生可以在登陆后查阅到个人的考试成绩等隐私信息,而他人在未经许可的情况下无法访问或知晓相关数据。
机密性包含两个相关概念:
数据机密性:确保隐私或机密信息不被非授权的个人利用,或被泄露给非授权 ...
集乐-统一多媒体文件资源管理器
项目地址:https://github.com/Ywrby/JiLe
摘要随着互联网的发展与短视频等流媒体展示分享方式的普及,如何同时进行多种多媒体文件资源的管理与分类逐渐成为困扰人们进行文件管理的主要问题。本项目为解决上述问题,设计了一款多媒体集成管理器,采用前后端分离的方式,使用 Electron 和 Vue.js 作为前端框架,Springboot 作为后端框架。项目主要模块分为电子书管理模块,图片管理模块以及影视资源管理模块。项目基本功能主要有:文件元数据编辑,文件标签操作,文件夹同步,高级文件搜索,本地文件操作,瀑布流展示,文件分享,应用内预览,页面自动截图,拟物播放器等。最后对系统进行了综合测试与结果分析,结果表明:项目交互性良好,兼容性高,实现了目标功能。具有实际应用意义。
系统详细设计通过对项目整体进行可行性分析与需求分析,项目设计的基本方向和功能内容相对明确,项目以普通用户为设计视角,详细介绍对应功能与界面的设计和实现。
系统总体架构设计项目总体架构设计采用前后端分离的设计模式,前端使用 Electron 和 Vue.js 作为前端开发框架,同时使用 Node.js ...
集乐-统一多媒体文件资源管理器-开发记录
开发初衷市面上常见的多媒体资源管理器并不少见,比如很有名的本地电子书管理工具-Calibre,图片管理工具-Eagle,以及音频爱好者喜爱的foobar2000。它们在各自的领域内都完美解决了诸多痛点,但人的需求是在不断变化的,互联网的环境也是在不断发生改变的。
作为一名仓鼠党,很多时候面对资源的收集与整理都会手足无措,起初多媒体文件数量相对较少的情况下,可以采用较为随意的管理方式对文件进行管理,但随着文件资源数量的增加,如果没有或缺乏一个合理的文件管理方式就会导致文件之间关系混乱,渐渐地,自己也会疲于维护与管理。而避免这种问题的方式就是通过文件管理工具对我们收集的资源或文件进行统一管理。
理想的情况是我们在软件使用初期定义我们的行为习惯,后续我们只需要将所有文件统一化的保存,工具就会帮我们进行统一的管理。这种管理方式在Calibre中就有所体现,我们在初次使用过程中定义电子书的保存地址,同时定义我们的元数据链接,后续我们在保存电子书的过程中就可以自动帮我们利用元数据链接(豆瓣,亚马逊等)获取电子书基本信息,从而进行统一管理。
而现有的多媒体文件资源管理器应用虽然数量众多,但有些在功能 ...
IndexedDB浏览器数据库基本概念
参考文档:https://www.cnblogs.com/chenjun1/p/11644866.html
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119<template> <div class="scroll-y"> <div class="mb-2">IndexDbDemo.vue</div> <button @click="addData()">增加数据</button> <br ...
25-两级页表
两级页表单级页表的问题某计算机系统按字节寻址,支持32位的逻辑地址,采用分页存储管理,页面大小为4KB,页表项长度为4B。
4KB = $2^{12}B$,因此页内地址要用12位表示,剩余20位表示页号。因此,该系统中用户进程最多有220页。相应的,一个进程的页表中,最多会有220 = 1M = 1,048,576个页表项,所以一个页表最大需要220*4B=$2^{22}B$,共需要$2^{22}/2^{12}=2^{10}$个页框存储该页表。
根据页号查询页表的方法:K号页对应的页表项存放位置=页表始址+K*4要在所有的页表项都连续存放的基础上才能用这种方法找到页表项
需要专门给进程分配$2^{10}=1024$个连续的页框来存放它的页表
同时根据局部性原理可知,很多时候,进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。
问题一:页表必须连续存放,因此当页表很大时,需要占用很多个连续的页框。解决方法:我们在解决“进程在内存中必须连续存储问题”时将进程地址空间分页,并为其建立一张页表,记录各页面的存放位置。同样的思路也可用于解决“页表必须连续存放 ...
24-基本分页存储管理
非连续分配管理方式-基本分页存储管理从之前文章介绍的两种连续分配管理方式中我们可以看到:
固定分区分配:缺乏灵活性,会产生大量的内部碎片,内存利用率很低
动态分区分配:会产生大量外部碎片,虽然可以用紧凑技术处理,但时间成本会增加
考虑到连续分配方式的缺陷,人们考虑到如果可以将一个进程分散然后分别装入到不相邻分区中就可以更加高效利用内存,基于这一思想,产生了“非连续分配方式”也成为离散分配方式
把“固定分区分配”改造为“非连续分配”假设进程A大小为23MB,但是每个分区大小只有10MB,如果进程只能占用一个分区,那显然放不下。
解决思路:如果允许进程占用多个分区,那么可以把进程拆分成10MB+10MB+3MB三个部分,再把这三个部分分别放到三个分区中(这些分区不要求连续)…
进程A的最后一个部分是3MB,放入分区后会产生7MB的内部碎片。如果每个分区大小为2MB,那么进程A可以拆分成11*2MB +1MB共12个部分,只有最后一部分1MB占不满分区,会产生1MB的内部碎片。显然,如果把分区大小设置的更小一些,内部碎片会更小,内存利用率会更高。
上面这种思想就是“基本分页存储管理” ...
23-内存空间的分配与回收
连续分配管理方式
连续分配:指系统为用户进程分配的必须是一个连续的内存空间
单一连续分配在单一连续分配方式中,内存被分为系统区和用户区。
系统区通常位于内存的低地址部分,用于存放操作系统相关数据
用户区用于存放用户进程相关数据。内存中只能有一道用户程序,用户程序独占整个用户区空间。
优缺点
优点:实现简单,无外部碎片,可以采用覆盖技术扩充内存,不一定需要内存保护机制
缺点:只能用于单用户,单任务的操作系统中,有内部碎片,存储器利用率极低
内部碎片:分配给某进程的内存区域中,如果有些部分没有用上,这些内存部分就被称为“内部碎片”
固定分区分配20世纪60年代出现了支持多道程序的系统,为了能在内存中装入多道程序,且这些程序之间又不会相互干扰,于是将整个用户空间划分为若干个固定大小的分区,在每个分区中只装入一道作业,这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。
固定分区分配又可以细分为分区大小相等与分区大小不等两种情况
针对分区大小不等的情况,系统为了维护分区状态以及管理各个分区,需要建立一个数据结构–分区说明表:
分区号
大小(MB)
起始地址(M) ...
22-内存空间扩充(覆盖与交换)
覆盖技术早期计算机内存很小,因此经常出现内存大小不够使用的情况,因此人们引入了覆盖技术,用来解决“程序大小超过物理内存总和”的问题
覆盖技术的思想在于,将程序分为多个段(多个执行模块),常用的模块常驻在内存中,不常用的模块在需要时调入,使用后调出。实现这种功能还需要将内存划分为固定区和若干个覆盖区
需要常驻在内存的模块进入固定区后就不再调出,直到整个程序运行结束,不常用的模块在需要时调入覆盖区,用不到时调出
以上图为例,A模块作为需要常驻的模块,在程序开始运行后就进入常驻区,直到程序运行结束。B,C模块只能由A调用,并且不可能同时调用,所以B,C共用一个覆盖区,覆盖区大小由最大模块决定,而D模块只能由B模块调用,E,F模块只能由C模块调用,显而易见,DEF三个模块同一时间只可能有一个运行,所以DEF可以共用一个覆盖区,同时由最大的程序D决定覆盖区大小
这种覆盖技术的缺点在于:必须由程序员声明覆盖结构,操作系统完成自动覆盖。对用户不透明,增加了用户编程负担。覆盖技术只用于早期的操作系统中,现在已成为历史。
交换技术交换(对换)技术的设计思想:内存空间紧张时,系统将内存中某些进程暂时换出 ...