🗊 Презентация Дискретная математика. Множество

Категория: Математика
Нажмите для полного просмотра!
Дискретная математика. Множество, слайд №1 Дискретная математика. Множество, слайд №2 Дискретная математика. Множество, слайд №3 Дискретная математика. Множество, слайд №4 Дискретная математика. Множество, слайд №5 Дискретная математика. Множество, слайд №6 Дискретная математика. Множество, слайд №7 Дискретная математика. Множество, слайд №8 Дискретная математика. Множество, слайд №9 Дискретная математика. Множество, слайд №10 Дискретная математика. Множество, слайд №11 Дискретная математика. Множество, слайд №12 Дискретная математика. Множество, слайд №13 Дискретная математика. Множество, слайд №14 Дискретная математика. Множество, слайд №15 Дискретная математика. Множество, слайд №16 Дискретная математика. Множество, слайд №17 Дискретная математика. Множество, слайд №18 Дискретная математика. Множество, слайд №19 Дискретная математика. Множество, слайд №20 Дискретная математика. Множество, слайд №21 Дискретная математика. Множество, слайд №22 Дискретная математика. Множество, слайд №23 Дискретная математика. Множество, слайд №24 Дискретная математика. Множество, слайд №25 Дискретная математика. Множество, слайд №26 Дискретная математика. Множество, слайд №27 Дискретная математика. Множество, слайд №28 Дискретная математика. Множество, слайд №29 Дискретная математика. Множество, слайд №30 Дискретная математика. Множество, слайд №31 Дискретная математика. Множество, слайд №32 Дискретная математика. Множество, слайд №33 Дискретная математика. Множество, слайд №34 Дискретная математика. Множество, слайд №35 Дискретная математика. Множество, слайд №36 Дискретная математика. Множество, слайд №37 Дискретная математика. Множество, слайд №38 Дискретная математика. Множество, слайд №39 Дискретная математика. Множество, слайд №40 Дискретная математика. Множество, слайд №41 Дискретная математика. Множество, слайд №42 Дискретная математика. Множество, слайд №43 Дискретная математика. Множество, слайд №44 Дискретная математика. Множество, слайд №45 Дискретная математика. Множество, слайд №46 Дискретная математика. Множество, слайд №47 Дискретная математика. Множество, слайд №48 Дискретная математика. Множество, слайд №49 Дискретная математика. Множество, слайд №50 Дискретная математика. Множество, слайд №51 Дискретная математика. Множество, слайд №52 Дискретная математика. Множество, слайд №53 Дискретная математика. Множество, слайд №54 Дискретная математика. Множество, слайд №55 Дискретная математика. Множество, слайд №56 Дискретная математика. Множество, слайд №57 Дискретная математика. Множество, слайд №58 Дискретная математика. Множество, слайд №59 Дискретная математика. Множество, слайд №60 Дискретная математика. Множество, слайд №61 Дискретная математика. Множество, слайд №62 Дискретная математика. Множество, слайд №63 Дискретная математика. Множество, слайд №64 Дискретная математика. Множество, слайд №65 Дискретная математика. Множество, слайд №66 Дискретная математика. Множество, слайд №67 Дискретная математика. Множество, слайд №68 Дискретная математика. Множество, слайд №69 Дискретная математика. Множество, слайд №70 Дискретная математика. Множество, слайд №71 Дискретная математика. Множество, слайд №72 Дискретная математика. Множество, слайд №73 Дискретная математика. Множество, слайд №74 Дискретная математика. Множество, слайд №75 Дискретная математика. Множество, слайд №76 Дискретная математика. Множество, слайд №77 Дискретная математика. Множество, слайд №78 Дискретная математика. Множество, слайд №79 Дискретная математика. Множество, слайд №80 Дискретная математика. Множество, слайд №81 Дискретная математика. Множество, слайд №82 Дискретная математика. Множество, слайд №83 Дискретная математика. Множество, слайд №84 Дискретная математика. Множество, слайд №85 Дискретная математика. Множество, слайд №86 Дискретная математика. Множество, слайд №87 Дискретная математика. Множество, слайд №88 Дискретная математика. Множество, слайд №89 Дискретная математика. Множество, слайд №90 Дискретная математика. Множество, слайд №91 Дискретная математика. Множество, слайд №92 Дискретная математика. Множество, слайд №93 Дискретная математика. Множество, слайд №94 Дискретная математика. Множество, слайд №95 Дискретная математика. Множество, слайд №96 Дискретная математика. Множество, слайд №97 Дискретная математика. Множество, слайд №98 Дискретная математика. Множество, слайд №99 Дискретная математика. Множество, слайд №100 Дискретная математика. Множество, слайд №101 Дискретная математика. Множество, слайд №102 Дискретная математика. Множество, слайд №103 Дискретная математика. Множество, слайд №104 Дискретная математика. Множество, слайд №105 Дискретная математика. Множество, слайд №106 Дискретная математика. Множество, слайд №107 Дискретная математика. Множество, слайд №108 Дискретная математика. Множество, слайд №109 Дискретная математика. Множество, слайд №110 Дискретная математика. Множество, слайд №111 Дискретная математика. Множество, слайд №112 Дискретная математика. Множество, слайд №113 Дискретная математика. Множество, слайд №114 Дискретная математика. Множество, слайд №115 Дискретная математика. Множество, слайд №116 Дискретная математика. Множество, слайд №117 Дискретная математика. Множество, слайд №118 Дискретная математика. Множество, слайд №119 Дискретная математика. Множество, слайд №120 Дискретная математика. Множество, слайд №121 Дискретная математика. Множество, слайд №122 Дискретная математика. Множество, слайд №123 Дискретная математика. Множество, слайд №124 Дискретная математика. Множество, слайд №125 Дискретная математика. Множество, слайд №126 Дискретная математика. Множество, слайд №127 Дискретная математика. Множество, слайд №128 Дискретная математика. Множество, слайд №129 Дискретная математика. Множество, слайд №130 Дискретная математика. Множество, слайд №131 Дискретная математика. Множество, слайд №132 Дискретная математика. Множество, слайд №133 Дискретная математика. Множество, слайд №134 Дискретная математика. Множество, слайд №135 Дискретная математика. Множество, слайд №136 Дискретная математика. Множество, слайд №137 Дискретная математика. Множество, слайд №138 Дискретная математика. Множество, слайд №139 Дискретная математика. Множество, слайд №140 Дискретная математика. Множество, слайд №141 Дискретная математика. Множество, слайд №142 Дискретная математика. Множество, слайд №143 Дискретная математика. Множество, слайд №144 Дискретная математика. Множество, слайд №145 Дискретная математика. Множество, слайд №146 Дискретная математика. Множество, слайд №147 Дискретная математика. Множество, слайд №148 Дискретная математика. Множество, слайд №149 Дискретная математика. Множество, слайд №150 Дискретная математика. Множество, слайд №151 Дискретная математика. Множество, слайд №152 Дискретная математика. Множество, слайд №153 Дискретная математика. Множество, слайд №154 Дискретная математика. Множество, слайд №155 Дискретная математика. Множество, слайд №156 Дискретная математика. Множество, слайд №157 Дискретная математика. Множество, слайд №158 Дискретная математика. Множество, слайд №159 Дискретная математика. Множество, слайд №160 Дискретная математика. Множество, слайд №161 Дискретная математика. Множество, слайд №162 Дискретная математика. Множество, слайд №163 Дискретная математика. Множество, слайд №164 Дискретная математика. Множество, слайд №165 Дискретная математика. Множество, слайд №166 Дискретная математика. Множество, слайд №167 Дискретная математика. Множество, слайд №168 Дискретная математика. Множество, слайд №169 Дискретная математика. Множество, слайд №170 Дискретная математика. Множество, слайд №171 Дискретная математика. Множество, слайд №172 Дискретная математика. Множество, слайд №173 Дискретная математика. Множество, слайд №174 Дискретная математика. Множество, слайд №175 Дискретная математика. Множество, слайд №176 Дискретная математика. Множество, слайд №177 Дискретная математика. Множество, слайд №178 Дискретная математика. Множество, слайд №179 Дискретная математика. Множество, слайд №180 Дискретная математика. Множество, слайд №181 Дискретная математика. Множество, слайд №182 Дискретная математика. Множество, слайд №183 Дискретная математика. Множество, слайд №184 Дискретная математика. Множество, слайд №185 Дискретная математика. Множество, слайд №186 Дискретная математика. Множество, слайд №187 Дискретная математика. Множество, слайд №188 Дискретная математика. Множество, слайд №189 Дискретная математика. Множество, слайд №190 Дискретная математика. Множество, слайд №191 Дискретная математика. Множество, слайд №192 Дискретная математика. Множество, слайд №193 Дискретная математика. Множество, слайд №194 Дискретная математика. Множество, слайд №195 Дискретная математика. Множество, слайд №196 Дискретная математика. Множество, слайд №197 Дискретная математика. Множество, слайд №198 Дискретная математика. Множество, слайд №199 Дискретная математика. Множество, слайд №200 Дискретная математика. Множество, слайд №201 Дискретная математика. Множество, слайд №202 Дискретная математика. Множество, слайд №203 Дискретная математика. Множество, слайд №204 Дискретная математика. Множество, слайд №205 Дискретная математика. Множество, слайд №206 Дискретная математика. Множество, слайд №207 Дискретная математика. Множество, слайд №208 Дискретная математика. Множество, слайд №209 Дискретная математика. Множество, слайд №210 Дискретная математика. Множество, слайд №211 Дискретная математика. Множество, слайд №212 Дискретная математика. Множество, слайд №213 Дискретная математика. Множество, слайд №214 Дискретная математика. Множество, слайд №215 Дискретная математика. Множество, слайд №216 Дискретная математика. Множество, слайд №217 Дискретная математика. Множество, слайд №218 Дискретная математика. Множество, слайд №219 Дискретная математика. Множество, слайд №220 Дискретная математика. Множество, слайд №221 Дискретная математика. Множество, слайд №222 Дискретная математика. Множество, слайд №223 Дискретная математика. Множество, слайд №224 Дискретная математика. Множество, слайд №225 Дискретная математика. Множество, слайд №226 Дискретная математика. Множество, слайд №227 Дискретная математика. Множество, слайд №228 Дискретная математика. Множество, слайд №229 Дискретная математика. Множество, слайд №230 Дискретная математика. Множество, слайд №231 Дискретная математика. Множество, слайд №232 Дискретная математика. Множество, слайд №233 Дискретная математика. Множество, слайд №234 Дискретная математика. Множество, слайд №235 Дискретная математика. Множество, слайд №236 Дискретная математика. Множество, слайд №237 Дискретная математика. Множество, слайд №238 Дискретная математика. Множество, слайд №239 Дискретная математика. Множество, слайд №240 Дискретная математика. Множество, слайд №241 Дискретная математика. Множество, слайд №242 Дискретная математика. Множество, слайд №243 Дискретная математика. Множество, слайд №244 Дискретная математика. Множество, слайд №245 Дискретная математика. Множество, слайд №246 Дискретная математика. Множество, слайд №247 Дискретная математика. Множество, слайд №248 Дискретная математика. Множество, слайд №249 Дискретная математика. Множество, слайд №250 Дискретная математика. Множество, слайд №251 Дискретная математика. Множество, слайд №252 Дискретная математика. Множество, слайд №253 Дискретная математика. Множество, слайд №254 Дискретная математика. Множество, слайд №255 Дискретная математика. Множество, слайд №256 Дискретная математика. Множество, слайд №257 Дискретная математика. Множество, слайд №258 Дискретная математика. Множество, слайд №259 Дискретная математика. Множество, слайд №260 Дискретная математика. Множество, слайд №261 Дискретная математика. Множество, слайд №262 Дискретная математика. Множество, слайд №263 Дискретная математика. Множество, слайд №264 Дискретная математика. Множество, слайд №265 Дискретная математика. Множество, слайд №266 Дискретная математика. Множество, слайд №267 Дискретная математика. Множество, слайд №268 Дискретная математика. Множество, слайд №269 Дискретная математика. Множество, слайд №270 Дискретная математика. Множество, слайд №271 Дискретная математика. Множество, слайд №272 Дискретная математика. Множество, слайд №273 Дискретная математика. Множество, слайд №274 Дискретная математика. Множество, слайд №275 Дискретная математика. Множество, слайд №276 Дискретная математика. Множество, слайд №277 Дискретная математика. Множество, слайд №278 Дискретная математика. Множество, слайд №279 Дискретная математика. Множество, слайд №280 Дискретная математика. Множество, слайд №281 Дискретная математика. Множество, слайд №282 Дискретная математика. Множество, слайд №283 Дискретная математика. Множество, слайд №284 Дискретная математика. Множество, слайд №285 Дискретная математика. Множество, слайд №286 Дискретная математика. Множество, слайд №287 Дискретная математика. Множество, слайд №288 Дискретная математика. Множество, слайд №289 Дискретная математика. Множество, слайд №290 Дискретная математика. Множество, слайд №291 Дискретная математика. Множество, слайд №292 Дискретная математика. Множество, слайд №293 Дискретная математика. Множество, слайд №294 Дискретная математика. Множество, слайд №295 Дискретная математика. Множество, слайд №296 Дискретная математика. Множество, слайд №297 Дискретная математика. Множество, слайд №298 Дискретная математика. Множество, слайд №299 Дискретная математика. Множество, слайд №300 Дискретная математика. Множество, слайд №301 Дискретная математика. Множество, слайд №302 Дискретная математика. Множество, слайд №303 Дискретная математика. Множество, слайд №304 Дискретная математика. Множество, слайд №305 Дискретная математика. Множество, слайд №306 Дискретная математика. Множество, слайд №307 Дискретная математика. Множество, слайд №308 Дискретная математика. Множество, слайд №309 Дискретная математика. Множество, слайд №310 Дискретная математика. Множество, слайд №311 Дискретная математика. Множество, слайд №312 Дискретная математика. Множество, слайд №313 Дискретная математика. Множество, слайд №314 Дискретная математика. Множество, слайд №315 Дискретная математика. Множество, слайд №316 Дискретная математика. Множество, слайд №317 Дискретная математика. Множество, слайд №318 Дискретная математика. Множество, слайд №319 Дискретная математика. Множество, слайд №320 Дискретная математика. Множество, слайд №321 Дискретная математика. Множество, слайд №322 Дискретная математика. Множество, слайд №323 Дискретная математика. Множество, слайд №324 Дискретная математика. Множество, слайд №325 Дискретная математика. Множество, слайд №326 Дискретная математика. Множество, слайд №327 Дискретная математика. Множество, слайд №328 Дискретная математика. Множество, слайд №329 Дискретная математика. Множество, слайд №330 Дискретная математика. Множество, слайд №331 Дискретная математика. Множество, слайд №332 Дискретная математика. Множество, слайд №333 Дискретная математика. Множество, слайд №334 Дискретная математика. Множество, слайд №335 Дискретная математика. Множество, слайд №336 Дискретная математика. Множество, слайд №337 Дискретная математика. Множество, слайд №338 Дискретная математика. Множество, слайд №339 Дискретная математика. Множество, слайд №340 Дискретная математика. Множество, слайд №341 Дискретная математика. Множество, слайд №342 Дискретная математика. Множество, слайд №343 Дискретная математика. Множество, слайд №344 Дискретная математика. Множество, слайд №345 Дискретная математика. Множество, слайд №346 Дискретная математика. Множество, слайд №347 Дискретная математика. Множество, слайд №348 Дискретная математика. Множество, слайд №349 Дискретная математика. Множество, слайд №350 Дискретная математика. Множество, слайд №351 Дискретная математика. Множество, слайд №352 Дискретная математика. Множество, слайд №353 Дискретная математика. Множество, слайд №354 Дискретная математика. Множество, слайд №355 Дискретная математика. Множество, слайд №356 Дискретная математика. Множество, слайд №357 Дискретная математика. Множество, слайд №358 Дискретная математика. Множество, слайд №359 Дискретная математика. Множество, слайд №360 Дискретная математика. Множество, слайд №361 Дискретная математика. Множество, слайд №362 Дискретная математика. Множество, слайд №363 Дискретная математика. Множество, слайд №364 Дискретная математика. Множество, слайд №365 Дискретная математика. Множество, слайд №366 Дискретная математика. Множество, слайд №367 Дискретная математика. Множество, слайд №368 Дискретная математика. Множество, слайд №369 Дискретная математика. Множество, слайд №370 Дискретная математика. Множество, слайд №371 Дискретная математика. Множество, слайд №372 Дискретная математика. Множество, слайд №373 Дискретная математика. Множество, слайд №374 Дискретная математика. Множество, слайд №375 Дискретная математика. Множество, слайд №376 Дискретная математика. Множество, слайд №377 Дискретная математика. Множество, слайд №378 Дискретная математика. Множество, слайд №379 Дискретная математика. Множество, слайд №380 Дискретная математика. Множество, слайд №381 Дискретная математика. Множество, слайд №382 Дискретная математика. Множество, слайд №383 Дискретная математика. Множество, слайд №384 Дискретная математика. Множество, слайд №385 Дискретная математика. Множество, слайд №386 Дискретная математика. Множество, слайд №387 Дискретная математика. Множество, слайд №388 Дискретная математика. Множество, слайд №389 Дискретная математика. Множество, слайд №390 Дискретная математика. Множество, слайд №391 Дискретная математика. Множество, слайд №392 Дискретная математика. Множество, слайд №393 Дискретная математика. Множество, слайд №394 Дискретная математика. Множество, слайд №395 Дискретная математика. Множество, слайд №396 Дискретная математика. Множество, слайд №397 Дискретная математика. Множество, слайд №398 Дискретная математика. Множество, слайд №399 Дискретная математика. Множество, слайд №400 Дискретная математика. Множество, слайд №401 Дискретная математика. Множество, слайд №402 Дискретная математика. Множество, слайд №403 Дискретная математика. Множество, слайд №404 Дискретная математика. Множество, слайд №405 Дискретная математика. Множество, слайд №406 Дискретная математика. Множество, слайд №407 Дискретная математика. Множество, слайд №408 Дискретная математика. Множество, слайд №409 Дискретная математика. Множество, слайд №410 Дискретная математика. Множество, слайд №411 Дискретная математика. Множество, слайд №412 Дискретная математика. Множество, слайд №413 Дискретная математика. Множество, слайд №414 Дискретная математика. Множество, слайд №415 Дискретная математика. Множество, слайд №416 Дискретная математика. Множество, слайд №417 Дискретная математика. Множество, слайд №418 Дискретная математика. Множество, слайд №419 Дискретная математика. Множество, слайд №420 Дискретная математика. Множество, слайд №421 Дискретная математика. Множество, слайд №422 Дискретная математика. Множество, слайд №423 Дискретная математика. Множество, слайд №424 Дискретная математика. Множество, слайд №425 Дискретная математика. Множество, слайд №426 Дискретная математика. Множество, слайд №427 Дискретная математика. Множество, слайд №428 Дискретная математика. Множество, слайд №429 Дискретная математика. Множество, слайд №430 Дискретная математика. Множество, слайд №431 Дискретная математика. Множество, слайд №432 Дискретная математика. Множество, слайд №433 Дискретная математика. Множество, слайд №434 Дискретная математика. Множество, слайд №435 Дискретная математика. Множество, слайд №436 Дискретная математика. Множество, слайд №437 Дискретная математика. Множество, слайд №438 Дискретная математика. Множество, слайд №439 Дискретная математика. Множество, слайд №440 Дискретная математика. Множество, слайд №441 Дискретная математика. Множество, слайд №442 Дискретная математика. Множество, слайд №443 Дискретная математика. Множество, слайд №444 Дискретная математика. Множество, слайд №445 Дискретная математика. Множество, слайд №446 Дискретная математика. Множество, слайд №447 Дискретная математика. Множество, слайд №448 Дискретная математика. Множество, слайд №449 Дискретная математика. Множество, слайд №450 Дискретная математика. Множество, слайд №451 Дискретная математика. Множество, слайд №452 Дискретная математика. Множество, слайд №453 Дискретная математика. Множество, слайд №454 Дискретная математика. Множество, слайд №455 Дискретная математика. Множество, слайд №456 Дискретная математика. Множество, слайд №457 Дискретная математика. Множество, слайд №458 Дискретная математика. Множество, слайд №459 Дискретная математика. Множество, слайд №460 Дискретная математика. Множество, слайд №461 Дискретная математика. Множество, слайд №462 Дискретная математика. Множество, слайд №463 Дискретная математика. Множество, слайд №464 Дискретная математика. Множество, слайд №465 Дискретная математика. Множество, слайд №466 Дискретная математика. Множество, слайд №467 Дискретная математика. Множество, слайд №468 Дискретная математика. Множество, слайд №469 Дискретная математика. Множество, слайд №470 Дискретная математика. Множество, слайд №471 Дискретная математика. Множество, слайд №472 Дискретная математика. Множество, слайд №473
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Дискретная математика. Множество. Доклад-сообщение содержит 473 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Федеральное государственное бюджетное образовательное учреждение высшего образования «КЕМЕРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Кафедра прикладной...
Описание слайда:
Федеральное государственное бюджетное образовательное учреждение высшего образования «КЕМЕРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Кафедра прикладной математики ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1 курс лекций Кемерово 2018 © С. Г. Гутова, 2018 © Кемеровский государственный университет, 2018 ISBN 978-5-8353-1686-1 Об издании – 1, 2, 3

Слайд 2


Дискретная математика. Множество, слайд №2
Описание слайда:

Слайд 3


Дискретная математика. Множество, слайд №3
Описание слайда:

Слайд 4


Дискретная математика. Множество, слайд №4
Описание слайда:

Слайд 5


Дискретная математика. Множество, слайд №5
Описание слайда:

Слайд 6


Дискретная математика. Множество, слайд №6
Описание слайда:

Слайд 7


Оглавление
Описание слайда:
Оглавление

Слайд 8


Дискретная математика. Множество, слайд №8
Описание слайда:

Слайд 9


Дискретная математика. Множество, слайд №9
Описание слайда:

Слайд 10


Лекция 1 Множества
Описание слайда:
Лекция 1 Множества

Слайд 11


Множество – это совокупность определенных различаемых объектов таких, что для любого объекта можно установить, принадлежит объект данному множеству...
Описание слайда:
Множество – это совокупность определенных различаемых объектов таких, что для любого объекта можно установить, принадлежит объект данному множеству или нет. Множество – это совокупность определенных различаемых объектов таких, что для любого объекта можно установить, принадлежит объект данному множеству или нет. Множество, которое подчиняется лишь такому ограничению, может содержать объекты почти любой природы.

Слайд 12


Георг Кантор определил множество так: Множество – это многое, мыслимое как целое.
Описание слайда:
Георг Кантор определил множество так: Множество – это многое, мыслимое как целое.

Слайд 13


Например: Например: множество всех станций Московского метро; множество левых ботинок; множество натуральных чисел: 1, 2, 3, 4 и т. д.; множество...
Описание слайда:
Например: Например: множество всех станций Московского метро; множество левых ботинок; множество натуральных чисел: 1, 2, 3, 4 и т. д.; множество символов, доступных специальному печатающему устройству; множество кодов операций конкретного компьютера.

Слайд 14


множество всех натуральных чисел: 1, 2, 3, . . Обозначим N. Часто 0 считают натуральным числом. Множество N с добавлением 0 обозначается . множество...
Описание слайда:
множество всех натуральных чисел: 1, 2, 3, . . Обозначим N. Часто 0 считают натуральным числом. Множество N с добавлением 0 обозначается . множество всех натуральных чисел: 1, 2, 3, . . Обозначим N. Часто 0 считают натуральным числом. Множество N с добавлением 0 обозначается . множество всех натуральных чисел, не превосходящих 100. множество всех решений уравнения

Слайд 15


Дискретная математика. Множество, слайд №15
Описание слайда:

Слайд 16


Множество, не содержащее элементов, называется пустым множеством и обозначается Ø. Множество, не содержащее элементов, называется пустым множеством и...
Описание слайда:
Множество, не содержащее элементов, называется пустым множеством и обозначается Ø. Множество, не содержащее элементов, называется пустым множеством и обозначается Ø.

Слайд 17


Способы задания множества Перечисление всех элементов множества (список), например, множество однозначных неотрицательных чисел Множества часто...
Описание слайда:
Способы задания множества Перечисление всех элементов множества (список), например, множество однозначных неотрицательных чисел Множества часто рассматриваются как «неупорядоченные совокупности элементов», хотя иногда полезно подчеркнуть, что, например

Слайд 18


Выяснить, какие из приведенных определений верные? Выяснить, какие из приведенных определений верные?
Описание слайда:
Выяснить, какие из приведенных определений верные? Выяснить, какие из приведенных определений верные?

Слайд 19


Порождающая процедура Описывает способ получения элементов множества из уже полученных элементов либо других объектов. Тогда элементы множества – все...
Описание слайда:
Порождающая процедура Описывает способ получения элементов множества из уже полученных элементов либо других объектов. Тогда элементы множества – все объекты, которые могут быть получены (построены) с помощью такой процедуры.

Слайд 20


Множество натуральных степеней двойки: 2, 4, 8, 16, 32, 64, 128… Множество натуральных степеней двойки: 2, 4, 8, 16, 32, 64, 128… Порождающую...
Описание слайда:
Множество натуральных степеней двойки: 2, 4, 8, 16, 32, 64, 128… Множество натуральных степеней двойки: 2, 4, 8, 16, 32, 64, 128… Порождающую процедуру зададим рекуррентно:

Слайд 21


Пример 2 Какое множество задается рекуррентной формулой:
Описание слайда:
Пример 2 Какое множество задается рекуррентной формулой:

Слайд 22


Задание множества описанием его элементов (разрешающая процедура)
Описание слайда:
Задание множества описанием его элементов (разрешающая процедура)

Слайд 23


Дискретная математика. Множество, слайд №23
Описание слайда:

Слайд 24


Множества А и В называют равными Множества А и В называют равными ( ), если каждый элемент множества А является одновременно элементом множества В и...
Описание слайда:
Множества А и В называют равными Множества А и В называют равными ( ), если каждый элемент множества А является одновременно элементом множества В и наоборот, т.е. если и .

Слайд 25


Множество U называется универсальным множеством (множество элементов всех подмножеств) для некоторой системы множеств, если каждое множество этой...
Описание слайда:
Множество U называется универсальным множеством (множество элементов всех подмножеств) для некоторой системы множеств, если каждое множество этой системы является подмножеством U, т.е. Множество U называется универсальным множеством (множество элементов всех подмножеств) для некоторой системы множеств, если каждое множество этой системы является подмножеством U, т.е.

Слайд 26


Дискретная математика. Множество, слайд №26
Описание слайда:

Слайд 27


Объединением двух множеств А и В называется множество , состоящее из тех элементов, которые принадлежат или множеству А, или В, или А и В...
Описание слайда:
Объединением двух множеств А и В называется множество , состоящее из тех элементов, которые принадлежат или множеству А, или В, или А и В одновременно. Объединением двух множеств А и В называется множество , состоящее из тех элементов, которые принадлежат или множеству А, или В, или А и В одновременно. Рис.3. Объединение множеств

Слайд 28


Дискретная математика. Множество, слайд №28
Описание слайда:

Слайд 29


Разностью двух множеств А и В Разностью двух множеств А и В ( или ) называется множество тех элементов множества А, которые не принадлежат множеству...
Описание слайда:
Разностью двух множеств А и В Разностью двух множеств А и В ( или ) называется множество тех элементов множества А, которые не принадлежат множеству В: Рис.5. Разность множеств

Слайд 30


Прямым (декартовым) произведением двух множеств А и В называется множество, состоящее из упорядоченных пар элементов, в которых первый элемент...
Описание слайда:
Прямым (декартовым) произведением двух множеств А и В называется множество, состоящее из упорядоченных пар элементов, в которых первый элемент принадлежит множеству А, а второй – множеству В. Прямым (декартовым) произведением двух множеств А и В называется множество, состоящее из упорядоченных пар элементов, в которых первый элемент принадлежит множеству А, а второй – множеству В.

Слайд 31


Пример 3
Описание слайда:
Пример 3

Слайд 32


Пояснение:
Описание слайда:
Пояснение:

Слайд 33


Пояснение:
Описание слайда:
Пояснение:

Слайд 34


Пояснение:
Описание слайда:
Пояснение:

Слайд 35


Пояснение:
Описание слайда:
Пояснение:

Слайд 36


Пример 4: Прямое (декартово) произведение: = {(-2, 0); (-2, 2); (-2, 4); (-2, 5);(-1, 0); (-1, 2); (-1, 4); (-1, 5);(0, 0); (0, 2);(0, 4);(0, 5); (1,...
Описание слайда:
Пример 4: Прямое (декартово) произведение: = {(-2, 0); (-2, 2); (-2, 4); (-2, 5);(-1, 0); (-1, 2); (-1, 4); (-1, 5);(0, 0); (0, 2);(0, 4);(0, 5); (1, 0); (1, 2); (1, 4); (1, 5); (2, 0); (2, 2); (2, 4); (2, 5)}; = {(0, -2); (0, -1); (0, 0); (0, 1); (0, 2); (2, -2); (2, -1); (2, 0); (2, 1); (2, 2); (4, -2); (4, -1); (4, 0); (4, 1); (4, 2); (5, -2); (5, -1); (5, 0). (5, 1); (5, 2)}

Слайд 37


Из примера 2 видно, что Из примера 2 видно, что
Описание слайда:
Из примера 2 видно, что Из примера 2 видно, что

Слайд 38


Пример 5
Описание слайда:
Пример 5

Слайд 39


Дискретная математика. Множество, слайд №39
Описание слайда:

Слайд 40


Дискретная математика. Множество, слайд №40
Описание слайда:

Слайд 41


Дискретная математика. Множество, слайд №41
Описание слайда:

Слайд 42


Дискретная математика. Множество, слайд №42
Описание слайда:

Слайд 43


Дискретная математика. Множество, слайд №43
Описание слайда:

Слайд 44


Дискретная математика. Множество, слайд №44
Описание слайда:

Слайд 45


Дискретная математика. Множество, слайд №45
Описание слайда:

Слайд 46


Лекция 2 Векторы и прямые произведения множеств. Проекция вектора на ось
Описание слайда:
Лекция 2 Векторы и прямые произведения множеств. Проекция вектора на ось

Слайд 47


Векторы Векторы Вектор – это упорядоченный набор элементов. Его элементы зазываются координатами или компонентами вектора. Длина (размерность)...
Описание слайда:
Векторы Векторы Вектор – это упорядоченный набор элементов. Его элементы зазываются координатами или компонентами вектора. Длина (размерность) вектора – число координат вектора. В отличие от элементов множества, его координаты могут совпадать. Обозначение вектора: в круглых скобках, координаты – через запятую (0, 5, 4, 5, 0, 1). Иногда скобки и даже запятые опускаются.

Слайд 48


Векторы длины 2 называют упорядоченными парами; длины 3 – тройками; и т.д., длины n – n-ками. Векторы длины 2 называют упорядоченными парами; длины 3...
Описание слайда:
Векторы длины 2 называют упорядоченными парами; длины 3 – тройками; и т.д., длины n – n-ками. Векторы длины 2 называют упорядоченными парами; длины 3 – тройками; и т.д., длины n – n-ками. Два вектора равны, если они имеют одинаковую длину, и соответствующие координаты равны, т. е. если и

Слайд 49


Прямое произведение n множеств Прямое произведение n множеств Прямое произведение множеств называется множеством всех векторов , длины n таких, что...
Описание слайда:
Прямое произведение n множеств Прямое произведение n множеств Прямое произведение множеств называется множеством всех векторов , длины n таких, что Иначе говоря

Слайд 50


Пример 1: Найти прямое произведение множеств Перечисляем тройки элементов в лексико-графическом порядке.
Описание слайда:
Пример 1: Найти прямое произведение множеств Перечисляем тройки элементов в лексико-графическом порядке.

Слайд 51


Пусть А – конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т. д.). Такие множества обычно...
Описание слайда:
Пусть А – конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т. д.). Такие множества обычно называют алфавитом. Пусть А – конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т. д.). Такие множества обычно называют алфавитом. Примеры алфавитов: 33 русских буквы, 26 латинских букв, 10 арабских цифр; список символов клавиатуры компьютера.

Слайд 52


Слова длины n в алфавите А – это элементы множества Множество всех слов в алфавите А – это множество Слова длины n в алфавите А – это элементы...
Описание слайда:
Слова длины n в алфавите А – это элементы множества Множество всех слов в алфавите А – это множество Слова длины n в алфавите А – это элементы множества Множество всех слов в алфавите А – это множество Здесь слово определено как вектор. При написании слова не принято пользоваться разделителями: скобками, запятыми; они могут оказаться символами самого алфавита. Поэтому слово в алфавите обозначается как конечная последовательность символов из алфавита А.

Слайд 53


Пример 2: 1) Десятичное число – слово в алфавите цифр {0, 1, 2, 3, ... , 9}. 2) Двоичное слово в алфавите {0, 1}. 3) Текст, отпечатанный на машинке –...
Описание слайда:
Пример 2: 1) Десятичное число – слово в алфавите цифр {0, 1, 2, 3, ... , 9}. 2) Двоичное слово в алфавите {0, 1}. 3) Текст, отпечатанный на машинке – слово в алфавите, определяемом клавиатурой этой машинки.

Слайд 54


Теорема (о мощности прямого произведения множеств) Пусть конечные множества и Тогда мощность множества равна произведению мощностей множеств:
Описание слайда:
Теорема (о мощности прямого произведения множеств) Пусть конечные множества и Тогда мощность множества равна произведению мощностей множеств:

Слайд 55


Следствие: Например, множество двоичных векторов длины 3, содержит
Описание слайда:
Следствие: Например, множество двоичных векторов длины 3, содержит

Слайд 56


Проекции множества векторов на оси Проекцией вектора длины n на i-ю ось называется его i-я координата. Обозначается это так: Например: , тогда
Описание слайда:
Проекции множества векторов на оси Проекцией вектора длины n на i-ю ось называется его i-я координата. Обозначается это так: Например: , тогда

Слайд 57


Проекцией вектора Проекцией вектора длины n на оси с номерами называется вектор, составленный из соответствующих координат. Обозначается это так:...
Описание слайда:
Проекцией вектора Проекцией вектора длины n на оси с номерами называется вектор, составленный из соответствующих координат. Обозначается это так: Например: , тогда

Слайд 58


Пусть дано множество V векторов одинаковой длины. Проекцией множества векторов на i-ю ось называется множество проекций на i-ю ось всех его векторов....
Описание слайда:
Пусть дано множество V векторов одинаковой длины. Проекцией множества векторов на i-ю ось называется множество проекций на i-ю ось всех его векторов. Обозначается это так: Например: Например: , тогда

Слайд 59


Проекцией множества векторов на оси с номерами называется Проекцией множества векторов на оси с номерами называется множество проекций на оси с...
Описание слайда:
Проекцией множества векторов на оси с номерами называется Проекцией множества векторов на оси с номерами называется множество проекций на оси с номерами всех его векторов. Обозначается: Например: тогда

Слайд 60


Пример 3: Дано множество векторов: V = {(Иванов Александр Николаевич), (Иванов Михаил Александрович), (Иванов Сергей Александрович)}. пр1 V =...
Описание слайда:
Пример 3: Дано множество векторов: V = {(Иванов Александр Николаевич), (Иванов Михаил Александрович), (Иванов Сергей Александрович)}. пр1 V = {Иванов}, пр2 V = {Александр, Михаил, Сергей}, пр23 V = {(Александр Николаевич), (Михаил Александрович), (Сергей Александрович)}.

Слайд 61


Пример 4
Описание слайда:
Пример 4

Слайд 62


Пример 4
Описание слайда:
Пример 4

Слайд 63


Пример 4
Описание слайда:
Пример 4

Слайд 64


Пример 4
Описание слайда:
Пример 4

Слайд 65


Лекция 3 Комбинаторика
Описание слайда:
Лекция 3 Комбинаторика

Слайд 66


Правило суммы Классическая формулировка Если элемент α можно выбрать k способами, а элемент β можно выбрать m способами. Тогда α или β можно выбрать...
Описание слайда:
Правило суммы Классическая формулировка Если элемент α можно выбрать k способами, а элемент β можно выбрать m способами. Тогда α или β можно выбрать k + m способами.

Слайд 67


Теорема о мощности объединения множеств Теорема о мощности объединения множеств (современная формулировка) Количество элементов объединения двух...
Описание слайда:
Теорема о мощности объединения множеств Теорема о мощности объединения множеств (современная формулировка) Количество элементов объединения двух множеств равно сумме количества элементов в первом и во втором множестве, за вычетом количества элементов их пересечения:

Слайд 68


Причем, если множества не пересекаются, то теорема приобретает вид, аналогичный классической формулировке:
Описание слайда:
Причем, если множества не пересекаются, то теорема приобретает вид, аналогичный классической формулировке:

Слайд 69


Для трех множеств теорема имеет вид: Для трех множеств теорема имеет вид:
Описание слайда:
Для трех множеств теорема имеет вид: Для трех множеств теорема имеет вид:

Слайд 70


Пример 1 Пример 1 Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по...
Описание слайда:
Пример 1 Пример 1 Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек. Сколько человек имеют “5” по указанным предметам? Сколько человек не имеет “5” по указанным предметам? Имеет “5” только по математике? Имеет “5” только по двум предметам?

Слайд 71


Пример 1 Пример 1 Введем обозначения. Обозначим буквой U множество всех учеников класса, буквой М множество учеников, имеющих «5» по математике,...
Описание слайда:
Пример 1 Пример 1 Введем обозначения. Обозначим буквой U множество всех учеников класса, буквой М множество учеников, имеющих «5» по математике, буквой Ф – имеющих «5» по физике, Х – имеющих «5» по химии. Тогда, согласно условию,

Слайд 72


Пример 1 Пример 1 На рисунке 1 приведено множество, состоящее из учеников, имеющих «5» хотя бы по одному из указанных предметов. Рис.1. Множество...
Описание слайда:
Пример 1 Пример 1 На рисунке 1 приведено множество, состоящее из учеников, имеющих «5» хотя бы по одному из указанных предметов. Рис.1. Множество учеников, имеющих «5» хотя бы по одному предмету

Слайд 73


Пример 1 Пример 1 Очевидно, что это объединение множеств М, Ф и Х. Для нахождения количества элементов объединения воспользуемся правилом суммы.
Описание слайда:
Пример 1 Пример 1 Очевидно, что это объединение множеств М, Ф и Х. Для нахождения количества элементов объединения воспользуемся правилом суммы.

Слайд 74


Пример 1 Пример 1 На рисунке 2 приведено множество, состоящее из учеников, не имеющих «5» ни по одному из указанных предметов. Обозначим его буквой...
Описание слайда:
Пример 1 Пример 1 На рисунке 2 приведено множество, состоящее из учеников, не имеющих «5» ни по одному из указанных предметов. Обозначим его буквой Н. Рис. 2. Множество учеников, не имеющих «5» по указанным предметам

Слайд 75


Пример 1 Пример 1 Очевидно, что это разность между универсальным множеством U и объединением множеств М, Ф и Х.
Описание слайда:
Пример 1 Пример 1 Очевидно, что это разность между универсальным множеством U и объединением множеств М, Ф и Х.

Слайд 76


Пример 1 Пример 1 На рисунке 3 приведено множество, состоящее из учеников, имеющих «5» только по математике. Обозначим его буквами ТМ. Рис. 3....
Описание слайда:
Пример 1 Пример 1 На рисунке 3 приведено множество, состоящее из учеников, имеющих «5» только по математике. Обозначим его буквами ТМ. Рис. 3. Множество учеников, имеющих «5» только по математике

Слайд 77


Пример 1 Пример 1 Очевидно, что это разность между множеством М и множествами ТМФ – имеющих «5» только по математике и физике, ТМХ – имеющих «5»...
Описание слайда:
Пример 1 Пример 1 Очевидно, что это разность между множеством М и множествами ТМФ – имеющих «5» только по математике и физике, ТМХ – имеющих «5» только по математике и химии, и

Слайд 78


Пример 1 Пример 1 На рисунке 4 приведено множество, состоящее из учеников, имеющих «5» только по двум предметам. Обозначим его Т2. Очевидно, что Т2...
Описание слайда:
Пример 1 Пример 1 На рисунке 4 приведено множество, состоящее из учеников, имеющих «5» только по двум предметам. Обозначим его Т2. Очевидно, что Т2 является суммой трех непересекающихся множеств ТМФ, ТМХ, ТФХ. Рис. 4. Множество учеников, имеющих «5» только по двум предметам

Слайд 79


Найдем мощность каждой части искомого множества: Тогда искомая мощность примет вид:
Описание слайда:
Найдем мощность каждой части искомого множества: Тогда искомая мощность примет вид:

Слайд 80


Правило произведения Классическая формулировка Если элемент α можно выбрать k способами, а элемент β можно выбрать m способами. Тогда пару α и β...
Описание слайда:
Правило произведения Классическая формулировка Если элемент α можно выбрать k способами, а элемент β можно выбрать m способами. Тогда пару α и β можно выбрать km способами.

Слайд 81


Теорема о мощности прямого произведения множеств (современная формулировка) Теорема о мощности прямого произведения множеств (современная...
Описание слайда:
Теорема о мощности прямого произведения множеств (современная формулировка) Теорема о мощности прямого произведения множеств (современная формулировка)

Слайд 82


Пример 2: Из 3 экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 6 экземпляров учебника физики, надо выбрать комплект, содержащий все...
Описание слайда:
Пример 2: Из 3 экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 6 экземпляров учебника физики, надо выбрать комплект, содержащий все учебники по одному разу. Сколькими способами это можно сделать? Ответ: 3 ⨉ 7 ⨉ 6 = 126.

Слайд 83


Пример 2: Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: а) все цифры были разными; б) на последнем...
Описание слайда:
Пример 2: Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: а) все цифры были разными; б) на последнем месте четная цифра. а) 10 ⨉ 9 ⨉ 8 ⨉ 7 ⨉ 6; б) 10 ⨉ 10 ⨉ 10 ⨉ 10 ⨉ 5.

Слайд 84


Число размещений без повторений Число размещений без повторений из n по k – это число способов, сколькими можно из n различных элементов построить...
Описание слайда:
Число размещений без повторений Число размещений без повторений из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k различными координатами. Число размещений без повторений находится по формуле:

Слайд 85


Число размещений без повторений Пример 3: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?
Описание слайда:
Число размещений без повторений Пример 3: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?

Слайд 86


Число размещений с повторениями Число размещений с повторениями из n по k – это число способов, сколькими можно из n различных элементов построить...
Описание слайда:
Число размещений с повторениями Число размещений с повторениями из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k координатами, среди которых могут быть одинаковые. Число размещений с повторениями находится по формуле:

Слайд 87


Число размещений с повторениями Пример 4: Сколько слов длины 6 можно составить из 26 букв латинского алфавита?
Описание слайда:
Число размещений с повторениями Пример 4: Сколько слов длины 6 можно составить из 26 букв латинского алфавита?

Слайд 88


Число перестановок без повторений Число перестановок без повторений из n элементов – это число способов, сколькими можно расположить на n различных...
Описание слайда:
Число перестановок без повторений Число перестановок без повторений из n элементов – это число способов, сколькими можно расположить на n различных местах n различных элементов. Число перестановок без повторений находится по формуле:

Слайд 89


Задача на рассадки и расстановки В задачах на рассадки и расстановки используется тот факт, что n различных элементов на n различных местах можно...
Описание слайда:
Задача на рассадки и расстановки В задачах на рассадки и расстановки используется тот факт, что n различных элементов на n различных местах можно расставить n! различными способами

Слайд 90


Пример 5: Сколькими способами можно расставить на книжной полке 5 различных книг? В скольких случаях две определенные книги А и В окажутся рядом?...
Описание слайда:
Пример 5: Сколькими способами можно расставить на книжной полке 5 различных книг? В скольких случаях две определенные книги А и В окажутся рядом? Всего вариантов расстановки 5 книг на 5 местах : 5!=120

Слайд 91


Замечание: В задаче на рассадки и расстановки число элементов множества А ищут по формуле: где х1 – число способов выбрать нужные места; х2 – число...
Описание слайда:
Замечание: В задаче на рассадки и расстановки число элементов множества А ищут по формуле: где х1 – число способов выбрать нужные места; х2 – число способов расположить на них нужные элементы; х3 – число способов расположить остальные элементы на оставшихся местах.

Слайд 92


Рис. 5. Схема расстановки
Описание слайда:
Рис. 5. Схема расстановки

Слайд 93


Число сочетаний без повторений Число сочетаний без повторений из n по k – это число способов, сколькими можно из n различных элементов выбрать k штук...
Описание слайда:
Число сочетаний без повторений Число сочетаний без повторений из n по k – это число способов, сколькими можно из n различных элементов выбрать k штук без учета порядка. Число сочетаний без повторений находится по формуле:

Слайд 94


Свойства числа сочетаний
Описание слайда:
Свойства числа сочетаний

Слайд 95


Урновая задача Урновая задача – это задача, в которой производится выбор сразу нескольких элементов из заданной совокупности. Пример 6: В урне 7...
Описание слайда:
Урновая задача Урновая задача – это задача, в которой производится выбор сразу нескольких элементов из заданной совокупности. Пример 6: В урне 7 шаров. Из них 3 белых, 4 черных. Наугад выбирают 3 шара. Сколькими способами это можно сделать? В скольких случаях среди них будет: 1) один белый; 2) два белых; 3) все белые.

Слайд 96


Схема урновой задачи
Описание слайда:
Схема урновой задачи

Слайд 97


Общее число исходов эксперимента найдем по общей формуле
Описание слайда:
Общее число исходов эксперимента найдем по общей формуле

Слайд 98


Количество элементов множества А1 найдем по формуле:
Описание слайда:
Количество элементов множества А1 найдем по формуле:

Слайд 99


Количество элементов множества А2 найдем по формуле:
Описание слайда:
Количество элементов множества А2 найдем по формуле:

Слайд 100


Количество элементов множества А3 найдем по формуле:
Описание слайда:
Количество элементов множества А3 найдем по формуле:

Слайд 101


Лекция 4 Соответствия
Описание слайда:
Лекция 4 Соответствия

Слайд 102


Соответствия и функции Соответствия и функции
Описание слайда:
Соответствия и функции Соответствия и функции

Слайд 103


Соответствие G называется всюду (полностью) определенным – если пр1 G = А (в противном случае – частично определенное соответствие). Соответствие G...
Описание слайда:
Соответствие G называется всюду (полностью) определенным – если пр1 G = А (в противном случае – частично определенное соответствие). Соответствие G называется всюду (полностью) определенным – если пр1 G = А (в противном случае – частично определенное соответствие). Соответствие G называется сюрьективным, если пр2 G = B.

Слайд 104


Образ элемента в множестве B при соответствии G – это множество всех элементов которые соответствуют a. Образ элемента в множестве B при соответствии...
Описание слайда:
Образ элемента в множестве B при соответствии G – это множество всех элементов которые соответствуют a. Образ элемента в множестве B при соответствии G – это множество всех элементов которые соответствуют a. Прообраз элемента в множестве А при соответствии G – это множество всех которым соответствует b.

Слайд 105


Образом множества Образом множества называется объединение образов всех элементов С. Прообразом множества называется объединение прообразов всех...
Описание слайда:
Образом множества Образом множества называется объединение образов всех элементов С. Прообразом множества называется объединение прообразов всех элементов D.

Слайд 106


Соответствие G называется функциональным (однозначным) соответствием, если образом любого элемента из пр1 G является единственный элемент из пр2 G....
Описание слайда:
Соответствие G называется функциональным (однозначным) соответствием, если образом любого элемента из пр1 G является единственный элемент из пр2 G. Соответствие G называется функциональным (однозначным) соответствием, если образом любого элемента из пр1 G является единственный элемент из пр2 G.

Слайд 107


Соответствие G называется инъективным соответствием, если прообразом любого элемента из пр2 G является единственный элемент из пр1 G. Соответствие G...
Описание слайда:
Соответствие G называется инъективным соответствием, если прообразом любого элемента из пр2 G является единственный элемент из пр1 G. Соответствие G называется инъективным соответствием, если прообразом любого элемента из пр2 G является единственный элемент из пр1 G.

Слайд 108


Соответствие F является функцией типа Соответствие F является функцией типа если оно функционально (однозначно)
Описание слайда:
Соответствие F является функцией типа Соответствие F является функцией типа если оно функционально (однозначно)

Слайд 109


Соответствие G является отображением множества А в множество В, если оно функционально и полностью определено. Соответствие G является отображением...
Описание слайда:
Соответствие G является отображением множества А в множество В, если оно функционально и полностью определено. Соответствие G является отображением множества А в множество В, если оно функционально и полностью определено. Соответствие G является отображением множества А на множество В, если оно сюрьективно.

Слайд 110


Соответствие G является взаимно однозначным, если оно: 1) всюду определено; Соответствие G является взаимно однозначным, если оно: 1) всюду...
Описание слайда:
Соответствие G является взаимно однозначным, если оно: 1) всюду определено; Соответствие G является взаимно однозначным, если оно: 1) всюду определено; 2) сюрьективно; 3) функционально; 4) инъективно.

Слайд 111


Пример 1: Определить свойства соответствия G между множествами A и B. A = {a, b, c}, B = {1, 2, 3}. G = {(a, 2), (b, 2), (c,3)}.
Описание слайда:
Пример 1: Определить свойства соответствия G между множествами A и B. A = {a, b, c}, B = {1, 2, 3}. G = {(a, 2), (b, 2), (c,3)}.

Слайд 112


Область определения: Область определения: D(G) = пр1G = {a, b, c} = A, значит полностью определено. Область значения: Е(G) = пр2G = {2, 3} ≠ B,...
Описание слайда:
Область определения: Область определения: D(G) = пр1G = {a, b, c} = A, значит полностью определено. Область значения: Е(G) = пр2G = {2, 3} ≠ B, значит не сюрьективно.

Слайд 113


Образы элементов области определения: Образы элементов области определения: G (a) = {2}; G (b) = {2}; G (c) = {3}. Видим, что есть единственность...
Описание слайда:
Образы элементов области определения: Образы элементов области определения: G (a) = {2}; G (b) = {2}; G (c) = {3}. Видим, что есть единственность образа, значит соответствие функционально.

Слайд 114


Прообразы элементов области значений: Прообразы элементов области значений: Нет единственности прообраза, значит не инъективно.
Описание слайда:
Прообразы элементов области значений: Прообразы элементов области значений: Нет единственности прообраза, значит не инъективно.

Слайд 115


Выводы: Соответствие является функцией, так как функционально. 2. Соответствие является отображением, так как полностью определено и функционально....
Описание слайда:
Выводы: Соответствие является функцией, так как функционально. 2. Соответствие является отображением, так как полностью определено и функционально. 3. Соответствие является отображением А в В, так как не сюрьективно. 4. Соответствие не является взаимно однозначным, так как не сюьективно и не инъективно.

Слайд 116


Пример 2: Определить свойства соответствия G между множествами A и B. A = {a, b, c}, B = {1, 2, 3}. G = {(b, 1), (b, 2), (c,3)}.
Описание слайда:
Пример 2: Определить свойства соответствия G между множествами A и B. A = {a, b, c}, B = {1, 2, 3}. G = {(b, 1), (b, 2), (c,3)}.

Слайд 117


Область определения: Область определения: D(G) = пр1G = {a, b} ≠ A, значит не полностью определено Область значения: Е(G) = пр2G = {1, 2, 3} = B,...
Описание слайда:
Область определения: Область определения: D(G) = пр1G = {a, b} ≠ A, значит не полностью определено Область значения: Е(G) = пр2G = {1, 2, 3} = B, значит сюрьективно

Слайд 118


Образы элементов области определения: Образы элементов области определения: G (b) = {1, 2}; G (c) = {3}. Видим, что нет единственности образа, значит...
Описание слайда:
Образы элементов области определения: Образы элементов области определения: G (b) = {1, 2}; G (c) = {3}. Видим, что нет единственности образа, значит соответствие не функционально.

Слайд 119


Прообразы элементов области значений: Прообразы элементов области значений: G-1 (1) = {b}, G-1 (2) = {b}, G-1 (3) = {c} Есть единственность...
Описание слайда:
Прообразы элементов области значений: Прообразы элементов области значений: G-1 (1) = {b}, G-1 (2) = {b}, G-1 (3) = {c} Есть единственность прообраза, значит инъективно.

Слайд 120


Выводы: Соответствие не является функцией, так как не функционально. 2. Соответствие является отображением, так как не полностью определено и не...
Описание слайда:
Выводы: Соответствие не является функцией, так как не функционально. 2. Соответствие является отображением, так как не полностью определено и не функционально. 3. Соответствие не является взаимно однозначным, так как не функционально и не полностью определено.

Слайд 121


Преобразованием множества А называется отображение типа Преобразованием множества А называется отображение типа Функция типа называется n-местной...
Описание слайда:
Преобразованием множества А называется отображение типа Преобразованием множества А называется отображение типа Функция типа называется n-местной функцией

Слайд 122


Соответствие называется обратным к если Н таково, что
Описание слайда:
Соответствие называется обратным к если Н таково, что

Слайд 123


Если соответствие, обратное к функции Если соответствие, обратное к функции является функциональным, то оно называется функцией, обратной к f,
Описание слайда:
Если соответствие, обратное к функции Если соответствие, обратное к функции является функциональным, то оно называется функцией, обратной к f,

Слайд 124


Пусть дана функция Соответствие является функцией тогда и только тогда, когда f инъективна, и является отображением тогда и только тогда, когда f...
Описание слайда:
Пусть дана функция Соответствие является функцией тогда и только тогда, когда f инъективна, и является отображением тогда и только тогда, когда f инъективна и сюрьективна, то есть биективна.

Слайд 125


Утверждение: Утверждение: Для функции существует обратная функция тогда и только тогда, когда f является взаимно однозначным соответствием между...
Описание слайда:
Утверждение: Утверждение: Для функции существует обратная функция тогда и только тогда, когда f является взаимно однозначным соответствием между своей областью определения и областью значений.

Слайд 126


Пусть даны функции Пусть даны функции и Функция называется композицией функций f и g, если Часто говорят, что h получена подстановкой f в g.
Описание слайда:
Пусть даны функции Пусть даны функции и Функция называется композицией функций f и g, если Часто говорят, что h получена подстановкой f в g.

Слайд 127


Для многоместных функций Для многоместных функций и возможны различные варианты подстановки f в g, задающие функции различных типов. Например, при m...
Описание слайда:
Для многоместных функций Для многоместных функций и возможны различные варианты подстановки f в g, задающие функции различных типов. Например, при m = 3 и n = 4 функция имеет 6 аргументов и тип

Слайд 128


Для множества многоместных Для множества многоместных функций типа возможны любые подстановки функций друг в друга, а также любые переименования...
Описание слайда:
Для множества многоместных Для множества многоместных функций типа возможны любые подстановки функций друг в друга, а также любые переименования аргументов. Например, переименование в из функции четырёх аргументов порождает функцию трёх аргументов:

Слайд 129


Функция, полученная из функций Функция, полученная из функций некоторой подстановкой их друг в друга и переименованием аргументов, называется...
Описание слайда:
Функция, полученная из функций Функция, полученная из функций некоторой подстановкой их друг в друга и переименованием аргументов, называется суперпозицией. Выражение, задающее эту суперпозицию и содержащее функциональные знаки, скобки и символы аргументов, называется формулой.

Слайд 130


Взаимно однозначные соответствия и мощность множеств Утверждение (о взаимно однозначном соответствии равномощных множеств): Если между конечными...
Описание слайда:
Взаимно однозначные соответствия и мощность множеств Утверждение (о взаимно однозначном соответствии равномощных множеств): Если между конечными множествами А и В существует взаимно однозначное соответствие, то

Слайд 131


Взаимно однозначные соответствия и мощность множеств Доказательство: Пусть мощность А больше, чем мощность В.
Описание слайда:
Взаимно однозначные соответствия и мощность множеств Доказательство: Пусть мощность А больше, чем мощность В.

Слайд 132


Взаимно однозначные соответствия и мощность множеств Тогда если выполняется свойство полной определенности, то не выполняется свойство инъективности.
Описание слайда:
Взаимно однозначные соответствия и мощность множеств Тогда если выполняется свойство полной определенности, то не выполняется свойство инъективности.

Слайд 133


Взаимно однозначные соответствия и мощность множеств Доказательство: 2. Пусть мощность А меньше, чем мощность В.
Описание слайда:
Взаимно однозначные соответствия и мощность множеств Доказательство: 2. Пусть мощность А меньше, чем мощность В.

Слайд 134


Взаимно однозначные соответствия и мощность множеств Тогда если выполняется свойство функциональности, то не выполняется свойство сюрьективности, и...
Описание слайда:
Взаимно однозначные соответствия и мощность множеств Тогда если выполняется свойство функциональности, то не выполняется свойство сюрьективности, и наоборот.

Слайд 135


Взаимно однозначные соответствия и мощность множеств Таким образом, получили противоречие, что доказывает истинность сформулированного утверждения.
Описание слайда:
Взаимно однозначные соответствия и мощность множеств Таким образом, получили противоречие, что доказывает истинность сформулированного утверждения.

Слайд 136


Этот факт: Этот факт: 1) позволяет установить равенство мощностей двух множеств, не вычисляя мощностей этих множеств; 2) дает возможность вычислить...
Описание слайда:
Этот факт: Этот факт: 1) позволяет установить равенство мощностей двух множеств, не вычисляя мощностей этих множеств; 2) дает возможность вычислить мощность множества, установив его взаимно однозначное соответствие с множеством, мощность которого известна или легко вычисляется.

Слайд 137


На понятии взаимно однозначного соответствия строится доказательство многих важных теорем в теории множеств. На понятии взаимно однозначного...
Описание слайда:
На понятии взаимно однозначного соответствия строится доказательство многих важных теорем в теории множеств. На понятии взаимно однозначного соответствия строится доказательство многих важных теорем в теории множеств. Теорема о числе подмножеств конечного множества Если мощность конечного множества U равна n, то число его подмножеств равно 2n .

Слайд 138


Доказательство: Доказательство: Пусть элементы множества U перенумерованы: U = {a1 , a2 , a3 ,…, an }. Установим взаимно однозначное соответствие...
Описание слайда:
Доказательство: Доказательство: Пусть элементы множества U перенумерованы: U = {a1 , a2 , a3 ,…, an }. Установим взаимно однозначное соответствие между множеством всех подмножеств U – булеаном ℬ (U) и множеством двоичных векторов длины n – Вn.

Слайд 139


Доказательство: Доказательство: Двоичный вектор v = (v1 , v2 , v3 ,…, vn ), соответствующий подмножеству М множества U: имеет координату vi = 0, если...
Описание слайда:
Доказательство: Доказательство: Двоичный вектор v = (v1 , v2 , v3 ,…, vn ), соответствующий подмножеству М множества U: имеет координату vi = 0, если ai не принадлежит U; vi = 1, если ai принадлежит U.

Слайд 140


Например: Например: Элементу булеана Ø соответсвует двоичный вектор (0, 0, …, 0); подмножеству {a1} – (1, 0,…,0); подмножеству {a2} – (0, 1,…,0);...
Описание слайда:
Например: Например: Элементу булеана Ø соответсвует двоичный вектор (0, 0, …, 0); подмножеству {a1} – (1, 0,…,0); подмножеству {a2} – (0, 1,…,0); подмножеству {a1 , a2 } – (1, 1,…,0); подмножеству U – (1, 1,…,1).

Слайд 141


Теорема о числе подмножеств конечного множества Таким образом, между множествами ℬ (U) и Вn установлено взаимно однозначное соответствие. Согласно...
Описание слайда:
Теорема о числе подмножеств конечного множества Таким образом, между множествами ℬ (U) и Вn установлено взаимно однозначное соответствие. Согласно утверждению, их мощности равны: │ℬ (U)│= │Вn │= 2n .

Слайд 142


Лекция 5 Отношения
Описание слайда:
Лекция 5 Отношения

Слайд 143


Определение:
Описание слайда:
Определение:

Слайд 144


Одноместное отношение – это просто подмножество М. Такие отношения называют признаками: элемент а – обладает признаком R, если и Одноместное...
Описание слайда:
Одноместное отношение – это просто подмножество М. Такие отношения называют признаками: элемент а – обладает признаком R, если и Одноместное отношение – это просто подмножество М. Такие отношения называют признаками: элемент а – обладает признаком R, если и Свойства одноместных отношений это свойства подмножеств М, поэтому для случая n = 1 термин «отношение» употребляется редко.

Слайд 145


Примером трехместного (тернарного) отношения является множество троек нападающих в хоккейной команде. Любой из нападающих находится в этом отношении...
Описание слайда:
Примером трехместного (тернарного) отношения является множество троек нападающих в хоккейной команде. Любой из нападающих находится в этом отношении со всеми теми игроками, с которыми он играет в одной тройке (один нападающий может, вообще говоря, участвовать более, чем в одной тройке). Примером трехместного (тернарного) отношения является множество троек нападающих в хоккейной команде. Любой из нападающих находится в этом отношении со всеми теми игроками, с которыми он играет в одной тройке (один нападающий может, вообще говоря, участвовать более, чем в одной тройке).

Слайд 146


При n = 2 – отношения называются двуместными или «бинарными». При n = 2 – отношения называются двуместными или «бинарными». Если a и b находятся в...
Описание слайда:
При n = 2 – отношения называются двуместными или «бинарными». При n = 2 – отношения называются двуместными или «бинарными». Если a и b находятся в отношении R, это записывается aRb. Таким образом, бинарное отношение, заданное на множестве М, это любое подмножество

Слайд 147


Способы задания Бинарные отношения задаются: 1) Списком; 2) Матрицей бинарного отношения; 3) Графом.
Описание слайда:
Способы задания Бинарные отношения задаются: 1) Списком; 2) Матрицей бинарного отношения; 3) Графом.

Слайд 148


Задание списком Списком задаются отношения, где М – конечное множество, а R содержит небольшое количество пар. Пример 1: – алфавит из трех букв,...
Описание слайда:
Задание списком Списком задаются отношения, где М – конечное множество, а R содержит небольшое количество пар. Пример 1: – алфавит из трех букв, отношение R – предшествования букв в алфавите. Тогда R содержит пары:

Слайд 149


Дискретная математика. Множество, слайд №149
Описание слайда:

Слайд 150


Пример 2: Отношение R – «быть больше или равно»
Описание слайда:
Пример 2: Отношение R – «быть больше или равно»

Слайд 151


Задание графом При задании графом, элементы М сопоставляются одноименным точкам. Точки a и b соединяются стрелками, если aRb. Пример 3: Отношение –...
Описание слайда:
Задание графом При задании графом, элементы М сопоставляются одноименным точкам. Точки a и b соединяются стрелками, если aRb. Пример 3: Отношение – быть меньше. Рис. 1. Задание отношения графом

Слайд 152


Свойства бинарных отношений Отношение R на М называется рефлексивным, если для любого выполняется Главная диагональ матрицы такого отношения содержит...
Описание слайда:
Свойства бинарных отношений Отношение R на М называется рефлексивным, если для любого выполняется Главная диагональ матрицы такого отношения содержит только единицы, граф – петлю в каждой вершине. Пример 4: Отношение «быть делителем», заданной на множестве N. 1 делитель 1; 2 делитель 2; 3 делитель 3; и т. д.

Слайд 153


Свойства бинарных отношений Отношение R на М называется антирефлексивным, если для любого выполняется Главная диагональ матрицы такого отношения...
Описание слайда:
Свойства бинарных отношений Отношение R на М называется антирефлексивным, если для любого выполняется Главная диагональ матрицы такого отношения содержит только нули, граф – не имеет петель. Пример 5: Отношение «быть больше», заданной на множестве N. 1 не больше 1; 2 не больше 2; 3 не больше 3; и т.д.

Слайд 154


Свойства бинарных отношений Отношение R на М называется симметричным, если для любой пары из aRb следует bRa (то есть, для любой пары отношение R...
Описание слайда:
Свойства бинарных отношений Отношение R на М называется симметричным, если для любой пары из aRb следует bRa (то есть, для любой пары отношение R выполняется в обе стороны или не выполняется вообще). Матрица симметричного отношения – симметрична относительно главной диагонали, у графа все стрелки парные, симметричные.

Слайд 155


Пример 6: Отношение «жить в одной комнате в общежитии». Если А живет в одной комнате с В, то и В живет в одной комнате с А. Если С живет в одной...
Описание слайда:
Пример 6: Отношение «жить в одной комнате в общежитии». Если А живет в одной комнате с В, то и В живет в одной комнате с А. Если С живет в одной комнате с D, то и D живет в одной комнате с C. И так далее.

Слайд 156


Свойства бинарных отношений Отношение R на М называется антисимметричным, если для любой пары из того, что одновременно выполняется: aRb и bRa...
Описание слайда:
Свойства бинарных отношений Отношение R на М называется антисимметричным, если для любой пары из того, что одновременно выполняется: aRb и bRa следует что a = b . Матрица антисимметричного отношения не имеет ни одной симметричной 1, у графа все стрелки непарные, направлены лишь в одну строну.

Слайд 157


Пример 7: Отношение «быть начальником». Если А начальник В, то В не является начальником А. Если C начальник D, то D не является начальником C. И так...
Описание слайда:
Пример 7: Отношение «быть начальником». Если А начальник В, то В не является начальником А. Если C начальник D, то D не является начальником C. И так далее.

Слайд 158


Свойства бинарных отношений Отношение R на М называется транзитивным, если для любых трех из того, что выполняется aRb и одновременно bRc следует,...
Описание слайда:
Свойства бинарных отношений Отношение R на М называется транзитивным, если для любых трех из того, что выполняется aRb и одновременно bRc следует, что aRc. Пример 8: Отношение «быть больше», заданной на множестве N. если 3 больше 2 и 2 больше 1, то 3 больше 1; если 5 больше 3 и 3 больше 1, то 5 больше 1; и т.д.

Слайд 159


Отношение эквивалентности Отношение R на М называется отношением эквивалентности, если оно Рефлексивно, Симметрично, Транзитивно.
Описание слайда:
Отношение эквивалентности Отношение R на М называется отношением эквивалентности, если оно Рефлексивно, Симметрично, Транзитивно.

Слайд 160


Пример 9: На множестве натуральных чисел задано отношение R – иметь одинаковый остаток от деления на 3. R – рефлексивно, так как каждое число само с...
Описание слайда:
Пример 9: На множестве натуральных чисел задано отношение R – иметь одинаковый остаток от деления на 3. R – рефлексивно, так как каждое число само с собой имеет одинаковый остаток от деления на 3, например 1 и 1, 2 и 2, 3 и 3, и т.д.

Слайд 161


Отношение: иметь одинаковый остаток от деления на 3 R – симметрично, так как каждое если число а имеет с числом b одинаковый остаток от деления на 3,...
Описание слайда:
Отношение: иметь одинаковый остаток от деления на 3 R – симметрично, так как каждое если число а имеет с числом b одинаковый остаток от деления на 3, то и число b с числом а тоже имеет одинаковый остаток от деления на 3. Например, 1 и 4 имеют одинаковый остаток от деления на 3, то и 4 и 1 тоже имеют одинаковый остаток; 2 и 5 имеют одинаковый остаток от деления на 3, то и 5 и 2 тоже имеют одинаковый остаток; 3 и 12 имеют одинаковый остаток от деления на 3, то и 12 и 3 тоже имеют одинаковый остаток, и т.д.

Слайд 162


Отношение: иметь одинаковый остаток от деления на 3 R – транзитивно, так для каждых чисел а , b и с если а с b имеют одинаковый остаток от деления на...
Описание слайда:
Отношение: иметь одинаковый остаток от деления на 3 R – транзитивно, так для каждых чисел а , b и с если а с b имеют одинаковый остаток от деления на 3, и b с с имеют одинаковый остаток от деления на 3, то и а с с тоже имеют одинаковый остаток от деления на 3, например 1 и 4 имеют одинаковый остаток от деления на 3, и 4 и 13 тоже имеют одинаковый остаток от деления на 3, тогда 1 и 13 тоже имеют одинаковый остаток.

Слайд 163


Отношение: иметь одинаковый остаток от деления на 3 Таким образом, отношение R – рефлексивно, симметрично и транзитивно, то есть является отношением...
Описание слайда:
Отношение: иметь одинаковый остаток от деления на 3 Таким образом, отношение R – рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности.

Слайд 164


Разбиение на классы эквивалентности Если отношение R – отношение эквивалентности, то оно разбивает множество, на котором задано, на классы...
Описание слайда:
Разбиение на классы эквивалентности Если отношение R – отношение эквивалентности, то оно разбивает множество, на котором задано, на классы эквивалентности.

Слайд 165


Разбиение на классы эквивалентности Для разбиения на классы надо: 1) Выбрать из М произвольный элемент и поместить его в класс , затем поместить в...
Описание слайда:
Разбиение на классы эквивалентности Для разбиения на классы надо: 1) Выбрать из М произвольный элемент и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему; 2) Затем из оставшихся элементов М выбрать элемент и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему; 3) Делать, пока останутся нераспределенные по классам элементы. Число классов разбиения – индекс разбиения I.

Слайд 166


Отношение: иметь одинаковый остаток от деления на 3 Для разбиения на классы надо: 1) Выбрать произвольный элемент 1 и поместить его в класс , затем...
Описание слайда:
Отношение: иметь одинаковый остаток от деления на 3 Для разбиения на классы надо: 1) Выбрать произвольный элемент 1 и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему: 4, 7, 10, 13, ... ; 2) Затем из оставшихся элементов М выбрать элемент 2 и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему: 5, 8, 11, 14, 17, … ; 3) Затем из оставшихся элементов М выбрать элемент 3 и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему: 6, 9, 12, 15, … Индекс разбиения равен 3.

Слайд 167


Отношение порядка Отношение R – отношение порядка, если оно антисимметрично и транзитивно.
Описание слайда:
Отношение порядка Отношение R – отношение порядка, если оно антисимметрично и транзитивно.

Слайд 168


Отношение порядка Отношение порядка R – отношение строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.
Описание слайда:
Отношение порядка Отношение порядка R – отношение строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.

Слайд 169


Отношение порядка Отношение порядка R – отношение нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно.
Описание слайда:
Отношение порядка Отношение порядка R – отношение нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно.

Слайд 170


Отношение порядка Если элементы a и b связаны отношением порядка, то есть aRb или bRa, то a и b сравнимы по отношению порядка R.
Описание слайда:
Отношение порядка Если элементы a и b связаны отношением порядка, то есть aRb или bRa, то a и b сравнимы по отношению порядка R.

Слайд 171


Отношение порядка Если любые два элемента a и b сравнимы по отношению порядка R, то R отношение полного или линейного порядка, а М называется...
Описание слайда:
Отношение порядка Если любые два элемента a и b сравнимы по отношению порядка R, то R отношение полного или линейного порядка, а М называется полностью упорядоченным.

Слайд 172


Пример 10: отношение «быть делителем», задано на N R – рефлексивно, так как каждое число является делителем самого себя: 1 делитель 1; 2 делитель 2;...
Описание слайда:
Пример 10: отношение «быть делителем», задано на N R – рефлексивно, так как каждое число является делителем самого себя: 1 делитель 1; 2 делитель 2; 3 делитель 3, и т.д.

Слайд 173


Отношение «быть делителем», задано на N R – антисимметрично, так как если числа разные и a делитель b,то b не является делителем a: если 1 делитель 2...
Описание слайда:
Отношение «быть делителем», задано на N R – антисимметрично, так как если числа разные и a делитель b,то b не является делителем a: если 1 делитель 2 и 2 не делитель 1; если 4 делитель 8, то 8 не делитель 4; если 3 делитель 9, то 9 не делитель 3, и т. д.

Слайд 174


Отношение «быть делителем», задано на N R – транзитивно, так как если числа разные и a делитель b и b делитель с, то а тоже является делителем с:...
Описание слайда:
Отношение «быть делителем», задано на N R – транзитивно, так как если числа разные и a делитель b и b делитель с, то а тоже является делителем с: если 1 делитель 2 и 2 делитель 4, то 1 – делитель 4; если 4 делитель 8 и 8 делитель 24, то 4 – делитель 24, и т. д.

Слайд 175


Отношение «быть делителем», задано на N R – рефлексивно, антисимметрично и транзитивно, значит R – отношение нестрогого порядка.
Описание слайда:
Отношение «быть делителем», задано на N R – рефлексивно, антисимметрично и транзитивно, значит R – отношение нестрогого порядка.

Слайд 176


Отношение «быть делителем», задано на N R – задает неполный порядок, так как можно найти хотя бы одну пару несравнимых элементов, например: 2 и 3; 7...
Описание слайда:
Отношение «быть делителем», задано на N R – задает неполный порядок, так как можно найти хотя бы одну пару несравнимых элементов, например: 2 и 3; 7 и 11; 4 и 9, и т.д.

Слайд 177


Лекция 6 Операции и алгебры
Описание слайда:
Лекция 6 Операции и алгебры

Слайд 178


Определение операции N-арная операция на множестве М – это функция типа где n – арность операции. Операция замкнута относительно множества М по...
Описание слайда:
Определение операции N-арная операция на множестве М – это функция типа где n – арность операции. Операция замкнута относительно множества М по определению, то есть операция над элементами множества М, и результат тоже элемент М.

Слайд 179


Определение алгебры Алгеброй называется множество М, вместе с заданной на нем совокупностью операций то есть система .
Описание слайда:
Определение алгебры Алгеброй называется множество М, вместе с заданной на нем совокупностью операций то есть система .

Слайд 180


М – основное (несущее) множество (носитель алгебры) алгебры А. М – основное (несущее) множество (носитель алгебры) алгебры А. Тип алгебры – вектор...
Описание слайда:
М – основное (несущее) множество (носитель алгебры) алгебры А. М – основное (несущее) множество (носитель алгебры) алгебры А. Тип алгебры – вектор арностей операций. Сигнатура – совокупность операций Σ.

Слайд 181


Множество называется замкнутым относительно n-арной операции на М, если Множество называется замкнутым относительно n-арной операции на М, если т. е....
Описание слайда:
Множество называется замкнутым относительно n-арной операции на М, если Множество называется замкнутым относительно n-арной операции на М, если т. е. если значения на аргументе из М' принадлежат М' .

Слайд 182


Если М' замкнуто относительно Если М' замкнуто относительно всех операций алгебры А с носителем М, то система называется подалгеброй алгебры А.
Описание слайда:
Если М' замкнуто относительно Если М' замкнуто относительно всех операций алгебры А с носителем М, то система называется подалгеброй алгебры А.

Слайд 183


Пример 1: Алгебра – называется полем действительных чисел. Обе операции бинарные, поэтому тип этой алгебры (2,2). Сигнатура Подалгеброй этой алгебры...
Описание слайда:
Пример 1: Алгебра – называется полем действительных чисел. Обе операции бинарные, поэтому тип этой алгебры (2,2). Сигнатура Подалгеброй этой алгебры является, например, поле рациональных чисел.

Слайд 184


Примеры 2: Пусть Определим на операции: – «сложение по модулю р», – «умножение по модулю р», следующим образом: и где с и d – остатки от деления на р...
Описание слайда:
Примеры 2: Пусть Определим на операции: – «сложение по модулю р», – «умножение по модулю р», следующим образом: и где с и d – остатки от деления на р чисел а + b и а  b соответственно.

Слайд 185


Пример 2: Пусть, например, р = 7, тогда и Часто обозначают: a + b = с (mod p) и a  b = d (mod p).
Описание слайда:
Пример 2: Пусть, например, р = 7, тогда и Часто обозначают: a + b = с (mod p) и a  b = d (mod p).

Слайд 186


Конечным полем характеристики р называется алгебра Конечным полем характеристики р называется алгебра если р – простое число.
Описание слайда:
Конечным полем характеристики р называется алгебра Конечным полем характеристики р называется алгебра если р – простое число.

Слайд 187


Пример 3: Булеаном U называется множество всех подмножеств множества U (обозначается ℬ(U)). Булева алгебра множеств над U или алгебра Кантора –...
Описание слайда:
Пример 3: Булеаном U называется множество всех подмножеств множества U (обозначается ℬ(U)). Булева алгебра множеств над U или алгебра Кантора – алгебра (ℬ(U), ) Ее тип (2,2,1), сигнатура

Слайд 188


Пример 3: Для любого B' = (ℬ(U'), U, ∩, ¬ ) – является подалгеброй В.
Описание слайда:
Пример 3: Для любого B' = (ℬ(U'), U, ∩, ¬ ) – является подалгеброй В.

Слайд 189


Пример 3: Множество U={a, b, c, d} тогда основное множество алгебры В содержит 16 элементов. B՛=(ℬ({a, b}),U, ∩, ¬ ). является подалгеброй В.
Описание слайда:
Пример 3: Множество U={a, b, c, d} тогда основное множество алгебры В содержит 16 элементов. B՛=(ℬ({a, b}),U, ∩, ¬ ). является подалгеброй В.

Слайд 190


Свойства бинарных алгебраических операций Операция φ называется ассоциативной, если для любых элементов а, b, с .
Описание слайда:
Свойства бинарных алгебраических операций Операция φ называется ассоциативной, если для любых элементов а, b, с .

Слайд 191


Пример 4: 1. Сложение и умножение чисел ассоциативны, что позволяет не ставить скобки в выражениях 2. Возведение в степень – не ассоциативна, так как...
Описание слайда:
Пример 4: 1. Сложение и умножение чисел ассоциативны, что позволяет не ставить скобки в выражениях 2. Возведение в степень – не ассоциативна, так как не равно

Слайд 192


Пример 4: 3. Прямое произведение множеств не ассоциативно:
Описание слайда:
Пример 4: 3. Прямое произведение множеств не ассоциативно:

Слайд 193


Свойства бинарных алгебраических операций Операция φ называется коммутативной, если для любых элементов a, b
Описание слайда:
Свойства бинарных алгебраических операций Операция φ называется коммутативной, если для любых элементов a, b

Слайд 194


Пример 5: 1. Сложение чисел коммутативно («от перемены мест слагаемых сумма не меняется»): 2. Умножение чисел коммутативно («от перемены мест...
Описание слайда:
Пример 5: 1. Сложение чисел коммутативно («от перемены мест слагаемых сумма не меняется»): 2. Умножение чисел коммутативно («от перемены мест множителей произведение не меняется»):

Слайд 195


Пример 5: 3. Вычитание и деление – некоммутативные операции: 4. Умножение матриц – некоммутативная операция, например:
Описание слайда:
Пример 5: 3. Вычитание и деление – некоммутативные операции: 4. Умножение матриц – некоммутативная операция, например:

Слайд 196


Свойства бинарных алгебраических операций Операция φ называется дистрибутивной слева относительно операции ψ, если для любых a, b, с
Описание слайда:
Свойства бинарных алгебраических операций Операция φ называется дистрибутивной слева относительно операции ψ, если для любых a, b, с

Слайд 197


Свойства бинарных алгебраических операций Операция φ называется дистрибутивной справа относительно операции ψ, если для любых a, b, с
Описание слайда:
Свойства бинарных алгебраических операций Операция φ называется дистрибутивной справа относительно операции ψ, если для любых a, b, с

Слайд 198


Пример 6: 1. Умножение дистрибутивно относительно сложения слева и справа
Описание слайда:
Пример 6: 1. Умножение дистрибутивно относительно сложения слева и справа

Слайд 199


Пример 6: 2. Возведение в степень дистрибутивно относительно умножения справа.
Описание слайда:
Пример 6: 2. Возведение в степень дистрибутивно относительно умножения справа.

Слайд 200


Пример 6: но не слева, так как
Описание слайда:
Пример 6: но не слева, так как

Слайд 201


Пример 6: 3. Сложение не дистрибутивно относительно умножения
Описание слайда:
Пример 6: 3. Сложение не дистрибутивно относительно умножения

Слайд 202


Лекция 7 Гомоморфизм алгебр
Описание слайда:
Лекция 7 Гомоморфизм алгебр

Слайд 203


Дискретная математика. Множество, слайд №203
Описание слайда:

Слайд 204


Дискретная математика. Множество, слайд №204
Описание слайда:

Слайд 205


Дискретная математика. Множество, слайд №205
Описание слайда:

Слайд 206


Дискретная математика. Множество, слайд №206
Описание слайда:

Слайд 207


Дискретная математика. Множество, слайд №207
Описание слайда:

Слайд 208


Дискретная математика. Множество, слайд №208
Описание слайда:

Слайд 209


Дискретная математика. Множество, слайд №209
Описание слайда:

Слайд 210


Дискретная математика. Множество, слайд №210
Описание слайда:

Слайд 211


Дискретная математика. Множество, слайд №211
Описание слайда:

Слайд 212


Дискретная математика. Множество, слайд №212
Описание слайда:

Слайд 213


Булевы алгебры Кантора образованные двумя различными множествами U и U΄ одинаковой мощности, изоморфны. Операции у них просто одинаковы, а...
Описание слайда:
Булевы алгебры Кантора образованные двумя различными множествами U и U΄ одинаковой мощности, изоморфны. Операции у них просто одинаковы, а отображением Г может служить любое взаимно однозначное соответствие между U и U΄ .

Слайд 214


Дискретная математика. Множество, слайд №214
Описание слайда:

Слайд 215


Дискретная математика. Множество, слайд №215
Описание слайда:

Слайд 216


Это позволяет получить такие соотношения в алгебре А и автоматически распространить их на все алгебры, изоморфные А. Распространенное в математике...
Описание слайда:
Это позволяет получить такие соотношения в алгебре А и автоматически распространить их на все алгебры, изоморфные А. Распространенное в математике выражение «рассматривать с точностью до изоморфизма» означает, что рассматриваются только те свойства объектов, которые сохраняются при изоморфизме, т. е. являются общими для всех изоморфных объектов. Это позволяет получить такие соотношения в алгебре А и автоматически распространить их на все алгебры, изоморфные А. Распространенное в математике выражение «рассматривать с точностью до изоморфизма» означает, что рассматриваются только те свойства объектов, которые сохраняются при изоморфизме, т. е. являются общими для всех изоморфных объектов. В частности, изоморфизм сохраняет ассоциативность, коммутативность, дистрибутивность.

Слайд 217


Лекция 8 Графы. Определения, способы задания. Виды графов.
Описание слайда:
Лекция 8 Графы. Определения, способы задания. Виды графов.

Слайд 218


Определение графа Пусть V – множество вершин, а Е – множество ребер. Графом G называется пара объектов (V, E) между которыми задано отношение...
Описание слайда:
Определение графа Пусть V – множество вершин, а Е – множество ребер. Графом G называется пара объектов (V, E) между которыми задано отношение инцидентности: Г : е → (v, w), где вершина v и ребро e инцидентны друг другу, если вершина является для этого ребра концевой точкой.

Слайд 219


Определение графа Вершины v' и v" называются смежными, если существует ребро, соединяющее их, т.е. они инцидентны одному и тому же ребру. Ребра...
Описание слайда:
Определение графа Вершины v' и v" называются смежными, если существует ребро, соединяющее их, т.е. они инцидентны одному и тому же ребру. Ребра e' и e" называются смежными, если они имеют, по крайней мере, одну общую вершину (инцидентны одной вершине).

Слайд 220


Определение графа Граф, содержащий направленные ребра (дуги) с началом v' и концом v" , называется ориентированным графом (ор-графом). Для...
Описание слайда:
Определение графа Граф, содержащий направленные ребра (дуги) с началом v' и концом v" , называется ориентированным графом (ор-графом). Для ор-графа Граф, содержащий ненаправленные ребра с конами v' и v" , называется неориентированным графом (н-графом). Для н-графа

Слайд 221


Определение графа Рис.1 Неориентированное ребро (a,b) Рис.2 Ориентированное ребро (a,b)
Описание слайда:
Определение графа Рис.1 Неориентированное ребро (a,b) Рис.2 Ориентированное ребро (a,b)

Слайд 222


Определение графа Ребро, концевые вершины которого совпадают, называется петлей. Рис.3. Неориентированная петля Рис.4. Ориентированная петля
Описание слайда:
Определение графа Ребро, концевые вершины которого совпадают, называется петлей. Рис.3. Неориентированная петля Рис.4. Ориентированная петля

Слайд 223


Определение графа Ребра (дуги), имеющие одинаковые начало и конец, называются параллельными или кратными. Рис.5. Кратные неориентированные ребра
Описание слайда:
Определение графа Ребра (дуги), имеющие одинаковые начало и конец, называются параллельными или кратными. Рис.5. Кратные неориентированные ребра

Слайд 224


Определение графа Рис. 6. Кратные ориентированные ребра
Описание слайда:
Определение графа Рис. 6. Кратные ориентированные ребра

Слайд 225


Определение графа Ребра ор-графа, соединяющие одну и туже пару вершин в разных направлениях называются симметричными или...
Описание слайда:
Определение графа Ребра ор-графа, соединяющие одну и туже пару вершин в разных направлениях называются симметричными или противоположно-направленными. Рис. 7. Симметричные ребра

Слайд 226


Определение графа Граф называется конечным, если множество его элементов (вершин и ребер) конечно. Рис. 8. Конечный граф
Описание слайда:
Определение графа Граф называется конечным, если множество его элементов (вершин и ребер) конечно. Рис. 8. Конечный граф

Слайд 227


Определение графа Граф называется бесконечным, если бесконечно множество вершин или множество его ребер. Рис. 9. Граф с бесконечным числом вершин
Описание слайда:
Определение графа Граф называется бесконечным, если бесконечно множество вершин или множество его ребер. Рис. 9. Граф с бесконечным числом вершин

Слайд 228


Определение графа Рис. 10. Граф с бесконечным числом ребер
Описание слайда:
Определение графа Рис. 10. Граф с бесконечным числом ребер

Слайд 229


Определение графа Рис. 11. Бесконечный граф
Описание слайда:
Определение графа Рис. 11. Бесконечный граф

Слайд 230


Каноническое соответствие Каждому неориентированному графу канонически соответствует ориентированный граф с тем же множеством вершин, в котором...
Описание слайда:
Каноническое соответствие Каждому неориентированному графу канонически соответствует ориентированный граф с тем же множеством вершин, в котором каждое ребро заменено двумя ориентированными ребрами, инцидентными тем же вершинам и имеющим противоположные направления.

Слайд 231


Каноническое соответствие Рис 12. Канонически соответствующие графы
Описание слайда:
Каноническое соответствие Рис 12. Канонически соответствующие графы

Слайд 232


Способы задания Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности. Пусть вершины графа ; ребра графа G. Граф...
Описание слайда:
Способы задания Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности. Пусть вершины графа ; ребра графа G. Граф задают: 1) Матрицей инцидентности. 2) Матрицу смежности. 3) Списком ребер. 4) Рисунком.

Слайд 233


Матрица инцидентности матрица инцидентности размера (строкам соответствуют ребра, столбцам – вершины графа), в которой для н-графа
Описание слайда:
Матрица инцидентности матрица инцидентности размера (строкам соответствуют ребра, столбцам – вершины графа), в которой для н-графа

Слайд 234


Матрица инцидентности для ор-графа
Описание слайда:
Матрица инцидентности для ор-графа

Слайд 235


Пример 1: Рис.13 Матрица инцидентности н-графа
Описание слайда:
Пример 1: Рис.13 Матрица инцидентности н-графа

Слайд 236


Пример 2: Рис. 14. Матрица инцидентности ор-графа
Описание слайда:
Пример 2: Рис. 14. Матрица инцидентности ор-графа

Слайд 237


Матрица смежности Матрица смежности размера , столбцам и строкам которой соответствуют вершины графа. Для н-графа равно количеству ребер, связывающих...
Описание слайда:
Матрица смежности Матрица смежности размера , столбцам и строкам которой соответствуют вершины графа. Для н-графа равно количеству ребер, связывающих i-ю и j-ю вершины, для ор-графа равно количеству ребер выходящих из i-й и входящих в j-ю вершину.

Слайд 238


Матрица смежности Матрица смежности н-графа всегда симметрична. Матрица смежности ор-графа в общем случае не симметрична. Она симметрична, если...
Описание слайда:
Матрица смежности Матрица смежности н-графа всегда симметрична. Матрица смежности ор-графа в общем случае не симметрична. Она симметрична, если данному орграфу есть канонически соответствующий н-граф.

Слайд 239


Пример 3: Рис. 15. Матрица смежности н-графа
Описание слайда:
Пример 3: Рис. 15. Матрица смежности н-графа

Слайд 240


Пример 4: Рис. 16. Матрица смежности ор-графа
Описание слайда:
Пример 4: Рис. 16. Матрица смежности ор-графа

Слайд 241


Список ребер Списком ребер можно задать граф без кратных ребер. Ребро представляется парой вершин, инцидентных ему, например е = (v, w). Для н-графа...
Описание слайда:
Список ребер Списком ребер можно задать граф без кратных ребер. Ребро представляется парой вершин, инцидентных ему, например е = (v, w). Для н-графа порядок вершин в строке произволен, для ор-графа первым стоит номер вершины–начала ребра.

Слайд 242


Рисунок Рисунок или геометрическая интерпретация появляется, если сопоставить вершинам точки плоскости, ребрам – линии на плоскости, причем, линия...
Описание слайда:
Рисунок Рисунок или геометрическая интерпретация появляется, если сопоставить вершинам точки плоскости, ребрам – линии на плоскости, причем, линия соединяет только те точки, которые соответствуют вершинам, инцидентным данной линии-ребру. Граф для которого возможна геометрическая интерпретация на плоскости, называется планарным.

Слайд 243


Пример 5: Рис. 17. Список ребер н-графа E = {(a,a), (a,b), (a,c), (b,c)}.
Описание слайда:
Пример 5: Рис. 17. Список ребер н-графа E = {(a,a), (a,b), (a,c), (b,c)}.

Слайд 244


Пример 6: Рис. 18. Список ребер ор-графа E={(a,a), (a,b), (a,c), (с,a), (b,c)}.
Описание слайда:
Пример 6: Рис. 18. Список ребер ор-графа E={(a,a), (a,b), (a,c), (с,a), (b,c)}.

Слайд 245


Планарные графы - это графы, допускающие геометрическую реализацию на плоскости без пересечения ребер. Далеко не все графы являются планарными. В...
Описание слайда:
Планарные графы - это графы, допускающие геометрическую реализацию на плоскости без пересечения ребер. Далеко не все графы являются планарными. В трехмерном пространстве можно геометрически реализовать без пересечения ребер любой граф.

Слайд 246


Планарные графы На рисунке приведен пример не планарного графа Рис. 19. Граф «три дома - три колодца»
Описание слайда:
Планарные графы На рисунке приведен пример не планарного графа Рис. 19. Граф «три дома - три колодца»

Слайд 247


Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.
Описание слайда:
Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.

Слайд 248


Изоморфные графы Рис.20. Изоморфные графы
Описание слайда:
Изоморфные графы Рис.20. Изоморфные графы

Слайд 249


Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.
Описание слайда:
Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.

Слайд 250


Пустой и полный граф Граф называется пустым, если множество ребер пусто: Рис. 21. Пустой граф
Описание слайда:
Пустой и полный граф Граф называется пустым, если множество ребер пусто: Рис. 21. Пустой граф

Слайд 251


Пустой и полный граф Н-граф называется полным, если любые две вершины связаны ребром: Рис. 22. Полный н-граф
Описание слайда:
Пустой и полный граф Н-граф называется полным, если любые две вершины связаны ребром: Рис. 22. Полный н-граф

Слайд 252


Пустой и полный граф Ор-граф называется полным, если любые две вершины связаны парой симметричных ребер: Рис. 23. Полный ор-граф
Описание слайда:
Пустой и полный граф Ор-граф называется полным, если любые две вершины связаны парой симметричных ребер: Рис. 23. Полный ор-граф

Слайд 253


Двудольный граф Граф называется двудольным если множество его ребер разбито на два подмножества, и ребрами связаны только вершины из разных...
Описание слайда:
Двудольный граф Граф называется двудольным если множество его ребер разбито на два подмножества, и ребрами связаны только вершины из разных подмножеств.

Слайд 254


Двудольный граф Рис. 6. Двудольный граф
Описание слайда:
Двудольный граф Рис. 6. Двудольный граф

Слайд 255


Двудольный граф Граф называется полным двудольным, если каждая вершина Связана ребром с каждой вершиной Рис. 24. Полный двудольный граф
Описание слайда:
Двудольный граф Граф называется полным двудольным, если каждая вершина Связана ребром с каждой вершиной Рис. 24. Полный двудольный граф

Слайд 256


Двудольный граф Если а то полный двудольный граф обозначается:
Описание слайда:
Двудольный граф Если а то полный двудольный граф обозначается:

Слайд 257


Двудольный граф Рис. 25. Полный двудольный граф
Описание слайда:
Двудольный граф Рис. 25. Полный двудольный граф

Слайд 258


Двудольный граф Рис. 26. Полный двудольный граф На рис. 24 приведен пример На рис. 19 приведен пример
Описание слайда:
Двудольный граф Рис. 26. Полный двудольный граф На рис. 24 приведен пример На рис. 19 приведен пример

Слайд 259


Лекция 9 Локальные степени вершин
Описание слайда:
Лекция 9 Локальные степени вершин

Слайд 260


Локальные степени вершин н-графа Пусть G = (V, E) – н-граф. Локальной степенью вершины называется число равное числу ребер, инцидентных вершине v....
Описание слайда:
Локальные степени вершин н-графа Пусть G = (V, E) – н-граф. Локальной степенью вершины называется число равное числу ребер, инцидентных вершине v. При этом вклад петли в степень вершины равен 2.

Слайд 261


Локальные степени вершин н-графа Вектор степеней н-графа G = (V, E) – вектор размерности n, составленный из степеней вершин графа, расположенных по...
Описание слайда:
Локальные степени вершин н-графа Вектор степеней н-графа G = (V, E) – вектор размерности n, составленный из степеней вершин графа, расположенных по убыванию.

Слайд 262


Локальные степени вершин н-графа ρ(a)=5 ρ(b)=2 ρ(c)=3 ρ(d)=0 Вектор степеней ρ = (5, 3, 2, 0) Рис.1 Степени вершин н-графа
Описание слайда:
Локальные степени вершин н-графа ρ(a)=5 ρ(b)=2 ρ(c)=3 ρ(d)=0 Вектор степеней ρ = (5, 3, 2, 0) Рис.1 Степени вершин н-графа

Слайд 263


Локальные степени вершин н-графа Замечание 1: векторы степеней изоморфных графов одинаковы: ρ = (5,3,2,0) Рис. 2. Граф, изоморфный графу на рис.1
Описание слайда:
Локальные степени вершин н-графа Замечание 1: векторы степеней изоморфных графов одинаковы: ρ = (5,3,2,0) Рис. 2. Граф, изоморфный графу на рис.1

Слайд 264


Локальные степени вершин н-графа Замечание 2: Сумма всех локальных степеней вершин н-графа равна удвоенному количеству ребер. - число ребер н-графа.
Описание слайда:
Локальные степени вершин н-графа Замечание 2: Сумма всех локальных степеней вершин н-графа равна удвоенному количеству ребер. - число ребер н-графа.

Слайд 265


Локальные степени вершин н-графа Теорема (о числе вершин нечетной степени) Число вершин нечетной степени – четно.
Описание слайда:
Локальные степени вершин н-графа Теорема (о числе вершин нечетной степени) Число вершин нечетной степени – четно.

Слайд 266


Локальные степени вершин н-графа Доказательство: Сумма в левой части равенства – четна. Если убрать все четные слагаемые, сумма останется четной....
Описание слайда:
Локальные степени вершин н-графа Доказательство: Сумма в левой части равенства – четна. Если убрать все четные слагаемые, сумма останется четной. Сумма нечетных слагаемых четна, если их четное число.

Слайд 267


Локальные степени вершин н-графа Однородным степени k называется н-граф, локальные степени которого одинаковы и равны k. Для однородного графа...
Описание слайда:
Локальные степени вершин н-графа Однородным степени k называется н-граф, локальные степени которого одинаковы и равны k. Для однородного графа степени k:

Слайд 268


Локальные степени вершин н-графа Локально-конечным называется н-граф, все локальные степени которого конечны. Рис. 3. Локально- конечный, бесконечный...
Описание слайда:
Локальные степени вершин н-графа Локально-конечным называется н-граф, все локальные степени которого конечны. Рис. 3. Локально- конечный, бесконечный однородный граф степени 4.

Слайд 269


Локальные степени вершин ор-графа Пусть G = (V, E) – ор-граф. Локальной степенью исхода вершины называется число равное числу ребер, выходящих из...
Описание слайда:
Локальные степени вершин ор-графа Пусть G = (V, E) – ор-граф. Локальной степенью исхода вершины называется число равное числу ребер, выходящих из вершины v.

Слайд 270


Локальные степени вершин ор-графа Локальной степенью захода вершины называется число равное числу ребер, входящих в вершину v.
Описание слайда:
Локальные степени вершин ор-графа Локальной степенью захода вершины называется число равное числу ребер, входящих в вершину v.

Слайд 271


Локальные степени вершин ор-графа Вектор степеней исхода ор-графа G = (V, E) – вектор размерности n, составленный из степеней исхода вершин графа,...
Описание слайда:
Локальные степени вершин ор-графа Вектор степеней исхода ор-графа G = (V, E) – вектор размерности n, составленный из степеней исхода вершин графа, расположенных по убыванию.

Слайд 272


Локальные степени вершин ор-графа Вектор степеней захода ор-графа – вектор размерности n, составленный из степеней захода вершин графа, расположенных...
Описание слайда:
Локальные степени вершин ор-графа Вектор степеней захода ор-графа – вектор размерности n, составленный из степеней захода вершин графа, расположенных по убыванию.

Слайд 273


Локальные степени вершин ор-графа
Описание слайда:
Локальные степени вершин ор-графа

Слайд 274


Локальные степени вершин ор-графа Замечание 3: Векторы степеней исхода и степеней захода изоморфных графов одинаковы.
Описание слайда:
Локальные степени вершин ор-графа Замечание 3: Векторы степеней исхода и степеней захода изоморфных графов одинаковы.

Слайд 275


Дискретная математика. Множество, слайд №275
Описание слайда:

Слайд 276


Локальные степени вершин н-графа Замечание 4: Сумма всех локальных степеней исхода вершин и сумма всех локальных степеней захода ор-графа равна...
Описание слайда:
Локальные степени вершин н-графа Замечание 4: Сумма всех локальных степеней исхода вершин и сумма всех локальных степеней захода ор-графа равна количеству ребер.

Слайд 277


Локальные степени вершин ор-графа Однородным степени k называется ор-граф, локальные степени исхода и степени захода которого одинаковы и равны k....
Описание слайда:
Локальные степени вершин ор-графа Однородным степени k называется ор-граф, локальные степени исхода и степени захода которого одинаковы и равны k. Для однородного графа степени k:

Слайд 278


Локальные степени вершин ор-графа Локально-конечным называется ор-граф, все локальные степени исхода и захода которого конечны. Рис. 5. Локально-...
Описание слайда:
Локальные степени вершин ор-графа Локально-конечным называется ор-граф, все локальные степени исхода и захода которого конечны. Рис. 5. Локально- конечный, бесконечный однородный граф степени 2.

Слайд 279


Лекция 10 Части графа. Операции над частями графа
Описание слайда:
Лекция 10 Части графа. Операции над частями графа

Слайд 280


Часть графа Пусть G = (V, E) – н-граф. Частью (подграфом) графа G называется граф Н =(V', E' ), где V' V, E' E , причем все ребра множества E' входят...
Описание слайда:
Часть графа Пусть G = (V, E) – н-граф. Частью (подграфом) графа G называется граф Н =(V', E' ), где V' V, E' E , причем все ребра множества E' входят в граф Н вместе со своими концами.

Слайд 281


Суграф Подграф Н = (V', E' ), называется суграфом, если V' = V. Суграф называется покрывающим, если каждая вершина инцидентна хотя бы одному ребру...
Описание слайда:
Суграф Подграф Н = (V', E' ), называется суграфом, если V' = V. Суграф называется покрывающим, если каждая вершина инцидентна хотя бы одному ребру графа G.

Слайд 282


Подграф, порожденным множеством вершин Подграф Н = (V', E' ), называется подграфом, порожденным множеством вершин А V, если V' = А, E' состоит из...
Описание слайда:
Подграф, порожденным множеством вершин Подграф Н = (V', E' ), называется подграфом, порожденным множеством вершин А V, если V' = А, E' состоит из ребер множества Е, соединяющих вершины множества А.

Слайд 283


Звездный граф Подграф Н = (V', E' ), называется звездным графом вершины если V' составляют вершина v и все смежные ей вершины, E' состоит из ребер...
Описание слайда:
Звездный граф Подграф Н = (V', E' ), называется звездным графом вершины если V' составляют вершина v и все смежные ей вершины, E' состоит из ребер множества Е, инцидентных вершине v.

Слайд 284


Пример покрывающего суграфа G(V,E) Н1 = (V', E' ) Рис.1. Покрывающий суграф
Описание слайда:
Пример покрывающего суграфа G(V,E) Н1 = (V', E' ) Рис.1. Покрывающий суграф

Слайд 285


Пример непокрывающего суграфа G(V,E) Н2 = (V', E' ) Рис.2. Непокрывающий суграф
Описание слайда:
Пример непокрывающего суграфа G(V,E) Н2 = (V', E' ) Рис.2. Непокрывающий суграф

Слайд 286


Пример подграфа, порожденного множеством А G(V,E) Н3 = (А, E' ), А={3,4,5,6} Рис.3. Подграф, порожденный множеством А
Описание слайда:
Пример подграфа, порожденного множеством А G(V,E) Н3 = (А, E' ), А={3,4,5,6} Рис.3. Подграф, порожденный множеством А

Слайд 287


Пример звездного графа G(V,E) Н4 = (V', E' ) = Z(4) Рис. 4. Звездный граф
Описание слайда:
Пример звездного графа G(V,E) Н4 = (V', E' ) = Z(4) Рис. 4. Звездный граф

Слайд 288


Операции над частями графа Суммой подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется граф Н = (V, E ), такой что Обозначается:
Описание слайда:
Операции над частями графа Суммой подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется граф Н = (V, E ), такой что Обозначается:

Слайд 289


Операции над частями графа Пересечением подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется граф D = (V, E ), такой что Обозначается:
Описание слайда:
Операции над частями графа Пересечением подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется граф D = (V, E ), такой что Обозначается:

Слайд 290


Операции над частями графа Сумма подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется прямой по ребрам, если у них нет общих ребер:
Описание слайда:
Операции над частями графа Сумма подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется прямой по ребрам, если у них нет общих ребер:

Слайд 291


Операции над частями графа Сумма подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется прямой по вершинам, если у них нет общих вершин:
Описание слайда:
Операции над частями графа Сумма подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется прямой по вершинам, если у них нет общих вершин:

Слайд 292


Операции над частями графа Дополнением подграфа Н = (V1, E1 ) до графа G = (V, E ) называется подграф где множество его ребер:
Описание слайда:
Операции над частями графа Дополнением подграфа Н = (V1, E1 ) до графа G = (V, E ) называется подграф где множество его ребер:

Слайд 293


Операции над частями графа а множество вершин V2 состоит из всех вершин множества V, инцидентных ребрам из Е2 и всех изолированных вершин, не...
Описание слайда:
Операции над частями графа а множество вершин V2 состоит из всех вершин множества V, инцидентных ребрам из Е2 и всех изолированных вершин, не попавших в множество V1.

Слайд 294


Пример суммы подграфов Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 5. Сумма подграфов
Описание слайда:
Пример суммы подграфов Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 5. Сумма подграфов

Слайд 295


Пример пересечения подграфов Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 6. Пересечение подграфов
Описание слайда:
Пример пересечения подграфов Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 6. Пересечение подграфов

Слайд 296


Пример суммы, прямой по ребрам Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 7. Прямая по ребрам сумма подграфов
Описание слайда:
Пример суммы, прямой по ребрам Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 7. Прямая по ребрам сумма подграфов

Слайд 297


Пример суммы, прямой по вершинам Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 8. Прямая сумма подграфов
Описание слайда:
Пример суммы, прямой по вершинам Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 8. Прямая сумма подграфов

Слайд 298


Пример дополнения Н = (V1, E1 ) G(V,E) Рис. 9. Дополнение
Описание слайда:
Пример дополнения Н = (V1, E1 ) G(V,E) Рис. 9. Дополнение

Слайд 299


Замечание: Подграф и его дополнение являются прямой суммой по ребрам:
Описание слайда:
Замечание: Подграф и его дополнение являются прямой суммой по ребрам:

Слайд 300


Лекция 11 Маршруты. Расстояние в графе
Описание слайда:
Лекция 11 Маршруты. Расстояние в графе

Слайд 301


Маршруты Пусть G = (V, E) – н-граф. Маршрутом в графе G называется чередующаяся последовательность вершин и ребер где ребро инцидентно вершинам
Описание слайда:
Маршруты Пусть G = (V, E) – н-граф. Маршрутом в графе G называется чередующаяся последовательность вершин и ребер где ребро инцидентно вершинам

Слайд 302


Маршруты Вершина - начальная вершина маршрута М, – конечная, – внутренняя вершина, маршрут соединяющий и Дина маршрута – число его ребер.
Описание слайда:
Маршруты Вершина - начальная вершина маршрута М, – конечная, – внутренняя вершина, маршрут соединяющий и Дина маршрута – число его ребер.

Слайд 303


Маршруты Маршрут М называется маршрутом общего вида, если вершины и ребра повторяются, цепью – если его ребра не повторяются, простой цепью – если...
Описание слайда:
Маршруты Маршрут М называется маршрутом общего вида, если вершины и ребра повторяются, цепью – если его ребра не повторяются, простой цепью – если его вершины не повторяются.

Слайд 304


Маршруты Маршрут М называется циклическим, если начальная и конечная вершина совпадают. Замечание: совпадают, не значит повторяются.
Описание слайда:
Маршруты Маршрут М называется циклическим, если начальная и конечная вершина совпадают. Замечание: совпадают, не значит повторяются.

Слайд 305


Маршруты Циклический маршрут М называется маршрутом общего вида, если вершины и ребра повторяются, циклом – если его ребра не повторяются, простым...
Описание слайда:
Маршруты Циклический маршрут М называется маршрутом общего вида, если вершины и ребра повторяются, циклом – если его ребра не повторяются, простым циклом – если его вершины не повторяются (кроме начала и конца). .

Слайд 306


Пример 1 М1 = (1, 2, 3, 4, 1, 3, 4, 5) – общего вида. М2 = (1, 2, 3, 4, 1, 5) – цепь М3 = (5, 6, 3, 4, 1) – простая цепь. Рис.1. Маршруты
Описание слайда:
Пример 1 М1 = (1, 2, 3, 4, 1, 3, 4, 5) – общего вида. М2 = (1, 2, 3, 4, 1, 5) – цепь М3 = (5, 6, 3, 4, 1) – простая цепь. Рис.1. Маршруты

Слайд 307


Маршруты М1 =(1, 2, 3, 1, 2, 3, 1) – циклический маршрут общего вида. М1 =(1, 3, 4, 5, 6, 4, 1) – цикл (не простой) М1 =(1, 2, 3, 4, 1) – простой...
Описание слайда:
Маршруты М1 =(1, 2, 3, 1, 2, 3, 1) – циклический маршрут общего вида. М1 =(1, 3, 4, 5, 6, 4, 1) – цикл (не простой) М1 =(1, 2, 3, 4, 1) – простой цикл. Рис.2. Циклические маршруты

Слайд 308


Расстояния в графе Расстоянием между вершинами a и b называется длина минимальной простой цепи, связывающей их. Расстояние обозначается d(a, b)....
Описание слайда:
Расстояния в графе Расстоянием между вершинами a и b называется длина минимальной простой цепи, связывающей их. Расстояние обозначается d(a, b). Аксиомы метрики: 1) d(a, b) = d(b, a); 2) d(a, b) ≥ 0, d(a, b) = 0 ↔ a = b; 3) d(a, b) ≤ d(a, c) + d(c, b)

Слайд 309


Расстояния в графе
Описание слайда:
Расстояния в графе

Слайд 310


Расстояния в графе ri – эксцентриситет i-ой вершины – расстояние от этой вершины до наиболее удаленной от нее вершины. ri = max d(vi,vj) по всем j от...
Описание слайда:
Расстояния в графе ri – эксцентриситет i-ой вершины – расстояние от этой вершины до наиболее удаленной от нее вершины. ri = max d(vi,vj) по всем j от 1 до n.

Слайд 311


Расстояния в графе Диаметр графа G – максимальное расстояние между вершинами графа d(G)= max d(vi,vj) по всем i и j от 1 до n, или d(G)=max ri по...
Описание слайда:
Расстояния в графе Диаметр графа G – максимальное расстояние между вершинами графа d(G)= max d(vi,vj) по всем i и j от 1 до n, или d(G)=max ri по всем i от 1 до n.

Слайд 312


Расстояния в графе Центр графа G – это вершина, расстояние от которой до наиболее удаленной вершины – минимальное. Что бы найти центр, надо сначала...
Описание слайда:
Расстояния в графе Центр графа G – это вершина, расстояние от которой до наиболее удаленной вершины – минимальное. Что бы найти центр, надо сначала найти радиус графа.

Слайд 313


Расстояния в графе Радиус графа G –расстояние от центра графа до наиболее удаленной вершины. r (G) = min ri по всем i от 1 до n.
Описание слайда:
Расстояния в графе Радиус графа G –расстояние от центра графа до наиболее удаленной вершины. r (G) = min ri по всем i от 1 до n.

Слайд 314


Расстояния в графе Центр графа G –такая вершина vi, для которой ri = r(G). Замечание: Центр в графе может быть не единственный.
Описание слайда:
Расстояния в графе Центр графа G –такая вершина vi, для которой ri = r(G). Замечание: Центр в графе может быть не единственный.

Слайд 315


Расстояния в графе В нашем примере центром является вершина 5. Радиус – 1, диаметр – 2.
Описание слайда:
Расстояния в графе В нашем примере центром является вершина 5. Радиус – 1, диаметр – 2.

Слайд 316


Расстояния в графе Диаметральные цепи графа G – простые цепи, длина которых равна d(G), соединяющие наиболее удаленные вершины графа.
Описание слайда:
Расстояния в графе Диаметральные цепи графа G – простые цепи, длина которых равна d(G), соединяющие наиболее удаленные вершины графа.

Слайд 317


Расстояния в графе Радиальные цепи графа G – простые цепи, длина которых равна r(G), соединяющие центр и наиболее удаленные от него вершины графа.
Описание слайда:
Расстояния в графе Радиальные цепи графа G – простые цепи, длина которых равна r(G), соединяющие центр и наиболее удаленные от него вершины графа.

Слайд 318


Расстояния в графе D1=(1,5,4), D2=(1,3,4), D3=(1,2,4), D4=(2,5,3), D5=(2,1,3), D6=(2,4,3), R1=(5,1), R2=(5,2), R3=(5,3), R4=(5,4). Рис.4. Расстояния
Описание слайда:
Расстояния в графе D1=(1,5,4), D2=(1,3,4), D3=(1,2,4), D4=(2,5,3), D5=(2,1,3), D6=(2,4,3), R1=(5,1), R2=(5,2), R3=(5,3), R4=(5,4). Рис.4. Расстояния

Слайд 319


Лекция 12 Связные компоненты графа
Описание слайда:
Лекция 12 Связные компоненты графа

Слайд 320


Связность Пусть G = (V, E) – н-граф. связными называются вершины a и b если существуют маршрут, связывающий их. Н-граф G называется связным, если все...
Описание слайда:
Связность Пусть G = (V, E) – н-граф. связными называются вершины a и b если существуют маршрут, связывающий их. Н-граф G называется связным, если все его вершины связны.

Слайд 321


Связность Утверждение: отношение связности является отношением эквивалентности. Доказательство: 1.Каждая вершина связана сама с собой маршрутом...
Описание слайда:
Связность Утверждение: отношение связности является отношением эквивалентности. Доказательство: 1.Каждая вершина связана сама с собой маршрутом нулевой длины, значит отношение связности рефлексивно.

Слайд 322


Связность 2. Если вершина a связна с b, то и b связна с a. Если a с b связаны маршрутом М(a,b), то b с a связаны маршрутом М(b,a), где ребра и...
Описание слайда:
Связность 2. Если вершина a связна с b, то и b связна с a. Если a с b связаны маршрутом М(a,b), то b с a связаны маршрутом М(b,a), где ребра и вершины идут в обратном порядке. Значит отношение связности симметрично.

Слайд 323


Связность 3. Если вершина a связана маршрутом с b, b связана с с, то и a связана маршрутом с с. Это маршрут, начало которого М(a,b), окончание –...
Описание слайда:
Связность 3. Если вершина a связана маршрутом с b, b связана с с, то и a связана маршрутом с с. Это маршрут, начало которого М(a,b), окончание – M(b,c), вершина b – общая. Значит отношение связности транзитивно.

Слайд 324


Связность Отношение рефлексивно, симметрично и транзитивно, значит является отношением эквивалентности. Множество вершин V разбивается отношением...
Описание слайда:
Связность Отношение рефлексивно, симметрично и транзитивно, значит является отношением эквивалентности. Множество вершин V разбивается отношением связности на классы эквивалентности – подмножества связных вершин.

Слайд 325


Связность Связными компонентами графа G называются подграфы, порожденные классами эквивалентности по отношению связности. Замечание: В связном графе...
Описание слайда:
Связность Связными компонентами графа G называются подграфы, порожденные классами эквивалентности по отношению связности. Замечание: В связном графе одна связная компонента.

Слайд 326


Связные компоненты V={a,b,c,d,g}, класс V1 = { a,c,d }, класс V2 = {b,g}. Рис. 1. Связные компоненты
Описание слайда:
Связные компоненты V={a,b,c,d,g}, класс V1 = { a,c,d }, класс V2 = {b,g}. Рис. 1. Связные компоненты

Слайд 327


Разделяющие множества Разделяющим множеством н-графа G = (V, E) называется множество ребер, при удалении которых число компонент связности графа...
Описание слайда:
Разделяющие множества Разделяющим множеством н-графа G = (V, E) называется множество ребер, при удалении которых число компонент связности графа увеличивается.

Слайд 328


Разделяющие множества Разрезом в н-графе G =(V, E) называется разделяющее множество в котором нет лишних ребер, то есть минимальное разделяющее...
Описание слайда:
Разделяющие множества Разрезом в н-графе G =(V, E) называется разделяющее множество в котором нет лишних ребер, то есть минимальное разделяющее множество.

Слайд 329


Разделяющие множества Мостом или перешейком в н-графе G = (V, E) называется разрез, состоящий из одного ребра.
Описание слайда:
Разделяющие множества Мостом или перешейком в н-графе G = (V, E) называется разрез, состоящий из одного ребра.

Слайд 330


Рис.2. Разделяющее множество Разделяющее множество: {(1,4), (2,3), (7,8)}; разрез:{(1,4), (2,3)}, (7,8) – лишнее; мост :{(4,5) }.
Описание слайда:
Рис.2. Разделяющее множество Разделяющее множество: {(1,4), (2,3), (7,8)}; разрез:{(1,4), (2,3)}, (7,8) – лишнее; мост :{(4,5) }.

Слайд 331


Шарнир Вершина н-графа G = (V, E) называется шарниром, если удаление этой вершины и всех инцидентных ей ребер приводит к увеличению числа компонент...
Описание слайда:
Шарнир Вершина н-графа G = (V, E) называется шарниром, если удаление этой вершины и всех инцидентных ей ребер приводит к увеличению числа компонент связности графа.

Слайд 332


Шарнир Рис.3. Шарнир в графе Шарниром является вершина 4.
Описание слайда:
Шарнир Рис.3. Шарнир в графе Шарниром является вершина 4.

Слайд 333


Лекция 13 Задачи об обходах
Описание слайда:
Лекция 13 Задачи об обходах

Слайд 334


Задача о мостах Кёнигсберга Рис.1. Карта мостов Кенигсберга во времена Эйлера
Описание слайда:
Задача о мостах Кёнигсберга Рис.1. Карта мостов Кенигсберга во времена Эйлера

Слайд 335


Граф – схема мостов Части города – вершины, мосты – ребра. Из рисунка видно, что задача, поставленная Эйлером, не выполнима. Рис.2. Граф,...
Описание слайда:
Граф – схема мостов Части города – вершины, мосты – ребра. Из рисунка видно, что задача, поставленная Эйлером, не выполнима. Рис.2. Граф, соответствующий схеме мостов

Слайд 336


Известные головоломки Рис.3. Сабли Магомеда Рис.4. Пентаграмма
Описание слайда:
Известные головоломки Рис.3. Сабли Магомеда Рис.4. Пентаграмма

Слайд 337


Эйлеров граф Эйлеровым циклом в н-графе называется цикл, обходящий все ребра графа (ровно по одному разу). Эйлеров граф – граф, в котором есть...
Описание слайда:
Эйлеров граф Эйлеровым циклом в н-графе называется цикл, обходящий все ребра графа (ровно по одному разу). Эйлеров граф – граф, в котором есть эйлеров цикл.

Слайд 338


Полуэйлеров граф Эйлеровой цепью в н-графе называется цепь, обходящая все ребра графа (ровно по одному разу). Полуэйлеров граф – граф, в котором есть...
Описание слайда:
Полуэйлеров граф Эйлеровой цепью в н-графе называется цепь, обходящая все ребра графа (ровно по одному разу). Полуэйлеров граф – граф, в котором есть эйлерова цепь.

Слайд 339


Теорема Эйлера (условие эйлеровости графа) Для того, чтобы произвольный н-граф был эйлеровым, необходимо и достаточно, чтобы он был связен; локальные...
Описание слайда:
Теорема Эйлера (условие эйлеровости графа) Для того, чтобы произвольный н-граф был эйлеровым, необходимо и достаточно, чтобы он был связен; локальные степени всех его вершин были четными.

Слайд 340


Теорема (условие полуэйлеровости графа) Для того, чтобы произвольный н-граф был полуэйлеровым, необходимо и достаточно, чтобы: 1) он был связен; 2)...
Описание слайда:
Теорема (условие полуэйлеровости графа) Для того, чтобы произвольный н-граф был полуэйлеровым, необходимо и достаточно, чтобы: 1) он был связен; 2) локальные степени всех его вершин, кроме двух, были четными. Вершины с нечетными степенями являются началом и концом эйлеровой цепи.

Слайд 341


Эйлеров, полуэйлеров, не эйлеров графы Рис.5. Эйлеров граф Рис.6. Полуэйлеров граф Рис.7. Не эйлеров граф
Описание слайда:
Эйлеров, полуэйлеров, не эйлеров графы Рис.5. Эйлеров граф Рис.6. Полуэйлеров граф Рис.7. Не эйлеров граф

Слайд 342


Алгоритм Флери При построении эйлерова цикла начинаем с произвольной вершины и двигаемся в произвольном направлении выполняя два условия: стираем...
Описание слайда:
Алгоритм Флери При построении эйлерова цикла начинаем с произвольной вершины и двигаемся в произвольном направлении выполняя два условия: стираем пройденные ребра и изолированные вершины, которые при этом появляются; идем по мосту, только если нет другой возможности.

Слайд 343


Рис. 8. Пример построения эйлерова цикла
Описание слайда:
Рис. 8. Пример построения эйлерова цикла

Слайд 344


Гамильтонов граф Гамильтоновым циклом в н-графе называется простой цикл, обходящий все вершины графа (ровно по одному разу). Гамильтонов граф – граф,...
Описание слайда:
Гамильтонов граф Гамильтоновым циклом в н-графе называется простой цикл, обходящий все вершины графа (ровно по одному разу). Гамильтонов граф – граф, в котором есть гамильтонов цепь.

Слайд 345


Полугамильтонов граф Гамильтоновой цепью в н-графе называется простая цепь, обходящий все вершины графа (ровно по одному разу). Полугамильтонов граф...
Описание слайда:
Полугамильтонов граф Гамильтоновой цепью в н-графе называется простая цепь, обходящий все вершины графа (ровно по одному разу). Полугамильтонов граф – граф, в котором есть гамильтонова цикл.

Слайд 346


Гамильтонов, полугамильтонов графы Рис.9. Гамильтонов граф Рис.10. Полугамильтонов граф
Описание слайда:
Гамильтонов, полугамильтонов графы Рис.9. Гамильтонов граф Рис.10. Полугамильтонов граф

Слайд 347


Задача о кратчайшем пути Пусть G = (V, E) – н-граф. Пусть каждому ребру e графа приписано положительное число – длина ребра L(e). Задача заключается...
Описание слайда:
Задача о кратчайшем пути Пусть G = (V, E) – н-граф. Пусть каждому ребру e графа приписано положительное число – длина ребра L(e). Задача заключается в нахождении маршрута от вершины a к вершине b, наименьшей длины.

Слайд 348


Алгоритм Присвоим всем вершинам метки s(v) = +∞, причем метка s(а) = 0. Проверим каждое ребро (vi , vj) на выполнение условия пересчета: s(vj) -...
Описание слайда:
Алгоритм Присвоим всем вершинам метки s(v) = +∞, причем метка s(а) = 0. Проверим каждое ребро (vi , vj) на выполнение условия пересчета: s(vj) - s(vi) > L(vi,vj). Если это так, пересчитаем метку конца ребра: s(vj) = s(vi) + L(vi,vj).

Слайд 349


Алгоритм Совершаем пересчет меток до тех пор, пока не перестанет выполнятся указанное условие. Метка, которую получила вершина b является длиной...
Описание слайда:
Алгоритм Совершаем пересчет меток до тех пор, пока не перестанет выполнятся указанное условие. Метка, которую получила вершина b является длиной искомого маршрута.

Слайд 350


Пример 1 Рис. 11. Задача о кратчайшем пути
Описание слайда:
Пример 1 Рис. 11. Задача о кратчайшем пути

Слайд 351


Задача о кратчайшем пути
Описание слайда:
Задача о кратчайшем пути

Слайд 352


Задача о кратчайшем пути
Описание слайда:
Задача о кратчайшем пути

Слайд 353


Задача о кратчайшем пути Таким образом, длина кратчайшего пути равна 5. Возвращаясь от вершины 6 переходя к вершинам, инцидентным ребрам, ведущим в...
Описание слайда:
Задача о кратчайшем пути Таким образом, длина кратчайшего пути равна 5. Возвращаясь от вершины 6 переходя к вершинам, инцидентным ребрам, ведущим в вершину 6, доходим о вершины 2. μ = ( 2, 1, 5, 7, 6)

Слайд 354


Лекция 14 Деревья
Описание слайда:
Лекция 14 Деревья

Слайд 355


Определения дерева Пусть G =(V, E) – н-граф. Деревом называется связный ациклический граф. Рис. 1. Дерево
Описание слайда:
Определения дерева Пусть G =(V, E) – н-граф. Деревом называется связный ациклический граф. Рис. 1. Дерево

Слайд 356


Определение леса Лесом называется несвязный ациклический граф. Рис. 2. Лес
Описание слайда:
Определение леса Лесом называется несвязный ациклический граф. Рис. 2. Лес

Слайд 357


Теорема 1 (о деревьях) Граф будет дерево тогда и только тогда, когда любые две его вершины связаны единственной простой цепью. Связность дает наличие...
Описание слайда:
Теорема 1 (о деревьях) Граф будет дерево тогда и только тогда, когда любые две его вершины связаны единственной простой цепью. Связность дает наличие такой цепи, ацикличность – ее единственность. Рис. 3. Теорема 1

Слайд 358


Терема 2 (о деревьях) Граф с n вершинами будет деревом тогда и только тогда, в нем ровно n-1 ребро. Если ориентировать дерево о выбранной вершины, то...
Описание слайда:
Терема 2 (о деревьях) Граф с n вершинами будет деревом тогда и только тогда, в нем ровно n-1 ребро. Если ориентировать дерево о выбранной вершины, то в каждую вершину будет входить 1 ребро, а в а0 – 0. Рис. 4. Теорема 2

Слайд 359


Вершины максимального типа Дано неориентированное дерево Т. Концевые вершины дерева – вершины, локальная степень которых равна 1. Назовем их...
Описание слайда:
Вершины максимального типа Дано неориентированное дерево Т. Концевые вершины дерева – вершины, локальная степень которых равна 1. Назовем их вершинами первого типа дерева Т. Рис. 5. Вершины 1 типа

Слайд 360


Вершины максимального типа Удалим из дерева Т ребра, инцидентные концевым вершинам – концевые ребра. Получим дерево Т1. Концевые вершины дерева Т1 –...
Описание слайда:
Вершины максимального типа Удалим из дерева Т ребра, инцидентные концевым вершинам – концевые ребра. Получим дерево Т1. Концевые вершины дерева Т1 – Вершины типа 2. Рис. 6. Вершины 2 типа

Слайд 361


Вершины максимального типа Удалим из дерева Т1 концевые ребра. Получим дерево Т2. Концевые вершины дерева Т2 – вершины типа 3. Рис. 7. Вершины...
Описание слайда:
Вершины максимального типа Удалим из дерева Т1 концевые ребра. Получим дерево Т2. Концевые вершины дерева Т2 – вершины типа 3. Рис. 7. Вершины максимального типа

Слайд 362


Вершины максимального типа Утверждение 1: В конечном дереве есть вершины только конечного числа типов. Утверждение 2: Вершин максимального типа k...
Описание слайда:
Вершины максимального типа Утверждение 1: В конечном дереве есть вершины только конечного числа типов. Утверждение 2: Вершин максимального типа k одна или две.

Слайд 363


Вершины максимального типа Утверждение 3: Центрами деревьев являются вершины максимального типа k и только они. Все диаметральные цепи проходят через...
Описание слайда:
Вершины максимального типа Утверждение 3: Центрами деревьев являются вершины максимального типа k и только они. Все диаметральные цепи проходят через центры. Длина диаметральной цепи равна 2k-1, если центра два и 2k-2, если центр один.

Слайд 364


Вершины максимального типа k = 3 , центров два, длина диаметральной цепи 2k-1=5. Рис. 8. Диаметральная цепь
Описание слайда:
Вершины максимального типа k = 3 , центров два, длина диаметральной цепи 2k-1=5. Рис. 8. Диаметральная цепь

Слайд 365


Корень дерева Если дерево не ориентировано, то его можно ориентировать от корня. Корень – это один из центров дерева.
Описание слайда:
Корень дерева Если дерево не ориентировано, то его можно ориентировать от корня. Корень – это один из центров дерева.

Слайд 366


Корень дерева У всех вершин дерева локальные степени захода равны 1, а у корня 0. Вершины, степени исхода которых равны 0 называются листьями....
Описание слайда:
Корень дерева У всех вершин дерева локальные степени захода равны 1, а у корня 0. Вершины, степени исхода которых равны 0 называются листьями. Высотой дерева называется наибольшее расстояние от корня до листа.

Слайд 367


Рис. 9 Листья
Описание слайда:
Рис. 9 Листья

Слайд 368


Бинарное дерево Бинарным деревом называется ориентированное дерево с корнем, где каждая вершина имеет локальную степень исхода, равную 2.
Описание слайда:
Бинарное дерево Бинарным деревом называется ориентированное дерево с корнем, где каждая вершина имеет локальную степень исхода, равную 2.

Слайд 369


Ветвь дерева Ветвью вершины а в дереве Т с корнем а0 называется подграф, порожденный множеством вершин В(а) состоящим из вершин, связанных с корнем...
Описание слайда:
Ветвь дерева Ветвью вершины а в дереве Т с корнем а0 называется подграф, порожденный множеством вершин В(а) состоящим из вершин, связанных с корнем цепь, проходящей через а.

Слайд 370


Ветвь
Описание слайда:
Ветвь

Слайд 371


Лекция 15 Характеристические числа графа
Описание слайда:
Лекция 15 Характеристические числа графа

Слайд 372


Цикломатическое число Цикломатическим числом графа G называется число ребер, которые надо убрать, что бы граф стал ацикличным.
Описание слайда:
Цикломатическое число Цикломатическим числом графа G называется число ребер, которые надо убрать, что бы граф стал ацикличным.

Слайд 373


Цикломатическое число 1.1 1.2 Рис.1. Цикломатическое число
Описание слайда:
Цикломатическое число 1.1 1.2 Рис.1. Цикломатическое число

Слайд 374


Цикломатическое число Цикломатическое число графа G находится по формуле:
Описание слайда:
Цикломатическое число Цикломатическое число графа G находится по формуле:

Слайд 375


Цикломатическое число Замечание 1: Цикломатическое число дерева равно 0. Замечание 2: Цикломатическое число леса равно 0. Замечание 3: Если...
Описание слайда:
Цикломатическое число Замечание 1: Цикломатическое число дерева равно 0. Замечание 2: Цикломатическое число леса равно 0. Замечание 3: Если цикломатическое число графа равно 1, то в графе ровно 1 цикл.

Слайд 376


Цикломатическое число Пример 1: Рис. 3. Нахождение цикломатического числа
Описание слайда:
Цикломатическое число Пример 1: Рис. 3. Нахождение цикломатического числа

Слайд 377


Цикломатическое число Пример 2: Рис.4. Цикломатическое число несвязного графа
Описание слайда:
Цикломатическое число Пример 2: Рис.4. Цикломатическое число несвязного графа

Слайд 378


Число внутренней устойчивости Внутренне устойчивым множеством графа G называется множество вершин S, все вершины которого попарно несмежны. Число...
Описание слайда:
Число внутренней устойчивости Внутренне устойчивым множеством графа G называется множество вершин S, все вершины которого попарно несмежны. Число внутренней устойчивости:

Слайд 379


Число внутренней устойчивости
Описание слайда:
Число внутренней устойчивости

Слайд 380


Число внешней устойчивости Внешне устойчивым множеством графа G называется множество вершин Q, таких, что из всех вершин множества Q ведут ребра в...
Описание слайда:
Число внешней устойчивости Внешне устойчивым множеством графа G называется множество вершин Q, таких, что из всех вершин множества Q ведут ребра в вершины множества Q. Число внутренней устойчивости:

Слайд 381


Число внешней устойчивости
Описание слайда:
Число внешней устойчивости

Слайд 382


Хроматическое число Граф G называется h- хроматическим, если его вершины можно раскрасить h различными красками так, чтобы никакие две смежные...
Описание слайда:
Хроматическое число Граф G называется h- хроматическим, если его вершины можно раскрасить h различными красками так, чтобы никакие две смежные (различные) вершины не были окрашены в один цвет. Хроматическое число графа – это наименьшее число красок.

Слайд 383


Хроматическое число
Описание слайда:
Хроматическое число

Слайд 384


Хроматическое индекс Граф G называется k-раскрашиваемым, если его ребра можно раскрасить k различными красками так, чтобы никакие два смежные ребра...
Описание слайда:
Хроматическое индекс Граф G называется k-раскрашиваемым, если его ребра можно раскрасить k различными красками так, чтобы никакие два смежные ребра не были окрашены в один цвет. Хроматический индекс графа – это наименьшее число красок.

Слайд 385


Хроматическое индекс Согласно теореме Визинга, если максимальная локальная степень вершины графа равна k, то хроматический индекс подчиняется условию:
Описание слайда:
Хроматическое индекс Согласно теореме Визинга, если максимальная локальная степень вершины графа равна k, то хроматический индекс подчиняется условию:

Слайд 386


Хроматическое число
Описание слайда:
Хроматическое число

Слайд 387


Пример 7: В пунктах Х1, Х2, Х3, Х4, Х5, Х6 могут быть источники излучения. Если источники расположены в пунктах Xi и Xj влияют друг на друга...
Описание слайда:
Пример 7: В пунктах Х1, Х2, Х3, Х4, Х5, Х6 могут быть источники излучения. Если источники расположены в пунктах Xi и Xj влияют друг на друга (поражают друг друга), то на графе они соединены ребром (Xi, Xj). Можно ли расположить в каких-либо из данных пунктов 4 или 3 источника, не поражающих друг друга?

Слайд 388


Рис.9. Нахождение Рис.9. Нахождение максимального внутренне устойчивого множества. S1={X2, X5}, S2={X1, X4}, S3={X3, X6}, S4={X2, X4, X6}.
Описание слайда:
Рис.9. Нахождение Рис.9. Нахождение максимального внутренне устойчивого множества. S1={X2, X5}, S2={X1, X4}, S3={X3, X6}, S4={X2, X4, X6}.

Слайд 389


Пример 8: Объекты Х1, Х2, … , Х9 расположены так, как показано на графе. Объекты, которые просматриваются друг из друга соединены ребрами. Определить...
Описание слайда:
Пример 8: Объекты Х1, Х2, … , Х9 расположены так, как показано на графе. Объекты, которые просматриваются друг из друга соединены ребрами. Определить в каких объектах достаточно поставить камеры наблюдения, чтобы они в совокупности просматривали все объекты.

Слайд 390


Дискретная математика. Множество, слайд №390
Описание слайда:

Слайд 391


Пример 9: Дана политическая карта континента. Найти минимальное число цветов, чтобы раскрасить карту. Пример 9: Дана политическая карта континента....
Описание слайда:
Пример 9: Дана политическая карта континента. Найти минимальное число цветов, чтобы раскрасить карту. Пример 9: Дана политическая карта континента. Найти минимальное число цветов, чтобы раскрасить карту.

Слайд 392


Рис.12. Замена стран на вершины, а границ между ними на ребра. Рис.12. Замена стран на вершины, а границ между ними на ребра. Найдем хроматическое...
Описание слайда:
Рис.12. Замена стран на вершины, а границ между ними на ребра. Рис.12. Замена стран на вершины, а границ между ними на ребра. Найдем хроматическое число графа. χ(G) = 3.

Слайд 393


Рис.13. Раскраска карты в три цвета Рис.13. Раскраска карты в три цвета
Описание слайда:
Рис.13. Раскраска карты в три цвета Рис.13. Раскраска карты в три цвета

Слайд 394


Лекция 16 Сети, потоки в сетях
Описание слайда:
Лекция 16 Сети, потоки в сетях

Слайд 395


Введение Сети – это графы, которые моделируют реальные транспортные и коммуникационные сети.
Описание слайда:
Введение Сети – это графы, которые моделируют реальные транспортные и коммуникационные сети.

Слайд 396


Введение Задача о максимальном потоке в сети заключается в том, чтобы подсчитать максимальное количество некоторых объектов, которые могут двигаться...
Описание слайда:
Введение Задача о максимальном потоке в сети заключается в том, чтобы подсчитать максимальное количество некоторых объектов, которые могут двигаться от одного конца сети к другому. При этом пропускная способность узлов сети ограничена.

Слайд 397


Введение Под объектами могут пониматься - пакеты данных, путешествующих по интернету; - коробки с товарами, которые везут по автомагистрали; и т. д.
Описание слайда:
Введение Под объектами могут пониматься - пакеты данных, путешествующих по интернету; - коробки с товарами, которые везут по автомагистрали; и т. д.

Слайд 398


Введение Эта задача может использоваться при составлении расписания авиарейсов, распределения задач в суперкомпьютерах, обработке цифровых...
Описание слайда:
Введение Эта задача может использоваться при составлении расписания авиарейсов, распределения задач в суперкомпьютерах, обработке цифровых изображений и расположении последовательности ДНК.

Слайд 399


Введение Перемещение объектов могут ограничено пропускной способностью соединений сети или скоростью транспорта на загруженных дорогах.
Описание слайда:
Введение Перемещение объектов могут ограничено пропускной способностью соединений сети или скоростью транспорта на загруженных дорогах.

Слайд 400


Введение В задаче о максимальном потоке одна их вершин графа назначается истоком – точкой, в которой все объекты начинают свой путь, а другая –...
Описание слайда:
Введение В задаче о максимальном потоке одна их вершин графа назначается истоком – точкой, в которой все объекты начинают свой путь, а другая – стоком, точкой, в которую они все направляются. Пропускная способ-ность каждого ребра ограничена. В вершинах вещество не накапливается – сколько пришло, столько и ушло.

Слайд 401


Сети Сетью называется частично ориентированный граф G(V, E) Истоком и стоком (входным и выходным полюсом) называются некоторые отмеченные вершины.
Описание слайда:
Сети Сетью называется частично ориентированный граф G(V, E) Истоком и стоком (входным и выходным полюсом) называются некоторые отмеченные вершины.

Слайд 402


Сети Исток – вершина, локальная степень захода которой равна 0. Сток – вершина, локальная степень исхода которой равна 0.
Описание слайда:
Сети Исток – вершина, локальная степень захода которой равна 0. Сток – вершина, локальная степень исхода которой равна 0.

Слайд 403


Сети Если в сети k истоков и m стоков – сеть называется (k,m)- полюсником. Если в сети 1 исток и 1 сток, сеть называется двухполюсной. Далее будем...
Описание слайда:
Сети Если в сети k истоков и m стоков – сеть называется (k,m)- полюсником. Если в сети 1 исток и 1 сток, сеть называется двухполюсной. Далее будем рассматривать только двухполюсные сети.

Слайд 404


Сети Пусть s – исток, t – сток, так что любая другая вершина лежит на пути из вершины s в t. Вершины, не являющиеся истоком и стоком называются...
Описание слайда:
Сети Пусть s – исток, t – сток, так что любая другая вершина лежит на пути из вершины s в t. Вершины, не являющиеся истоком и стоком называются внутренними вершинами сети.

Слайд 405


Сети Разобьем множество вершин V на два подмножества Х и таких, что Множество ребер, реализующих это разбиение назовем разрезом в сети
Описание слайда:
Сети Разобьем множество вершин V на два подмножества Х и таких, что Множество ребер, реализующих это разбиение назовем разрезом в сети

Слайд 406


Сети Ориентированные ребра с началом в Х и концом в называются прямыми. Множество прямых ребер обозначим
Описание слайда:
Сети Ориентированные ребра с началом в Х и концом в называются прямыми. Множество прямых ребер обозначим

Слайд 407


Сети Ориентированные ребра с началом в и концом в Х называются обратными. Множество обратных ребер обозначим
Описание слайда:
Сети Ориентированные ребра с началом в и концом в Х называются обратными. Множество обратных ребер обозначим

Слайд 408


Сети Все неориентированные ребра являются прямыми. Их ориентация произвольна, и определяется при задании потока в сети.
Описание слайда:
Сети Все неориентированные ребра являются прямыми. Их ориентация произвольна, и определяется при задании потока в сети.

Слайд 409


Сети Замечание 1: Прямым или обратным ребро будет в зависимости от вида разреза в сети.
Описание слайда:
Сети Замечание 1: Прямым или обратным ребро будет в зависимости от вида разреза в сети.

Слайд 410


Пример 1 Дана частично ориентированная двухполюсная сеть.
Описание слайда:
Пример 1 Дана частично ориентированная двухполюсная сеть.

Слайд 411


Дискретная математика. Множество, слайд №411
Описание слайда:

Слайд 412


Дискретная математика. Множество, слайд №412
Описание слайда:

Слайд 413


Дискретная математика. Множество, слайд №413
Описание слайда:

Слайд 414


Дискретная математика. Множество, слайд №414
Описание слайда:

Слайд 415


Поток в сети Пусть S произвольная частично ориентированная сеть. Пусть каждому ребру сети приписано число – пропускная способность ребра е.
Описание слайда:
Поток в сети Пусть S произвольная частично ориентированная сеть. Пусть каждому ребру сети приписано число – пропускная способность ребра е.

Слайд 416


Поток в сети Потоком в сети S называется пара, составленная из числовой и нечисловой функций ( f ,w): w – ориентация всех неориентированных ребер...
Описание слайда:
Поток в сети Потоком в сети S называется пара, составленная из числовой и нечисловой функций ( f ,w): w – ориентация всех неориентированных ребер сети, f =f(e) – функция значений потока на ребрах.

Слайд 417


Поток в сети Функция f удовлетворяет условиям: 1) 2) выполняется закон Киргофа: дивергенция любой внутренней вершины сети равна 0.
Описание слайда:
Поток в сети Функция f удовлетворяет условиям: 1) 2) выполняется закон Киргофа: дивергенция любой внутренней вершины сети равна 0.

Слайд 418


Поток в сети Дивергенция вершины сети – число находимое по формуле:
Описание слайда:
Поток в сети Дивергенция вершины сети – число находимое по формуле:

Слайд 419


Поток в сети Величина потока в сети S – равна дивергенции потока в вершине s (дивергенция истока).
Описание слайда:
Поток в сети Величина потока в сети S – равна дивергенции потока в вершине s (дивергенция истока).

Слайд 420


Поток в сети Замечание 2:
Описание слайда:
Поток в сети Замечание 2:

Слайд 421


Поток в сети Замечание 3: Величина потока в сети есть величина переменная, зависящая от значений функции f(e).
Описание слайда:
Поток в сети Замечание 3: Величина потока в сети есть величина переменная, зависящая от значений функции f(e).

Слайд 422


Пример 2 Дана частично ориентированная двухполюсная сеть. Найти величину потока в сети.
Описание слайда:
Пример 2 Дана частично ориентированная двухполюсная сеть. Найти величину потока в сети.

Слайд 423


с(a)=2; c(b)=3; c(h)=1; c(d)=2; c(q)=1; c(w)=1; c(x)=3; c(y)=2; c(z)=2.
Описание слайда:
с(a)=2; c(b)=3; c(h)=1; c(d)=2; c(q)=1; c(w)=1; c(x)=3; c(y)=2; c(z)=2.

Слайд 424


Дискретная математика. Множество, слайд №424
Описание слайда:

Слайд 425


Дискретная математика. Множество, слайд №425
Описание слайда:

Слайд 426


Поток в сети Каждому ребру разреза R ставится в соответствие пропускная способность разреза с(R), равная сумме пропускных способностей всех прямых...
Описание слайда:
Поток в сети Каждому ребру разреза R ставится в соответствие пропускная способность разреза с(R), равная сумме пропускных способностей всех прямых ребер разреза.

Слайд 427


с(a) = 2; c(b) = 3; c(h) = 1; c(d) = 2; c(q) = 1; c(w) = 1; c(x) = 3; c(y) = 2; c(z) = 2. C = c(w) + c(d) = 3 + 1 = 4.
Описание слайда:
с(a) = 2; c(b) = 3; c(h) = 1; c(d) = 2; c(q) = 1; c(w) = 1; c(x) = 3; c(y) = 2; c(z) = 2. C = c(w) + c(d) = 3 + 1 = 4.

Слайд 428


C = c(b) + c(h) + c(x) + c(y) = = 3 + 1 + 3 + 2 = 9.
Описание слайда:
C = c(b) + c(h) + c(x) + c(y) = = 3 + 1 + 3 + 2 = 9.

Слайд 429


Поток в сети Теорема Форда-Фалкерсона Максимальная величина потока в сети S равна минимальной пропускной способности среди всех ее разрезов.
Описание слайда:
Поток в сети Теорема Форда-Фалкерсона Максимальная величина потока в сети S равна минимальной пропускной способности среди всех ее разрезов.

Слайд 430


Лекция 17 Основы теории кодирования
Описание слайда:
Лекция 17 Основы теории кодирования

Слайд 431


Основы теории кодирования
Описание слайда:
Основы теории кодирования

Слайд 432


Основы теории кодирования Пример 1: Алфавит А={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Слова: натуральные числа, составленные их цифр. n1=23421, n2= 5600976, и...
Описание слайда:
Основы теории кодирования Пример 1: Алфавит А={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Слова: натуральные числа, составленные их цифр. n1=23421, n2= 5600976, и так далее. Двоичный код натуральных: разложение по неотрицательным степеням 2. код числа m1 = 3 – v1 =11; код числа m2 = 4 – v2 =100; код числа m3 = 6 – v3 =110; код числа m4 = 12 – v4 =1100; и так далее.

Слайд 433


Дискретная математика. Множество, слайд №433
Описание слайда:

Слайд 434


Дискретная математика. Множество, слайд №434
Описание слайда:

Слайд 435


Дискретная математика. Множество, слайд №435
Описание слайда:

Слайд 436


Дискретная математика. Множество, слайд №436
Описание слайда:

Слайд 437


Дискретная математика. Множество, слайд №437
Описание слайда:

Слайд 438


Побуквенное кодирование Кодирование является побуквенным, если каждой букве алфавита ставиться в соответствие двоичный код. Код слова получается из...
Описание слайда:
Побуквенное кодирование Кодирование является побуквенным, если каждой букве алфавита ставиться в соответствие двоичный код. Код слова получается из последовательной записи кодов букв.

Слайд 439


Побуквенное кодирование Пример 4: Алфавит А={a, b, c, d} Двоичные код букв: код буквы a – v1 =0; код буквы b – v2 =11; код буквы c – v3 =01; код...
Описание слайда:
Побуквенное кодирование Пример 4: Алфавит А={a, b, c, d} Двоичные код букв: код буквы a – v1 =0; код буквы b – v2 =11; код буквы c – v3 =01; код буквы d – v4 =011. Тогда слово bc имеет код 1101. Его можно однозначно разделит на коды букв. Тогда слово ab имеет код 011. Его можно декодировать как ab или как d.

Слайд 440


Побуквенное кодирование Побуквенный код называется равномерным, если коды букв имеют одинаковую длину. Пример 5: Алфавит А={a, b, c, d} Двоичные код...
Описание слайда:
Побуквенное кодирование Побуквенный код называется равномерным, если коды букв имеют одинаковую длину. Пример 5: Алфавит А={a, b, c, d} Двоичные код букв: код буквы a – v1 =000; код буквы b – v2 =110; код буквы c – v3 =010; код буквы d – v4 =011.

Слайд 441


Побуквенное кодирование Побуквенный код называется префиксным, если ни одно кодовое слово не является началом другого кодового слова. Пример 6:...
Описание слайда:
Побуквенное кодирование Побуквенный код называется префиксным, если ни одно кодовое слово не является началом другого кодового слова. Пример 6: Алфавит А={a, b, c, d} Двоичные код букв: код буквы a – v1 =00; код буквы b – v2 =10; код буквы c – v3 =010; код буквы d – v4 =011.

Слайд 442


Побуквенное кодирование Побуквенный код называется разделимым, если код слова можно однозначно разделить на коды букв.
Описание слайда:
Побуквенное кодирование Побуквенный код называется разделимым, если код слова можно однозначно разделить на коды букв.

Слайд 443


Побуквенное кодирование Утверждение 1: Равномерный код всегда разделим. Утверждение 2: Префиксный код всегда разделим. Утверждение 3: Префиксный код...
Описание слайда:
Побуквенное кодирование Утверждение 1: Равномерный код всегда разделим. Утверждение 2: Префиксный код всегда разделим. Утверждение 3: Префиксный код всегда является разделимым, но разделимый код не обязательно является префиксным, т. е. префиксность является достаточным условием разделимости, но не является необходимым условием.

Слайд 444


Дискретная математика. Множество, слайд №444
Описание слайда:

Слайд 445


Дискретная математика. Множество, слайд №445
Описание слайда:

Слайд 446


Дискретная математика. Множество, слайд №446
Описание слайда:

Слайд 447


Дискретная математика. Множество, слайд №447
Описание слайда:

Слайд 448


Пример 6: Дано распределение частот для букв алфавита. Построить код Фано. Найти стоимость кода.
Описание слайда:
Пример 6: Дано распределение частот для букв алфавита. Построить код Фано. Найти стоимость кода.

Слайд 449


Код Фано 1. Упорядочить буквы по не возрастанию частот.
Описание слайда:
Код Фано 1. Упорядочить буквы по не возрастанию частот.

Слайд 450


Дискретная математика. Множество, слайд №450
Описание слайда:

Слайд 451


Код Фано 1. Упорядочить буквы по не возрастанию частот. 2.Разделить список на две последовательные части так, чтобы разница между суммами частот этих...
Описание слайда:
Код Фано 1. Упорядочить буквы по не возрастанию частот. 2.Разделить список на две последовательные части так, чтобы разница между суммами частот этих частей была минимальна.

Слайд 452


Дискретная математика. Множество, слайд №452
Описание слайда:

Слайд 453


Код Фано 1. Упорядочить буквы по не возрастанию частот. 2.Разделить список на две последовательные части так, чтобы разница между суммами частот этих...
Описание слайда:
Код Фано 1. Упорядочить буквы по не возрастанию частот. 2.Разделить список на две последовательные части так, чтобы разница между суммами частот этих частей была минимальна. 3. Сопоставить частотам первой части символ 0, второй части сопоставить 1.

Слайд 454


Дискретная математика. Множество, слайд №454
Описание слайда:

Слайд 455


Код Фано 1. Упорядочить буквы по не возрастанию частот. 2.Разделить список на две последовательные части так, чтобы разница между суммами частот этих...
Описание слайда:
Код Фано 1. Упорядочить буквы по не возрастанию частот. 2.Разделить список на две последовательные части так, чтобы разница между суммами частот этих частей была минимальна. 3. Сопоставить частотам первой части символ 0, второй части сопоставить 1. 4.С каждой из полученных частей произвести аналогичное деление.

Слайд 456


Дискретная математика. Множество, слайд №456
Описание слайда:

Слайд 457


Дискретная математика. Множество, слайд №457
Описание слайда:

Слайд 458


Дискретная математика. Множество, слайд №458
Описание слайда:

Слайд 459


Дискретная математика. Множество, слайд №459
Описание слайда:

Слайд 460


Дискретная математика. Множество, слайд №460
Описание слайда:

Слайд 461


Стоимость кода Стоимость кода V при распределении Р находится по формуле: Здесь длина кодирующего слова частота появления слова
Описание слайда:
Стоимость кода Стоимость кода V при распределении Р находится по формуле: Здесь длина кодирующего слова частота появления слова

Слайд 462


Дискретная математика. Множество, слайд №462
Описание слайда:

Слайд 463


Дискретная математика. Множество, слайд №463
Описание слайда:

Слайд 464


Дискретная математика. Множество, слайд №464
Описание слайда:

Слайд 465


Дискретная математика. Множество, слайд №465
Описание слайда:

Слайд 466


Стоимость кода
Описание слайда:
Стоимость кода

Слайд 467


Дискретная математика. Множество, слайд №467
Описание слайда:

Слайд 468


Дискретная математика. Множество, слайд №468
Описание слайда:

Слайд 469


Дискретная математика. Множество, слайд №469
Описание слайда:

Слайд 470


Дискретная математика. Множество, слайд №470
Описание слайда:

Слайд 471


Дискретная математика. Множество, слайд №471
Описание слайда:

Слайд 472


Дискретная математика. Множество, слайд №472
Описание слайда:

Слайд 473


Дискретная математика. Множество, слайд №473
Описание слайда:

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию